Vorlesung Theoretische Informatik für Studierende der Angewandten Informatik

Die Vorlesung Theoretische Informatik für Studierende der Angewandten Informatik ist im SoSe 12 inhaltlich gleich mit Grundbegriffe der theoretischen Informatik. Sie besteht wie die GTI aus zwei Teilen. Der erste Teil beschäftigt sich mit formalen Sprachen. Im Mittelpunkt stehen die regulären und kontextfreien Sprachen. Beide Sprachklassen sind fundamental für die Syntax von Programmiersprachen. Grob gesagt, korrespondieren reguläre Sprachen zum Scannen eines Programmtextes, also der Zerlegung des Zeichenstroms in einzelne Strings. Die kontextfreien Sprachen entsprechen dem Parsen, also der strukturellen Analyse des Programmtextes. Reguläre Sprachen lassen sich durch reguläre Ausdrücke spezifizieren (grep!), diese können in Algorithmen transformiert werden, die sich (außer einem Positionszeiger) nur konstant viel Information merken müssen: endliche Automaten. Die Bedeutung von regulären Sprachen und insbesondere von endlichen Automaten reicht jedoch sehr viel weiter. Endliche Automaten spielen beispielsweise in der Hardware- und Software-Verifikation eine große Rolle, oft unter dem Namen -Transitionssysteme-. Kontextfreie Sprachen können durch kontextfreie Grammatiken (oder auch Backus-Naur-Formen) spezifiziert werden und haben ebenfalls ein grundlegendes korrespondierendes Automatenmodell, die Automaten mit einem Pushdown-Speicher. Die Vorlesung gibt eine Einführung in die verschiedenen, jeweils äquivalenten Arten zur Beschreibung regulärer und kontextfreier Sprachen, untersucht Algorithmen zum Umgang mit solchen Sprachen, stellt ihre wichtigsten Eigenschaften dar, und betrachtet Anwendungen. Der zweite Teil der Vorlesung beschäftigt sich mit den wesentlichen Resultaten der Theorie von Algorithmen: dabei geht es vor allem um die beiden Fragen -was ist überhaupt algorithmisch berechenbar?- und -was ist -effizient algorithmisch berechenbar?-. Die erste Frage führt zur Berechenbarkeitstheorie, die zweite zur Komplexitätstheorie. In der Berechenbarkeitstheorie wird zunächst der Begriff des -algorithmisch berechenbaren- geklärt. Sodann wird gezeigt, dass konkrete algorithmische Probleme, wie z.B.: -haben zwei gegebene Programme bei jeder Eingabe dieselbe Ausgabe?- nicht algorithmisch lösbar sind. Die Komplexitätstheorie klassifiziert die algorithmisch lösbaren Probleme nach ihrem Ressourcenverbrauch, insbesondere hinsichtlich Laufzeit und Speicherbedarf. Die berühmteste offene Frage (der theoretischen und vielleicht der gesamten Informatik) ist die nach dem Verhältnis der Probleme, die in polynomieller Zeit gelöst werden können (z.B.: testen, ob ein gegebener Graph zusammenhängend ist) und denen, für die ein Lösungskandidat in polynomieller Zeit überprüft werden kann (wie z.B. ob eine gegebene Menge von Jobs auf einer gegebenen Menge von Prozessoren in einer gegebenen Zeit bearbeitet werden kann). Die bisher unbewiesene Vermutung ist, dass es Probleme der zweiten Art gibt, die nicht zugleich von der ersten Art sind, also keine polynomielle Lösung haben (also: zu testen, ob eine Zuordnung von Jobs zu Prozessoren korrekt ist, ist einfach, aber selbst eine zu finden, ist schwierig). Typisch für die theoretische Informatik ist, dass sie Phänomene aus der Informatik mathematisch modelliert und sich dadurch die Möglichkeit schafft, Aussagen (über die Modelle) zu beweisen. Ein Beweis liefert (idealerweise) mindestens zweierlei: die Sicherheit, dass die Aussage gilt und eine präzise Erklärung, warum sie gilt. Neben der reinen Darstellung von Fakten, soll in der Vorlesung insbesondere auch diese Denkweise vermittelt werden. Im Rahmen der Übungen und Tutorien wird spezifisch auf die Bedürfnisse der Studierenden der Angewandten Informatik eingegangen. Literatur Die Vorlesung orientiert sich stark an: E. Hopcroft, R. Motwani, J.D. Ullman, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson. Weitere empfehlenswerte Bücher: Schöning, U.: Theoretische Informatik - kurz gefasst. Spektrum Akademischer Verlag. Wegener, I.: Theoretische Informatik - eine algorithmenorientierte Einführung. Teubner. Im folgenden Buch werden wichtige Ideen der Vorlesung auf eine informellere Weise dargestellt, was für das Verständnis hilfreich sein kann, aber nicht den Inhalt der Vorlesung vollständig abdeckt. Wegener, I.(1996). Kompendium der Theoretischen Informatik - eine Ideensammlung. Teubner. Die angegebenen Bücher haben sich in den neueren Auflagen wenig geändert. Weitere Literaturhinweise erfolgen in der Vorlesung. Die Vorlesung orientiert sich stark an: E. Hopcroft, R. Motwani, J.D. Ullman, Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson. Weitere empfehlenswerte Bücher: Schöning, U.: Theoretische Informatik - kurz gefasst. Spektrum Akademischer Verlag. Wegener, I.: Theoretische Informatik - eine algorithmenorientierte Einführung. Teubner. Im folgenden Buch werden wichtige Ideen der Vorlesung auf eine informellere Weise dargestellt, was für das Verständnis hilfreich sein kann, aber nicht den Inhalt der Vorlesung vollständig abdeckt. Wegener, I.(1996). Kompendium der Theoretischen Informatik - eine Ideensammlung. Teubner. Die angegebenen Bücher haben sich in den neueren Auflagen wenig geändert. Weitere Literaturhinweise erfolgen in der Vorlesung. Lehrstuhl Informatik II Es werden Kenntnisse aus RS, DAP I und DAP II vorausgesetzt. Für die Anmeldung zur Modulprüfung wird aber nicht (!) der erfolgreiche Abschluss dieser Module vorausgesetzt. Technische Universität Dortmund SoSe 2012 Bachelor Angewandte Informatik Prof. Dr. Schwentick Thomas