Datenstrukturen Daten: (lesbar / bearbeitbar) + Bedeutungskontext

Datenstrukturen
Daten:
(lesbar / bearbeitbar) + Bedeutungskontext / Kodierung in Zeichenketten gemäß Syntax / Attribute Beziehung /
Wertebereich / Speicherplatz.
Datentyp:
endliche Menge (Wertebereich des Types/Konstanten) + gewisse Anzahl Operationen
Untypisierte Sprachen: Variable kann beliebigen Typ annehmen (LISP, Smalltalk, Scriptsprachen) -> Laufzeitfehler
Typisierte Sprachen:
Variablen müssen definiert werden mit Hilfe eines Datentyps (C,C++,Java) der Compiler kann Integrität prüfen
weniger Laufzeitfehler / ADA gar keine LZF
Atomare Typen:
Vordefinierte Typen einer Sprache, Grundlage für Ableitung von weiteren Typen (Java int, float, boolen, char)
Strukturierte Datentypen (Klassen) Zusammenfassung beliebiger Datentypen + Spezifikation von Methoden & Operationen
kartesisches Produkt: DT = DT1 x DT2 x DT3. (DTx atomare oder strukturierte Datentypen)
Abstrakter Datentyp: Definition von Datentyp ohne Implementation! + Operationspezifikation. Verwendung Geheimnisprinzip +
Wiederverwendbarkeit. Definiert einen Datentyp nur mit Hilfe des Wertebereichs und der Menge der Operationen
auf diesen Bereich. Jeder Operation ist definiert durch ihre Spezifikation, Input und Outputparameter und Vor und
Nachbedingung.Spezifiziert eine Liste von Dienstleistungen (Operationen, Methoden, Funktionen), die der
Datentyp dem Anwender zur Verfügung stellt. Die Spezifikation eines DT muss vollständig, präzise und eindeutig
sein Achtung vor einer Überspezifikation mittels der Implementationsvorgaben.
Geheimnisprinzip:
Spezifikation sichtbar / Implementation verborgen Vorteile: Anwender kann verwenden ohne die Komplexität der
Impl. Zu kennen / Implementator kann die Implementation verändert, solange er den Spez-Vertrag erfüllt. / Klare
Verantwortlungsregelung zwischen den Aktoren – hilft bei Debugging.
Wiederverwendbarkeit: Modul soll in verschiedenen Apps wieder verwendtbar sein, um ähnliche Probleme zu lösen. Reduktion der
Entwicklungszeit / Kosten
Datenstruktur:
ist eine Instanz eines (abstrakten) Datentyps Beinhaltet die Repräsentation der Daten und die Implementation von
Prozeduren für die Operationen.
Logische / physikalische Form von Datenelement: Abstrakter Datentyp ist logische Form / Implementation ist die physikalische Form
Algorihmus:
beschreibt das Vorgehen oder Methode für lösen einer Aufgabe/Problems. Besteht aus einer Folge von einfachen
Rechenschritten/Anweisungen welche zur Lösung der Aufgabenstellung führen. Die 7 Muss-Kriterien: 1) Reihe
konkret ausführbarer Schritte bestehen 2) er muss in einem endlichen Text beschreibbar sein 3) nur endliche
viele Schritt benötigen (Termination) 4) zur jeder Zeit nur endlich viel Speicherplatz benötigen 5) muss mit gleicher
Eingabe das selbe Ergebnis liefern 6) die nach Ausführung eines Schrittes ist eindeutig definiert welcher der
nächste Schritt ist /) der ausgabewert des Algorithmus muss richtig sein.
Ausnahme: z.B. Lottozahlenalgorithmus…
Algorithmen-Schema
Iteration:
Greedy:
Rekursion:
Divide and Conquer:
verstehen wir ein Verfahrens-Muster oder allgemeine Methode um ein Problem lösen zu können. Ein Problem wird
gelöst mittels …
gelöst, falls der zugehörige Algorithmus eine Loop (while oder for Schleife) benutzt. Hilfreich bei Arrays
(gierige Methode) für Optimierungsprobleme / Bewertunsgsfunktion bei mehreren Lösungen (Spiele Strategien)
z.B. Suche nach em besten Weg)
direkt oder indirekt selber aufruft. 1) Darf nicht unendlich sein, es müssen Abbruchkriterien existieren. Ein
instruktionszweig muss existieren der keinen Aufruf der Prozedur beinhaltet. 2) muss sichergestellt werden, dass
die Anzahl rekursiver Aufrufe vernünftig bleibt und kein Speicher-Notstand dadurch entsteht. Achtung auf
Asymptotische Komplexität. 3) die Lösung sollte durch die Verwendung der Rekrusion klarer und kürzer werden!
DAC zerlegt das Problem in kleiner Teilprobleme bis die
Lösung der Teilprobleme einfach ist. Anschliessend werden
die Teillösungen wieder zur Gesamtlösung vereint (Merge)
1) Hard Split Easy Join: Quicksort Dabei wird die gesamte
Arbeit beim Teilen des Problems verrichtet und die
Kombination ist trivial, das heisst, F wird so in Teilfolgen F1
und F2 partitioniert, dass zum Schluss die sortierten
Teilfolgen einfach aneinandergereiht werden konnen: S =
S1S2.
2) Easy Split Hard Join: Mergesort Dabei ist die Aufteilung in Teilfolgen F = F1F2 trivial und die Hauptarbeit liegt
beim Zusammensetzen der sortierten Teilfolgen S1 und S2 zu S. Dieses Prinzip führt zum Mergesort-Algorithmus
Rekursionselimination: Vermeidung der Rekursion durch Umstellung des Algorithmus. Einfach wenn die letzte Instruktion (Rekursiv
aufgerufen wird. 1) Umdrehung der Berechnung 2) Zwischenspeicherung von Ergebnissen
public long procRek(int n) {
if(n<=3)
return 2;
else
return 2*procRek(n-1) + procRek(n-2)/2 - procRek(n-3);
}
public long procRek( int n ) {
long tmp[] = new long[n+1];
tmp[0] = tmp[1] = tmp[2] = tmp[3] = 2;
for (int i=4; i<=n; i++) {
tmp[i] = 2*tmp[i-1] + tmp[i-2]/2 - tmp[i-3];
}
return tmp[n];
}
Komplexitätsanalyse
3 Gruppen: Alle Funktionen -> Berechenbare Funktionen -> Durchführbare Algorithmen
Ermittlung der erforderlichen Betriebsmittel (Zeit & Speicherbedarf) / Gibt Hinweis zur
Einsatzfähigkeit eines Algorithmus / Wichtig für die Programmoptimierung (ein Problem ->
mehrere Lösungswege -> bester Lösungsweg) Ermittlung der Effizenz der Algor. Komplexität in der
Regel abhängig von der Grösse der Eingabedaten (Für Grössenordnung der Komplex. des Algor.->
zählen der relevanten Operationen (Anzahl Rechenschritte; Vergleiche Vertauschungen).
Best-Case(1), Average-Case(2), Worst-Case Analyse(3) :
1) gibt an, wie lange der Algorithmus mindestens braucht( idealen Eingabe), trifft nur für wenige
Fälle zu und wird selten angegeben / die best-case-Laufzeit in der für die schlechteren Fälle
enthalten ist
2) gibt die erwartete Laufzeit bei einer gegebenen Verteilung der Eingaben an. Da allerdings die Verteilung der Eingaben bei Programmen
nicht immer bekannt ist, ist die Berechnung nur unter einschränkenden Annahmen möglich.
3) gibt an, wie lange der Algorithmus maximal braucht. Speziell wichtig für Echtzeitsystemen / sonst nicht zwingend
Asymptotische Komplexität:
z.B. eines Polynoms entspricht dessem größten Term (Konstanten ignorieren). 1.) Log(n) kleinere Ordnung als O(n) 2) Ordnung eines
Polynoms -> O(n^k) (nur höchste Potenz) 3) zwei Funktionen O(f + g) = max{O(f), O(f)} 4) O(f*g) = O(f)*(O(g)
int proc4( int n )
{
int res = 0, m = n*n;
for( i = m; i > 1; i=i/2 )
res = do_something(res,
i);
return res;
}
m+m/2+m/4+···+ 4+2 =
2m−2 = O(n^2)
int procRec( int n )
{
int res = 0;
if(n <= 1)
return res;
for( int i = 0; i < n; i++ )
res = do_something(res, i);
return procRec(n/2);
}
n = 1: 0
n = 2: 2 + 0
n = 4: 4 + 2 + 0
n = 2^k: 2^k+2^(k−1)+···+4+2+0 =
n = 2^(k+1)−2 = 2n−2
void procedure2( int n )
{
for(int i=0; i<n; i++)
for(int j=0; j<2*i; j++)
do something(i,j,n);
}
void procedure4( int n )
{
int j=n;
while( j > 0 )
{
j = j/2;
do something(i,j,n);
}
}
JAVA Syntax Helper
long tmp[][] = new long[x+1][y+1];
for( int i=0; i<=x; i++ )
tmp[i][0] = 1;
for( int j=1; j <= y; j++ )
for( int i=1; i<=x; i++ )
tmp[i][j] = tmp[i-1][j] + tmp[i][j-1];
if (initialCapacity < 0)
throw new IllegalArgumentException( ... );
this.elementData = (E[]) new Object[initialCapacity];
if (index > size || index < 0)
throw new IndexOutOfBoundsException( ... );
System.arraycopy(elementData, index,
elementData, index + 1, size - index );
elementData[index] = element;
Object[] myList = new Object[] {new Integer(1), new Integer(2), …}
ObjectIterator iterator = new ObjectIterator(myList);
while(iterator.hasNext()) {
System.out.println(iterator.next());
}
Datentypen: Listen, Stacks und Queues (arraybasiert oder zeigerbasierend implementiert)
Array Listen (Java: ArrayList,Vector (sync))
In einer Array Liste werden die einzelnen Elemente (bzw. die Referenzen auf die
Elemente) in einen Array (vom generischen Typ E) abgelegt
 Es entspricht direkt dem
Speicherabbild
 Ein Element somit extrem
schnell adressiert werden
 Array sind werden immer auf eine statische Grösse erstellt. Ein nachträgliches Vergrössern
ist nicht möglich.
 Zufüge bzw. Lösch-Aktionen: In diesem Falle muss ein neuer Array erstellt werden und die
bestehenden Werte kopiert/teilweise kopiert werden.
 Vergrösserung benötigt erheblich Systemressourcen (Kopieren)
Doppelt verkettete Listen (Java: LinkedList,
Jedes Listenelement referenziert einem Datenelement (Entry ) und zwei Zeigern (next und previous ). Liste
entsteht durch Zusammenfugen der Entry Elemente. Listenanfang = Header
Element. Die Elemente werden nur am Kopf der Liste zugefügt.




Die Elemente in der zweiten Hälfte einer sortierten Liste sind schneller aufzufinden.
Schnelles Löschen und Einfügen von Elementen.
Das macht zum Beispiel das effiziente Sortieren der Liste möglich.
Über die Liste kann von hinten nach vorne iteriert werden.
 Höherer Speicherbedarf für die
zusätzlichen Zeiger.
Stack-Stapelspeicher (Last-In-First-Out-Prinzip (LIFO)) (Java: Stack,
Elemente können nur oben auf den Stapel gelegt bzw. von dort wieder gelesen werden. Push:
legt das Objekt oben auf den Stapel. Pop: liefert das oberste Objekt und entfernt es vom Stapel.
Peek: liefert das oberste Objekt, ohne es zu entfernen. Empty: wenn Liste leer ist
Anwendung: Sehr häufig eingesetzte Datenstruktur / meisten von Mikroprozessoren in der Hardware direkt unterstützt.
Queue /Warteschlange (First In First Out Prinzip) (Java: PriorityQueue,
Eine Queue kann eine beliebige Menge von Objekten aufnehmen und gibt diese in der
Reihenfolge ihres Einfügens wieder zurück. Die neuen Elemente immer am Ende angehängt.
Anwendung: zur Interprozesskommunikation(Pipe) / Programmabarbeitung entkoppelt
(langsame Drucker) / Datenübergabe zwischen asynchronen Prozessen / Message Queue
Oft auch als Ringpuffer mit je einem Zeiger auf Anfang (In-Pointer) und Ende (Out-Pointer) implementier z.B. Flugschreiber.
Iterator
Ein Pattern als Hilfsmittel zum Durchlaufen von Listen. Enormer Performance Gewinn bei verketteten Listen O(n) vs. O(n^2)
hasNext: prüft ob das Ende der Liste erreicht ist next: verschiebt den Iterator auf das nächste Element und gibt ihn zurück
 Die Implementierung der zu Grunde
 Je nach Variante der Implementierung können sich Nachteile durch erhöhte
liegenden Datenstruktur bleibt verborgen
Laufzeit- und Speicherkosten ergeben. z.B. Java: Iterator sein Aggregat kennt
und/oder das Aggregat über seine Iteratoren Buch führt
Weitere Listen: HashSet, LinkedHashSet, TreeSet,-> Mengenlehre Element sind immer einmalig keine Dupletten
public class LinkedList<E> {…}
LinkedList(){ ... };
boolean isEmpty(){ ... };
E get(int index){ ... };
void add(int index, E element){ ... };
E remove(int index){ ... };
int indexOf(Object o){ ... };
}
public void add(int index, E element) {
addBefore(element, (index == size ? header :
entry(index)));
}
private Entry<E> addBefore(E o, Entry<E> e) {
Entry<E> newEntry = new Entry<E>(o, e,
e.previous);
newEntry.previous.next = newEntry;
newEntry.next.previous = newEntry;
size++;
return newEntry;
}
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsExce..(...);
Entry<E> e = header;
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++) e = e.next;
} else {
for (int i = size; i > index; i--) e = e.previous;
}
return e;
}
private Entry<E> header; STACK
private int size = 0;
public E push(E item) {
header = new Entry<E>(item, header);
size++;
return item;
}
public E pop() {
if (size==0) throw new EmptyStackException();
Entry<E> e = header;
E result = e.element;
header = e.next;
e.element = null;
e.next = null;
size--;
return result; }
E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementExce…();
E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
size--;
return result;
}
public E peek() {
if (size==0) throw new EmptyStackException();
return header.element;
}
public boolean empty() {
return size == 0;
}
private static class Entry<E> {
E element;
Entry<E> next;
Entry(E element, Entry<E> next) {
this.element = element;
this.next = next;
}
}
Datenbäume
Graph:
definiert als ein Paar B = (E,K) bestehend aus je einer endlichen Menge E von Ecken (Knoten, Punkten) und einer Menge von
Kanten. Eine Kante wird dargestellt als Zweiermenge von Ecken {x,y}, den Endpunkten der Kante.
Baum:
ist ein Graph mit der zusätzliche Einschränkung, dass es zwischen zwei Ecken nur eine (direkte oder indirekte) Verbindung gibt.
Ein Baum ist ein zusammenhängender Graph ohne Zyklen.
Binärer Baum
besteht aus einer Wurzel (Root) und endlich vielen Knoten und verbindenden Kanten dazwischen. Jeder Knoten hat entweder 0, 1 oder 2
Nachfolgerknoten. Weg: in einem Baum ist eine Liste von disjunkten, direkt verbunden Kanten. Vollständiger binärer Baum (von der Höhe
n) falls alle inneren Knoten zwei Nachfolger haben und die Blätter maximal Weglänge n bis zur Wurzel haben.
Maximale Nodes in einem Baum = 2^(Höhe+1)-1 K Ecken (optimal plaziert): log2(n)
Präorder
Baumdurchlaufe
Praorder: 1) Betrachte zuerst den Knoten 2 ) durchsuche L-Teilbaum 3) durchsuche R-Teilbaum
Inorder:
1 ) durchsuche L-Teilbaum 2) Betrachte zuerst den Knoten 3) durchsuche R-Teilbaum
Postorder: 1 ) durchsuche L-Teilbaum 2) durchsuche R-Teilbaum 3) Betrachte zuerst den Knoten
Anmerkung: Inorder perfekt für für mathematische Ausdrucke Klammern wären überflüssig
Inorder
Tiefensuche mit Hilfe eines Stacks zur Vermeidung rekursiven Aufrufe. Inorder und Postorder können so nicht
erfolgen, das Prinzip funktioniert nur für Präorder!
Breitensuche mit Hilfe einer Queue Starte bei der Wurzel. Bis die Höhe des Baumes erreicht ist, setze den Level
um eines höher und gehe von links nach rechts durch alle Knoten dieser Ebene. Um mittels Breitensuche durch
Postorder
einen Baum zu wandern, werden alle Baumknoten einer Ebene in einer Queue vermerken für den späteren Zugriff
Binäre Suchbäume
Alle Werte des linken Nachfolger-Baumes eines Knotens K sind kleiner, alle Werte des rechten Nachfolger-Baumes von K sind grösser als der
Wert von K selber. Vorteil (Einfügen/Suchen) es muss immer nur ein Nachfolger untersucht werden. Kleiner dann links sonst rechts
B-Bäume
Ein B-Baum ist ein stets vollständig balancierter und sortierter Baum. In einem B-Baum darf die Anzahl Kindknoten
variieren. Durch die flexiblere Anzahl Kindknoten ist das Rebalancing weniger häufig nötig. 2-3-4 B-Baum: jeder
innere Knoten minimal 2 und maximal 4 Nachfolger haben darf (der Wurzelknoten hat 0-4 Nachfolger, Blätter haben keine Nachfolger).
Knoten im Baum speichert: 1) eine variable Anzahl s von aufsteigend sortierten Daten-Elementen k1;:::;ks 2) isLeaf gibt an ob es ein Blatt
ist. 3) s+1 Referenzen auf Kindknoten, falls der Knoten kein Blatt ist. Schranke m, so dass m <= s <= 2m gilt (Kindknoten hat mindestens m,
aber höchstens 2m Daten-Elemente).
Elementsuche: 1) Wurzel ->Suchknoten k 2) Suche in k von links her die Position p des ersten Daten-Elementes x, welches grösser oder
gleich e ist. 3) Falls alle Daten-Elemente von k kleiner sind als e, führe die Suche im Kindknoten ganz rechts weiter. 4) Falls
x gleich e ist, ist die Suche zu Ende. 5) Anderfalls wird die Suche beim p-ten Kindelement von k weitergeführt. 6) Falls k ein
Blatt ist, kann die Suche abgebrochen werden (fail).
Einfügen:
(Achtung: nicht mehr als 2m Daten-Elemente in einem Knoten) 1) Blatt sucht (siehe Elementsuche), wo neues Element
eingefügt werden muss. Bis zur Blatt-Tiefe weitersuchen (sogar, wenn wir den Wert unterwegs gefunden haben)! Falls
Platz vorhanden wird der Wert dort eingefügt. Anderenfalls Knoten aufteilen und nach Mitte nach oben verschieben.
Verbleibende Elemente in zwei Gruppen zerlegen.
Löschen:
(Achtung: jeder Knoten muss mindestens m Datenelemente enthalten) Falls Element in Blatt liegt mit mehr als m
Elementen einfach löschen anderenfalls Elemente verschieben oder Blätter verschmelzen.
Verschieben:
wird aus dem rechten Nachbarn das kleinste Element nach oben, und das Splitter-Element des Vorgängers in das linke
Blatt verschoben oder konnte (falls vorhanden) aus einem linken Nachbarn das grösste Element verschoben werden.
Verschmelzen: (Achtung: links und rechts haben nur noch m Elemente im Knoten) Das linke Blatt erhält vom mittleren Blatt das Element,
sowie von der Wurzel das Element drüber.
Priority Queues
Ziel: Elemente in einer bestimmten Reihenfolge (Priorität) abarbeiten. Elemente werden gemäss ihrer Priorität in einer Priority Queue
gesammelt, so dass immer das Element mit höchster Priorität direkt verfügbar ist. Einsatzgebiet: Filekomprimierungs- oder bei Graph
Algorithmen.
Heap: ist ein (fast) vollständiger Baum, in welchem nur in der untersten Ebene ganz rechts Blätter fehlen dürfen. Jeder Knoten im Baum
besitzt eine Priorität und eventuell noch weitere Daten. Heapbedingung: Die
Knoten-priorität ist immer grösser als (oder gleich wie) die Priorität der
Nachkommen. Falls als Array abgelegt siehe Bild (Vorbedingung festzulegen
falls Element fehlt! (z.B. Ferner gilt: heap[i] ≥ heap[ 2*i+1]).
parent(i)=[(i-1)/2]; left(i) = 2i+1; right(i) = 2i+2
Insert:
RemoveMax:
Array um 1 verländern, Element am Ende zufügen. Kontrolle der Heapbeding. Loop(Element nach oben vertauschen wenn
grösser als Vorgänger) Max Vertauschungen log2(n)
Wurzel-Element wird gelöscht und an deren Stelle das Element von unten rechts kopiert. Kontrolle Heapbeding
Loop(Element wird mit dem grösseren seiner beiden Nachfolger vertauscht bis Bedingung erfüllt ist). Max
Vertauschungen log2(n)+1
Suche:
Einflussfaktoren auf Effizienz der Suche: Grösse der Datenmenge; benutze Datenstruktur direkt Zugriff auf das Element (Array) notfalls
Pointer-Arrays bei Datenobjekten.
Lineare Suche
Vorne beginnen und jedes Element der Liste nacheinander vergleichen bis Element gefunden oder Ende
der Liste erreicht. Komplexität (1 |n/2 | n) Asymptotische Komplextität O(n)
Binäre Suche
Vorbedingung: Sortierte Liste in dem man das Element an der richtigen Stelle direkt einfügt. JAVA:
Sortierung erfordert das interface Comparable Methode compareTo().
Vorgehensweise: 1)Folge teilen in 2 Hälften. 2) Wert gefunden? 3)Falls der gesuchte Wert kleiner ist als
die Hälfte dann Suche in der linken Teilliste wiederholen anderenfalls rechte verwenden. Wiederholen
bis gefunden oder Teilliste leer ist. Asymp Komplex.: Tbest(n) in O(1) bis Tworst(n) in O(log2(n))
Hashing (.B. ELFHash mit guter Streuung)
Anforderung an Hashfunktion: 1) Hashwert eines Objekts muss während der Applikation-Session zwingend gleich bleiben 2) bei Objekten
die gemäss der equals() Methode gleich sind, muss der Hashwert auch gleich sein 3)verschiedene Objekte dürfen gleichen Hashwert haben.
Double Hashing
Lösungsansätze für Kriterium 3 Problem
Verwendet zwei verschiedene Hashfunktionen Hash1 und Hash2. Hash1 dient dazu, die Hashadresse eines
Schlüssels in der Tabelle zu suchen. Hash2 dient dazu, bei einer Kollision in der Tabelle den nächsten freien
Platz zu suchen. Als zweite Hashfunktion kann z.B. Hash2(k) = k mod 8 + 1. Achtung Sicherstellung dass diese
Funktionswerte teilerfremd zur Lange der Hashtabelle ist, Als Länge der Tabelle eine Primzahl wählen
Einfügen: 1) Hashadresse Hash1(k) mod N berechnen. 2) Falls Platz bereits verwendet so wird nacheinander
bei den Adressen Hash1(k) + Hash2(k)) mod N bzw, Hash1(k) + 2* Hash2(k)) mod N usw. gesucht
bis ein Platz frei ist. Übersteigt der Füllstand die 60% muss die Hashtabelle vergrössert und ein
Rehashing vorgenommen werden (alle Elemente neu zuteilen).
Suche:
Hashadresse 'Hash1(k) mod N' wird berechnet. Falls das gesuchte Element mit Schlüssel k nicht
dort ist, wird der Wert Hash2(k) berechnet und das Element gemäss der Einfüge Regel gesucht.
Abbruchkriterium:1) Element gefunden 2) Leeren Tabellenplatz gefunden 3) Erkennen eines Suche
in einen Zyklus
Löschen: Elemente werden nur gelöscht markiert! können aber wiederverwendet werden!
Sortierung
Suchalgorithmen
Einfach:
zu implementierender, langsamer Suchalgorithmus / Algorithmen mit einer Komplexitat von O(n2) ausreichend / Bubble Sort
/ Bei kleinen Datenmengen (weniger als 500 Elemente)
Komplexere: aber schnellere Suchalgorithmus / Bei grossen Datenmengen / Algorithmen mit einer Komplexität von O(nlog2(n))
Datenstrukturen (wichtiger als der Algorithmus)
Array-Strukt: ein BasisTyp-Array wie float[n] oder eine ArrayList / Vorteil: direkter Zugriff auf eine konkretes Element / Nachteil:
Aufwändiges Verschieben und Löschen von Elementen
Listenstruktur: z.B. LinkedList / Vorteil: Schnelles Umketten von Elementen (Einfügen und Löschen von Elementen) / Nachteil: Langsamer
Zugriff auf ein konkretes Element
Stablität von Sortier-Algorithmen
Stabil heist, falls Elemente, welche gemäss der Vergleichsfunktion gleich sind, ihre Originalreihenfolge bei erneuten
Sortieren behalten. Viele Sortier-Algorithmen auf Array-Strukturen zwar sehr schnell aber nicht stabil sind.
Selection Sort
Algorithmus: Nicht Stabil Komplexität: O(n^2) Einsatzgebiet: Für Arrays geeignet.
Ablauf:
Teilung der Menge in sortiert Menge S und nichtsortiert Menge U. Aus U wird das kleinste Element
gesucht und mit dem letzten Element von S vertauscht. Swap gut für Array-Strukturen, deshalb aber
auch nicht stabil.
Insertion Sort
Algorithmus: Stabil Komplexität: O(n^2) Einsatzgebiet: Für Listen geeignet.
Ablauf:
Teilung der Menge in sortiert Menge S und nichtsortiert Menge U Das jeweils erste Element aus der
unsortierten Folge U wird an der richtigen Stelle in die sortierte Folge S eingefügt. Wegen dem Einfügen
an einer Position nicht für Array-Strukturen geeignet, Falls das Element beim Ein-Sortieren jeweils am
Ende aller (gemäß der Ordnung) gleichen Elemente eingefügt wird, ist dieser Algorithmus stabil.
Quicksort
Algorithmus: Hard split / Easy join - nicht stabil Komplexität: minimum: O(nlog2(n)) max: O(n^2)
Einsatzgebiet: Nur für Arrays geeignet!
Schwierigkeit: Das Pivot Element zu bestimmen ist die eigentliche Schwierigkeit. z.B. links Element
oder mittleres Element
Ablauf:
Loop(1) Pivot Element q auswählen 2) der zu sortierende Bereich F so in zwei
Teilbereiche Fklein und Fgross partitioniert, dass alle Element kleine als q in der
Partition klein liegen der Rest in der Partition gross. ) Am Ende sortierten Folgen
zusammenhängen. Ab eine Mengengrösse mit 4 oder 8 Elementen wird Selection
Sort angewandt
Merge Sort
Algorithmus: Easy split / Hard join- stabil Komplexität: minimum: O(nlog2(n)) max:
O(nlog2(n)Einsatzgebiet: Nur für Listen geeignet!
Vorteil:
Kein Zusätzlicher Speicher wird benötigt Schwierigkeit: Das Pivot
Element zu bestimmen ist die eigentliche Schwierigkeit.
Ablauf:
die Folge F mit Hilfe einer Methode divideList() in zwei (möglichst) gleich
grosse Hälften geteilt. Die (im rekursiven Aufruf) sortierten Folgen
werden in einem linearen Durchgang zur sortierten Endfolge zusammen
gefügt (gemischt). Das Mischen geschieht dadurch, dass jeweils das
kleinere Kopfelement der beiden Listen ausgewählt, herausgelöst und als nächstes Element an die neue Liste angefügt wird.
Bucket Sort
Einsatz nur sinnvoll, wenn der Wertebereich der zu sortierenden Zahlen eng
begrenzt ist. Jede der n Karteikarten wird genau einmal in einen Eimer geworfen
und genau einmal wieder entnommen. Die Komplexität von Bucket Sort liegt also
in O(n), benützt aber O(n) zusätzlichen Speicher. Implementation: Die Eimer
werden als Array list von verketteten Listen dargestellt. Das Legen einer Karteikarte
in den Eimer k wird implementiert, indem eine Referenz auf die Karteikarte in die
Liste list[k] eingefügt wird.
42
3
24
33
13
5
7
25
28
14
46
16
49
15
3
24
33
13
5
7
25
28
14
15
16
49
46
42
16
46
42
16
46
49
46
49
42
16
3
15
14
13
5
7
3
Bucket Hashing (Eimer Hashing) / Kollisionsvermeidung
Aufteilen des Hash-Arrays in verschiedene Buckets. Eine Hashtabelle der Länge H wird dabei aufgeteilt in
H/B Teile (buckets), von der Grosse B. Nur 1 Hashfunktion wird benutzt, Elemente mit gleichem Hashwert
(modulo Hashsize) werden im selben Bucket abgelegt
Einfügen: Zuordnung von Element mittels Hashfunktion dem Bucket. Suche nach dem ersten freien Platz
/ gelöscht markierten Element anderenfalls ab in die Overflow Liste. Alle Buckets teilen sich
denselben Überlauf-Speicher. Wichtig: damit Buckets nicht überlaufen muss ab einem
gewissen Füllgrad ein Rehashing erfolgen, so dass die Zugriffe schnell bleiben.
Suche:
1) Ermittlung mittels Hashfunktion vom richtigen Bucket 2) Abbruch der Suche falls das
Element nicht gefunden wurde und im Bucket noch freie Plätze sind 3) Anderenfalls den ganzen Overflow durchsucht ob
Element dort vorhanden ist.
Variante des Bucket Hashing (leerer Platz = jungfräulich aber nicht gleich gelöscht markiert!!!)
Keine explizite Aufteilung in Buckets / Verwendung von virtuellen Bucket rund um den Hashwert. Vorteil,
jeder Tabellenplatz kann als Ausgangspositionen für das Einfugen benutzt werden Reduktion der Anzahl
Kollisionen bei gleicher Tabellen-Grösse.
Einfügen: 1) Ermittlung von Platz P mittels Hashfunktion. 2) Falls Platz bereits besetzt ist, wird ein freier
Platz gesucht (rund um P in der Reihenfolge P + 1, P + 2, …, P + B − 2, P + B – 1) 3) Falls kein freier
Platz gefunden kommt Element in den Überlauf-Speicher.
Suchen:
1) gleiche Vorgehensweise wie beim Einfügen 2) Abbruch wenn gefunden oder leeren Platz
gefunden 2) Anderenfalls den ganzen Overflow durchsucht ob Element dort vorhanden ist.
Löschen: Elemente werden nur gelöscht markiert! können aber wiederverwendet werden!
Separate Chaining
Ist die flexibelste Art, um Kollisionen zu beheben. Jedes Element der Hashtabelle einen next-Zeiger auf
eine verkettete Liste. Vorteil des Bucket System jedoch ohne Overflow!!!
Einfügen: Zuerst wird die Hashadresse Hash(k) berechnet. Dann wird der neue Schlüssel am Anfang
der verketteten Liste eingefügt.
Suchen:
Berechnen der Hashadresse Hash(k). Dann wird k mit den Schlüsseln in der entsprechenden
Liste verglichen, bis k entweder gefunden wird oder das Ende der Liste erreicht ist.
Löschen: Das Element wird einfach aus der Liste in Hash(k) entfernt.
3
Radix Sort
Wie bucket Sort jedoch mit der Begrenzung der Anzahl Eimer. Prinzip zur
Sortierung einzelner Zahlenstellen gemäss dem Zahlensystem, welches durch die
Anzahl Eimer definiert wird. zB. 10 Eimer also Dezimalzahlen, 8 Eimer Oktalzahlen
etc. Sortierkriterium = (Zahl / Zahlensystem ^ (Durchlaufebene-1) ) mod
Zahlensystem
3
5
3
5
5
13
7
13
7
13
14
7
13
14
14
15
7
25
16
25
16
16
24
16
15
16
24
28
33
24
42
24
33
25
28
25
28
33
42
25
28
33
42
28
42
42
Pattern Matching
Technik, mit welcher ein String aus Text oder Binardaten nach einer Zeichenfolge durchsucht wird. Die gesuchten Zeichenfolgen werden
dabei in Form eines Suchmusters (Pattern) angegeben.
Beschreiben von Pattern, Regulare Ausdrücke
Benötigen Sprache für die Beschreibung von Pattern.
Alphabet E: definiert die endliche Menge Zeichen Wort über E ist eine endliche Folge von Zeichen aus E; leeres Wort λ(Lamda) besteht aus
keinem Zeichen; Menge aller Wörter des Alphabets bezeichnet man als E* ||| Für E = {A;B} ist E∗ = {λ;A;B;AA;AB;BA;BB;:::}:
Reguläre Ausdrücke
Ist ein Wort was mit Hilfe der Operation Konkatenation, der Auswahl oder der Iteration zusammengebaut wurden.
Konkatenation: setzt zwei Wörter zusammen z.B ‚AB‘ ‚CD‘ -> ‚ABCD‘
(mittlere Bindungsstärke)
Auswahl:
erlaubt zwischen Wörtern auszuwählen (OR) z.B. AB|B -> ‚AB‘ oder ‚B‘
(tiefste Bindungsstärke)
Iteration:
repetiert das angegebene Wort beliebig oft (0…x) z.B. A(AB)* -> ‚A‘, ‚AAB‘ ‚AABAB‘
(höchste Bindungsstärke)
Endliche Automaten (z.B. zur Prüfung der regulären Ausdrücke)
Ein endlicher (deterministischer) Automat besteht aus einer endlichen Menge von Zuständen, einem Anfangs(oder Start-) Zustand und einem oder mehreren Endzustanden (oder akzeptierenden Zustanden).
Deterministisch: wenn jede Eingabe des Eingabealphabetes in jedem Zustand erlaubt ist und zu einem
eindeutigen Nachfolgezustand führt.
Eingabe:
Es gibt also eine endliche Menge E von Eingabezeichen, die der Automat lesen kann und die
eine gewisse Aktion auslösen. Die Menge E heisst Eingabealphabet. E = {EC-Karte, Pincode
(korrekt/falsch), Auswahl (Geld, Kontost.), Geldbetrag, Ok }
Zustand:
Ein deterministischer Automat befindet sich immer in einem bestimmten Zustand. Die endliche
Menge Z der möglichen Zustände heisst die Zustandsmenge. Z = {1 (Startzustand), 2 (warten auf
Pincode) (Anfangszustand Robus / Endzustand Doppelter Kreis)
Zustandsübergang: Die Verarbeitung eines einzelnen Eingabezeichens kann durch eine Nachfolgefunktion, ein Zustandsdiagramm oder
durch eine Zustandstafel beschrieben werden. Durch die Einwirkung der Eingabe kann er einen Zustandswechsel machen.
Ausgabe:
Im Laufe seiner Arbeit kann der Automat eine Ausgabe produzieren. Die endliche Menge A
der produzierten Ausgabezeichen heisst Ausgabealphabet. A = {EC-Karte, Kontostand, Geld}
Nichtdeterministischer: endlicher Automat kann für jeden Zustand und jede Eingabe null, einen oder mehrere
Nachfolgezustände haben.
leere Übergänge ε: Übergänge ohne gelesenes Zeichen (epsilon- Übergänge) ε WICHTIG: jedes Zeichen muss gelesen werden können!!
Von einer leeren Menge kommt man NIE zurück!!!
Automaten zu regulären Ausdrücken
Suche einen zu einem regulären Ausdruck äquivalenten Automaten.
(AB|C)*(A|B)
(AB|BC)∗(C|BC)
Prüfung von Regulären Ausdrücken
BBCC –B->{1} –A->{1} –C->{4} –C-> {3} 
Vergleich mit dem Endzustand wenn gleich dann ok!
Top Down Parser
Kontextfreie Grammatik
Grammatik EBNF: Extended Backus-Naur Form
Mit Hilfe einer Grammatik wird Aufbau oder Strktur (Regeln) einer
Satz
S
ist
Satz
::= S ’ist’ A
Sprache beschrieben. KFG dient als Notation einer Sprachsyntax. Sie
S
Artikel
Nomen
S
::= Artikel Nomen
beschreibt eine Sprache (Menge von Wörtern oder Strings).
KFG hat 4 Muss Kriterien:
Artikel
der
Artikel ::= ’der’
1) Eine Menge von Terminalen wie ’ist’, ’der’, ’ein’ … 2) Eine Menge
Artikel ::= ’ein’
ein
von Nichtterminalen, d.h. Namen bzw. Symbole, die weiter ersetzt
werden. 3) Einer Menge von Produktionen (l ::= r), Jede Produktion
A
Adjektiv
A
::= Adjektiv
besteht aus einem Nichtterminal auf der linken Seite und einer
A
::= Adjektiv ’und’ A
und
rechten Seite, welche eine Reihe von Terminalen und/oder
A
::= Adjektiv ’oder’ A
oder
Nichtterminalen darstellt. 4) Ein ausgezeichnetes Nichtterminal dient
Adjektiv::= ’schön’ | ’gross’ | ...
als Startsymbol (ist immer ein Nichtterminal und immer links von
einer Produktion)
Herleiten eines Wortes: Beginn mit Startsymbol, 2) ersetzten im hergeleiteten Wort ein Nichtterminal durch die rechte
Seite der Produktion. 3) Wiederholung bis alle Nichtterminale ersetzt worden sind. Alle Wörter zusammen bilden die
Grammatik.
Top-Down Parser
public class ArithmeticExpressionParser {
private String parseString;
private int position;
private int length;
public void parse(String aExpr) throws
ParseException { . . . }
// one method per grammar line
...
}
public void parse(String aExpr)
throws ParseException {
position = 0;
parseString = aExpr;
length = parseString.length();
expression();
if (position < length) throw new
ParseException(position, "parse");
}
expression ::= term {′+′term |′−′term }
term ::= factor {‘*′factor }
private void expression() throws
ParseException {
term();
while(position < length ) {
if( parseString.charAt(position) == ’+’
|| parseString.charAt(position) == ’-’) {
position++;
term();
}
else
return;
}
}
private void term() throws
ParseException {
factor();
while (position < length)
if( parseString.charAt(position) ==
’*’) {
position++;
factor();
}
Else
return;
}
A
A
number ::= digit { digit }
private void number() throws ParseException {
int n = position;
while (position < length &&
isDigit(parseString.charAt(position)))
position++;
if (n == position)
throw new ParseException(position, "number:
digit expected");
factor ::=′(′expression′)′| number
private void factor() throws ParseException {
try {
if (parseString.charAt(position) == ’(’) {
position++;
expression();
if (parseString.charAt(position) == ’)’)
position++;
else
throw new ParseExcon(position, "factor");
} else
number();
}
catch (StringIndexOutOfBoundsException e) {
throw new ParseException(position, "factor");
}
}
Kryptologie
Kryprographie=Lehre des Verschlüsselns, Kryptoanalyse=Lehre des CodeKnackens, Kryptologie= Kryprographie + Kryptoanalyse
Geheimhaltung, Authentifizierung(Nachweis eigener Identität), Integrität
(Fälschungssicherheut)
Einfache Verschlüsselung
Caesar Chiffre:
Vigenère Chiffre:
einfachste und älteste Verschlüsselungsmethode. jeder Buchstabe wird um k verschoben (Stromchiffre) (27
Variationen)
etwas verbesserter Caesar mit Schlüsselwort als Additionstabelle (Blockchiffre). -> Schlüsselwort wird endlos
wiederholt und entsprechende Stellen im Klartext mit Buchstabennummer des Schlüssels addiert
jedem Buchstaben wird ein anderer Zugeordnet -> Permutationsfunktion (27! Variationen)
Zweierblöcken von Buchstaben wird ein anderer Block zugewiesen (272! Variationen)
Permuttationschiffre:
Permutation von Blöcken:
Knackbar?
Es gibt keine einfache und trotzdem sichere Verschlüsselungsverfahren, jeder Code ist knackbar (mit genügend Zeit und verschl. Text)
Alle Methoden einfach knackbar mit Häufigkeitsanalysen (Häufigkeit von Buchst.: E, SPACE, N, R, I, S, T... oder Silben: en, ...)
Vernamchiffre, OneTimePad: absolut sicher wenn: Vigenère Chiffre verwendet wird mit Schlüsselwort gleich lang wie der Text bestehend
aus zufälliger Buchstabenfolge und jeder Schlüssel nur einmal verwendet. -> Sehr umständlich da pro Zeichen ein Zeichen über sicheren
Weg transp. werden muss. Lösung: Als Schlüssel wird eine Zufalls-Zahlenreihe benutzt -> Zufallsfunktion muss bekannt und geheim sein.
Beispiel für eine gute Zufallsfunktion: f(n) = 100*(sin(n)+1). Verschlüsselungs/Entschlüsselungsmaschinen für grosse Datenmengen (z.B.
Telefone)
Symmetrische Verfahren
Es wird für die Verschlüsselung und Entschlüsselung derselbe Schlüssel verwendet. Die meisten sym. verfahren sind Blockchiffren. -> Auf
Blöcke von 8 od. 16 Zeichen resp. 64 od. 128 Bit wird eine kombination von einfachen Verschlüsselungsverfahren angewendet (zB. modulare
Addition, Substitution, Linear-Transformation, etc.)
Beispiele: DES (Data Encryption Standard), DEA (Data Encryption Algorithm), Tripple-DES, CAST, RC4 (Rivest Cipher), IDEA
Vorteil: ist relativ schnell und sicher!
Asymmetrische Verfahren
Verschlüsselung und Entschlüsselung verwenden nicht denselben Schlüssel.
Ermöglicht PKK (Public Key Kryprosystem) das ohne Austausch von
geheimen Schlüsseln auskommt. Jeder Teilnehmer braucht ein
Schlüsselpaar:.
Bedingungen für eine PKK: 1) Genügend viele Paare von
Verschlüsselungsfunktionen (V,E) und Schlüsseln (v,e), 2) für jede Meldung
m gilt: E(V(m))=m, 3) V ist eine Einwegfuntion (nur mit Kenntnis des 2. Schlüssels oder gr. Aufwand invertierbar), 4) V und E leicht
berechenbar mit Kenntnis der Schlüssel v und e.
Beispiele für PKK: Diffie-Hellmann Algorithmus (1976) und RSA Algorithmus (1978) -> Verfahren werden RSA-Kryptosysteme genannt.
RSA
meist genutztes PKK (SSL, SET, S/Mime, SSH, S-HTTP, ...).
Ausgangslage: Berechnung von m^v mod n ist einfach, m^(1/v) mod n aber
nicht
Erzeugen von Schlüsseln: 1) zwei verschiedene grosse Primzahlen wählen
(p,q) und Produkt m=p*q berechnen. -> Setze n=(p-1)*(q-1), 2) Wähle
beliebigen wert e kleiner m und teilerfremd zu n. Berechne zu e das v zu
dem gilt: e*v=1+l*n
Authentifikation mit RSA (geht nur mit RSA)
Die RSA-Funktionen sind umkehrbar (Verschlüsseln mit priv. Schlüssel und entschlüsseln mit öff. Schlüssel). Wird die Meldung vom
Absender zusätzlich mit dem eigenen privaten Schlüssel verschlüsselt kann der Empfänger durch Entschlüsseln mit dem öffentlichen
Absender-Schlüssel verifizieren ob die Meldung wirklich von diesem stammt.
Integritätsprüfung mit RSA
Versicherung das eine Webseite zu einem bestimmten Anbieter gehört oder dass eine Meldung unterwegs nicht verändert wurde.
Vorgehensweise: Bilden eines Hash-Wertes aus den Webseiten-/Meldungsdaten, verschlüsseln mit dem privaten Schlüssel des Anbieters
und senden an den Empfänger. Letzterer kann den Hashwert ebenfalls berechnen und mit dem erhaltenen Hashwert (entschlüsselt mit dem
öff. Schlüssels des Anbieters) vergleichen. Wichtig öffentliche Schlüssel muss korrekt ist, uns also kein falscher Schlüssel vorgetäuscht!!
Dies garantieren spezielle Firmen und Institutionen, sogenannte Trustcenter wie TC TrustCenter, VeriSign oder Thawte
Hybride Verfahren
Bei hybriden Verfahren werden weniger sichere symmetrische Verschlüsselungen verwendet (z.B. DES) und mittels sicheren asym.
Verfahren ergänzt. Konkret wird er Schlüssel für das sym. Verfahren mit dem öff. Schlüssel des Empfängers verschlüsselt und an die sym.
Verschlüsselte Meldung angehängt. Verbindet Schnelligkeit von sym. Verfahren und Sicherheit von asym. Verfahren.
Diverses
Datentyp
Einfügen am
Anfang
Überschreiben der Einfügen am
idx
Ende
Einfügen
sortiert
Suchen
"Gefundenes"
Element löschen
Array, unsortiert
Θ(n)
Θ(1)
Θ(1)
-
Θ(n)
Θ(n)
Array, sortiert
-
-
-
Θ(n)
Θ(log2(n))
Θ(n)
Einfach / doppelt verkette
Listen
Θ(1)
Θ(n)
Θ(1)
Θ(n)
Θ(n)
Θ(1)
Stack
Θ(1)
-
-
-
-
Θ(1)
Queue
-
-
Θ(1)
-
-
Θ(1)
Binärer Suchbaum
-
-
-
Θ(log2(n))
Θ(log2(n))
Θ(log2(n))
Heap(priority Queue)
-
-
-
Θ(log2(n))
Θ(n) *
Θ(log2(n))
Hash Tabelle
-
-
-
Θ(1)
Θ(1)
Θ(1)
Public class BinaryTreeNode<T>{
protected T data;
protected BinaryTreeNode<T>leftChild; protected BinaryTreeNode<T>rightChild;
public BinaryTreeNode(T item){data = item;}
public BinaryTreeNode<T> inOrderFind(final T item){. . . }
public BinaryTreeNode<T> postOrderFind(final T item){. . . }
public BinaryTreeNode<T> preOrderFind(final T item){. . . }
}
public BinaryTreeNode<T>preOrderFind(final T item){
if (data.equals(item)) return this; // Präordersuche Punkt 1
if (left.Child != null)
// Präordersuche Punkt 2
{BinaryTreeNode<T> result = leftChildren.preOrderFind(item); if (result != null) return result;}
if (right.Child != null)
// Präordersuche Punkt 3
{BinaryTreeNode<T> result = rightChildren.preOrderFind(item); if (result != null) return result;}
return null;
}