Humboldt-Universität zu Berlin, Institut für Informatik

Lehrstuhl für Komplexität und Kryptografie

Vorlesung: Theoretische Informatik II

Dozent: Prof. Johannes Köbler

Übungen: Olaf Beyersdorff, M. Füssel, P. Liske, C. Schwarz


Klausurtermin

Die Klausur findet am 30.3.2004 von 9.00 bis 12.00 Uhr im Kinosaal (Hauptgebäude) statt.

Noch ein wichtiger Hinweis zur Klausur: Bücher, Skripte oder andere Unterlagen dürfen nicht verwendet werden.


Konsultationen

Die Konsultationen zur Prüfung "Theoretische Informatik 2" finden

Mittwoch, 24. März, 9 bis 11 Uhr (mit Carsten Schwarz) und
Donnerstag, 25. März, 13 bis 15 Uhr (mit Matthias Füssel)
im Johann von Neumann-Haus, Raum 3.110 statt.

Bitte schickt rechtzeitig eine E-Mail mit
- euren Fragen bzw. den nicht verstandenen Übungsaufgaben und
- der Konsultation, an der ihr teilnehmen werdet,
an caschwar@informatik.hu-berlin.de, damit wir diese sinnvoll strukturieren können.


Termine: VL Di 09-11 (RUD 25, 3.001) Prof. J. Köbler

VL Do 09-11 (RUD 25, 3.001) Prof. J. Köbler


UE Di 11-13 (RUD 26,  0'313)  O. Beyersdorff 

UE Mi 13-15 (RUD 26, 1'305)  O. Beyersdorff

UE Mi 15-17 (RUD 26, 1'308)  C. Schwarz

UE Do 15-17 (RUD 25, 4.111)  C. Schwarz

UE Fr 09-11 (RUD 26, 1'308)  M. Füssel

UE Fr 11-13 (RUD 26, 1'308)  P. Liske


Zuordnung: Grundstudium, 3. Semester

Die Einschreibung zu den Übungen und die Vergabe der Punkte erfolgt über das Goya-System.


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

Übungsaufgaben

Skript


JK

Erstellt am 05.08.2003