Theoretical Foundations of Computer Science
Vorlesung: Grundzüge der Informatik A3
|
|
|
|
|
Veranstaltungsnummer: 18.005 / 18.006 (Übungen) / 18.903 /Tutorium)
Titel: Grundzüge der Informatik A3
Veranstalter: Rüdiger Valk
Ort und Zeit:
Di 10-12 Audi I und Fr 10-12 Audi II.
Dazu gehören 2-std. Übungen n.V. (10 Gruppen) und ein Tutorium
(4 Gruppen).
Lernziel:
Kennenlernen und Vertrautwerden mit grundlegenden formalen Konzepten und Methoden, die für fast alle Teilgebiete der Informatik wichtig sind. Erwerben und Einüben der Standardhilfsmittel für Beschreibung, Analyse, Entwurf und Bewertung von Problemen und deren Lösung.
Inhalt:
- Denkmethoden und ihre Formalisierung
- Formalisierung von Sachverhalten, Problemen, Zusammenhängen, Methoden zur Spezifikation von Algorithmen, Regeln des vernünftigen Schlußfolgerns, Aussagenlogik und Prädikatenlogik.
- Probleme der Textverarbeitung
- Formale Beschreibung von Texten, Erzeugung, Änderung und Prüfung der syntaktischen Korrektheit, Einführung in Syntaxanalyse und Compilerbau, Kontextfreie Grammatik, Einführung in die Theorie formaler Sprachen, speziell Chomsky-Hierarchie.
- Automaten, Maschinen, Petrinetze
- Methoden zur Erkennung und Übersetzung formaler Sprachen: Endliche Automaten, Kellerautomaten und Turingmaschinen. Klassifikation der formalen Sprachen durch Automaten. Vergleich mit Chomsky-Grammatiken. Deterministische, nichtdeterministische Arbeitsweise, Petrinetze. Aufwand, Komplexität, Effizienz Bewertung von Algorithmen und Verfahren hinsichtlich der Zeit und des Platzes, den sie bei ihrer Ausführung im ungünstigsten Fall benötigen.
- Absolute Grenzen (prinzipiell nicht mögliche Verfahren) und durch den
- Aufwand bestimmte Grenzen. Einführung in die Komplexitätstheorie. Rekursive Funktionen, Entscheidbarkeit und Berechenbarkeit Algorithmusbegriff, Turing'sche These, aufzählbare versus entscheidbare Mengen und ihr Zusammenhang zu Turingmaschinen bzw. Programmiersprachen. Primitiv rekursive Funktionen im Vergleich dazu. Unentscheidbare Probleme: Halteproblem bei Turingmaschinen.
Voraussetzung: Teilnahme an den Übungen
Stellung im Studienplan: Für 3. Semester, Stoff für die Vordiplomprüfung "Informatik".
Literatur:
- Bergmann/Noll: Mathematische Logik mit Informatik-Anwendungen (Springer)
- Hopcroft/Ullman: Introduction to Automata Theory, Languages, and Computation (Addison-Wesley)
- Peters: Einführung in mathematische Methoden der Informatik (BI)
- Sander/Stucky/Herschel: Automaten, Sprachen, Berechenbarkeit (Teubner 1992)
- Schöning: Theoretische Informatik - kurz gefasst (BI 1992)
- Schöning: Logik für Informatiker (BI 1989) und andere Bücher.
- Zur Vorlesung wird ein Skript verteilt.
Für LehrerInnen / NebenfächlerInnen mit mathematischem Interesse geeignet.
Last Change: 17:40 05/19/2011 Imprint/Disclaimer