Theoretische Informatik I und II

Pflichtfach
10 ECTS-P
8 SWS
jährlich angeboten

Prof. Dr. Erwin Holland-Moritz

• Die Studierenden sollen den in der Vorlesung dargestellten theoretischen Stoff durch ergänzende selbständige Literaturarbeit und an anderen Beispielen aufarbeiten.
• Aufgaben zu den Lehrinhalten(s.u.) werden in kleinen Gruppen (Teamarbeit) selbständig gelöst. Die Lösungen sollen in den Übungsstunden vorgetragen erden und der Lösungsweg den Kommilitonen hierbei erläutert werden.
• Zum Abschluss muss jeder Studierende zum erfolgreichen Abschluss des Faches in der Lage sein, entsprechende Problemstellungen selbstständig zu lösen.

Dieses Grundlagenfach zur Informatik ersreckt sich über zwei Semester.

• Grundlagen: Mengen, Relationen, Graphen, Polynome; Zahlensysteme, Zahlendarstellung, Numerische Aspekte; Codierung, Informationstheorie
• Logik und Boolesche Algebra: Aussagenlogik; Prädikatenlogik; Boolesche Algebra, Schaltnetze und Schaltwerke
• Reguläre (Typ-3) Sprachen: Endliche Automaten, Reguläre Ausdrücke; Typ3-Grammatiken, Syntaxdiagramme; Chomsky-Hierarchie
• Modellierung sequentieller und paralleler (Ausgabe-) Prozesse: Endliche Maschinen, Berechnungen; Automatennetze, Petri-Netze
• Kontextfreie (Typ-2) Sprachen: Kontextfreie Grammatiken, Chomsky- und Greibach-Normalform; Kellerautomaten; Anwendungen (Ableitungs- und Syntaxbäume, Syntax von Programmiersprachen, Backus-Naur-Form)
• Kotextsensitive (Typ-1) und rekursiv aufzählende (Typ-0) Sprachen: Grammatiken, Monotonie, Normalform; Turingautomaten; Einführung in die Begriffe: Berechenbarkeit, Entscheidbarkeit und Komplexität

Vorlesungen (2 SWS) und Übungen (2 SWS) pro Semester

Keine über die Zulassungsvorraussetzungen hinausgehenden Vorraussetzungen

Dean, N. ( 2003 ): Diskrete Mathematik. Pearson Studium. München.

Meinel, C., Mundhenk, M. ( 2002 ): Mathematische Grundlagen der Informatik. B. G. Teubner, Stuttgart.

Brill, M. ( 2005 ): Mathematik für Informatiker. Carl Hanser Verlag, München.

Ehrig, H. et al. (1999): Mathematisch-strukturelle Grundlagen der Informatik. Springer, Heidelberg. Kelly, J. ( 2003 ): Logik. Pearson Studium, München.

Kelch, R. ( 2003 ): Rechnergrundlagen. Von der Binärlogik zum Schaltwerk. Fachbuchverlag Leipzig im Carl Hanser Verlag.

Vossen, G., Witt K. (2004): Grundlagen der Theoretischen Informatik mit Anwendungen. 3. Aufl. Vieweg & Sohn, Braunschweig.

Asteroth, A., Baier, C. (2002) Theoretische Informatik. Pearson Studium München

Hedtstück, U. ( 2004 ): Einführung in die Theoretische Informatik. Oldenbourg, München.

Hopcroft, J. E. et al. (2002): Einführung in die Automatentheorie, Formale Sprachen und Kom plexitätstheorie. Pearson Studium, München.

Schöning, U. (1997): Theoretische Informatik - kurzgefaßt. 3. Aufl. Spektrum Akademischer Verlag, Heidelberg.

Rembold, U. et al. (1991): Einführung in die Informatik. 2. Aufl. Hanser, München.

Rembold, U. et al. (1990): Aufgaben zur Informatik. Hanser, München.

Schiffmann, W. und Schmitz, R. (1993): Technische Informatik 1. 2.Aufl. Springer, Heidelberg.

Tietze, U. und Schenk, C. (1990): Halbleiter-Schaltungstechnik. 9.Aufl. Springer, Berlin.

Beuth, K. (1992): Digitaltechnik. 9.Aufl.Vogel, Würzburg.

Urbanski, K. und Woitowitz, R. (1993): Digitaltechnik. BI-Wiss.- Verlag, Mannheim.

Morgenstern, B. (1992): Elektronik III, Digitale Schaltungen und Systeme. Vieweg&Sohn, Braunschweig.

Theoretische Informatik