• Administrativa
• Einleitung
  • Es geht um Daten: wie man sie darstellt, manipuliert, auf sie zugreift und sie speichert?
• Einführendes Beispiel: Polynome
  • Darstellung eines Polynoms vom Grad n als Koeffizientenform
    • Addition zweier Polynome in O(n) Operationen
    • Multiplikation zweier Polynome in O(n^2) Operationen
    • Auswerten an einer Stelle x0 (naiv) in O(n^2) Operationen 

• Einführendes Beispiel: Polynome
  • Darstellung eines Polynoms vom Grad n als Koeffizientenform
    • Auswerten an einer Stelle x0 in O(n) Operationen mit dem Horner Schema
  • Darstellung eines Polynoms vom Grad n durch Auswertung an mindestens n+1 verschiedenen Stellen
    • Addition zweier Polynome in O(n) Operationen
    • Auswerten an einer Stelle z in O(n^2) Operationen durch Polynominterpolation (z.B., Newton oder Lagrange Interpolation)
    • Multiplikation zweier Polynome in O(n) Operationen
  • Durch geschickte Wahl der Stellen kommt man von der Koeffizienten- zur Wertedarstellung mit O(n log n) Operationen (schnelle Fourier Transformation, FFT)
  • FFT ist einer der wichtigsten Algorithmen überhaupt, mit Anwendungen in der Signalverarbeitung, der Datenkompression, für schnelle Quantenalgorithmen zur Faktorisierung von großen Zahlen uvam; siehe dazu auch Seite 27ff des MafI2 Skripts oder z.B. auch hier.

• Abschluss Polynome und FFT
• Rekursionsgleichungen und Rekursionsbäume

• Algorithmen: Definition und Qualitätsmerkmale
• Arten der Evaluation von Algorithmen: experimentell und theoretisch
• Experimentelle Analyse (Testen/Benchmarking): sehr konkrete Ergebnisse, aber problematisch.
• Theoretische Analyse: liefert leicht vergleichbare und allgemeine Aussagen, ist oft mit geringerem Aufwand verbunden als experimentelle Analyse, kann aber auch wesentliche Aspekte vernachlässigen.
• Theoretische Analyse benötigt ein abstraktes Maschinenmodell, um die erlaubten elementaren Schritte festzulegen.
• Definition Registermaschine/Random Access Machine (RAM)
• Definition: Laufzeit und Speicherplatz auf der RAM
• Programmierung und Laufzeitbestimmung auf der RAM sind anstrengend, also: Pseudocode,
• O-Notation und asymptotische Analyse, um von konstanten Faktoren und Termen niedriger Ordnung zu abstrahieren (Achtung: kann manchmal irreführend sein)

• O-Notation: Definitionen und Eigenschaften
• Analyse rekursiver Algorithmen
  • Abschaetzung mittels Rekursionsbaum oder mehrfachem Einsetzen
  • Beweis der Abschaetzung durch Induktion
  • Merge sort als Beispiel

• Rekursion: Die Fibonacci-Zahlen
  • Analyse und effizientere Variante
• Einfache Datenstrukturen: Stapel und Schlange
  • Implementierungen als Array fester Grösse und als verkettete Liste

• Amortisierte Laufzeitanalyse
  • Buchhaltermethode
  • Beispiele: Dynmaisches Array (nur Vergroessern), Binaerzaehler mit Inkrement
• Definition ADT
• Spezifikation Prioritaetswarteschlange und moegliche Implemetierungen

• Implemetierung und Laufzeitanalyse von Prioritaetswarteschlangen mittels
  • verketteten Listen mit "zweiI Ebenen"
  • binaeren Heaps

• Bottom-up Aufbau eines binaeren Heaps
• ADT Woerterbuch
  • Hashfunktionen
  • Kollisionen und moegliche Behandlungsstrategien

• Beispiele fuer Kompressionsfunktionen
• Kollisionsbehandlung mittels
  • Verkettung
  • linearem Sondieren

• Kuckuckshashing
• Hashfunktionen fuer "Fingerprinting"

• Kryptographisches Hashing, Hashzeiger
• ADT geordnetes Woerterbuch
  • Spezifikation Skipliste

• Erwartete Laufzeitanalyze von Skiplisten
• Spezifikation Binaere Suchbaeume

• Implementierung binaerer Suchbaeume
• hoehenbalancierte binaere Suchbaeume
  • Definition und Hoehen-/Laufzeitanalyse von AVL-Baeumen

• Rotationen an BSBs (AVL-Baeume als Beispiel)
• Red-Black-Baeume

• (a,b)-Baeume
  • Definition
  • Einfuegen
  • Loeschen (wird naechste Vorlesung wiederholt)

• Wiederholung Loeschen in (a,b)-Baeumen
• Zeichenketten
• Codes, praefix(freie) Codes, optimale praefix(freie) Codes

• Algorithmus zur Erstellung von Huffman Codes (de facto Definition)
• Beweis der Optimalitaet von Huffman Codes

• Fortsetzung des Beweises zur Optimalitaet von Huffman-Codes
• laengste gemeinsame Teilfolgen

• kurze Fortsetzung zu laengsten gemeinsamen Teilfolgen
• Rabin-Karp-Algorithmus

• kurze Fortsetzung und Korrekturen zum Rabin-Karp-Algorithmus
• (PATRICIA) Tries, Suffixbaeume

• Komprimierte Tries
• Objektorientierte Programmierung: Motivation, Beispiel

• Objektorientiere Programmierung: Klassenvariablen/statische Methoden, Kapselung, Vererbung

• Objektorientiere Programmierung: Beispiel in Java
• Graphen

• Graphen: Adjazenliste und Adjazenzmatrix
• Tiefensuche und Breitensuche

• kürzeste Wege in Graphen
• Algorithmus von Dijkstra

Algorithmus von Dijkstra: Korrektheit 

A*-Suche: Dijkstras Algorithmus mit Heuristik

Der Algorithmus von Bellmam-Ford

Kürzeste aufspannemde Bäume 

Komplexitätstheorie: Die Komplexitätsklassen P und NP

NP-vollständige Probleme: Definition und Beispiele