| Modulname |
Theoretische Informatik |
| Gebiet |
Gebiet 3
|
| Profil |
Profil Freie Studien
|
| CPs |
10 CP |
| Campus |
Hier geht
es zum Vorlesungsverzeichnis |
| Voraussetzungen |
Fähigkeit zum Mathematischen Denken. Vorkenntnis in Informatik und Diskreter Mathematik sowie Vertrautheit mit mindestens einer Programmiersprache sind von Vorteil, aber nicht zwingend erforderlich. |
| Besonderheiten |
Turnus: jährlich Anmeldungen für den Optionalbereich: Bitte wenden Sie sich an den jeweiligen Dozenten. TN-Plätze: 30/180 für den Optionalbereich |
| Blockseminar |
Nein |
| Vorkenntnisse |
|
| Veranstaltungszeit |
Montag 10:00 - 12:00, Mittwoch 10:00 - 12:00, Dienstag 14:00 - 16:00, Mittwoch 12:00 - 14:00, Mittwoch 14:00 - 16:00 |
| Dozenten |
Maike Buchin, Christoph Ries |
| Arbeitsaufwand |
Teilnahme an der Vorlesung, aktive Teilnahme an den Übungen, erfolgreiche Teilnahme an der Abschluss-Klausur. Zusammensetzung der Endnote: Resultat der Klausur |
| Literatur |
"Theoretische Informatik - kurz gefasst" von Uwe Schöning (Spektrum 2001) bzw. Skriptum zur Vorlesung |
| Modulteil |
[150240] Theoretische Informatik - WS 20/21, [150241] Übungen zu Theoretische Informatik - WS 20/21 |
| Modultyp |
|
| Modulanbieter |
Fakultät für Mathematik |
| Inhalt |
Die Vorlesung liefert eine Einführung in die Theorie der Grammatiken (insb. kontextfreie Grammatiken) und Automaten (endlicher Automat, Kellerautomat, Turing-Maschine). Sie gibt ferner einen Einblick in die Berechenbarkeits- und NP-Vollständigkeitstheorie, wo es um die Frage geht, welche Rechenprobleme (überhaupt bzw. mit vertretbarem Auifwand) gelöstwerden können. Es wird sich zeigen, dass es inhärent schwere Probleme gibt, die von Rechnern nicht zufrieden stellend gelöst werden können. In der Vorlesung ergeben sich fundamentale Einsichten zum Verhältnis von Determinismus und Nicht-Determinismus. Durch Einüben von Techniken wie wechselseitige Simulation oder (polynomiell) berechenbare Reduktionen soll die Einsicht reifen, dass an der Oberfläche verschieden aussehende Konzepte im Kern identisch sein können. Ziel ist zudem ein tieferes Verständnis von Komplexität im Kontext der so genannten Chomsky-Hierarchie. |
| Lernziele |
Kenntnis der Chomsky-Hierarchie und Verständnis für die zentralen Resultate zu Grammatiken und Automaten. Fähigkeit die Komplexität von Problemen abzuschätzen und diese in die Chomsky-Hierarchie einzuordnen. |
