Abteilung Formale Konzepte

Universität Stuttgart
Institut für Informatik
Breitwiesenstr. 20/22
D-70565 Stuttgart
 Lageplan
Stadtplan
Abteilung
Institut
Fakultät
Universität

Vorlesung: Theoretische Informatik III (swt)

Grundvorlesung
Vorlesung3V+1Ü
Dozenten:Claus
Schmid
Termine:Mo08:30 bis 10:00im V20.02Vorlesung
Fr 8:30 bis 10:00im V20.02Vorlesung/Übung

Übungsblätter


  • Übungsblatt 2 (ps),
  • Übungsblatt 3 (ps),
  • Test 1 (ps),
  • Übungsblatt 4 (ps),
  • Übungsblatt 5 (ps),
  • Übungsblatt 6 (ps),
  • Test 2 (ps),

    Beschreibung

    Geplanter Aufbau (nach Wochen aufgelistet, Feiertage sind hier noch nicht berücksichtigt):

    Teil A: Effiziente Algorithmen
    1. Algorithmen: Beispiele, Analyse
    2. Algorithmenentwurfsverfahren: Übersicht, Beispiele


    Teil B: Komplexitätstheorie
    3. Wiederholung: det. und nichtdet. Turingmaschinen, Modell der Registermaschine
    4. Komplexitätsklassen, Beispiele, Konstanten, die Klasse P, einfache Sätze
    5. Reduktionsbegriff, die Klasse NP: NP-hart, NP-vollständig, SAT, 3SAT, Färbbarkeit, Erreichbarkeit bei B/E-Netzen
    6. Spezielle Algorithmen und ihre Einordnung in Klassen


    Teil C: Semantik
    7. Transitionssysteme, Beschreibung mit Regeln (Grammatik, Übergangsrelation, Inferenzen), Reduktionssysteme, Normalformen, Eigenschaften, IMP
    8. Operationale Semantik
    9. denotationelle Semantik,Fixpunkte, Beispiele
    10. Vor- und Nachbedingungen, axiomatische Semantik


    Teil D: Weiterführendes
    11. Parallele Berechnungsmodelle und ihre Auswirkung auf die Komplexität (PRAM mit Konfliktbehandlung), Wegeberechnungen
    12. Spezielle Algorithmen (z.B. aus den Bereichen Zuordnungen, Stundenplan, Verkehrsprobleme, Kryptographie)

    Voraussetzungen

    Einführung in die Informatik II, Theorie I und II für Softwaretechnik und Höhere Mathematik I und II.

    Literatur

    k.A.