Grundzuege der Informatik A3
Veranstaltungsnummer:
18.005
Titel:
Grundzüge der Informatik A3
Veranstalter:Matthias Jantzen
Zeit und Ort:
Di. 10-12 ESA B, Fr. 10-12 Erzw Hörs., Beginn: Di. 21.Okt.
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,
Grundlagen der Logikprogrammierung.
- 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 und Maschinen: 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.
- 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.
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.
Stellung im Studienplan: Grundstudium,
3. Fachsemester, Stoff für die Vordiplomprüfung
Voraussetzungen: Teilnahme an den Übungen
Vorgehen: Vorlesung mit 2-std. Übungen,
Vorl.-Nr. 18.006, und ein Tutorium mit vier 1-std. Gruppen. Zur
Vorlesung wird ein Skript verteilt, das abschnittsweise über die
Übungsgruppen erhältlich sein wird.
Ein neuer Aufgabenzettel
wird jeden Dienstag in der Vorlesung verteilt.
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 gefaßt, 2. Aufl. (Spektrum Akad.
Verlag Heidelberg, Berlin,
1995)
Schöning: Logik für Informatiker 4. Aufl. (Spektrum Akad. Verlag
Heidelberg, Berlin,
1995)
Periodizität: jährlich
Eignung: Für Lehrer und Nebenfächler geeignet
Stichworte: vergl. Inhaltsangabe
Letzte Änderung: 17:40 19.05.2011
Impressum