| AlgoDat Selbsttest (01) (Stefan Bosse) [14.2.2025] |
Dieser Selbsttest dient der Vorbereitung auf die Klausur.
Zusammenfassung der Themen (gemäß Vorlesungsmaterial und Konzepte/Methoden aus den Übungen):
In der Klausur wird nicht programmiert, mit Ausnahme von algorithmischen Beschreibungen in einem wie nachfolgend eingeführten Pseudokode (quasi JavaScript light, Abweichungen sind erlaubt).
Das Semikolon ist nur zur Trennung von Anweisungen in gleicher Zeile notwendig und kann i.A. weggelassen werden.
Variablen und Aggregationen werden ohne Schlüsselwort, Datentypen und Typsignatur eingeführt ("on-the-fly").
// Zuweisung mit Ausdruck ε
x=ε
// ε: Ausdrücke wie in Java!
ε := number | variable | (operand +.*/%<>== operand) | functioncall ...
// Arrays
x=vector(N); x=array(N); x=array(N,init); x=[ε,ε,ε...]
fill(x,0)
// Zugriff auf Element
x[index]
// Structures
x={a:ε,b:ε,...}
// Zugriff auf Attribut/Element
x.attribute
Zeiger auf Elemente werden direkt durch Angabe eines Variablenamens ausgedrückt. Ein Nullzeiger wird mit null belegt.
Beispiel
o1 = { x:0, y:0, child:null }
o2 = { x:1, y:1, child:o1 }
Arrays können hier statisch aber leer mit array(n) und dann durch indizierte Zuweisung erzeugt werden. Die Indizierung beginnt immer mit Null (erstes Element).
Beispiel
table=array(4)
table[0]=...
table[1]=...
imag = { re:1, im:2 }
function Imag(re,im) { return { re:re, im:im }}
image = Imag(1,2)
a + - * / b: Addition, Subtraktion, Multiplikation, Division
a % n : Modulo n
a & | b : Logische (bitstellige) Operationen
a && || b : Boolesche Operationen
-a ~a !a: Numerische Negation, logische Negation, Boolesche Negation
function foo(arg1,arg2,..) {
...
return ε
}
// Aufruf
foo(ε,ε,...)
Es gibt in der Pseudonotation keine Klassen, Objekte und Methoden. Daher werden hier alle Daten prozedural verarbeitet. Datentstrukturen werden mit Funktionen erstellt. Das Schlüsselwort function kann auch weggelassen werden.
Beispiel:
// JAVA
public class Node {
Data data;
int key;
Node more;
...
public Node(Data data,int key) {
this.data=data;
this.key=key;
...
}
public void insert(...) {
}
}
// Pseudo
function Node(data,key) { return {data:data,key:key,more:null} }
node=Node("Hello",12)
function insert(node,...) { ... }
for(index=ε;εCond(index);index=ε(index) {
...
break; continue
}
for(element in object) { ... }
while (εCond) { .. }
do { .. } while (εCond)
if (ε) { } else { }
switch (ε) {
case v: ... break
default: ...
}
Komplexere Operationen als Platzhalter im Algorithmus können textuell beschrieben werden. Besser ist es aber Erkärungen als Kommentare (//) einzufügen.
I.a. nicht notwendig, aber nützlich:
array(n) : Erzeuge statisches Array mit n Elementen (leer)
head(o) : Kopfelement eines Arrays
length(o) : Anzahl der Elemente in einem Array
slice(0,a,b) : Teil eines Arrays [a,b]
tail(o) : Rest eine Arrays ohne Kopfelement
Eine Pseudonotation ist nicht standardisiert sondern dient als (konsequentes) Muster Algorithmen in ihrem wesentlichen Verhalten, Wirkung auf Daten und Aktionen zu beschreiben. Der Pseudocode, häufig mathematische Basisnotation, kann mit textuellen Passagen ergänzt sein um komplexe Berechnungen auf das Wesentliche zu reduzieren. Es ist nicht notwendig sich strikt an eine bestimmte Notation zu halten, nur konsequent sollte man sein, also z.B. statt {x:1} kann man auch {x=1} schreiben. Abweichungen sind immer zulässig!
Aufgabe 1. Welche Vor- und welche Nachteile haben lineare Tabellen als Datenstruktur, auch bezüglich Saklierbarkeit (wachsendes N) und den elementaren Operationen Einfügen, Löschen und Suchen?
Aufgabe 2. Geben Sie für folgende Tabelle eine programmatische Erzeugung in Pseudonotation an (mit Datenstrukturen über Erzeugungsfunktionen, Arrays, und Einfügeoperation)
| a | b | c | y |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 |
dGFibGU9YXJyYXkoNCkKZnVuY3Rpb24gUm93KGEsYixjLHkpIHsgcmV0dXJuIHsgYTphLGI6YixjOmMseTp5IH19CmZ1bmN0aW9uIGluc2VydFJvdyhyb3cpIHsgdGFibGVbbGVuZ3RoW3RhYmxlXV09cm93IH19Cmluc2VydFJvdyhSb3coMCwwLDAsMCkpCmluc2VydFJvdyhSb3coMCwxLDAsMSkpCmluc2VydFJvdyhSb3coMCwwLDEsMSkpCmluc2VydFJvdyhSb3coMSwwLDEsMCkp
Aufgabe 3. (1) Beschreiben Sie die Eigenschaften und das Prinzip von einfach verketteten Listen. (2) Wie sieht ein Element, (3) wie der Zugang zu der Liste aus?
Aufgabe 4. Beschreiben Sie in Pseudonotation die Datenstruktur einer einfach verketteten Liste (Knoten Node und Liste List1 selber). Sowohl Knoten als auch die Liste sollen durch Funktionen erzeugt werden. Überlegen Sie was als administrative Datenstruktur bei einer Liste wirklich nur benötigt wird. Ein Knotenelement enthält neben der Verknüpfungsstruktur noch data und key als Elemente.
ZnVuY3Rpb24gTm9kZShkYXRhLGtleSkgeyByZXR1cm4geyBkYXRhOmRhdGEsa2V5OmtleSxuZXh0Om51bGwgfX0KZnVuY3Rpb24gTGlzdDEoaGVhZCkgeyByZXR1cm4geyBoZWFkOmhlYWQgfQ==
Aufgabe 5. Stellen Sie eine einfach verkettete Liste graphisch dar. Es sollen die Elemente mit ("Hello",10), ("World", 12), ("Joe",5) verkettet werden, dabei hat das Tupel die Inhalte (data,key). Ein Knoten soll dabei alle Elemente der Datenstruktur enthalten.
|
⧉
|
|
Aufgabe 6. Geben Sie die Komplexitätsklasse für die Operationen "Einfügen am Anfang", "Einfügen in der Mitte" und "Suche" an. Es ist immer von dem "worst case" auszugehen.
Aufgabe 7. Implementieren Sie in Pseudonotation die Suchfunktion in einer einfach verketteten Liste. Erstens mit einer Schleife und zweitens mit einer Rekursion. Es soll nach einem numerische Schlüssel key gesucht werden und die Daten des gefundenen Knotens zurück gegeben werden. Der Zugang zur Liste erfolgt über das Kopfelement.
ZnVuY3Rpb24gTm9kZShkYXRhLGtleSkgeyByZXR1cm4geyBkYXRhOmRhdGEsa2V5OmtleSxuZXh0Om51bGwgfX0KZnVuY3Rpb24gTGlzdChoZWFkKSB7IHJldHVybiB7IGhlYWQ6aGVhZCB9CmZ1bmN0aW9uIHNlYXJjaExvb3AoaGVhZCxrZXkpIHsKICBub2RlPWhlYWQKICB3aGlsZSAobm9kZSAmJiBub2RlLmtleSE9a2V5KSBub2RlPW5vZGUubmV4dAogIHJldHVybiBub2RlP25vZGUuZGF0YTtudWxsCn0KZnVuY3Rpb24gc2VhcmNoUmVjdShub2RlLGtleSkgewogIGlmIChub2RlICYmIG5vZGUua2V5IT1rZXkpIHNlYXJjaFJlY3Uobm9kZS5uZXh0LGtleSkKICByZXR1cm4gbm9kZT9ub2RlLmRhdGE7bnVsbCAKfQ==
Aufgabe 8. (1) Durch welche Eigenschaften ist ein Binärbaum definiert, auch im Unterschied zu einer Liste? (2) Welchen Vorteil bietet die Verwendung eines Binärbaums gegenüber eine einfach verketteten Liste?
Kreuze richtige Feststellungen an
Aufgabe 9. Zeichnen Sie einen ungerichteten Syntaxgraphen (zweistellige binäre Knoten) für folgden Ausdruck. Ein Knoten ist dabei entweder eine Operation, eine Variable, oder eine Konstante. Die Kanten bestimmen die Bindung von Werten oder Teilausdrücken mit Operationen (also z.B. +). Jede Operation ist binär, d.h. hat maximal zwei Operanden. Komplexere Ausrücke müssen zerlegt werden.
(x+y)*(x-y)+2
|
⧉
|
|
Aufgabe 10. Implementieren Sie nachfolgende Berechnung der Differenzierung mit einem einfachen numerischen festen Delta Algorithmus und zwei Stützstellen.
ZnVuY3Rpb24gZGVyaXYoZix4LGRlbHRhKSB7CiAgcmV0dXJuIChmKHgrZGVsdGEpLWYoeCkpL2RlbHRhCn0=
Reguläre Ausdrücke. Allgemeine Form:
/.../, Konstante und zusammenhängende Textmuster:abcd, Alternative:x|y(entweder x oder y), Sequenz:x*(kein mal, einmal, oder mehrmals x),x+(einmal oder mehrmals x). Probieren Sie es aus: https://regex101.com
Aufgabe 11. Es gibt eine Sprache mit dem Alphabet {0,1}. Es sollen in einer Folge von Zeichen mit diesem Alphabet zusammenhängende Folgen 000, 111, und 101 gefunden werden. (1) Gebe einen regulären Ausdruck an der alle Vorkommen dieser drei Sequenzen findet. (2) Aber wo könnten Folgen "übersehen" werden bzw. könntes es Mehrdeutigkeiten geben? (3) In einer zweiten Suchen sollen alle zusammenhängenden Folgen mit mindestens zwei Ziffern, die entweder ausschließlich aus der Ziffer 0 oder ausschliesschlich aus der Ziffer 1 bestehen, gefunden werden.
cmVnZXgxPS8wMDB8MTAxfDExMS9nCnJlZ2V4Mj0vMFswXSt8MVsxXSsvZw==
Aufgabe 12. Zeichnen Sie für den regulären Ausdruck /00|11/ ein Zustandsübergangsdiagramm für einen endlichen Zustandsautomaten (EZA). Die Knoten des EZA beinhalten einen unterscheidbaren Zustand (numeriert, 1,2,3...) und die Kanten werden mit der nächsten Eingabe aus einem Eingabestrom von Textzeichen annotiert. Beachten Sie das fehlende "g" am Ende des RA. Zwischenzustände werden mit einem Kreis, Endzustände (Muster gefunden) mit einem Quadrat symbolisch dargestellt. Der Startzustand ist Nummer 1.
Beispiel für /abcd/:
|
⧉
|
|
Aufgabe 13. Sortieren Sie schrittweise das nachfolgende Array aufsteigend nach dem Bubblesort Verfahren (links kleinstes, rechts größtes Element). Sortieren Sie bis die Folge sortiert ist. Geben Sie jeden Durchlauf an, auch wenn sich nichts ändert. In jeder Zeile steht das Ergebnis eines Einzelschrittes. Markiere das Ende eines Durchlaufs mit einer Leerzeile. Die erste Zeile ist schon Bestandteil der Sortierung. Tipp: Nach der Eingabe in einem Feld der Tabelle (auf das Feld doppelt klicken) kann einfach mit der Tabulatortaste in das nächste Feld gewechselt werden.
[ 2 , 7 , 1 , 9 , 5 , 3 , 5 , 4 ] WyAyLCA3LCAxLCA5LCA1LCAzLCA1LCA0IF0KWyAyLCAxLCA3LCA5LCA1LCAzLCA1LCA0IF0KWyAyLCAxLCA3LCA5LCA1LCAzLCA1LCA0IF0KWyAyLCAxLCA3LCA1LCA5LCAzLCA1LCA0IF0KWyAyLCAxLCA3LCA1LCAzLCA5LCA1LCA0IF0KWyAyLCAxLCA3LCA1LCAzLCA1LCA5LCA0IF0KWyAyLCAxLCA3LCA1LCAzLCA1LCA0LCA5IF0KLS0tLQpbIDEsIDIsIDcsIDUsIDMsIDUsIDQsIDkgXQpbIDEsIDIsIDcsIDUsIDMsIDUsIDQsIDkgXQpbIDEsIDIsIDUsIDcsIDMsIDUsIDQsIDkgXQpbIDEsIDIsIDUsIDMsIDcsIDUsIDQsIDkgXQpbIDEsIDIsIDUsIDMsIDUsIDcsIDQsIDkgXQpbIDEsIDIsIDUsIDMsIDUsIDQsIDcsIDkgXQpbIDEsIDIsIDUsIDMsIDUsIDQsIDcsIDkgXQotLS0tClsgMSwgMiwgNSwgMywgNSwgNCwgNywgOSBdClsgMSwgMiwgNSwgMywgNSwgNCwgNywgOSBdClsgMSwgMiwgMywgNSwgNSwgNCwgNywgOSBdClsgMSwgMiwgMywgNSwgNSwgNCwgNywgOSBdClsgMSwgMiwgMywgNSwgNCwgNSwgNywgOSBdClsgMSwgMiwgMywgNSwgNCwgNSwgNywgOSBdClsgMSwgMiwgMywgNSwgNCwgNSwgNywgOSBd