geplanter Inhalt der Vorlesung Algorithmen und Programmierung
III
Freie Universität Berlin, Wintersemester 2003/2004, Prof.
Günter Rote
- Algorithmen
- Effizienz von Algorithmen und Datenstrukturen
- Laufzeit und Speicher
- asymptotische Analyse, O-Notation
- Wichtigkeit der Effizienz auch bei leistungsfähigeren
Computern
- Datenstrukturen
- lineare und verkettete Liste (aus ALP2)
- Bitvektor
- Halde
- Suchbaum
- balancierte Bäume: 2-3-Bäume,
Rot-Schwarz-Bäume
- Bäume für externen Speicher: B-Bäume
- digitaler Suchbaum (trie)
- gestreute Speicherung (hashing) (aus ALP2)
- Abstrakte Datentypen
- für Mengen und Listen
- Stapel und Schlange (aus ALP2)
- Prioritätswarteschlange
- Aufzählung, Iterator
- Wörterbuch (Map)
- Relationen, Graphen und Bäume
- geometrische Objekte: Polygone
- Algorithmenentwurfsprinzipien
- Teile und herrsche
- dynamische Programmierung
- der gierige Algorithmus
- backtracking
- plane-sweep
- Sortieralgorithmen
- Sortieren durch Einfügen
- Sortieren durch Auswahl
- Bubblesort
- Quicksort (aus ALP2)
- Sortieren durch Verschmelzen (aus ALP2)
- Sortieren mit einer Halde
- Sortieren mit einem Baum
- Sortieren durch Fachverteilung, Radix-Sort
- sonstige Algorithmen
- Graphenalgorithmen
- topologisches Sortieren
- Suchalgorithmen in Graphenalgorithmen
- Breitensuche
- Tiefensuche
- kürzeste Wege, Algorithmus von Dijkstra
- Problemlösung in der künstlichen Intelligenz
als
Wegesuchproblem
- kürzeste Spannbäume
- Der Algorithmus von Kruskal
- Suchen in Zeichenketten
- Huffman-Codes
- konvexe Hülle
- Streckenschnitt
- alpha-beta-Suche für Spielbäume
- Programmierung
- Ziele bei der Software-Erstellung (Qualitätsmerkmale)
- Wiederverwertbarkeit
- Wartbarkeit
- Zerlegung in übersichtliche Einheiten
- Sicherheit vor Programmierfehlern
- Hilfsmittel
- Abstraktion, Trennung von Schnittstelle und Implementierung
- Modularisierung
- Generizität
- Objektorientierung
- Ausdrucksmittel in Programmiersprachen
- Objekte und Vererbung in Java (ALP2)
- statische Klassenfelder und -methoden
- Polymorphie in Haskell und Java (ALP2)
- Typklassen in Haskell (ALP2)
- Interfaces und abstrakte Klassen in Java (ALP2)
- Collection-Klassen in Java (Set, List, Iterator,
Map)
- generische Klassen in C++ (templates)
- Programmpakete in Java; Zugriffsklassen, kontrollierte
Sichtbarkeit
- Modularisierung in Haskell: expliziter Export und Import
- algebraische Datentypen in Haskell
- dauerhafte Objekte (Persistenz und Serialisierung) in Java
- Spezifikation und Korrektheit
- natürlichsprachliche Spezifikation
- formale Spezifikation
- modellierende Spezifikation
- Abstrakte Datentypen
- abstraktere und konkretere Datentypen,
Abstraktionsfunktion
- Korrektheit von Implementierungen
- algebraische Spezifikation
- Korrektheitsbeweis durch strukturelle Induktion
- funktionale Spezifikation, Haskell als Spezifikationssprache
- Korrektheit von Programmen (aus ALP2)
- Hoare-Kalkül, Vor- und Nachbedingungen,
Schleifeninvarianten (ALP
2)
- dynamische Speicherverwaltung
- stack und heap (Keller und Halde)
- Programmiersprachen mit Speicherfreigabe durch den
Programmierer
(dispose)
- Müllsammlung (garbage collection); Referenzzähler
und
Markierungsmethoden
- Freispeicherorganisation, Fragmentierung