Themenübersicht zu Algorithmen und Programmierung III

Freie Universität Berlin, Wintersemester 2013/2014, Wolfgang Mulzer

Algorithmen
- Grundlagen
  - Maschinenmodell
  - Laufzeit und Speicherbedarf
  - Ansätze zur Algorithmenanalyse
  - O-Notation
  - Lösung von Rekursionsgleichungen
  - Wofür effiziente Algorithmen?
- Datenstrukturen
  - Listen: einfach und doppelt verkettet
  - Bitvektor
  - Halden
  - Suchbäume
    - balanciert: AVL, rot-schwarz, ...
    - extern: B-Bäume, (a,b)-Bäume
    - digital: tries
  - Skip-Listen
  - Hashtabellen
    - Konfliktbehandlung (Chaining, offene Adressierung, Kuckuck)
    - universelles Hashing
- abstrakte Datentypen
  - für Mengen und Listen
    - Stapel, Schlange
    - Prioritätswarteschlange
    - Map, Ordered Map
    - Iteratoren
  - Relationen, Graphen, Bäume
  - geometrische Objekte
- Entwurfsparadigmen
  - Teile und Herrsche
  - dynamisches Programmieren
  - Backtracking
  - gierige Algorithmen
  - Plane-sweep
  - Zufallsalgorithmen
  - amortisierte Analyse
- diverse Algorithmen
  - Graphenalgorithmen
    - Breitensuche, Tiefensuche
    - topologisches Sortieren
    - kürzeste Weg (Dijkstra, Bellman-Ford)
    - minimale aufspannende Bäume
  - Suche in Zeichenketten
  - Huffman-Kompression
  - Spielbäume
  - FFT
Programmierung
- Merkmale guter Software
  - Wiederverwendbarkeit
  - Wartbarkeit
  - Übersichtlichkeit
  - geringe Fehleranfälligkeit
- Hilfsmittel
  - Abstraktion/Geheimnisprinzip
  - Modularisierung
  - Generizität
  - Objektorientierung
- Entwurfsmuster
  - Adapter
  - Iterator
  - Komposition
  - template method
  - Komparator
  - Decorator
- sprachliche Ausdrucksmittel
  - Objekte und Vererbung, Zugriffsmodifizierer
  - Polymorphie
  - Interfaces und abstrakte Klassen
  - Java collections framework
  - Generics in Java
  - Pakete in Java
  - Annotations in Java
  - Persistenz und Serialisierung in Java
  - Module in Haskell
  - algebraische Datentypen in Haskell
- Spezifikation und Korrektheit
  - natürlichsprachliche Spezifikation
  - formale Spezifikation (modellierend/algebraisch/funktional)
  - Hoare-Kalkül
- Speicherverwaltung
  - Keller und Haufen/Halde
  - Speicherverwaltung in C/C++
  - Speicherbereinigung
  - Freispeicherverwaltung/Fragmentierung