1. 1. Algorithmus
1.1. Merkmale
1.1.1. Allgemeinheit, d.h. er löst eine Vielzahl von Problemen
1.1.2. Eindeutigkeit, d.h. an jeder Stelle des Algorithmus muss eindeutig festgelegt sein, was zu tun ist und welcher Schritt der nächste ist
1.1.3. Ausführbarkeit, d.h. Jede einzelne Anweisung eines Algorithmus muss vom Computer (vom Mensch) ausführbar sein
1.1.4. Endlichkeit, d.h. die Beschreibung eines Algorithmus besitzt eine endliche Länge und besteht aus einer begrenzten Anzahl von Anweisungen mit begrenzter Länge
1.1.5. Terminierung, d.h. der Algorithmus ist nach endlich vielen Schritt beendet, also er liefert ein Ergebnis oder hält an
1.1.6. Effizienz, d.h. der Algorithmus kommt mit minimalem Speicherbedarf und/oder minimalem Zeitaufwand zum Ziel (Effizienzsteigerung ist eine fortgeschrittene Aufgabe des Programmiereres)
1.2. Definiton 1
1.2.1. Ein Algorithmus gibt eine Vorgehensweise vor, um ein Problem zu lösen. Anhand dieses Lösungsplans werden in Einzelschritten Eingabedaten in Ausgabedaten umgewandelt
1.3. Defintion 2
1.3.1. “Ein Algorithmus ist so etwas wie ein präzises Kochrezept. Ziel und Zutaten müssen festgelegt und dann klare Handlungsanweisungen gegeben werden, was wann wie in welcher Reihenfolge geschehen soll.“
2. 2. Algorithmen II
2.1. Phasen der Programmentwicklung
2.2. Operationen
2.2.1. führen Berechnungen durch
2.2.2. basieren oft auf Variablenwerten
2.2.3. weisen Variablen (neue) Werte zu
2.3. Verzweigungen
2.3.1. ermöglichen "Dynamik" in Algorithmen
2.3.2. enthalten boolesche Werte
2.3.3. Umsetzung in Programmiersprachen
2.3.3.1. if... then ... else
2.3.3.2. repeat... until...
2.3.3.3. while...do...
2.4. Euklid'scher Algorithmus
2.4.1. Definition
2.4.1.1. Man benutzt ihn, um den größten gemeinsamen Teiler (ggT) von zwei Zahlen zu bestimmen
2.4.2. Beispiel und Vorgehensweise
2.4.2.1. Wir haben zwei Zahlen gegeben und teilen die größere durch die kleinere Zahl
2.4.2.2. Divisor -> Dividend
2.4.2.3. Rest -> Divisor
2.4.2.4. neue Division mit Rest
2.4.2.5. solange wiederholen bis als Rest 0 rauskommt
2.4.2.6. In der letzten Zeile können wir dann den letzten gemeinsamen Teiler ablesen
3. 3. Rekursion
3.1. Iteration
3.2. Rekursionsarten
3.3. linerare Rekursion
4. 4. Komplexität
4.1. O-Notation
4.2. Laufzeit
4.3. Worst-Case-Szenario
4.4. Best-Case-Scenario
4.5. Komplexitäten vergleichen können
5. 5. Suchalgorithmen und zugehörige Datenstrukturen
5.1. Reihung (Array)
5.2. Operationen auf Reihungen
5.3. Strukturierte Datensätze
5.4. Suchen in Reihungen
5.5. Lineare Suche / sequenzielles Suchen
5.5.1. Komplexitätsbetrachtung
6. 6. Suchalgorithmen und zugehörige Datenstrukturen II
6.1. Methoden für Dateioperationen
6.1.1. Komplette Darstellung in Python wird im Skript "Suchen 2" erklärt
6.2. Binäre Suche
6.2.1. arbeitet nach dem Prinzip "teile und herrsche"
6.2.2. funktioniert nur auf sortierten Reihungen
6.2.3. ist aufgrund des "intelligenteren" Verfahrens effizienter als die lineare Suche
6.2.4. Ablauf bei aufsteigend sortierter Reihung
6.2.4.1. 1. die Reihung wird in der Mitte geteilt
6.2.4.2. 2. ist das gesuchte Element gleich dem mittleren, ist man fertig
6.2.4.3. 3. ist das gesuchte Element größer als das mittlere, wird nur noch die obere Hälfte betrachtet
6.2.4.4. 4. ist das gesuchte Element kleiner als das mittlere, wird nur noch die obere Hälfte betrachtet
6.2.4.5. 5. die betrachtete Hälfte wird wieder in der Mitte geteilt
6.2.4.6. 6. zurück zu Schritt 2, bis das gesuchte Element übrig bleibt
6.2.5. rekursive Implementation
6.2.5.1. Python-Darstellung steht im Skript "Suchen 2"
6.2.6. Komplexität und Zeitaufwand
6.2.6.1. Tabelle zu den Werten steht im Skript "Suchen 2"
6.3. Lineare Suche vs. Binäre Suche
6.3.1. Die Binäre Suche ist effizienter, wenn folgende Bedingung erfüllt ist: Es muss eine Ordnung auf den Elementen definiert sein und die Elemente müssen entsprechend dieser Ordnung sortiert sein
6.3.2. Arrays eignen sich für die binäre Suche
6.3.3. Anwendungsbeispiele stehen im Skript "Suchen 2"
7. 7. Statische vs. Dynamische Datenstrukturen
7.1. Arrays
7.1.1. Definition
7.1.1.1. Ein Array oder Feld ist eine zusammenhängende Folge einer festen Anzhal hintereinander abgelegter Datenelemente gleichen Typs
7.2. Listen
7.2.1. Definition
7.2.1.1. Eine Liste ist eine zusammenhämgende Folge einer variablen Anzahl beliebig im Speicher abgelegter Datenelemente auf Basis von Objekten
7.2.2. Verkettete Listen
7.2.2.1. Definition
7.2.2.1.1. Die verkettete Liste ist eine "Aneinanderreihung" von Objekten, die beliebig im Speicher angeordnet sein können
7.2.3. Vor - und Nachteile
7.2.3.1. Ansätze und Probleme, wie man das in Python lösen könnte, steht im Skript "Arrays und Listen"
7.3. Beispiel für Array vs. Liste
7.3.1. Nachbildung eines Kartenspiels im Computer: Stapel mit zu ziehenden Karten -> Array (feste Anzahl Karten im Spiel) /// Blatt des einzelnen Spielers -> Liste (variable Anzahl Karten im Spielverlauf)
7.4. Folgerung
7.4.1. Arrays eignen sich zur Behandlung von Sequenzen (Folgen) mit fester Anzahl von Elementen, während verkettete Listen besser bei dynamischen Sequenzen sind, deren Länge sich häufig zur Laufzeit ändert
8. 8. Bäume
8.1. Binärer Baum
8.1.1. Was ist ein Binärbaum?: Ein Knoten hat immer nur höchstens zwei Nachfolger (Kinderknoten)
8.2. Verzweigungsgrad
8.2.1. Anzahl der maximal möglichen Verzweigungen (Bei Binärbäumen maximal 2)
8.3. Höhe des Baumes
8.3.1. Der längste Weg von der Wurzel zur untersten Stufe (Höhe des Baums minus 1) oder einfach: Anzahl der Stufen
8.4. Zweig des Baumes
8.4.1. Ein Zweig des Baumes besteht aus einer Reihe von Knoten, die an der Wurzel beginnen und an irgendeinem Blatt enden
8.5. Ausgeglichenheit
8.5.1. Ist der Höhenunterschied zwischen dem linken und rechten Teilbaum kleiner als 1? Wenn sie die gleiche Höhe haben -> ausgeglichen
8.6. Vollständigkeit
8.6.1. Vollständige Bäume: Alle Knoten haben so viele Nachfolger wie maximal möglich
8.7. Größe / Gewicht
8.7.1. Die Gesamtzahl der Knoten
8.8. Blätter
8.8.1. Anzahl der Knoten, die keine Kinder haben
9. 9. Binäre Suchbäume
9.1. Operationen
9.1.1. Einfügen, Löschen, Suchen
9.2. Binärbaumerzeugung
9.2.1. Normale Vorgehensweise: Erster Schlüssel der Zahlenfolge ist die Wurzel und alle kleineren Zahlen kommen auf die linke Seite, alle größeren auf die rechte Seite
9.2.2. Wenn er so ausgeglichen wie möglich sein soll: Den Median (mittleren Wert) der Schlüsselfolge zur Wurzel nehmen. Alle Schlüssel, die kleiner sind als der Median bilden den linken Teilbaum der Wurzel und alle Schlüssel, die größer als der Median sind, bilden den rechten Teil der Wurzel (Gleiches Vorgehen bei den Teilbäumen -> Rekursion)
9.2.2.1. "oberer Median": Die Zahl, die einen Wert über dem Median ist
9.2.2.2. "unterer Median": Die Zahl, die unter dem Wert des Medians ist
9.3. Minimum finden
9.3.1. Den kleinsten Schlüssel findet man, indem man solange in den linken Teilbaum nach links absteigt, bis man nicht mehr weiterkommt
9.4. Maximum finden
9.4.1. Den größten Schlüssel findet man, indem man solange in den rechten Teilbaum nach rechts absteigt, bis man nicht mehr weiterkommt
9.5. Einfügung von Knoten
9.5.1. Regel beachten: Die Zahl (Schlüssel), die man einfügt, steht links, wenn sie kleiner als die Wurzel und rechts, wenn sie größer als die Wurzel ist
9.6. Löschen eines Knotens
9.6.1. Nach dem Löschen eines Knotens müssen immer noch die Bedingungen für einen Binären Suchbaum gelten! Es gibt 3 Fälle:
9.6.1.1. 1. Fall (Einfachster Fall): Knoten hat keine Kinder und wird schlicht entfernt
9.6.1.2. 2. Fall: zu löschender Knoten hat nur einen Nachfolger. Der Nachfolger-Knoten wandert eine Ebene höher
9.6.1.3. 3. Fall (kompliziertester): zu löschender Knoten hat 2 Nachfolger und einer der Nachfolger ist Wurzel eines Teilbaums. Der gelöschte Knoten wird ersetzt durch das größte Element im linken Teilbaum oder das kleinste Element im rechten Teilbaum
10. Level-Order
10.1. von oben nach unten, von links nach rechts ablesen
11. 10. Traversieren
11.1. Pre-Order
11.1.1. Wurzel-Linker Baum-Rechter Baum (links, WLR)
11.2. In-Order
11.2.1. Linker Baum-Wurzel-Rechter Baum (unten, LWR)
11.3. Post-Order
11.3.1. Linker Baum-Rechter Baum-Wurzel (rechts, LRW)
12. 11. Bäume - Implementierung
12.1. Wie man Bäume in Python implementiert steht im Moodle-Skript "Baumimplementierung"(Die Wege sind zu lang, um sie hier aufzuzählen)
13. 12. Heaps (Haufen)
13.1. Defintion
13.1.1. Ein Heap ist eine Datenstruktur in Form eines linksvollständigen binären Baumes mit der Eigenschaft: Jeder Knoten hat einen Schlüssel, der kleiner, größer oder gleich dem Schlüssel des Elternknotens ist
13.2. Arten von Heaps
13.2.1. Max-Heap
13.2.1.1. größtes Element befindet sich in der Wurzel
13.2.2. Min-Heap
13.2.2.1. kleinstes Element befindet sich in der Wurzel
13.3. Eigenschaften in Array Darstellung
13.3.1. Wegen der Linksvollständigkeit: Ein neues Element fügt man immer am Ende des Arrays ein
13.3.2. Wurzel ist immer der 0. Index, der zweite Schlüssel der 1. Index usw.
13.4. Basisoperationen
13.4.1. Einfügen
13.4.1.1. Das neue Element wird in der untersten Ebene so weit links wie möglich eingefügt (damit der Baum linksvollständig bleibt)
13.4.1.2. Wenn das neue Element, was wir einfügen möchten, das kleinste bzw. das größte Element des Teilbaums ist, müssen wir das Element mit dem Vorgänger vertauschen (damit die Heapeigenschaft erhalten bleibt)
13.4.2. Entnehmen / Löschen
13.4.2.1. 1. Vergleiche Eintrag in (Wurzel-)knoten k mit beiden Kindern (falls vorhanden)
13.4.2.2. 2. Falls Eintrag von Knoten k kleiner als der größte Kind-Eintrag ist: vertausche mit größtem Kind-Knoten (Maxheap)
13.4.2.3. Falls nicht: fertig
13.4.2.4. 3. Wiederhole Prozedur bis "unten" angekommen oder Kinder kleiner oder gleich dem Eltern-Knoten sind
13.4.3. weitere Operationen (nicht so wichtig für die Klausur)
13.4.3.1. Erzeugen
13.4.3.2. Mischen
13.5. Binärer Heap-Baum
13.5.1. Darstellung in Python steht im Skript "Heaps"
13.6. Komplexität
13.6.1. Beim Einfügen: O(log N)
13.6.2. Beim Entnehmen: O(1), weil das größte bzw. kleinste Element bereits in der Wurzel steht
13.7. Priority Queues
13.7.1. Defintion
13.7.1.1. Prioritätswarteschlangen: Es werden Elemente mit hoher Priorität vor einem Element mit niedriger Priorität bedient und umgekehrt
13.7.2. Beispiele für Einsatz
13.7.2.1. Job-Verteilung in Computersystemen -> Schlüssel sind Prioritäten, die angeben, welche Benutzer zuerst bedient werden
13.7.2.2. Numerische Berechnungen -> Schlüssel sind Berechnungsfehler (größte Fehler werden zuerst nachbereitet)
13.7.2.3. Sortieren -> Heapsort
14. 13. Sortieralgorithmen
14.1. Merge-Sort
14.1.1. Laufzeitkomplexität
14.1.1.1. IMMER O(n*log(n)) -> im Worst, Best- und Average Case
14.1.2. Vorgehensweise
14.1.2.1. 1. Wir haben eine unsortierte Liste und zerlegen sie in 2 Hälften
14.1.2.2. 2. Die Teile solange zerlegen bis wir nur noch einzelne Zahlen übrig haben
14.1.2.3. 3. Verschmelzen: die benachbarten Zahlen werden paarweise zusammengefügt und beim Zusammenfügen sortiert
14.1.2.4. 4. Solange verschmelzen bis wir eine sortierte vollständige Liste haben
14.2. Quick-Sort
14.2.1. Laufzeitkomplexität
14.2.1.1. Average- und Best Case: O(n*log(n)) im Worst Case -> O(n^2) (d.h. die Liste ist bereits sortiert und wir wählen das letzte Element als Pivot-Element
14.2.2. Vorgehensweise
14.2.2.1. 1. Wir haben eine unsortierte Liste und suchen uns ein Pivotelement aus (meistens den Median)
14.2.2.2. 2. Das ausgewählte Pivotelement packen wir in die Mitte und alle kleineren Zahlen der Liste wandern auf die linke Seite und alle Größeren auf die rechte Seite des Pivotelements
14.2.2.3. 3. Wir suchen uns sowohl für die linke als auch die rechte Seite erneut ein Pivotelement aus und gehen erneut so vor, dass alle Kleineren nach links und alle Größeren nach rechts wandern.
14.2.2.4. 4. Das Verfahren machen wir solange bis die finale Liste wieder richtig sortiert ist
14.3. Bubble-Sort
14.3.1. Laufzeitkomplexität
14.3.1.1. Average- und Worst Case: O(n^2) Best Case: O(n)
14.3.2. Vorgehensweise
14.3.2.1. 1. Wir haben eine unsortierte Liste und gucken uns die ersten beiden Zahlen an
14.3.2.2. 2. Wir vergleichen die ersten beiden Zahlen miteinander und schreiben die Kleinere nach links und die Größere nach rechts
14.3.2.3. 4. Wir machen so viele Durchläufe bis die Liste am Ende sortiert ist
14.3.2.4. 3. Dann vergleichen wir die Zweite mit der Dritten und gehen nach dem selben Prinzip vor bis wir am Ende sind
14.4. Selection-Sort
14.4.1. Laufzeitkomplexität
14.4.1.1. Keine Unterschiede: Im Best- und Worst Case -> O(n^2), weil man immer strikt von vorne bis hinten durcharbeitet
14.4.2. Vorgehensweise
14.4.2.1. 1. Wir haben eine unsortierte Liste und picken uns im ersten Schritt die kleinste Zahl aus
14.4.2.2. 2. Die kleinste Zahl tauschen wir mit der ersten Zahl der Reihe und müssen sie im weiteren Verlauf nicht mehr beachten
14.4.2.3. 3. Jetzt gucken wir uns die restliche Reihe an und picken die zweitkleinste Zahl, um sie an die zweite Stelle der Reihe zu platzieren
14.4.2.4. 4. Diesen Vorgang machen wir solange bis wir eine sortierte Liste haben
14.5. Insertion-Sort
14.5.1. Laufzeitkomplexität
14.5.1.1. Average- und Worst- Case: O(n^2) Best Case: O(n)
14.5.2. Vorgehensweise
14.5.2.1. 1. Wir haben eine unsortierte Liste und legen die erste Zahl der Reihe als bereits sortiertes Element fest
14.5.2.2. 2. Wir gucken uns die zweite Zahl der Reihe an und verschieben sie nach links, falls sie kleiner als das erste Element ist bzw. lassen sie stehen, wenn sie größer ist
14.5.2.3. 3. Dann gucken wir uns die dritte Zahl an und vergleichen sie mit den beiden vorherigen Elementen. Wenn sie kleiner als die Zweite, jedoch größer als die Erste ist, packen wir sie entsprechend in die Mitte von den beiden
14.5.2.4. 4. Wir vergleichen solange die Zahlen mit den Vorgängern und verschieben sie solange an die richtigen Stellen, bis die Liste vollständig sortiert ist
15. Mitschriften
15.1. Rekursion
15.1.1. Was sind Bestandteile einer Rekursiven Funktion?
15.1.1.1. Abbruchbedingung zur Beendigung der Rekursionsaufrufe
15.1.1.2. wiederholter Funktionsaufruf der selben Methode mit veränderten Parametern
15.1.2. Warum muss man eine Rekursion in Erwägung ziehen?
15.1.2.1. Rekursive Lösungen sind immer dann in Erwägung zu ziehen, wenn die Aufgabenstellung bereits rekursive Elemente ausweist, und zu vermeiden, wenn es eine offensichtliche iterative Lösung gibt
15.2. Suchen
15.2.1. Lineare Suche
15.2.1.1. Was ist Vorteil und Nachteil von Lineare Suche?
15.2.1.1.1. Vorteil: man muss nur einmal sortieren
15.2.1.1.2. Nachteil: suche nach der richtigen Zahl kostet viel Zeit
15.2.2. Binäre Suche
15.2.2.1. Nach welchem Prinzip arbeitet die Binäre Suche?
15.2.2.1.1. arbeitet nach dem Prinzip "teile und herrsche"
15.2.2.1.2. funktioniert nur auf sortierten Reihungen
15.2.3. Beliebte Klausurenfrage
15.2.3.1. Auf welchem Algorithmus basiert die Methode "teile und herrsche"?
15.2.3.1.1. Binäre Suche
15.3. Heaps
15.3.1. Konzeptionelle Darstellung wird abgefragt und nicht die Codierung