SoSe 2010 » Formale Grundlagen der Informatik I + II
Prof. Dr. Otto

ÜbersichtSynopsisSkriptÜbungenFolien

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