Das ''Should-Have'': Theoretische Informatik 2

Allen Studierenden, die sich in der theoretischen Informatik spezialisieren möchten wird dringend empfohlen diese Veranstaltung zu besuchen

Die Veranstaltung Theoretische Informatik 2

Als eine gute Fortsetzung der Diskreten Modellierung bietet sich die Veranstaltung ''Theoretische Informatik 2'' an. In der Diskreten Modellierung wurden die Konzepte wie kontextfreie Grammatiken und reguläre Sprachen eingeführt. Diese Konzepte werden in der Theoretischen Informatik 2 im Detail behandelt. Beispielsweise lässt sich überlegen, ob man DFA's minimieren kann (d.h. ob sich ein anderer DFA konstruieren lässt, der weniger Zustände besitzt und die gleiche Sprache akzeptiert) und wie sich diese minimieren lassen. Weiterhin werden kontextfreie Grammatiken näher angeschaut. Zum einen kann man sich fragen: Wie ausdrucksstark sind kontextfreien Grammatiken? Ähnlich wie bei dem Pumping-Lemma für reguläre Sprachen lässt sich auch für kontextfreie Grammatiken nachweisen, dass eine gegebene Sprache sich nicht als eine kontextfreie Grammatik ausdrücken lässt. Weitere Fragen sind: Diese Fragen sind vor allem im Compilerbau sehr wichtig. Diese haben als ''Wörter'' einen gegebenen Code, den ein Benutzer programmiert hat, und es muss bei der Syntaxanalyse festgestellt werden, ob dieser Code auch wirklich ein syntaktisch korrekter Code ist, der zu der geforderten Programmiersprache gehört. Dazu verfügt der Compiler über eine kontextfreie Grammatik. Hier sind für eine effiziente Auswertung schöne mathematische Eigenschaften der kontextfreien Grammatik vom Vorteil. Darüber hinaus werden sogenannte Kellerautomaten eingeführt, die äquivalent zu den kontextfreien Grammatiken sind. Nachdem wir die Ausdrucksstärke der verschieden Modellierungen von Sprachen angeschaut haben, sind wir in der Lage eine Hierarchie aufzubauen, eine sogenannte Chomsky-Hierarchie.
Im Anschluss können Wahlthemen von jeweiligen Dozenten ausgewählt werden. Das könnte beispielsweise sein:

Informationen zur Veranstaltung

Empfohlene Vorkenntnisse: Kenntnisse aus der Diskreten Modellierung, über Algorithmen und Laufzeitanalyse
Benötige Module: B-MOD (Diskrete Modellierung)
CP: 8 CP (3 Vorlesungsstunden, 2 Übungsstunden pro Woche)
Rhythmus: jedes SoSe
Empfehlung: 4. Semester (Start im WiSe) 3. Semester (Start im SoSe)
Link zur Veranstaltung

Überblick über die Module im Bereich "Grundlagen der Informatik" im Bachelor-Studiengang: