AlgoDat SoSe21

Notizen zu den Vorlesungen

Zusammenfassung Grundlagen

• Probleme und Instanzen
• Algorithmen
  • Definition
  • Darstellungen (Prosa, Pseudocode, Programmcode)
  • Eigenschaften
• Grundlegende Datenstrukturen
  • Arrays
  • Listen
    • Stacks
    • Queues
• Bäume
  • Eigenschaften
  • Binärbäume
  • Traversierungen
  • Heaps

Video 3

• Queues:

  • Spezifikation

    • Wie Liste: sequentielle Ordnung, aber: mit Operationen:
    • Einfügen: nur am Ende anhängen ("enqueue", bei "in")
    • Auslesen; vorderstes Element zurückgeben ("dequeue", bei "out")
    • FIFO-Prinzip ("First-In-First-Out")

  • Versuch: Queue als zyklisches (lin.)Array:

    • belegter Bereich wandert von vorne nach hinten (FIFO)
    • am letzten Platz angekommen → durch auslesen ist vorne wieder Platz:
    • Aber: verschieben ist zu teuer

  • Lösungsansatz: "zyklisches Array"

    • Verbinde Ende mit Anfang
    • Ringschluss durch Modulo-Funktion:

  • Eigenschaften:

    • kein Speicher für Pointer benöt.
    • leere Elemente (Speicherplatzverlust)
    • beschränkte Länge

  • (Priority Queue):

    • Charakterisierung: Elemente mit Prioritätswerten
    • für Algorithmen mit "Bestensuche", Bsp.: searchShortestPath
    • statt FIFO(push-pop) und LIFO(enqueue-dequeue)
    • Operationen: Insert,GetMin
    • Bem.: prio kann minimum oder maximum sein,meist durch Heap implementiert.

• Bäume:

  • erweitertes Listen Konzept erlaubt mehrere Nachfolger
  • Relationen in Bäumen def. eine Hierarchie
  • Terminologie für Bäume:
    • Pfad: Folge von Knoten, die durch Kanten direkt verbunden sind
    • Pfadlänge: Anzahl der Kanten eines Pfades („Kantenlänge“)
    • Grad eines Knotens: Anzahl der unmittelbaren Nachfolger
    • Verzweigungsgrad eines Baums: Maximum aller Knotengrade
    • Kantenmaximalität: Ein Baum mit 𝑛𝑛 Knoten hat genau $𝑛 − 1$ Kanten
      • Entfernt man eine Kante → nicht mehr zusammenhängend
      • Fügt man eine Kante hinzu → nicht mehr zyklenfrei
    • Vollständiger Baum: Jeder Knoten hat max. Grad.
    • Höhe: Länge des längsten Pfads von Wurzel zu einem Blatt. (Anzahl Kanten/Knoten)

  Für einen Binärbaum $𝑡𝑡$ der Höhe $ℎ$ gilt:

  i. 𝑡 hat maximal 2ℎ+1 − 1 Knoten.
  ii. 𝑡 hat mindestens ℎ + 1 Knoten
  iii. 𝑡 hat maximal 2ℎ − 1 innere Knoten.
  iv. 𝑡 hat maximal 2ℎ Blätter 
  

  Beweis durch Induktion (siehe Material)

  • Baumdarstellungen: Bsp.:
  • $[37, 18, 42, 11, 23, 39, 45, 10, 17, 19, 32, 38]$
  • $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]$
  • Ein Baum kann in einem ArrayGespeichert werden(von Wurzel beginn)
  • Kinder von Knoten 𝑖:
    • $𝑖2, (i2)-1$
  • Vorgänger Knoten $𝑖$
    • $[𝑖/2]$
  • Knoten $\frac{𝑛}{2} < 𝑖 ≤ 𝑛$ sind Blätter, da Knoten $2𝑖 > 𝑛$ nicht existieren

• Baumtraversierung:

• Tiefendurchlauf, Preorder/Präfix, Postorder/Postfix, Inorder/Infix, Breitendurchlauf

• Infix nur auf BinTree gebräuchlich.

Video 4

Komplexität

Zusammenfassung:

• Analyse des Ressourcenverbrauchs von Algorithmen (Laufzeit, Speicherbedarf) nicht im Detail, sondern als Kopmlexitätsklasse

• Dazu O-Notation als obere Schranke

• Analyse von Algorithmen geht direkt für einfache Anweisungen und Schleifen

• Für rekursive Funktionen schwieriger:

  • sukzessives Einsetzen
  • Mastertheoreme!
  • Substitution

• Effektivität

  • Algorithmus liefert die gewünschten Ergebnisse \arrow "die Richtigen Dinge tun", das Ziel wird erreicht.

• Effizienz

  • Ressourcenverbrauch $\rightarrow$ nicht zu viel Aufwand… (Effizienzfaktoren: Laufzeit, Speicher(in/ext), Kommunikation(Netzwerk,IO), Energie etc.)
  • konkrete Laufzeit viele Faktoren (CPUTakt, Input-Länge, implem. der Basisoperationen (ARM, x86?))

• Komplexität

  • Abhängig von Eingabedaten
  • abstrakte Rechenzeit $𝑇(𝑛)$ abhängig von $n$

  Problem	$T(n)$
  Suchen einer $n$-elementiger Menge	Vergleiche zu durchlaufeneder Knoten
  Sortieren einer $𝑛$-elementigen Liste	Vertauschungen/Vergleiche
  Auswertung einer rekursiven Funktion $𝑓(𝑛)$	Funktionsaufrufe
  Finden aller Primzahlen bis $𝑛$	Rechenoperationen
  Matrixmultiplikation $ℝ^𝑚×𝑘 ⋅ ℝ^𝑘×𝑛$	Skalare Multiplikationen

• üblicherweise Asymptotische Betrachtung

• Laufzeiten-Verhalten $T(n)$ für sehr große Eingaben $𝑛 ∈ ℕ$:

  • Maß an Komplexität soll unabhängig von konstanten Faktoren/Summanden sein.
  • Rechnergeschwindigkeit, Aufwände für Initialisierung etc. sollen ausgeklammert werden.

• Formal:

  • O-Notation $𝑂(𝑓)= { 𝑔 : ℝ → ℝ ∣ ∃𝑐 > 0: ∃𝑥~0~ > 0: \forall𝑥 ≥ 𝑥~0~: 𝑔(𝑥 ) ≤ 𝑐 ⋅ 𝑓(𝑛) }$

• Informatik: diskrete Eingaben aus ℕ: $𝑂(𝑓 ) = { 𝑔 : ℕ → ℝ ∣ ∃𝑐 > 0: ∃𝑛~0~ > 0: \forall𝑛 ≥ 𝑛~0~: |𝑔(𝑛 )| ≤ 𝑐 ⋅ |𝑓(𝑛)| }$

  • Sprechweise: $ƒ$ ist obere Schranke von $𝑔$ $𝑔$ wächst höchstens so schnell wie $𝑂(ƒ)$

• O-Notation Rechenregeln:

• Konstanten:

  • sei $g(x) = a ∈ ℝ$ eine konstante Funktion, so gilt: $g ∈ O(1)$
  • Beweis: $c ≥ a (c = a +1)$, dann gilt für alle $x ∈ ℝ: |g(x)| = a ≤ c * 1$
  • Bsp.: $3, 10000, O(\sqrt{313,56}) = O(1) = O(π) ∈ O(1)$

• Skalare Multiplikation:

  • sei $g ∈ O(ƒ)$ und $a ∈ ℝ$, so gilt: $a * g ∈ O(ƒ)$
  • Beweis: Es gibt $c > 0$ und $x_{0} > 0$, sodass für alle $x ≥ x_{0}$ gilt: $|g(x)| ≤ c * |ƒ(x)|$ Für $c' = c * |a|$ gilt dann auch: $|a * g(x)| ≤ c' * |ƒ(x)|$
  • Bsp.:
    • $100n ∈ O(n)$
    • $32n^{5} ∈ O(23n^{5}) = O(n)$
    • $2^{n+a} = 2^{a} * 2^{n} \in O(2^{n})$
    • $O(log\ n) = O(ln\ n) = O(log_{2}\ n)$

• Addition:

  • sei $g_{1} ∈ O(ƒ_{1})$ und $g_{2} ∈ O(ƒ_{2})$, so gilt:
  • $g_{1} + g_{2} ∈ O(max(ƒ_{1},ƒ_{2}))$
  • Beweis: siehe Folien
  • Bsp.:
    • $23n^{5} + 2n^{4} + 56n^{3} ∈ O(n^{5})$

Multiplikation:-

• Komplexitätsklassen

• sei n die Länge der Eingabe (z.B. Arraylänge/stringl)

• Beziehungen zwischen Komplexitätsklassen:

  • Komplexität definiert eine totale Ordnung auf reelenFunktionen von reellen Zahlen, z.B.:
    • $O(1) ⊆ O(log\ n) ⊆ O(n) ⊆ O(n * log\ n) ⊆ O(n^{2}) ⊆ O(n^{3})$
  • alle Potenzen von n bzgl. des Exponenten geordnet:
    • $\forall a ≤ b: n^{a} ∈ O(n^{b})$
  • Logarithmen mit unterschiedlichen Basen fallen in die gleiche Klasse:
    • $\forall a,b >1: O(log_{a}n) = O(log_b{n})$
  • Logarithmus wächst langsamer als jede Potenz:
    • $\forall a > 0: log n ∈ O(n^{a})$
    • $\forall a > 0: n^{a} ∉ O(log n)$
  • Exponentialfunktionen wachsen superpolynomiell:
    • $\forall a > 1: n^{a} ∈ O(b^{n})$
    • $\forall b > 1: b^{n} ∉ O(n^{a})$

• Anwendung auf Algorithmen:

  • elementare Anweisungen $\rightarrow O(1)$
    • var Deklaration (String str), Initialisierung und Zuweisungen (int i = j+1), Vergleiche (if j == 3)..
  • Laufzeiten von Sequenzen von Anweisungen werden addiert
    • im Algemeinen einfach mehrere Codzeilen Anweisungen...
  • Bei Sequenzen und Verzweigungen wird addiert $O(ƒ) + O(g)$
    • Folge von Anweisungen: x = 0; y = 0; z = 0
    • Bedingte Anweisungen: if(a%2 == 0) a = /2; else a++
    • Fallunterscheidung: switch(n) case: … break
  • Schleifen werden multipliziert:
    • Wenn Anzahl der Schleifendurchläufe durch $O(ƒ)$ nicht beschränkt ist und der Schleifenrumpf maximal den Aufwand $O(g)$ hat, dann ist die Komplexitätsklasse der Schleife $O(f\ g)$…
    • for(int i…){for(int j…){…} } $\rightarrow O(n) * O(n) = O(n^{2})$

• Iteration vs. Rekursion

  • Vergleich
    • Rekursive Formulierung oft eleganter
    • Iterative Lösung oft effizienter aber komplizierter
  • Äquivalenz der Programmierprinzipen
    • Jede rekursive Lösung iterativ(d.h. mit Schleifen) lösbar und umgekehrt
    • Rekursion lässt sich in Spezialfällen automatisiert auflösen
      • endständige Rekursion

• Zusammenfassung Kopmlexität

  • Analyse der Resourcenverbrauchs con Algorithmen (Laufzeit, Speicherbedarf) nicht im Detail sondern Komplexitätsklasse
  • Dazu O-Notation als obere Schranken
  • Analyse von Algorithmen geht direkt für einfache Anweisungen und Schleifen
  • Für rekursive Funktionen schwieriger:
    • Sukzessives Einsetzen
    • Mastertheoreme
    • Substitution