Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Vorlesung: Theoretische Informatik II

Dozent: Prof. Johannes Köbler



Termine:
VL
VL
UE
UE
UE
UE
UE
UE
Di
Do
Di
Mi
Do
Do
Fr
Fr
09-11
09-11
11-13
13-15
11-13
15-17
09-11
11-13
RUD 25, 3.001
RUD 25, 3.001
RUD 26, 1'307
RUD 26, 1'307
RUD 25, 3.113
RUD 26, 1'307
RUD 25, 3.113
RUD 25, 3.113
J. Köbler
J. Köbler
M. Bodirsky
G. Grunert
W. Kössler
M. Stigge
W. Kössler
W. Kössler

Zuordnung: Grundstudium, 3. Semester

Übungen:
Die Übungen finden ab Di., 23.10.2007 statt.

Übungsschein: Zum Erwerb eines Übungsscheins werden 50% der Punkte in den schriftlichen Aufgaben und 50% der "Kreuze" für gelöste mündliche Aufgaben benötigt. Es wird 14 Übungsblätter geben. (Anstelle eines 15. Übungsblattes wird es eine Probeklausur geben.)

Prüfung:
Die Prüfung findet in Form einer Klausur am Di., 19.02.2008 um 9 Uhr in RUD26, 0'115 (großer Hörsaal) statt. Vorraussetzung zur Teilnahme ist der Übungsschein. Reine Klausurzeit ist 2 Stunden. Es sind keine Hilfsmittel zugelassen. Mitzubringen sind:
  • Stift und eigenes Papier
  • Amtlicher Lichtbildausweis (d.h. Personalausweis, Reisepass oder Führerschein) zur Identifikation
  • Studentenausweis

Prüfungsanmeldung: Bis Mo., 04.02.2008,
  • Prüfungsordnung 2005 und Kombi-Bachelor: Online
  • Prüfungsordnung 1995 und Nebenfach bei Frau Neugebauer (RUD25, 2.323) zu den Sprechzeiten
  • (Abmeldung bis 14.02.08)
  • Klausureinsicht: Mi., 16.04.2008 um 13:30 Uhr und Fr., 18.04.2008 um 13:30 Uhr in Raum RUD25, 4.012.
  • Nachklausur: Do., 24.07.2008, gegen 9 Uhr in RUD26 0'115


Inhalte und Lernziele


Die VL führt in die Kerngebiete der Theoretischen Informatik ein, wobei die Themengebiete Automaten und formale Sprachen im Mittelpunkt stehen. Die hierbei behandelten Fragen sind nicht nur aus theoretischer Sicht interessant, sondern bilden zugleich die Grundlage für so praktische Anwendungsgebiete wie den Compilerbau. Aufbauend auf dem Automatenmodell der Turingmaschine läßt sich der Begriff des Algorithmus formalisieren, der in allen Bereichen der Informatik eine zentrale Rolle spielt. Die für den praktischen Einsatz wichtige Frage, welcher Rechenaufwand zur Lösung algorithmischer Problemstellungen nötig ist, führt uns einerseits zu verschiedenen Entwurfsmethoden für effiziente Algorithmen (wobei sich Kenntnisse über algebraische und relationale Strukturen, insbesondere Graphen, als überaus nützlich erweisen). Da die gefundenen Algorithmen "nur" obere Schranken für den benötigten Rechenaufwand liefern, versuchen wir andererseits mit Methoden der Komplexitätstheorie, diesen Aufwand auch nach unten abzuschätzen.


Empfohlene Literatur

  • Blum: Theoretische Informatik. Oldenbourg 1998.
  • Emden-Weinert, Hougardy, Kreuter, Prömel, Steger: Einführung in Graphen und Algorithmen, Vorlesungsskript, 450 Seiten, Berlin 1996.
  • Garey, Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.
  • Hopcroft, Ullman: Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 1979.
  • Lewis, Papadimitriou: Elements of the Theory of Computation. Prentice-Hall, 1981.
  • Motwani, Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
  • Papadimitriou: Computational Complexity. Addison-Wesley, 1994.
  • Schöning: Perlen der Theoretischen Informatik. BI-Wissenschaftsverlag, 1995.
  • Schöning: Theoretische Informatik - kurz gefaßt. Spektrum Akademischer Verlag, 1997.
  • Sipser: Introduction to the Theory of Computation. PWS Publishing Company, 1997.
  • Wagner: Einführung in die Theoretische Informatik, Grundlagen und Modelle. Springer Verlag, 1994.
  • Wegener: Theoretische Informatik. Teubner Verlag, 1993.
  • Harry Mairson : The Pumping Lemma (poem)

Aufgabenblätter


Abgabe der schriftlichen Lösungen im Sekretariat bei Frau Sandig (Raum 3.320) jeweils bis 9:15 Uhr am Abgabetag!
Bitte Angabe von Name, Matrikelnr., Übungstermin und ggf. Goya-Gruppe nicht vergessen!

Blatt 1 (mündl. Besprechung 23.-26.10.2007; schriftl. Abgabe: 30.10.2007, 9:15 Uhr)
Blatt 2 (mündl. Besprechung 30.10.-2.11.2007; schriftl. Abgabe: 6.11.2007, 9:15 Uhr)
Blatt 3 (mündl. Besprechung 6.11.-9.11.2007; schriftl. Abgabe: 13.11.2007, 9:15 Uhr)
Blatt 4 (korrigiert!, mündl. Besprechung 13.11.-16.11.2007; schriftl. Abgabe: 20.11.2007, 9:15 Uhr)
Blatt 5 (mündl. Besprechung 20.11.-23.11.2007; schriftl. Abgabe: 27.11.2007, 9:15 Uhr)
Blatt 6 (mündl. Besprechung 27.11.-30.11.2007; schriftl. Abgabe: 4.12.2007, 9:15 Uhr)
Blatt 7 (mündl. Besprechung 4.12.-7.12.2007; schriftl. Abgabe: 11.12.2007, 9:15 Uhr)
Blatt 8 (mündl. Besprechung 11.12.-14.12.2007; schriftl. Abgabe: 18.12.2007, 9:15 Uhr)
Blatt 9 (mündl. Besprechung 18.12.-21.12.2007; schriftl. Abgabe: 8.1.2008, 9:15 Uhr)
Blatt 10 (aktualisiert, mit Lösungshinweisen, mündl. Besprechung 8.1.-11.1.2008; schriftl. Abgabe: 15.1.2008, 9:15 Uhr)
Blatt 11 (mündl. Besprechung 15.1.-18.1.2008; schriftl. Abgabe: 22.1.2008, 9:15 Uhr)
Blatt 12 (mündl. Besprechung 22.1.-25.1.2008; schriftl. Abgabe: 29.1.2008, 9:15 Uhr)
Blatt 13 (mündl. Besprechung 29.1.-1.2.2008; schriftl. Abgabe: 5.2.2008, 9:15 Uhr)
Blatt 14 (mündl. Besprechung 5.2.-8.2.2008; schriftl. Abgabe: 12.2.2008, 9:15 Uhr)
Probeklausur (mündl. Besprechung 12.2.-15.2.2008)


Skript