Vorlesung Übung Theoretische Informatik Formale Sprachen

In dieser Vorlesung wird in das unbedingt notwendige Grundwissen aus dem Bereich der Theoretischen Informatik eingeführt, das als Grundlage für viele Gebiete der praktischen und der technischen Informatik dient. Dabei werden die folgenden drei Gebiete angesprochen: (1.) Formale Sprachen und Automaten Eine formale Sprache ist eine Menge von (endlichen) Zeichenketten (Wörtern) über einem endlichen Zeichenvorrat (Alphabet). Jede Programmiersprache ist etwa eine solche formale Sprache. Welche Formalismen sind entwickelt worden, um formale Sprachen zu beschreiben? Es werden verschiedene Arten von Grammatiken betrachtet, wobei eine Grammatik ein formales System ist, das beschreibt, wie die Elemente einer Sprache erzeugt werden. Komplementär hierzu werden dann Klassen von Automaten entwickelt, die genau die Sprachen einer bestimmten Art akzeptieren. (2.) Berechenbarkeitstheorie Welche Funktionen sind überhaupt berechenbar, d.h., für welche Funktionen gibt es überhaupt Algorithmen, um sie zu berechnen? Zur Beantwortung dieser Frage braucht man einen formal fundierten Algorithmusbegriff. Hierzu gibt es viele verschiedene Ansätze, die aber alle letztendlich zueinander äquivalent sind, was zur sogenannten Churchschen These geführt hat. Insbesondere stellt es sich heraus, dass es Funktionen gibt, die nicht berechenbar sind, und es Probleme gibt, die nicht algorithmisch gelöst werden können. Beispiele solcher Probleme werden in der Vorlesung behandelt werden. (3.) Komplexitätstheorie Hier stellt man die Frage nach den notwendigen Ressourcen für die algorithmische Lösung eines Problems, wobei man insbesondere nach dem erforderlichen Bedarf an Rechenzeit oder Speicherplatz fragt. Hier zeigt sich, dass es Probleme gibt, die zwar prinzipiell algorithmisch gelöst werden können, die aber dennoch praktisch unlösbar sind. Zentral sind in diesem Bereich das bisher ungelöste P-NP-Problem und der Begriff der NP-Vollständigkeit. Uwe Schoening, Theoretische Informatik - kurzgefasst. Spektrum Akademischer Verlag Heidelberg/Berlin, 4. Auflage 2001, ISBN 3827410991 Ergänzende Literatur: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. ISBN 3486254952 VoraussetzungenGrundkenntnisse in der Mathematik und in der Programmierung LeistungsnachweisErfolgreiche Teilnahme an den Übungen und Bestehen der Abschlussklausur FB 16 Elektrotechnik / Informatik Uni Kassel WS 2006/2007 Informatik Mathematik Prof. i.R. Dr. rer. nat. Werner Heinrich i.R rer nat