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.:
- Folien 1-13, 17 aus http://cvpr.uni-muenster.de/teaching/ws08/info1WS08/script/Kapitel6-Complexity-1.pdf
- ggf. ergänzend ausschnittsweise Folie 1-22 aus http://www.inf.fu-berlin.de/lehre/SS12/ALP2/slides/V6_Rekursion_vs_Iteration_ALP2.pdf
-
ausführliche textuelle Erklärung:
http://www.linux-related.de/index.html?/coding/o-notation.htm
; daraus die Rechenregeln für den O-Kalkül:
- `c = O(1)`
- `c*f(n)=O(f(n))`
- `O(f(n))+O(f(n))=O(f(n))`
- `g(n)=a_k*n^k + a_(k-1)*n^(k-1) + ... + a_0 = O(n^k)`
- `O(f(n))*O(g(n))=O(f(n)*g(n))`
- `O(f(n))+O(g(n))=O(max{f(n),g(n)})`
Thema: anonyme Evaluation mit Moodle:
- Test-Eval; persönlich interessant für J.Busse: Bitte nehmen Sie sich 5 Minuten Zeit für Demo-Evaluation: Wer macht Musik? Danke!
-
Die echte Evaluation für GdI:
https://moodle.haw-landshut.de/mod/evaluation/view.php?id=23791
Ü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.