Grundstudiumsvorlesung im WiSe 2003/2004
18.011 Formale Grundlagen der Informatik 3 (F3)

   Matthias Jantzen

2st. Di 12 - 14 Phil A
Lernziel:
In dieser Grundstudiums-Veranstaltung soll das theoretische Wissen über algorithmische Probleme und ihre Lösbarkeit vertieft werden. Analysetechniken für typische Algorithmen werden studiert, und es wird gezeigt, dass es neben lösbaren Problemen auch unlösbare Probleme gibt. Dazu muss der Algorithmenbegriff präzisiert werden. Es erfolgt eine Klassifikation der algorithmischen Probleme in leicht-lösbare und schwer-lösbare Probleme, und es werden die Grenzen des mit einem Computer Machbaren aufgezeigt. Kennenlernen von grundlegenden Konzepten und Methoden der Komplexitätstheorie.
Inhalt:
1. Probleme und Algorithmen:
  • Problemarten
  • der intuitive Algorithmen-Begriff
  • Beschreibungsformen von Algorithmen
  • Entwurfs-Techniken für Algorithmen
  • Analyse von Algorithmen: Laufzeitverhalten, Effizienz, Korrektheit
  • Leicht-lösbare und schwer-lösbare Probleme
  • Konkrete Algorithmen für Suchen, Sortieren, Graphen
  • Datenstrukturen: Listen, Stapel, Warteschlangen u.a.
2. Berechenbarkeit:
  • Berechenbare und nicht-berechenbare Probleme
  • Präzisierung des Algorithmen-Begriffs:
    • primitiv-rekursive und allgemein-rekursive Funktionen
    • Turingmaschinen
    • Registermaschinen
  • das Halteproblem und andere unentscheidbare Probleme
3. Komplexitätstheorie:
  • Darstellung von Problemen als Mengen
  • Platz- und Zeitkomplexitätsklassen
  • Speed-up-Sätze
  • Reduktionsbegriff
  • NP-Vollständigkeit
4. Höhere Grammatiken:
  • Chomsky-Typ-0 und Typ-1-Grammatiken
  • Normalformen
  • Chomsky-Hierarchie
Stell. im Studienplan:
Grundstudium
Voraussetzungen:
F1, F2
Vorgehen:
Vorlesung mit Übungen für Studierende der Wirtschafts-Informatik und einiger Studiengänge an der TUHH
Literatur:
Vorlesungsbegleitendes Skript,
Hopcroft/Ullman: Introduction to Automata Theory, Languages, and Computation (Addison-Wesley, 1979)
Robert Sedgewick: Algorithmen (Addison-Wesley 1992)
D.C. Kozen: The Design and Analysis of Algorithms (Springer-Verlag, 1992)
Brassard/Bratley: Algorithmik: Theorie und Praxis Attenkirchen (Wolfram, 1993)
K. Ruediger Reischuk: Komplexitätstheorie, Bd. I: Grundlagen (B.G. Teubner, 1999)
I. Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung (B.G. Teubner, 1999)
I. Wegener: Komplexitätstheorie (Springer-Verlag, 2003)
Periodizität:
jährlich zum WS
Eignung:
Geeignet für Lehramtsstudierende, Nebenfachstudierende, Bioinformatikstudierende, Wirtschaftsinformatikstudierende.
Stichworte:
Datenstrukturen, Algorithmus, Entwurf von Algorithmen, Analyse von Algorithmen, Berechnungsmodelle, Komplexität von Problemen und Algorithmen