Datenstrukturen und Algorithmen

Da die Anzahl der Schlüssel im Hashverfahren begrenzt ist, werden notwendigerweise Schlüssel mehrfach besetzt. Das Lineare Sondieren versucht durch eine lineare Konstante eine Gleichverteilung zu erreichen, um eine "Entartung" des Hashs zu verhindern. Dabei wird T(h(e)) gerechnet (Objekt MOD #Schlüsselelemente) und falls der Schlüssel besetzt ist, nochmal um 1 inkrementiert, also T(h(e)+1) berechnet, bis man einen leeren Eintrag findet. 

Es sind auch andere Konstanten als 1 zulässig. Dabei ist zu beachten, dass ggT von Konstante c und Tabellenlänge N = 1 ist. 

Ähnlich wie beim Linearen Sondieren werden Quadratzahlen für die Sondierabstände benutzt, also {T(h(e)), T(h(e)+1), T(h(e))+4, T(h(e))+9, T(h(e))+16,...,T(h(e))+i²} berechnet.

Empfehlenswert ist die Wahl einer Primzahl für N, die modulo 4 den Rest 3 liefert, da die Sondierungsfolge alle Plätze der Hashtabelle erreicht.

• Surjektivität: Jedes Element der Zielmenge muss erreicht werden
• Gleichverteiltheit: gute Streuung, sonst kommes es an bestimmten Stellen zu mehr Kollison als nötig
• Berechenbarkeit in konstanter Zeit

Hashfunktion mit erweiterbarem Bildbereich.

Minimale Anzahl von Editierfunktionen, um einen String in einen anderen überzuführen.

Datenstruktur, die für eine Menge an Dokumenten, für jedes Wort speichert:
Anzahl Vorkommen, Dokument ID, evtl. Position

• Eine Transistion kann schalten (bzw. feuern), wenn jede Eingabestelle von t mindestens eine Marke enthält.
• Schaltet eine Transition, dann wird aus jeder Eingabestelle eine Marke entfernt und zu jeder Ausgabestelle eine Marke hinzugefügt.
• 
  Bei Stellen mit Kapazitäten darf das Hinzufügen nicht die Kapazitätsbegrenzung verletzen

Erweiterung um gewichtete Kanten: bewegen mehrere Marken auf einmal.

Garantiert wechselseitigen Ausschluss durch Synchronisation Prozeduren mit kritischen Abschnitten werden als Monitor Operationen gekennzeichnet.

Metapher: Raum, in dem sich nur eine Person (ein Prozess) zur Zeit aufhalten kann. Weitere Personen müssen warten, bis der Raum wieder frei ist.

Analogie mit mechanischen Eisenbahnsignalen: ein kritischer Gleisabschnitt darf nur von je einem Zug zur
Zeit befahren werden

Konstrukt zur Kontrolle des Zugriffs auf gemeinsame Ressourcen

Greedy-Algorithmen (gierige Algorithmen) zeichnen sich dadurch aus, dass sie immer denjenigen Folgezustand auswählen, der zum Zeitpunkt der Wahl den größten Gewinn bzw. das beste Ergebnis verspricht

Rekursive Rückführung eines zu lösenden Problems auf ein identisches Problem mit kleinerer Eingabemenge

Teillösung werden schrittweise zu einer Gesamtlösung ausgebaut
• Falls Teillösung nicht zu einer Lösung führt…
• … letzten Schritt bzw. letzte Schritte zurücknehmen und alternative Wege probieren

Bei der dynamischen Programmierung werden kleinere Teilprobleme zuerst gelöst, um aus diesen größere Teillösungen zusammenzusetzen.

Nicht immer ist es möglich, die Lösungen kleinerer Probleme so zu kombinieren, dass sich die Lösung eines größeren Problems ergibt.
Die Anzahl der zu lösenden Probleme kann unvertretbar groß werden

•  zu viele Teillösungen, die dann doch nicht benötigt werden
•  Gewinn durch Wiederverwendung zu gering da Lösungszweige disjunkt

\(h(x)= N \cdot (k \cdot z - \lfloor k \cdot z \rfloor\) mit N ist Anzahl der Hashingschlüssel und k ist Element das eingefügt werden soll und z eine irrationale Zahl (in der Regel der Goldene Schnitt: 0,362)

\(\)Eingabe: Folge F der  Länge n, Suchschlüssel  k
Ausgabe: Position p des ersten Elementes aus F,  das  gleich k ist,  sonst NO_KEY

\(\textbf{for}\ i:= 1\ to \ n\ do \\ \ \ \ \ \ \ \ \ \textbf{if} \ F[i] = k\ \textbf{then}\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{return}\ i\\ \ \ \ \ \ \ \ \ \textbf{fi} \\ \textbf{od};\\ \textbf{return} \ NO \_ KEY \)

Ein Algorithmus ist eine eindeutige Beschreibung eines in mehreren Schritten durchgeführten (Bearbeitungs-)Vorganges.

Bester Fall: \(1\)
schlechtester Fall: \(n\)
Durchschnitt (erfolgreiche Suche): \( \frac{n + 1}{ 2 }\)
Durchschnitt (erfolglose Suche): \(n\)

Idee: Nutze Sortierung aus
Nutze „wahlfreien“ Zugriff auf beliebige Elemente
Prinzip: Wähle den mittleren Eintrag und prüfe, ob gesuchter Wert in der ersten oder in der zweiten Hälfte der Folge ist. Fahre rekursiv mit der Hälfte fort, in der sich der Eintrag befindet. 

Bester Fall: \(1\)
schlechtester Fall: \(\log_2n\)
Durchschnitt (erfolgreiche Suche): \(\log_2n\) 
Durchschnitt (erfolglose Suche): \(\log_2n\)

nach dem ersten Teilen der Folge: noch n/2 Elemente
nach dem zweiten Schritt: n/4 Elemente
nach dem dritten Schritt: n/8 Elemente

\(1 = \frac{n}{2^i} \rightarrow 2^i=n \rightarrow \log_2(2^i)=\log_2n \rightarrow i=\log_2n\)

• Datenstruktur mit beschränktem Zugriff
• 3 Methoden
• push: legt das Objekt als obersts Element auf dem Stack ab
• pop: nimmt das oberste Element vom Stack und gibt es zurück
• top (bzw. peek): gibt das oberste Element des Stacks zurück ohne es zu entfernen
• Außerdem: isEmpty: liefert true, wenn keine Element auf dem Stack liegen, andernfalls false

• FIFO-Prinzip
• Einfache Datenstruktur mit beschränktem Zugriff mit 3 Methoden
• enter (bzw. enqueue): fügt das Objekt zur Warteschlange hinzu
• leave (bzw. dequeue): nimmt das "älteste" Element aus der Warteschlange heraus und gibt es zurück
• front (bzw. peek): liefert das "älteste" Element aus der Warteschlange, ohne es zu entfernen
• Außerdem: isEmpty: liefert true, wenn kein Element und false falls Elemente in der Warteschlange

• Array muss mit einer festen Größe intialisiert werden (wenn die Kapazität erschöpft, dann neues größeres Array erstellen und Umkopieren der Elemente)
• Zeiger auf die "Spitze des Stacks" notwendig

Gilt für Stack und Queue:

• void addFirst(Object obj): fügt das Objekt obj als erstes Eleemnt in die Liste ein
• Object getFirst(): liefert das erste Element der Liste
• Object removeFirst(): entfern das erste Element der Liste udn gibt es gleichzeitig als Ergebnis zurück
• void addLast(Object obj): hängt das Objekt obj als letztes Element an die Liste an
• Object getLast(): liefert das letzt Element der Liste
• Object removeLast(): entfernt das letzte Element der Liste und gibt es gleichzeitig als Ergebnis zurück

\(\begin{matrix} \underline{Umsetzung} & \underline{Operation} & \underline{Komplexit \ddot a t} \\ \textbf{ArrayList} & \\ & addFirst & \mathcal{O}(1)\\ \ & getFirst & \mathcal{O}(1)\\ & removeFirst & \mathcal{O}(1)\\ \textbf{Linked List} \\ & addFirst & \mathcal{O}(n) \\ & getFirst & \mathcal{O}(n)\\ & removeFirst & \mathcal{O}(n)\\ \textbf{DoubleLinkedList} \\ & addFirst & \mathcal{O}(1) \\ & getFirst & \mathcal{O}(1) \\ & removeFirst & \mathcal{O}(1)\\ \end{matrix}\)

Der Speicherplatzbedarf des Arrays ist vorgegeben durch die Größe des Arrays und nicht durch die Anzahl der Elemente.  Operationen für Queue und Stack sind effizient mit doppelt verketteter Liste umzusetzen.

• boolean hasNext() prüft, ob noch weitere Elemente in der Kollektion verfügbar sind
• Object next() liefert das aktuelle Element zurück und setzt den internen Zeiger des Iterators auf das nächste Element
• void remove() erlaubt es, das zuletzt von next() gelieferte Element zu löschen
• Implementiert als Interface

Ein Sortierverfahren heißt stabil, wenn es die relative Reihenfolge gleicher Schlüssel beibehält.

Ansatz: Suche das größte Element und setze es an das Ende der Folge: fahre dann mit der um 1 kleineren Liste fort.