Zusammenfassung mit Übungen und Lösungen PDF

Preview

Summary

Dozent: Christopher Franzen, M.Sc.;
Standort: Aachen;
Sommersemester 2019;
Algorithmen, Datenstrukturen, Hashtabellen, Hashfunktionen, Verkettete Listen, Stack, Queue, Warteschlange, Heapsort, Quicksort, Insertionsort, Mergesort, Binäre Suchbäume, Graphen etc.
...

Description

● ● ● ● ● ● ● ● ●

●

Die Klausur wird sich an den Übungsaufgaben orientieren. Es werden nur Fälle behandelt die wir auch gemacht und besprochen haben. Es wird wahrscheinlich nicht programmiert werden (also kein Code muss schriftlich aus einer Aufgabe gemacht werden) Ihm ist wichtig, das man die Grundsätze versteht, wie funktioniert ein Algorithmus, Pseudocode erklären können usw. Alle Übungsaufgaben können in der Klausur kommen. Natürlich in abgeänderter Form. o Außer Übung 5 (Folie 40 in PDF 6). Fragen werden klar formuliert. Nicht zu viel schreiben – auf den Punkt kommen (wenn dort steht in drei Sätzen, sollte man auch nur drei Sätze schreiben) Beispielfrage: Das ist euer Array, zeig mir (es wird gesagt ob z.B. grafisch oder in Schritten) wie das anhand des folgenden Algorithmus (e.g. Insertion-Sort, Merge-Sort benannt oder als Pseudocode gezeigt) sortiert wird. Themen die kommen: o Pseudocode wird auf jeden Fall kommen! ▪ Wie funktionieren die Programme muss man können ▪ Es kann kommen: Folgender Pseudocode ist gegeben, erklären sie diesen ▪ Oder auch: Folgende Aufgabe ist gegeben, schreiben sie den Pseudocode dazu. Wird sehr wahrscheinlich kommen! o Sortierproblem / Sortieralgorithmen (Insertion-Sort, Merge-Sort, etc.) ▪ Durchlauf grafisch darstellen (vergl. 1 - Grundlagen.pdf, Folie 34, Aufgabe 1) sehr wahrscheinlich als Aufgabe! o Laufzeitanalyse (verstehen wofür, warum und nur ganz grob wie was Formeln etc. angeht) ▪ Bei Formeln z.B. Grundlagen.pdf, Folie 37, erklären können warum die Anzahl Durchläuft an einer bestimmten Stelle n – 1 ist, oder wie viele Durchläufe man ab einem bestimmten Punkt im Pseudocode benötigt. Themen die nicht kommen: o Es werden keine Definitionen abgefragt. Wichtig ist zu wissen was ein Algorithmus ist! o Historische Fakten (e.g. PDF 1, Folie 14 – 29) nicht relevant o Berechnung Laufzeit (Laufzeitanalyse) wird nicht kommen. Erklären wofür, warum etc. sollte man können.

Definition Algorithmus ● ● ● ● ●

●

Hat eine Eingabe und eine Ausgabe Ist eine Rechenvorschrift Ist eine Folge von Rechenschritten, die Eingabe in Ausgabe umwandelt Nicht jede Rechenvorschrift ist ein Algorithmus! Kriterien/Eigenschaften eines Algorithmus: o Korrektheit ▪ der Algorithmus erfüllt die seiner Entwicklung zugrunde liegende Spezifikation o Vollständigkeit ▪ der Algorithmus ist eine vollständige Beschreibung eines Lösungsverfahrens (inkl. Vor- und Rahmenbedingungen) o Eindeutigkeit/Ausführbarkeit ▪ jede Aktion muss (durch einen Prozessor) eindeutig interpretierbar und ausführbar sein o Statische Endlichkeit ▪ der Umfang der Beschreibung des Algorithmus muss endlich sein o Dynamische Endlichkeit ▪ Algorithmus kann terminierend (abbrechend) oder nicht-terminierend (nicht-abbrechend) sein o Effizienz ▪ Erfüllung des Zwecks des Algorithmus unter bestmöglicher Ausnutzung aller benötigten Ressourcen; Wichtig da: -> Kosten (Rechenzeit), wenn ein Algorithmus lange braucht, kann er bei komplexen Anwendungen vermehrt Kosten verursachen, da mehr Rechenleistung bzw. Zeit gebraucht wird, um den Algorithmus möglichst schnell zu beenden. o Verständlichkeit ▪ Aufwand, der zum Verständnis und zum Nachweis der Korrektheit notwendig ist Ein Algorithmus heißt terminierend, wenn er die Werte der gesuchten Datenobjekte in endlich vielen Schritten liefert, andernfalls heißt der Algorithmus nicht terminierend.“

Sortierproblem / Sortieralgorithmen Sortieren durch Einfügen ฀ Inkrementelle Vorgehensweise ฀ Insertion-Sort Alternative Entwurfstechnik ฀ Teile und Beherrsche ฀https://arnehannappel.de/blog/28sortieralgorithmen Merge-Sort o Verwendung einer rekursiven Struktur. Der Algorithmus ruft sich selbst erneut auf, um das Ursprungsproblem ähnlich, aber in kleineren Teilproblemen zu lösen Guter Link: https://arnehannappel.de/blog/28-sortieralgorithmen ● ●

Insertion-Sort (Sortieren durch Einfügen) ●

Alle Elemente werden nacheinander geprüft. Dabei werden immer zwei Elemente verglichen. Ist das linke größer als das rechte, werden die Elemente vertauscht.

●

Ist somit sehr einfach aufgebaut, hat aber den Nachteil, das der Durchlauf ggf. sehr lange sein kann (vor allem wenn eine kleine Zahl sehr weit hinten steht - beim Sortieren von klein nach groß). -> Performance!

●

Merge-Sort (Sortieren durch Mischen) ● ●

Teile und Beherrsche ist eine Alternative zur inkrementellen Vorgehensweise. Die Fibonacci-Folge ist ein gutes Beispiel dafür (Hasenbild); Die Fakultät ebenfalls. Der Merge-Sort basiert auf diesem Prinzip! Vereinfacht bricht man das Problem immer weiter in kleinere Teilprobleme runter, bis es eine triviale Lösung gibt.

● Grundprinzip besteht aus drei Schritten: 1. Teile das Problem in mehrere Teilprobleme auf, die kleinere Instanzen des gleichen Problems darstellen 2. Beherrsche die Teilprobleme rekursiv. Wenn die Teilprobleme klein genug sind, dann löse die Teilprobleme auf direktem Weg. 3. Vereinige die Lösungen der Teilprobleme zur Lösung des Ursprünglichen Problems ●

Merge-Sort wird also auf rekursivem Weg gelöst (wird so oft runtergebrochen bis man nur noch ein Element hat und dieses dann sortiert. Danach verbindet man wieder alles). 1. Teile die Folge von n Elementen in zwei Teilfolgen von n/2 Elemente auf. 2. Beherrsche durch rekursives Sortieren der zwei Teilfolgen; Abbruch, wenn Teilfolge nur noch ein Element aufweist. 3.Vereinige: Mische die zwei sortierten Teilfolgen, um die sortierte Lösung zu erzeugen. (zentrale Operation: MERGE).

●

Merge-Sort ist ein Algorithmus der sich immer wieder selbst aufruft!

●

Merge-Sort hat eine Konstante Laufzeit, da beim Teilen nicht auf die Zahlen geachtet wird. Erst beim Mergen, wird auf die Zahlen geachtet. → Konstante Laufzeit im Best-Case, Worst-Case und Average-Case. Der MergeSort ist somit dem Insertion-Sort überlegen wenn es um größere Zahlenreihen geht. o Laufzeit ist somit immer: O(n log(n))

●

Aufgabe: Merge-Sort Vorgehensweise zeigen - siehe: https://www.youtube.com/watch?v=yKgzwtqWvFU

Laufzeitanalyse ● ● ● ● ●

●

● ●

● ●

● ● ●

Notwendig für Bestimmung notwendiger Ressourcen: Rechenzeit, Speicher, Kommunikationsbandbreite Genaue Analyse kann aufwendig sein (viele mathematische Hilfsmittel notwendig) Ziel: Identifikation von charakteristischen Eigenschaften (Analyse ist ein einfacher Weg dafür) Schafft Vergleichbarkeit von Algorithmen. Annahmen bei Analyse: o Verwendung von Maschine mit RAM und einem Prozessor zur Ausführung des Algorithmus o Orientierung an real existierenden Maschinenbefehlen o Effekte durch Speicherhierarchien (Caches) werden nicht berücksichtigt Unterscheidung in 3 Felder (Erklärung rechts am Beispiel Insertion-Sort:) o Günstigster Fall: Feld ist bereits korrekt sortiert (nahezu kein Aufwand) o Mittlerer Fall: Feld ist willkürlich sortiert (häufigster Fall und oft nah am schlechtesten Fall, was die Laufzeit angeht) o Schlechtester Fall: Feld ist komplett falsch herum sortiert (maximaler Aufwand) Am Ende erhält man eine Formel mit der man die Laufzeit berechnen kann Analyse wird oft auf den schlechtesten Fall ausgelegt, da dieser o eine obere Schranke für die Laufzeit angibt o in vielen Anwendungsfällen häufig auftritt (z. B. bei der Suche nach nicht vorhandenen Schlüsseln in einer Datenbank) o der mittlere Fall oft annähernd so schlecht ist wie der schlechteste Fall (Laufzeit bei Sortierung durch Einfügen wäre auch dann noch quadratisch) Die Analyse des mittleren Falls wird im Rahmen probabilistischer (Wahrscheinlichkeit) Analysen verwendet; dabei sind Wissen/Annahmen über die Verteilung der Eingaben notwendig Wachstumsgrad Θ o Bisher durchgeführte Abstraktionen ▪ tatsächliche Kosten → Konstanten (ci) für Kosten ▪ Zusammenfassung der Konstanten ci → an2 + bn + c o Weitere Abstraktionen ▪ ausschließliche Betrachtung des führenden Terms → an2 ▪ Weglassen des konstanten Koeffizienten → n2 o Laufzeit des Algorithmus wächst im schlechtesten Fall wie n2 (Wachstumsrate / Wachstumsgrad), sie ist aber nicht gleich n2! o Man sagt, der Algorithmus (Sortieren durch Einfügen) hat im schlechtesten Fall eine Laufzeit von Θ(n2); (sprich: Theta von n2) Die Wachstumsrate der Laufzeit ist ein Maß für die Effizienz eines Algorithmus u. erlaubt Vergleiche alternativer Algorithmen. Verwendung asymptotischer Notation und sogenannter Landau-Symbole Analyse Insertion-Sort: o Laufzeit hängt von Eingabe ab o Anzahl der Elemente = Eingabegröße o Allgemein wird die Laufzeit meist als Funktion der Eingabegröße beschrieben o Definition der Eingabegröße hängt vom Problem ab (beim Sortieren z. B. die Anzahl der zu sortierenden Elemente; Grad der Vorsortierung spielt beim Sortieren, je nach Algorithmus, auch eine Rolle) o Laufzeit ergibt sich aus der Anzahl und der Art der auszuführenden Schritte (Grundoperationen) o Annahme: die Bearbeitung einer bestimmten Zeile Pseudocode benötigt einen konstanten Zeitaufwand o Laufzeit für Sortieren durch Einfügen: T(n) = an2 + bn + c m, haben mind. 2 Schlüssel den gleichen Hashwert. ● Wenn die Menge an tatsächlichen Schlüsseln |K| > m ist kommt es zwangsläufig zu Kollisionen ○ (bei |K| ≤ m kann es zu Kollisionen kommen). ● Anders formuliert: Die Werte werden in einer Hashtabelle mit dem Schlüssel k der Universalmenge U gespeichert. Bei der Verwendung einer beliebigen Hashfunktion mit mehreren Werten, kommt es schnell zu Kollisionen, da die Hashfunktion für unterschiedliche Werte denselben Schlüssel als Ergebnis ergibt. Es können aber keine Werte mit dem gleichen Schlüssel gespeichert werden! Daher ist eine Kollisionsauflösung notwendig. ● Kollisionsauflösung notwendig ○ Verkettung ○ offene Adressierung

Kollisionsauflösung durch Verkettung (https://www.youtube.com/watch?v=jMhwc1UfqIs) ● ●

●

Werte die mit dem selben Schlüssel gespeichert werden sollen, werden als Liste verkettet. Dabei werden neue Elemente am Listenkopf eingefügt. Laufzeiten ○ CHAINED-HASH-INSERT(T, x) → Im Schlechtesten Fall: O(1) ○ CHAINED-HASH-SEARCH(T, x) → Im schlechtesten Fall: Θ(1); Im mittleren Fall: O(1) ○ CHAINED-HASH-DELETE(T, x) → Im Schlechtesten Fall: O(1) Aufgabe dazu - Vorgehensweise: 1. Rest aller Werte mit der gegebenen Hashfunktion ermitteln (e.g. 5 mod 9 = 5; 28 mod 9 = 1 usw.) 2. Konflikte erkennen (gleiche Ergebnisse) und Reihenfolge notieren (letzter Konflikt ist Position 1, vorletzter Position 2 usw.) ← Für jeden Konflikt einzeln 3. Werte in der Tabelle eintragen

Hashfunktionen ●

●

Eine gute Hashfunktion, sollte Schlüssel gleichmäßig über Hashtabelle verteilen (damit weniger Konflikte entstehen) ○ → Da Schlüssel von Speicherung i.d.R. nicht bekannt, kann Gleichverteilung aber nicht garantiert werden. ○ Hashwert sollte unabhängig von Mustern in den Schlüsseln sein (e.g. via Divisionsmethode) Hashfunktionen erwarten i.d.R. natürliche Zahlen als Schlüssel. Falls nicht vorhanden, müssen sie als solche interpretiert werden (e.g. via ASCII)

Divisionsmethode (Rechenbeispiel oben bei Konfliktlösung mit Verkettung)

Multiplikationsmethode ● ● ● ●

● ● ●

Hashfunktion nach der Multiplikationsmethode für einen Schlüssel k und eine Tabelle mit m Slots Konstante A (Zahl zwischen 0 und 1) kommt dazu Hashfunktion: h(k) = m * (k * A mod 1) Wird berechnet wie folgt: Schritte mit Beispiel: k = 21, m = 8, A = 0,618 1. k * A | 21 * 0,618 = 13,987 2. Rest nach dem Komma * m | 0,987 * 8 = 7,824 3. Zahl vor dem Komma ist der Wert | h(21) = 7 Vorteil: Wert von m spielt keine kritische Rolle (wird oft als Potenz von 2 gewählt) Nachteil: langsamer als die Divisionsmethode Beispiel:

Kollisionsauflösung durch Offene Adressierung (Anwendung mit Linearem Sondieren) (https://www.youtube.com/watch?v=NbgTir1OzT8) ● ●

●

Alternative zur Verkettung Idee: ○ Speicherung aller Schlüssel direkt in der Hashtabelle (somit keine Verkettung notwendig) ○ Jeder Slot enthält entweder den Schlüssel k oder NIL ○ Suche nach dem Schlüssel k (Insert folgt gleichem Prinzip) ■ berechne h(k) und prüfe (sondiere) Slot h(k) ■ wenn der Slot den Schlüssel enthält war die Suche erfolgreich, wenn der Slot NIL enthält war die Suche nicht erfolgreich ■ wenn der Slot einen Wert ungleich dem Schlüssel enthält, wird, basierend auf k und der Anzahl der bereits durchgeführten Sondierungen (Sondierungszahl), ein neuer Hashwert berechnet ■ führe die Sondierung solange fort, bis Schlüssel k oder NIL gefunden ○ Die Sondierungssequenz bei der Suche soll eine Permutation der Slots sein Hashfunktion: h :U×{0, 1, ..., m-1}→{0, 1, ..., m-1}

● Methoden für die Sondierung ○ Jeder Slot enthält entweder den Schlüssel k oder NIL ○ Nutzung der ‚normalen‘ Hashfunktionen, die hier als Hilfshashfunktionen h´:U→{0,1,...,m-1} bezeichnet werden

Beispiel mit Linearem Sondieren ●

Schritte in der Berechnung - für jeden Schlüssel k nacheinander durchführen! 1. Rest eines Schlüssels k, mit der gegebenen Hilfshashfunktion ermitteln (e.g. 10 mod 11 = 10; 59 mod 11 = 4 usw.) 2. Überprüfen ob Schlüssel in der Tabelle bereits belegt. a. Falls ja: Schlüssel um 1 aufaddieren und Schritt 1 erneut ausführen; Sofern wieder belegt, solange beide Schritte wiederholen, bis nicht mehr aufgetreten. (e.g. 59 + 1 → 60 mod 11 = 5 → 60 + 1 = 61 mod 11 = 6 usw.) b. Falls nein: Wert in der Tabelle hinterlegen (e.g. 10 an Stelle 10; 59 an Stelle 8)

Heap (Haufen, Halde) Allgemeines ● ●

Ist eine Datenstruktur binärer Heap ○ fast vollständiger binärer Baum (auf allen Ebenen, außer evtl. auf der niedrigsten, vollständig gefüllt) Daher gilt das er maximal 2h+1 - 1 Knoten/Elemente haben kann (h + 1, da die Höhe die Wurzel nicht berücksichtigt) ■ Und minimal 2h Knoten/Elemente haben muss (letzte Ebene/Höhe/Tiefe, hat nur ein Blatt) Repräsentation als Feld Anordnung der Elemente erlaubt effizienten Zugriff Unterscheidung Min-Heap / Max-Heap ■

○ ○ ○

Max-Heap & Min-Heap

Funktion MAX-HEAPIFY (erzeugt einen Max-Heap) ● ● ●

Sortiert einen Heap so, dass die größeren Werte oben stehen (links und rechts wird nicht beachtet) Nach Anwendung wird der Baum dann als Max-Heap bezeichnet (auch lediglich auf Teilbäume anwendbar) Beispiel für Teilbaum: A={4,14,7,2,8,1} & Pseudocode zur Funktion:

●

Weiteres Beispiel:

Funktion BUILD-MAX-HEAP

Funktion HEAPSORT ●

● ●

Arbeitsweise: 1. Max-Heap wird mittels Funktion BUILD-MAX-HEAP welche auch die Funktion MAX-HEAPIFY verwendet erzeugt. 2. Die Wurzel wird mit dem letzten Element im Heap vertauscht (Im Beispiel wird bei 7 (Wurzel) mit 2 (Letztes Element) vertauscht) 3. Das letzte Element wird gelöscht → Endposition für korrekte Reihenfolge am Ende von HEAPSORT 4. MAX-HEAPIFY wird auf der neuen Wurzel für den gesamten Heap ausgeführt. (Es wird also wieder ein MAX-Heap erzeugt.) → Schritte 2 - 4 wiederholen sich solange, bis der Heap eine Größe von 2 hat. Bei der Illustration eines HEAPSORT, reicht es Schritt 1 schriftlich zu erwähnen und die Schritte 2 - 4 immer als einen Schritt aufzuzeigen. Beispiel der Arbeitsweise mit Pseudocode:

● Weiteres Beispiel:

Quicksort Allgemeines (https://www.youtube.com/watch?v=UoJJ78K-uc0) ● ● ●

● ●

Sortiert in-place Algorithmus ruft sich immer wieder selber auf (rekursiv) - ähnlich dem Merge-Sort Nutzt das Prinzip Teile, Beherrsche, Vereinige ○ Sortiert in-place, daher kommen nur Teile & Beherrsche vor. Die Sortierung findet schon im Teil Beherrsche statt. Pivotelement = Element einer Zahlenmenge, das als Erstes von einem Algorithmus ausgewählt wird, um bestimmte Berechnungen durchzuführen. Vorgehensweise 1. Letztes Element im Array wird als Pivotelement (x) deklariert 2. Danach wird das Array von links nach rechts durchlaufen (bis r) und in zwei Felder unterteilt. → j markiert dabei immer die nächste Zahl und auch das Ende des zweiten Feldes (j-1) → i markiert dabei immer das Ende des ersten Feldes (i) → p markiert Beginn des Arrays → r markiert Ende des Arrays a. Ist die Zahl (j) ≤ x → an das linke Feld anhängen (Zahl an der Stelle j, wird mit Zahl an der Stelle i+1 getauscht - exchange i+1 & j; i+1; j+1) b. Ist die Zahl (j) > x → an das rechte Feld anhängen (Zahl bleibt also stehen - j+1) 3. Zuletzt wird x zwischen die beiden Felder gesetzt (wird mit Zahl an Stelle i+1 getauscht). → Schritte 1 - 3 (Funktion Partition) wiederholen sich nun jeweils für das linke und das rechte Feld, sofern das Array noch nicht vollständig sortiert wurde. Dadurch entstehen dann wieder jeweils mindestens zwei weitere Felder, mit denen jeweils wieder die Schritte 1 - 3 wiederholt werden usw., bis das Array vollständig sortiert wurde. Diese Wiederholung findet statt, da sich die Funktion Quicksort rekursiv aufruft und dabei immer wieder die Funktion Partition aufruft.

Anderes Beispiel für Funktion Partition

Beispiel für Funktion Quicksort (Fehler in Quicksort(A,1,7) -> 9|8|7 müsste eigentlich 7|9|8 sein)

Laufzeiten ●

●

● ●

Hängt von Aufteilung der Teilfelder ab ○ Wenn “balanciert” → “so schnell wie Merge-Sort” ○ wenn “unbalanciert” → “so langsam wie Insertion-Sort” Best Case: O(n * log(n)) ○ Voraussetzungen: ■ alle Teilfelder sind komplett balanciert ■ jedes Teilfeld hat...