ALGOS UND DATA STRUCTURES.txt

1 Algorythmen und Datenstrukturen leichte erklärt
    Bespiele für Algorythmen:
    Sortieren
    YouTube-Empfehlungen
    Google-Suche
    NPCs in Games
    Routenplanung
    News-Feed

2 Bedigungen und erste Beispiele
    Berechnung A mit 3 Bedinungen
        falls X gilt dann Berechnung B
        falls Y gilt dann Berechnung B'
        sonst dann Berechnung B''
    Beispiel:
        Algo Sortiere_Zwei_Werte: (Wert_A, Wert_B)
        Falls Wert_A < Wert_B: Klein<-Wert_A, Groß<-Wert_B
        Falls Wert_A >= Wert_B: Klein<-Wert_B, Groß<-Wert_A
        Ergebnis Klein, Groß

3 Algorithmisches Denken und Schleifen
    Algorithmus "Spiel"
    Solange wir im Spiel sind
        Leertaste => Springen
        Rechts Pfeil => nach Rechts laufen
    Schleife springt zurück zu Solange

4 Datenstrukturen einfach erklärt
    langsame und schnelle Datenstrukturen
    z.B. Array, Linked List, Queues, Map, Set, Graph, Baum

5 Laufzeitanalyse / Landau Notation / O-Notation
    O(n) jedes Element wird 1x angegriffen (von oben nach unten)
        => z.B. wenn ein bestimmtes Element gesucht wird
    O(n²) jedes Mal alle Element anfassen wenn ein Element gesucht wird
        => z.B. bei Elementvergleichen
    O(1) Direktzugriff
        => das 26. Element lesen

6 Array
    praktisch in allen Programmiersprachen       
    grundsätzlich sehr unflexibel beim verändern
    schnell: direkter Zugriff auf Element x
    langsam: einfügen, suchen, löschen

7 Linked List
    Jedes Element zeigt zum nächsten
    Einfügen/Löschen von Elementen sehr schnell (im Gegensatz z.b. zu Arrays)
    Zugriff und Suchen sehr langsam (es müssen alle Elemente angefasst werden
    => vor allem geeignet wenn viel angepasst wird - wenig gelesen
    Doubled Linked List => kennen nicht nur Nachfolger sondern auch den Vorgänger des Elements

8 Queues / FIFO First In First Out
    nur 2 Funktionen - ist wie eine Warteschlange
    Push => Element an der ersten Stelle einfügen
    Pop => letztes Element abschneiden
    Stack / LIFO Last In First Out
    Push / Pop bezieht sich immer auf das letzte Element
    Einfügen / Löschen => Schnell
    Zugriff / Suchen => Langsam
    
9 Sets
    Elemente im Set sind einzigartig - keine doppelten Elemente möglich

10 Maps / HashMaps
    Immer Zuordnung von Schlüssel zu Wert
    Zuweisung zwischen Schlüssel und Wert erfolgt mittels Hashfunktion h

11 Die Binäre Suche
    Sortierte Liste wird dafür benötigt
    Liste wird geteilt und geschaut ob gesuchtes Element links oder rechts der Mitte ist
    Dann wird der jeweilige Teil genommen usw. bis die gesuchte Zahl gefunden wird

12 Binäre Suche in Python
    siehe BinarySearch.py

13 Selection Sort
    Z.b. um eine Liste zu sortieren
    Kleinstes Element wird ganz vorne eingefügt und getauscht
    Danch wird das kleinste Element ab dem zweiten gesucht und so weiter
    Komplexität: O(n²) - ist nicht gut für einen Sortieralgorythmus
    Sortierung erfolgt InPlace - Sortierung innerhalb eines Arrays möglich - braucht wenig Speicher

14 Selection Sort in Python
    siehe SelectionSort.py

15 Insertion Sort
    Algo bildet neue (sortierte Liste)
    Erstes Element bleibt gleich
    nächste Element wenn kleiner wird als erstes eingefügt
    drittes Element wird dann wieder entsprechend eingeordnet
    => jedes mal muss die gesamte Ergebnisliste durchlaufen werden
    => Sortierung nicht in place (zweite Ergebnisliste wird benötigt)

16 Insertin Sort in Python
    siehe InsertionSort.py

17 Bubble Sort
    vergleicht erste beiden Elemente und werden bei Bedarf vertauscht
    nächsten beiden Elemente werden verglichen und bei Bedarf vertauscht
    nach einem Lauf steht der größte Werte ganz hinten - muss nicht mehr angegriffen werden
    nach jedem Lauf ist dann an der letzten Stelle ein Wert dazugekommen sortiert
    => inPlace (keine zweite Ergebnisliste benötigt)

18 Bubble Sort in Python
    siehe BubbleSort.py

19 Brute Force Algorythmen
    es wird komplett alles ausprobiert (mit "brutaler Gewalt")
    z.B. ein Sudoko komplett lösen - alles ausprobieren
    z.b. Hashcracken, Sudoko, Passwörter cracken

20 Divide and Conquer Verfahren
    Aufteilung einer Kette in kleinere Teile und dort den Algorythmus anwenden
    und am Ende die einzelnen Teile dann zusammenführen

21 Merge Sort - Rekursives Divide und Conquer
    Teile der Liste auf 2 Teile
    Nochmal teilen bis keine Teilung mehr möglich ist (2 Elemente)
    dann werden die einzelnen Teile sortiert
    dann werden die einzuelne Teile wieder zusammengefügt und dabei immer sortiert
    (dabei muss immer nur der erste Buchstabe beider Teile überprüft werden)
    => Aufteilung erfolgt sehr schnell - log(n) mal
    => Zusmamenfügen und währendessen Sortieren

22 Merge Sort - in Python
    siehe MergeSort.py

23 Quick Sort
    => weiterer Divide and Conquer Algorythmus
    Sortierung anhand eines Pivot-Elements
    Implementierung jetzt mit rechts Element ist immer das Pivot-Element
    Ist High < als Pivot? => wenn nicht wird high 1 nach links geschoben
    Elemente die < als Pivot sind kommen in den linken Teil - wenn die > sind in den rechten Teil
    Pivot-Elemetn kommt dann in die Mitte => links sind alle Elemtne die < Pivot sind - recht die > sind
    Auf die Teilisten wird dann wieder der Quicksort angewandt => rechts Element wird Pivot usw.

24 Quick Sort - in Python
    siehe QuickSort.py

25 Bogo Sort
    auch bekannt als Stupid Sort
    Liste wird so zufällig zusammengewürfelt bis das Ergebnis sortiert ist

26 Big O Notation visualisiert
    Laufzeit steigt generell linear bei O(n)
    (n sind die Elemente)
    n^n => N³ => n² => n => log(n)
    (n ist realistische Laufzeit - log(n) ist das was man anstrebt - Rest zu langsam)

27 Notationen - Deta und Omega
    Omega-Notation - Funktion wächst schneller oder mind. gleich
    Deta-Notation - wächst exakt so wie sie angegeben ist

28 Korrektheitsbeweise Empirisch
    empirisch = "auf Erfahrung basierend"
    stichprobenartig test (wie bei einem Unittest)
    z.b. find_max([0,1,2,3,4,5]) == 5
    es können damit aber nur Fehler gefunden werdne - es kann aber nicht bewiesen werden, das der
    Algroryhtmus 100% funktioniert (weil es immer neue Kombinationen gibt - weil unendliche Kombinationen)

29 Korrektheitsbeweis Mathematisch
    Startbedingung und Invariante
    Startbedingung gibt Voraussetzung an: z.B. jedes Element muss >= -1 sein
    Invariante 1: {0,i-1}: list[j] <= max (aktuelles max)
    Invariante 2: {0,i-1}: max aus list[0:j]
    Induktsionsanfang: j=0: list[j] <= max => list[0] >= -1
    Induktsionschritt: j=>j+1

30 Graphen - Einführung
    Bahnnetz, Google, Netzwerk, Socialplan, Logistikunternehmen, Beziehnungen
    Einzelne Punkte heißen Knoten
    Verbindungen werden Kanten genannt
    Pfeilspitze gibt Richtung vor
    gerichteter Graph: z.b. nur eine Richtung der Beziehung
    ungerichteter Graph: z.B. Facebook-Freundschaft
    bi-direktonialer Graph: z.B. Zug fährt in beide Richtungen
    zyklische Graphen: es gibt die Möglichekeit "im Kreis zu laufen" (normalerweise sind immer Zyklen vorhanden)
    azyklische Graphen: man kann nicht mehr zu einem Knoten zurückkehren (Endlos nicht möglich)
    self-loop: Schleife auf dem Graphen selbst - macht eher wenig Sinn - z.B. man fährt von Wien nach Wien

31 Knotengrade
    Die Anzahl der Aus- und Eingänge pro Knotenpunkt ist der Knotengrad
    self-loop zählt 2x (1x eingehend und 1x ausgehend)

32 Pfade
    walk => Folge von Kanten (Kanten können auch wiederholt werden)
    z.B. Freiburg nach Berlin, welche Straßen nehmen
    trail => eine Folge von Kanten - aber ohne doppelte Kanten
    path => eine Folge von Kanten - ohne doppelten Knoten

33 Gewichtete Graphen
    jede Kante zeigt wie lange etwas dauert - z.B. von Stadt Stadt x Stunden
    manche Kanten können auch negative Gewichte haben
    (z.B. Operation A - dann Operation B - und dann irgenetwas was die Laufzeit verbessert)
    (das erste kostet 3 Euro, das zweite kostet 5 Euro - und danach immer 1 Euro zurück)

34 Teilgraphen
    Teilgraph
    induzierter Teilgraph (auch Untergraph)
    => nur Knoten werden entfernt und all deren Kanten
    spannender Teilgraph
    => alle Knoten bleiben erhalten  - alle Knoten sind zusammenhängend

35 Bäume
    sind spezielle Graphen
    Wurzel => Element ganz oben
    Kante => Verbindungen zwischen Knoten
    innerer Knoten => Knoten zwischen Wurzel und Blättern
    Blatt => Knoten der ganz unten ist
    In der Informatik arbeitet man normalerweise nur mit Binärbäumen (1 Knoten hat nur max. 2 Kanten nach unten)
    Einzelne Ebenen werden als "Niveau" bezeichnet
    z.B. Computerspiele mit Entscheidungen

36 Gerichtete Graphen auf Zyklen prüfen
    is_dag(G = (V,E)):       => G ist der Graph, V ist Menge aus Knoten und E sind die Kanten
    Schleife mit: solange es noch einen Knoten gibt der keine ausgehenden Kanten hat (egal welcher Knoten genommen wird)
        Knoten wird entfernt aus der Gesamtmenge
        Entfernen aller Kanten von diesem Knoten egal wohin sie gehen
    Anzahl der übriggebliebene Knoten wird ausgegeben (wenn nicht mehr überig bleibt
    => gerichteter, azyklischer Graph wenn 0 Knoten übrig bleiben - sonst ist er ein gerichteter, zyklischer Graph

37 Breitensuche
    jeder Knote soll 1x gesucht werden - den Graphen der Reihe nach durchgehen
    3 Listen / Arrays : Visited / Queue / Ausgabe
    Visited => Übersicht der besuchten Knoten
    Queue => welche Knoten noch angeschaut werden muss
    Ausgabe => Ergebnisse
    Knoten wird genommen - alle Kanten die weggehen kommen in Queue und werden in Visited auf 1 gesetzt
    Knoten werden aufsteigend nummeriert
    Anwendungsbeispiele: P2P Nachbarknoten, Suchmaschinen Crawler, Broadcasting in Netztwerken

38 Graph Breitensuche in Python
    siehe Graph Breitensuche.py

39 Tiefensuche
    3 Listen / Arrays : Visited / Stack / Ausgabe (Stack ist der Unterscheid zu der Queue bei der Bereitensuche)
    Beginnt bei Knoten 0
    Man geht einer Kante entlang und nimmt den nächsten Knoten (z.B. 1)
    Immer das neueste / letzte Element wird als erstes bearbeitet
    Wenn von einem Knoten nicht mehr mit einer Kante zu einem anderen Knoten gegangen werden kann
    => Knoten wird aus dem Stack entfernt
    Anwendungsbeispiel: Labyrinthe lösen, Sortierungen, Min-Spanning Trees

40 Tiefensuche in Python
    siehe Graph Tiefensuche.py

41 Tiefensuche im Labyrinth mit Turtle
    siehe Laby.py

42 Greedy Algorithmen
    Das Death Stranding Problem
    (Rucksack möglichst effizient einpacken)
    "Wir nehme das was am meisten bringt und packen das ein"

43 Dijkstra Algortihmus
    Algo für gewichtete Graphen der den kürzesten / günstigsten Weg findet
    Jede Kante hat ein "Gewicht" (Kosten, Stunde, usw.)
    Algo funktioniert nur bei positiven Gewichten - bei einem negativen Wert funktioniert es nicht
    Start bei Knoten A - B und C werden durch die Kosten ersetzt - sucht den nächst günstigsten Weg
    wenn es schnelleren Weg gibt => den bestimmten Knoten updaten
    fixierte Knoten werden nicht mehr angegriffen
    Am Ende steht dann in jedem Knoten wieviel der Weg kostet

44 Dijkstra Algorithmus in Python
    siehe Dijkstra.py

45 Bellmann Ford Algorithmus
    selbes Ziel wie Dijkstra
    funktoniert aber auch mit negativen Kantenwerten
    (Dijkstra hat den Nachteil das er nur mit positiven Kanten umgehen kann)
    läuft aber etwas länger (daher Dijkstra bei pos. Kantenwerten anwenden) - sonst Bellmann Ford Algo verwenden
    => (1) alle Kantengewichte auf unendlich-Wert setzen
    => alle Knoten müssen Anzahl-Knoten minus 1 durchlaufen werden
    => funktiniert für neg. Kanten - aber bei negativen Zyklen funktioniert es nicht - weil diese würde unendlich
    weitergehen und das Ergebnis unendlich Minus machen
    => dadurch ist eine ergänzende Abbruchbedingung notwendig: es wird noch einmal zum Abschluß alle Knoten durch-
    gegangen - wenn es dann noch immer einen Wert gibt der sich ändert (=negativer Zyklus), dann kann es für diese
    Graphen kein Ergebnis geben

46 Bellmann Ford Algo in Python
    siehe Bellmann.py

47 Minimum Spanning Trees
    Kruskals MST Algorithmus
    baut Teilgraph auf der nur aus den minimalen Gewichten besteht
    1) Löschen aller Kanten und sortieren nach der Größe
    2) Kleinste Kante wird eingefügt - dann die nächst kleinste Kante - und usw.
    alle Zyklen sind verboten - d.h. wenn bei der Bildung ein Kreislauf entsteht wird die Kante wieder gelöscht
    => Fertig ist, wenn alle Knoten irgendwie verbunden sind (aber ohne Kreislauf bei einem bestimmten Teil)
    Anwendung z.B. bei Stromnetzen - muss nicht der kürzste Weg zwangsläufig sein - aber alle Knoten müssen verbunden sein