Literatur: Aus der umfangreichen Literatur
zu diesem Thema sind hier zwei Beispiele.
Combinatorial Optimization (Algorithms and Complexity)
(Dover) von Christos H. Papadimitriou und Kenneth Steiglitz
Flows in Networks (Princeton University Press) von L.R. Ford und D.R. Fulkerson
Zum Inhalt der Vorlesung:
In der Vorlesung wurden kombinatorische Algorithmen zur Lösung von
Optimierungsproblemen behandelt. Als Beispiele seien erwähnt: De Brujin
Folgen; kürzeste Wege in Graphen; minimale aufspannende Bäume;
Sheriff-Problem; optimale Matchings; Flüsse in Netzwerken; 0-1-Matrizen.
Ein paar Algorithmen wurden in der Programmiersprache PROLOG ausgeführt.
Als Einführung in PROLOG kann ich das Buch
Prolog Programming in Depth (Prentice Hall) von Michael A. Covington
und Donald Nute sehr empfehlen.
lib.pl ist die Library.
pantheon.pl beinhaltet die Verwandtschaftsbeziehungen der griechischen Götterwelt.
DeBrujin.pl generiert De Brujin - Sequenzen für k=2 bis etwa k=10 (für grössere k's dauert's dann ziemlich lange).
FloydWarshall.pl berechnet mit dem Floyd-Warshall Algorithmus die Länge der kürzesten Bahn zwischen allen Punktepaaren in einem Graphen.
GaleRyser.pl produziert mit dem Ford-Fulkerson Algorithmus eine 5x5 Matrix mit Einträgen 0 und 1, so dass die Zeilensummen 5,3,3,2,2, und die Spaltensummen 4,4,4,2,1 ergeben. Um eine 0-1-Matrix bezüglich anderen Partitionen zu erhalten, muss das Programm geändert werden.
Viel Spass bei PROLOG!