Theoretische Informatik 1

(WAS) Die Studierenden erlernen formale Grundlagen der Informatik wie Begriffe, Methoden, Modelle und Arbeitsweisen, (WOMIT) indem Sie Probleme abstrahieren und modellieren, etwa mithilfe logischer und algebraischer Kalküle, graphentheoretischer Notationen, formalen Sprachen und Automaten. (WOZU) um den algorithmischen Kern von Problemen identifizieren, passende Algorithmen entwerfen und implementieren, sowie bestehende Umsetzungen auf ihre Eigenschaften hin untersuchen zu können.

Grundlagen

• Mengen, Relationen, Graphen
• Zahlensysteme, Zahlendarstellung, Numerische Aspekte

Logik und Boolesche Algebra

• Aussagenlogik
• Prädikatenlogik
• Boolesche Algebra

Reguläre Sprachen

• Endliche Automaten
• Reguläre Ausdrücke
• Reguläre (Typ-3) Grammatiken, Syntaxdiagramme
• Chomsky-Hierarchie

Kontextfreie Sprachen

• Kontextfreie (Typ-2) Grammatiken, Chomsky- und Greibach-Normalformen
• Anwendungen (Ableitungs- und Syntaxbäume, Syntax von Programmiersprachen, Backus-Naur-Form)

Kontextsensitive und rekursiv aufzählbare Sprachen

• Kontextsensitive (Typ-1) und Phrasenstruktur- (Typ-0) Grammatiken, Monotonie, Normalform

Berechenbarkeit, Entscheidbarkeit und Komplexität

• Turing-Maschinen, Turing-Berechenbarkeit
• Entscheidbarkeit, rekursive Aufzählbarkeit
• Komplexität

• Vermittlung der Theorie in der Vorlesung
• Aufgaben zu den Lehrinhalten werden in kleinen Gruppen (Teamarbeit) selbständig gelöst. Die Lösungen sollen in den Übungsstunden vorgetragen und der Lösungsweg den Kommilitonen hierbei erläutert werden.

Vorlesung 2 SWS, Übung 2 SWS

• Hoffmann, D. (2018): Theoretische Informatik, 4. Auflage, Carl Hanser Verlag München.
• Hedtstück, U. (2004): Einführung in die Theoretische Informatik. Oldenbourg, München.
• Kelly, J. (2003): Logik. Pearson Studium, München.
• Ehrig, H. et al. (1999): Mathematisch-strukturelle Grundlagen der Informatik. Springer, Heidelberg.
• Beuth, K. (1992): Digitaltechnik. 9. Auflage, Vogel, Würzburg.