Theoretische Informatik II
| Inhalt: |
| Zunächst wird die Frage behandelt, ob es überhaupt nichtberechenbare Probleme gibt, und in diesem Zusammenhang wird ein realitätsnahes Rechnermodell (Turingmaschine) eingeführt. Danach wenden wir uns berechenbaren Problemen zu und untersuchen diese hinsichtlich ihrer algorithmischen Schwierigkeit. Dabei werden speziell die Komplexitätsklassen P und NP sowie NP-vollständige Probleme betrachtet. Untersucht werden in dieser Vorlesung auch andere Rechnermodelle wie endliche Automaten und ihre "Berechnungskraft". Des Weiteren werden Grammatiken für formale Sprachen behandelt. Hierzu wird die Chomsky Hierarchie erläutert und in diesem Zusammenhang nach geeigneten Programmiersprachen gefragt. |
| Literatur: |
|
| Teilnehmer: |
| Studierende der Informatik und Mathematik |
| Voraussetzungen: |
| Für Nichtinformatiker: Ein vorheriger Besuch der Vorlesung "Theoretische Informatik I" ist hilfreich. |
| Abschluss: |
| Fachprüfung oder Leistungsnachweis je nach Studiengang. |
| Übungen: |
