Grundbegriffe der Theoretischen Informatik

Auf dieser Seite

• Termine
• Inhalte
• Klausurzulassung

 
 

Termine

 Grundbegriffe der Theoretischen Informatik (VL, Ü) 

        Vorlesung    Wehrheim
       
           Mittwoch 10-12, HS G
           Freitag 12-14, HS B 
       
        Übungen (5 Gruppen) 
           Montag 16-18, V322           Schmedes
           Dienstag 12-14, V322         Steinert
           Mittwoch 14-16, V322         Dierks
           Mittwoch 14-16, A4 2-221  Wimmel, 
           Mittwoch 16-18, A4 2-221  Najman

 

Inhalte

Nach Vermittlung diverser (mathematischer) Grundlagen wird im ersten Teil der Vorlesung untersucht, welche Funktionen algorithmisch berechenbar bzw. welche Probleme algorithmisch entscheidbar sind. Dazu wird der Begriff des Algorithmus formalisiert. Turingmaschinen, µ-rekursive Funktionen und Grammatiken stellen sich als äquivalente Ansätze heraus. Es wird gezeigt, daß es Probleme gibt, die nicht algorithmisch entscheidbar sind. Dazu gehören leider auch viele Probleme von praktischem Interesse.

Zur Beschreibung der Syntax von Programmiersprachen sind reguläre und kontextfreie Sprachen am wichtigsten. Im zweiten Teil der Vorlesung wird gezeigt, daß solche Sprachen von einfacheren Maschinen als Turingmaschinen erkannt werden können, nämlich durch endliche Automaten und Kellerautomaten. Ferner werden grundlegende Eigenschaften dieser Sprachen und Automaten hergeleitet.

Im dritten Teil der Vorlesung geht es um die Komplexität von Algorithmen, d. h. wieviel Zeit und Spreicherplatz zum Lösen einer Aufgabe benötigt wird. Insbesondere werden Probleme betrachtet, die deterministisch oder nichtdeterministisch in polynomieller Zeit lösbar sind. Diese Problemklassen sind unter den Namen P und NP bekannt.

 

Klausurzulassung

Zu der Klausur am Semesterende wird nur zu gelassen, wer in diesem Semester erfolgreich an den Übungen teilgenommen hat. Eine Liste mit den Matrikelnummern der Zugelassenen wird rechtzeitig am Mitteilungsbrett der Theoretischen Informatik ausgehängt.