| Datum: | 2000-04-03 |
|---|---|
| Prüfer: | Waldschmidt |
| Beisitzer: | Guntermann |
| Prüfungsumfang: | GA (4+2), AEA (2+2) |
| Prüfungsdauer: | 60 Minuten |
Prof. Waldschmidt hatte ein Problem vorbereitet und eröffnete mit diesem die Prüfung. Für Notizen lag ein Blatt und ein Stift bereit.
Es sind 5 Sitzungen zu planen, an denen mehrere Personen teilnehmen. Manche Personen nehmen an mehreren Sitzungen teil. Die Frage lautet, ob man mit 3 Terminen auskommt.
Das Problem läßt sich als Graph darstellen: Jede Sitzung wird durch einen Knoten repräsentiert. Zwei Knoten sind miteinander verbunden, wenn eine Person an beiden Sitzungen teilnehmen muß.
Gefragt ist nun, ob man diesen Graph mit 3 Farben färben kann. Wenn eine solche Färbung existiert, reichen 3 Termine.
Welche Darstellungen von Graphen gibt es. Vergleiche diese bezüglich Platzbedarf und Laufzeit.
| Darstellung | Platz | Nachbarschaftstest |
|---|---|---|
| Adjazenzliste | E | O(V) |
| Adjazenzmatrix | V*V | O(1) |
| Inzidenzmatrix | V*E | |
| Implizite Darstellung | V*log V | O(1) |
Die implizite Darstellung ist nur eine Forderung. Wodurch ist diese begründet?
Nicht jede Graphenklasse hat eine implizite Darstellung: Es gibt 2^(V^2) verschiedene Adjazenzmatrizen. Selbst bei einer Numerierung benötigt eine Aufzählung mindestens V^2 Speicherplatz.
Andererseits existiert eine implizite Darstellung für Intervallgraphen: Für jedes Intervall wird sein Start- und Endzeitpunkt notiert. Für jeden Knoten werde 2 Zahlen der Länge log(2n) notiert, insgesammt benötigt man also O(n*log n) Speicherplatz. Der Nachbarschaftstest besteht nur darauf, Start und Ender der beiden Intervall miteinander zu vergleichen: Die beiden Knoten(=Intervalle) sind nicht benachbart, wenn das eine Intervall vollstaendig vor bzw. hinter dem anderen liegt.
Was ist die Modulardarstellung?
Jede Zahl u läßt sich eindeutig bezüglich der Restklassenringe ui darstellen, wenn diese paarweise prim sind und 0≤u≤Prod(ui) ist. Dies wird durch den Chinesischen Restsatz sichergestellt und liefert gleichzeitig eine Methode zur Rückumwandlung der Modulardarstellung in die Basisdarstellung.
Das Rechner in der Modulardarstellung ist effizienter möich, da jede Rechnung durch die Länge des Moduls längenbeschränkt ist. Die Umwandlung von Basis- in Modulardarstellung muß ebenfalls effizient erfolgen. Dazu betrachten man den Produktbaum, in dessen Blättern die Moduli stehen und ein innerer Knoten das Produkt seiner beidne Söhne enthält. Die Länge der dabei auftretenden Zahlen läßt sich für jede Ebene der Höhe i durch b*2^i abschätzen. Auf jeder Ebene i finden sich 2^i solcher Produkte. Auf dem Rückweg von der Wurzel zu den Blättern wird die Zahl in Basisdarstellung durch das vorher berechnete Teilprodukt dividiert und der Rest bestimmt. Die Reste haben höchstens die Länge der Teilprodukte. Als Ergebnis erhält man Sum(i=0..ld(n), 2^i*D(b*2^(ld(n)-i)))=...=O(m*log m), wobei m die Länge des Produkts der ui ist. Dies ist eine Verbesserung gegenüber der Variante, in der die Zahl in Basisdarstellung einzeln durch jeden Modul dividiert wird.
Dies war meine zweite mündliche Prüfung, aber die erste über 10 SWS. Mit seinem Einstieg hatte er mich einkalt erwischt und ich hatte große Probleme. Die zweite Hälfte hat mich dann doch noch auf eine 2- gerettet. Ansonsten war die Prüfung sehr fair.
Vorbereitet habe ich mich etwa sechs Wochen mit Durcharbeitung des Skripts und dem Lesen folgender Bücher:
Philipp Hahn