TGI

• Heimatseite
• Ankündigungen
• Mitarbeiterinnen und Mitarbeiter
• Studentinnen und Studenten

Lehre

• Lehre

Forschung

• Forschung
• Publikationen

Misc

• Service
• Tools
• Petri Nets World
  

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