Dozent: Mathias Schacht
Termine
Beginn der Vorlesung: 18.04.2007.
Beginn der Übungen: 24.04.2007.
| VL | Mittwoch | 15:15 - 16:45 | RUD 26, 0'115 |
|---|---|---|---|
| UE | Dienstag (14tgl./1) | 11:15 - 12:45 | (RUD 26, 1'307) M. Schacht |
| Dienstag (14tgl./2) | 11:15 - 12:45 | (RUD 26, 1'307) M. Schacht | |
| Mittwoch (14tgl./1) | 13:15 - 14:45 | (RUD 26, 1'307) S. Kirchner | |
| Mittwoch (14tgl./2) | 13:15 - 14:45 | (RUD 26, 1'307) S. Kirchner | |
| Donnerstag (14tgl./1) | 11:15 - 12:45 | (RUD 26, 1'307) M. Schacht | |
| Donnerstag (14tgl./2) | 11:15 - 12:45 | (RUD 26, 1'307) M. Schacht |
Klausurtermine
- Klausur: Donnerstag, 26.07.2007, 13:00-15:00 Uhr, RUD 26, 0'115
- Nachklausur: Donnerstag, 13.09.2007, 9:00-11:00 Uhr, RUD 26, 0'115
Klausurergebnisse
Die Ergebnisse der Klausur vom 26.07.2007 liegen vor. Die Klausureinsicht findet am 30.07.2007 von 15:00 bis 17:00 Uhr in Raum 3.321, RUD 25 statt. Zur Klausureinsicht ist in jedem Fall der Personalausweis vorzuzeigen.
Die Ergebnisse der Nachklausur vom 13.09.2007 liegen vor. Die Klausureinsicht findet am 17.09.2007 von 15:00 bis 16:00 Uhr in Raum 3.321, RUD 25 statt. Zur Klausureinsicht ist in jedem Fall der Personalausweis vorzuzeigen.
Zuordnung
- Grundstudium, 4. Semester
Inhalte und Lernziele
Teil I: Elementare Algorithmen
- Sortieralgorithmen
- Suchalgorithmen
- Verarbeiten von Zeichenfolgen
Teil II: Algorithmen für Graphen
- Tiefen- und Breitensuche
- Kürzeste Wege
- Minimal spannende Bäume
Teil III: Mathematische Algorithmen
- Generierung von Zufallszahlen
- Die schnelle Fourier-Transformation
Lernziele: Thema der Vorlesung sind Entwurf und Analyse effizienter Algorithmen sowie die dafür notwendigen Grundlagen über diskrete Strukturen.
Die Vorlesung ist angelehnt an Kapitel aus den Büchern:
- Algorithmen von R. Sedgewick (2. Auflage, 2002)
- Algorithmen - Eine Einführung von T. Cormen, C. Leiserson, R. Rivest, C. Stein (2. Auflage, 2007)
Voraussetzungen
- Theoretische Informatik 1 und Theoretische Informatik 2
Folien
Kompletter Satz: druckerfreundliche Version und Vorlesungsversion (Stand 23.07.07)Teil I: Elementare Algorithmen
- VL 18.04.2007 - 23.05.2007 (Einführung, Sortierverfahren, Suchen in Texten, dynamische Datenstrukturen)
Teil II: Algorithmen für Graphen
- VL 23.05.2007 - 27.06.07 (Einführung in die Graphentheorie, DFS, BFS, minimale Spannbäume, kürzeste Pfade, Matchings)
Teil III: Mathematische Algorithmen
- VL 27.06.2007 - 11.07.07 (lineare Kongruenzmethode, Polynommultiplikation, diskrete Fourier-Transformation)
Ü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 Freitag der nächsten Woche 13:00 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 04.05.2007, 13:00 Uhr)
- Serie 2 (Abgabe bis 18.05.2007, 13:00 Uhr)
- Serie 3 (Abgabe bis 01.06.2007, 13:00 Uhr)
- Serie 4 (Abgabe bis 15.06.2007, 13:00 Uhr)
- Serie 5 (Abgabe bis 29.06.2007, 13:00 Uhr)
- Serie 6 (Abgabe bis 13.07.2007, 13:00 Uhr)
Literatur
- , Algorithmen, Pearson Studium, 2. Auflage (2002)
- , Algorithmen - Eine Einführung, Oldenbourg, 2. Auflage (2007)
- , Theoretische Informatik 3 , Vorlesungsskript, Berlin 2006
- , The Art of Computer Programming; Bd. 1, 3 und 4, Addison-Wesley, 3. Auflage (1997/98)
English