Theoretische Informatik 2
| Inhalt: |
| In dieser Vorlesung werden zunächst Probleme betrachtet, welche sich prinzipiell nicht mit Rechnern lösen lassen. Hat man dann die Lösbarkeit eines Problems (unter Rechnereinsatz) nachgewiesen, fragt man nach der praktischen Lösbarkeit. Für eine große Klasse von Problemen ist jedoch bekannt, dass sie alle effizient (in Polynomialzeit) lösbar sind oder alle nicht effizient lösbar sind. Die Entscheidung dieses Sachverhalts ist das größte offene Problem der theoretischen Informatik. In dieser Vorlesung werden die entsprechenden Konzepte vorgestellt. Die erzielten negativen Resultate ersparen die Suche nach nicht existierenden bzw. effizienten Algorithmen. Weiter werden endliche Automaten, welche eine Grundlage moderner Schaltwerke modellieren, vorgestellt. Grammatiken beschreiben die Syntax von Programmiersprachen. Zum einen erwartet man hier Komfortabilität, zum anderen jedoch sollen auch etwa Tests auf syntaktische Korrektheit schnell durchführbar sein, was gewisse Einschränkungen ergibt. Es zeigt sich in dieser Vorlesung, dass die so genannten kontextfreien Grammatiken als Basis von Programmiersprachen geeignet sind. Eine aktive Teilnahme in den angebotenen Übungen ist sehr zu empfehlen. |
| Literatur: |
|
| Teilnehmer: |
| Informatik (4. Semester) |
| Übungen: |
