Grundstudiumsvorlesung

Veranstaltungs-Nr.: 18.011 (WiSe 2004/2005)
Titel: Formale Grundlagen der Informatik 3 (F3)
Veranstalter:Manfred Kudlek
Zeit / Ort: 2 st. Di. 12-14 Phil A
-
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
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.
Stell. im Studienplan: Grundstudium
Voraussetzungen: F1, F2
Vorgehen: Vorlesung mit Übungen für Studierende der Wirtschaftsinformatik 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
Datenbank-Inhalt am 03.09.2004 um 17:18 Uhr KVV-Online