SoSe 2010 » Formale Grundlagen der Informatik I + II
Prof. Dr. Otto
Synopsis
Formale Grundlagen der Informatik
Diese Veranstaltung im Format (4+2) besteht aus zwei Teilen:
Formale Grundlagen der Informatik I: Automaten und Formale Sprachen
Formale Grundlagen der Informatik II: Logik in der Informatik
Synopsis: Formale Grundlagen der Informatik I
Automatentheorie und formale Sprachen bieten einen
Einstieg in mathematische Grundbegriffe und elementare
Techniken und Konzepte der theoretischen Informatik.
Neben allgemeinen ersten Grundbegriffen der diskreten Mathematik
und mathematischer Methodologie befasst sich die Vorlesung
inhaltlich mit endlichen Automaten (Systeme mit endlicher
Zustandsmenge) und mit der Klassifikation formaler Sprachen
(Eigenschaften von Zeichenreihen; Syntax).
Die Untersuchung einer Hierarchie von formalen Sprachen
anhand unterschiedlicher Beschreibungsformalismen
liefert einen Einblick in Beziehungen zwischen
syntaktischen, deskriptiven und prozeduralen Sichtweisen fuer
die Spezifikation von Syntax.
Inhalt (FGdI I):
Mathematische Grundbegriffe und elementare Beweistechniken.
Endliche Automaten und regulaere Sprachen;
Determinismus und Nichtderterminismus,
Abschlusseigenschaften und Automatenkonstruktionen;
Saetze von Kleene, Myhill-Nerode und Pumping Lemma.
Grammatiken und die Chomsky-Hierarchie;
kontextfreie Sprachen, Abschlusseigenschaften,
Pumping Lemma, CYK Algorithmus.
Berechnungsmodelle: Kellerautomaten, Turingmaschinen;
Entscheidbarkeit und Aufzaehlbarkeit in der Chomsky-Hierarchie
Synopsis: Formale Grundlagen der Informatik II
Die mathematische Logik stellt einerseits die Basis fuer einige
der fundamentalen Konzepte der theoretischen Informatik bereit
und hat andererseits (auch ganz aktuell) grosse praktische
Bedeutung, z.B. in den Bereichen Verifikation, Wissensrepraesentation,
Datenbanken.
In dieser einfuehrenden Vorlesung werden typische logische Begriffe,
Methoden und Resultate im Rahmen der Aussagenlogik und im Rahmen der
Logik erster Stufe vorgestellt.
Neben den Grundbegriffen zu Syntax und Semantik stehen syntaktische
Beweiskalkuele und ihre algorithmische Bedeutung im Vordergrund.
Inhalt (FGdI II):
Syntax und Semantik der Aussagenlogik,
semantische Grundbegriffe;
funktionale Vollstaendigkeit und Normalformen;
Kompaktheitssatz der Aussagenlogik;
vollstaendige Beweiskalkuele: Resolution
und ein Sequenzenkalkuel.
Syntax und Semantik der Logik erster Stufe, Strukturen unmd Belegungen;
Normalformen und Skolemisierung;
der Satz von Herbrand und der Kompaktheitssatz der Logik erster Stufe;
vollstaendige Beweiskalkuele: Resolution (insbesondere
Grundinstanzenresolution) und ein Sequenzenkalkuel;
der Goedelsche Vollstaendigkeitssatz;
Unentscheidbarkeit (Satz von Church-Turing).
Literatur
Skripte zur Vorlesung sind auf der Webseite der Veranstaltung verfuegbar.
Dort werden auch weitere Literaturempfehlungen angegeben.
(Siehe auch links von http://www2.mathematik.tu-darmstadt.de/~otto/ )
Literaturempfehlungen zu FGdI I
U.Schöning: Theoretische Informatik - kurzgefasst, Spektrum, 4. Aufl., 2001.
I.Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, Teubner, 1999.
J.Hopcroft, R.Motwani, and J.Ullman: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2nd ed., 2001.
Literaturempfehlungen zu FGdI II
Burris: Logic for Mathematics and Computer Science, Prentice-Hall 1998.
Ben-Ari: Mathematical Logic for Computer Science, Springer 1993.
Schoening: Logik für Informatiker, Spektrum 2000.
Boolos, Burgess, Jeffrey: Computability and Logic, 4th ed., Cambridge University Press 2002
Impressum | Datenschutzerklärung