Zur Seitennavigation oder mit Tastenkombination für den accesskey-Taste und Taste 1 
Zum Seiteninhalt oder mit Tastenkombination für den accesskey und Taste 2 
Prüfungsnummer 65600
Studiengang [079] - Informatik
Prüfungsversion [-1] - besondere Verarb.
Abschnitt [G] - Grundstudium
Kurztext FMI-IN0160
Drucktext Komplexitätstheorie LAB
Pflichtkennzeichen [WP] - Wahlpflichtfach
Prüfungsform [G] - generiert
Prüfungsart [MO] - Modul
Art der Notengebung [G] - Berechnung nur m. 1 NachK
Inhalt und Qualifikationsziel

Algorithmische Begleitung der Vorlesung Komplexitätstheorie; Prototyp-Implementierungen von Algorithmen und Konzepten aus der Komplexitätstheorie:

  • Simulation von Rechenmodellen: Turing-Maschinen, Schaltkreise etc.
  • Hornformeln
  • 2-KNF
  • Erreichbarkeit in Graphen
  • Flüsse in Graphen
  • Experimente zur Laufzeit schwerer Probleme
  • Reduktionen zwischen NP-vollständigen Problemen
  • Testen der Reduktionen zur Lösung schwerer Probleme mit SAT- und QBF-Solvern
Lehr- und Lernformen

4 Ü

Voraussetzungen für die Teilnahme

keine

Voraussetzungen für die Vergabe von Leistungspunkten

Klausur oder mündliche Prüfung (Festlegung erfolgt zu Beginn des Moduls)

Impressum | Datenschutzerklärung