geplanter Inhalt der Vorlesung Algorithmen und Programmierung 3

Freie Universität Berlin, Wintersemester 1999/2000, 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 (aus ALP2)
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)

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 (ALP2)
plane-sweep

Sortieralgorithmen

Sortieren durch Einfügen
Sortieren durch Auswahl
Quicksort
Sortieren durch Verschmelzen
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
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
[ alpha-beta-Suche für Spielbäume - nicht gemacht ]

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

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

[ Beweis durch strukturelle Induktion - nicht gemacht ]

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