GdI 2015-01-07

GdI 2015-01-07

Informatik-Thema heute: Komplexität, hier konkret als O-Kalkül; incl. Rück-Anbindung an Algorithmen in diesem Semester. Ein Standard-Thema; geguckt, wie machen das die Kollegen? Didaktisch schön sind z.B.:

Thema: anonyme Evaluation mit Moodle:

Übung

Recherchieren Sie die Algorithmen unter de.wikipedia.org/wiki/Landau-Symbole > Beispiele und Notation:

  • Worum geht es bei dem Algorithmus, wofür braucht man ihn?
  • Lässt seine Komplexität in der Praxis eine Implementierung erhoffen?
  • Wenn nicht: Welche Näherung ist in der Praxis erreichbar?

Lesen Sie in Gumm/Sommer in Kap 9.6 (S.765-780) nach, was die folgenden Begriffe bedeuten:

  • SAT
  • CLIQUE-Problem
  • TSP-Problem
  • NP-vollständig
  • P = NP ?

Ziel: Sie sollten eine Ahnung haben und in maximal 3 Sätzen erklären können, worum es bei der Abkürzung geht.