Dozent: Amin Coja-Oghlan
Termine
Beginn der Vorlesung: 18.04.2006.
Beginn der Übungen: 04.05.2006.
Klausur: 31.07.2006, 9:00-13:00 Uhr, RUD 26, 0'115
Nachklausur: 11.09.2006, 9:00-13:00 Uhr, RUD 26, 0'115
Hier sind die Ergebnisse der Nachklausur und der Klausur. Eine allgemeine Klausureinsicht findet am 20.10. um 16 Uhr in Raum 3.321, RUD 25 statt.
| VL | Mittwoch | 15:15 - 16:45 | RUD 26, 0.115 |
|---|---|---|---|
| UE | Dienstag (14tgl./1) | 11:15 - 12:45 | (RUD 26, 1'307) A. Coja-Oghlan |
| Dienstag (14tgl./2) | 11:15 - 12:45 | (RUD 26, 1'307) A. Coja-Oghlan | |
| Mittwoch (14tgl./1) | 13:30 - 15:00 | (RUD 25, 4.113) A. Coja-Oghlan | |
| Mittwoch (14tgl./2) | 13:30 - 15:00 | (RUD 25, 4.113) A. Coja-Oghlan | |
| Donnerstag (14tgl./1) | 11:15 - 12:45 | (RUD 25, 4'112) M. Bodirsky | |
| Donnerstag (14tgl./2) | 11:15 - 12:45 | (RUD 25, 4'112) M. Bodirsky |
Zuordnung
- Grundstudium, 4. Semester
Inhalte und Lernziele
Thema der Vorlesung sind Entwurf und Analyse effizienter Algorithmen sowie die dafür notwendigen Grundlagen über diskrete Strukturen.
Das Skript zur Vorlesung gibt es hier: skriptthi3.pdf, 284k (Letzte Änderung: 05.07.2006)
Die Folien der Vorlesung zu parametrisierten Algorithmen sind auch online verfügbar: para.ps
Voraussetzungen
- Theoretische Informatik 1 und Theoretische Informatik 2
Übungen
In den Übungen kann ein Übungsschein "Theoretische Informatik 3" erworben werden. Voraussetzung ist das Erreichen von mindestens 50% der möglichen Punkte in den Übungsaufgaben sowie die aktive Mitarbeit in der Übung. Der Übungsschein ist notwendig, um zur Klausur zugelassen zu werden.
Die neuen Übungsaufgaben erscheinen jeweils mittwochs auf dieser Seite und in Goya und werden in der Vorlesung verteilt. Abgabe ist bis zum Mittwoch der übernächsten Woche 15:15 Uhr im Sekretariat möglich. Die Abgabe erfolgt in Papierform, elektronische Abgabe per E-Mail oder Goya ist nicht erlaubt. Die Aufgaben dürfen in Zweiergruppen oder einzeln bearbeitet werden, wobei jedes Blatt der Abgabe Name(n) und Matrikelnummer(n) der beteiligten Studenten enthalten muss. Bitte achten Sie auf nachvollziehbare Lösungswege!
Die korrigierten Lösungen erhält man in seiner Übungsgruppe. Alle übriggebliebenen, korrigierten Übungszettel können dienstags von 9:30 bis 11:30 Uhr und donnerstags von 15 bis 16 Uhr im Sekretariat abgeholt werden.
Zur Teilnahme an den Übungen ist es erforderlich, sich über Goya in einer der Übungsgruppen anzumelden. In den Übungen werden die Übungsaufgaben besprochen, Fragen dazu beantwortet und Lösungen diskutiert.
- Serie 1 (Abgabe bis 03.05.2006, 15:15 Uhr)
- Serie 2 (Abgabe bis 17.05.2006, 15:15 Uhr)
- Serie 3 (Abgabe bis 31.05.2006, 15:15 Uhr)
- Serie 4 (Abgabe bis 13.06.2006, 15:15 Uhr)
- Serie 5 (Abgabe bis 27.06.2006, 15:15 Uhr)
Material zur Programmieraufgabe:- Programmiersprache
- Java 1.5.0 (Download von java.sun.com)
- zu ergänzender Quelltext
Kruskal.javaDijkstra.java- vorgegebene Datenstrukturen
- ein einfacher Graph,
Graph.class - mit gewichteten Kanten,
Kante.class - Hinweise
- » Java-Dokumentation zu den gegebenen Klassen
- höhere Datenstrukturen als Arrays oder einfach verkettete Listen sind nicht erlaubt
- die Funktionsfähigkeit kann mit der einfachen Testklasse
Test.javaoder mit der JUnit-TestklasseJTest.javaüberprüft werden - Laufzeiten
Graph.getSortierteKanten()benötigt O(m logn)Graph.getAdjazenteKanten(...)benötigt O(|N(v)|), wobei N(v) die Nachbarschaft des gegebenen Knoten v sei- Abgabe per E-Mail
- "
Kruskal.java" und "Dijkstra.java" an liske@informatik.hu-berlin.de
Literatur
- , Einführung in Graphen und Algorithmen, Vorlesungsskript, Berlin 1996
- , Theoretische Informatik 3, Vorlesungsskript, Berlin 2005
- , Computational Complexity, Addison Wesley, 1994
English