Lehr- und Forschungseinheit für Theoretische Informatik,
Institut für Informatik
der Ludwig-Maximilians-Universität München
Vorlesung im Hauptstudium Komplexitätstheorie (WS 02/03):
- Vorlesung:
- Martin Hofmann, 2-stündig
- Zeit und Ort: Mo 12 - 14, Raum 0.13
- Beginn: 14. 10. 2002
- Übung:
-
Steffen Jost, 2-stündig
- Zeit und Ort der Übung: Do 12 - 14, Raum 15 (Kellerraum)
- Beginn: 24. 10. 2002
- Vorkenntnisse:
-
Effiziente Algorithmen empfehlenswert aber nicht Voraussetzung
- Hörerkreis:
- Studierende der Informatik im Hauptstudium
- Studierende mit Nebenfach Informatik
- Schein:
- Schein gilt für Diplomprüfung in
Haupt- und Nebenfach Informatik
- Scheinerwerb durch Kolloquium
zurück zum
Inhaltsverzeichnis dieser Seite
Die Komplexitätstheorie beschäftigt sich mit der Klassifikation von
Algorithmen und Berechnungsproblemen nach ihrem Ressourcenverbrauch,
z.B. Rechenzeit oder benötigtem Speicherplatz. Probleme
mit gleichartigem Ressourcenverbrauch werden zu Komplexitätsklassen
zusammengefasst. Die bekanntesten Komplexitätsklassen sind sicherlich
P und NP, die die in polynomieller Zeit deterministisch bzw.
nicht-deterministisch lösbaren Probleme umfassen.
P und NP sind jedoch nur zwei Beispiele von
Komplexitätsklassen. Andere Klassen ergeben sich etwa bei der
Untersuchung der effizienten Parallelisierbarkeit von Problemen, der
Lösbarkeit durch zufallsgesteuerte oder interaktive Algorithmen, der
approximativen Lösung von Problemen, um nur einige Beispiele zu
nennen. Die Vorlesung hat das Ziel, einen Überblick über die
Hauptergebnisse der Komplexitätstheorie zu geben. Wir werden dabei das
Buch von Bovet und Crescenzi zur Grundlage nehmen und es durch einige
aktuelle Themen aus dem programmiersprachlichen Bereich ergänzen.
- Bovet, Crescenzi. Introduction to the Theory of Complexity. Prentice
Hall. New York.1994.
Dieses Buch liegt ab sofort zur kurzzeitigen Ausleihe in Raum Z1.05, dem
Sekretariat des Lehrstuhls Theoretische Informatik, bereit.
Wer es ausleiht sollte es spätestens zur Vorlesung wieder mitbringen und bei
Bedarf an seine Mitstudenten abgeben. Die Bibliothek hat inzwischen ebenfalls ein
Exemplar angeschafft.
- Papadimitriou. Computational Complexity. Addison-Wesley. Reading. 1995.
- Originalarbeiten, die in der Vorlesung nach Bedarf bekannt gegeben werden.
zurück zum
Inhaltsverzeichnis dieser Seite
- Eine 2Band Maschine fuer Palindrome ist hier .
- Ein Vorlesungslogbuch (Themen, die nicht im Buch stehen sind hier detailliert aufgeschrieben.): hier .
zurück zum
Inhaltsverzeichnis dieser Seite
| Übungsblatt |
Datum |
Lösungsvorschläge |
Hausaufgaben? |
Bemerkungen und Berichtigungen (Stand: 06.02.03 --- Ende der Veranstaltung) |
| Übung 1 |
23.01.03 |
Beispiellösungen 1 |
Keine! |
| Übung 2 |
31.10.02 |
Beispiellösungen 2 |
H1, H2, H3, H4 |
- H2:
- Die Mengen A,A1,A2 sollen Zahlen auch mehrfach enthalten dürfen,
sind also endliche Multimengen oder endliche Listen.
- Zeige, dass Partitionieren NP-vollständig ist.
- H3:
- Die Aufgabe fragt nach einem Algorithmus für duale Horn-Formeln,
was aber an der Schwierigkeit nichts ändert.
Horn-Formeln erhalten maximal eine positive Variable pro Klausel.
|
| Übung 3 |
7.11.02 |
Beispiellösungen 3 |
|
| Übung 4 |
14.11.02 |
Lösungsideen 4 |
(Abgabe H1-H4) |
Die korrigierten Hausübungen können
nun in der Übung oder in D1.09 abgeholt werden. |
| Übung 5 |
21.11.02 |
Lösungsideen 5 |
Keine |
| Übung 6 |
28.11.02 |
Lösungsideen 6 |
Keine |
| Übung 7 |
5.12.02 |
Lösungsideen 7 |
Keine |
G28: sollte enden mit "gibt, mit L in P hoch S" |
| Übung 8 |
12.12.02 |
Lösungsideen 8 |
H5, H6, H7,
H8 |
H7: Zwei Zeichen zu vertauschen gilt nicht als Editieroperation;
desweiteren wurde der Hinweis erweitert. |
| Übung 9 |
19.12.02 |
Lösungsideen 9 |
|
| Übung 10 |
9.01.03 |
Lösungsideen 10 |
(Abgabe H5-H7) |
Leider konnten in der Vorlesung am 16.12. nicht alle
Voraussetzung zu H8 geschaffen werden;
die Abgabe von H8 verschiebt sich daher auf den 23.01.2003. |
| |
16.01.03 |
|
|
Entfällt; ebenso entfällt die Vorlesung am 20.01.2003. |
| Übung 11 |
23.01.03 |
Lösungsideen 11 |
Abgabe H8,
Bekanntgabe H9 |
- Neue überarbeitete Version des Übungsblattes!!!
- Hilfen und weitere Details zur Hausaufgabe H9:
- Anstelle der Borel-Implementation von LFPL benutzen wir nun die Implementation
von Robert Atkey, die unter
"http://www.dcs.ed.ac.uk/home/resbnd/prototypes/by_Robert_Atkey/"
zu finden ist. Leider ist die Übersetzung nach C etwas fehlerhaft.
Deshalb könnt ihr Euch den korrigierten Compiler als ausführbare
Binary-Datei für Linux herunterladen.
Das erspart auch die Mühe mit dem hin- und herkopieren
in die Browseroberfläche!
Desweiteren liefert dieser Compiler ausführlichere Fehlermeldungen;
kennt dafür aber leider keine generischen Datentypen mehr.
- Desweiteren gibt es eine Vorlagedatei,
die schon zahlreiche Funktionen enthält. In dieser Datei
müsst ihr also nur noch die Lücken ausfüllen!
Natürlich dürft ihr noch weitere Funktionen ausser den
vorgegebenen definieren, falls nö.
- Die Datei sollte bereits fehlerfrei zu übersetzen sein:
" > lfplc --backend=c huffman.lfpl huffman.c"
sollte die Datei huffman.c erzeugen - die Übersetzung nach C.
Diese kann man dann zum Beispiel mit
" > gcc -o huffman_lfpl huffman.c"
in eine lauffähige Datei compilieren.
Wenn ihr diese aufruft, solltet ihr sowas wie
" > A,13 B,11 C,14 D,11 E,40 F,12 "
"No Tree received!"
" > "
sehen! Das erste ist eine List mit Symbolen und deren Häufigkeiten,
die ihr in einen Huffman-Coding-Tree verwandeln sollt! Danach
wird der Baum ausgedruckt, da diese Funktionen noch nicht implementiert sind,
erscheint nur "No Tree received!". Viel Spass!
- Bei technischen Problemen könnt ihr Euch gerne an mich wenden, auf
den Rechnern im Rechnerpool sollte jedoch alles problemlos laufen!
|
| Übung 12 |
30.01.03 |
Lösungsideen 12 |
|
| Übung 13 |
6.02.03 |
Lösungsideen 13 |
Abgabedatum für H9
war Montag, der 3.2.2003 gewesen.
Hier eine Beispielimplementation dazu.
|
- Hausübungen:
Damit stehen alle Benotungen der Hausübungen fest.
Wer insgesamt 2 Punkte erzielt hat, bekommt in der letzten Übung seinen
Schein ausgehändigt (sofern mir die Matrikelnummer bekannt war); danach kann der Schein noch
im Sekretariat abgeholt werden. Wer 1 Punkt erreicht hat, muss sich zum Schweinerwerb mit Martin Hofmann
in Verbindung setzen und einen Termin für ein kurzes persönliches Gespräch (ca. 10 Minuten) über
Komplexitätstheorie ausmachen.
Mit 0 Punkte in den Hausübungen ist der Scheinerwerb nicht mehr möglich.
|
Bei Fragen zu den Übungen wendet Euch bitte an
Steffen Jost.
Hinweis:
Die Übungen sind als Gruppenübungen unter Anleitung konzipiert.
Einige Aufgaben können daher etwas schwerer sein.
Bewertung der Hausaufgabe:
Auf jede Hausaufgabe gibt es 2 Punkte. Einen für sinnvolle Bearbeitung und einen für
die richtige Lösung. Daraus berechnet sich die Punktzahl (0-2) für das Hausaufgabenblatt,
wobei höchstens eine Aufgabe mit 0 Punkten durch eine Aufgabe mit 2 Punkten ausgeglichen werden kann.
Das gilt analog für die Gesamtpunktzahl.
Bei einer Gesamtpunktzahl von 1 ist zum Erhalt des Übungscheines noch eine kurze mündliche
Prüfung am Semesterende abzulegen.
zurück zum
Inhaltsverzeichnis dieser Seite