Ein paar administrative Sachen vorweg. Erstens, Evaluation läuft noch bis siebter, siebter,

nehmen Sie Teil. Wer noch keine TAN hat, ich habe noch welche. Zweitens, Schein- und Bonusregelung.

Mit Blick auf die Statistik. Normalerweise würde man hier ansetzen 50 Prozent der Punkte,

wir verschieben das ein bisschen zwischen den beiden Punktesorten. Das heißt, es werden nur

40 Prozent der Individualpunkte verlangt, dafür 60 Prozent der Gruppenpunkte. Das wäre das Erste,

wie gesagt, das mit Blick auf die aktuell erzielten Quoten. Naja, das erkennen Sie daran,

dass Sie ja eine Aufgabe als für sich individuell markiert haben und die Punktezahl auf

Sie haben ja, Sie haben ja immer drei Aufgaben und Sie markieren eine davon typischerweise als

von Ihnen individuell gelöst oder so und für diese Aufgabe kriegen Sie Individualpunkte und

für die anderen Aufgaben, die nach der Theorie zumindest die anderen gelöst haben, kriegen Sie

Gruppenpunkte. Naja, so viele wie es auf die Orte gibt, es gibt keine einzelnen, bepunkteten Aufgaben.

Genau, ja. Naja, Sie kriegen ja aber pro Aufgabe nur eine Sorte Punkt. Ja, Sie kriegen ja auch pro

Aufgabe jeweils nur, ach so, jetzt verstehe ich. Die Anzahl der Gruppenpunkte, die man bekommt,

es gibt glaube ich eine einfache Formel für die Anzahl Gruppenpunkte und zwar ist das Max von

der dastehenden Zahl und 5 glaube ich. Nicht Max, Min von der dastehenden Zahl und 5. Ich werde Herrn

Gorin anregen, dass er mal Statistiken rausgibt. Also er hat das ja alles irgendwo in einer großen

Excel-Tabelle, er kann Sie darüber informieren. Also machen Sie das nur, wenn Sie Zweifel haben,

ob Sie dieses Kriterium erfüllen. Ja, also wir haben das schon so ausgelegt, dass das also nur

die wenigsten betreffen sollte. Gut, so das ist einmal zu Thema Schein und dann zum Thema

Bonuspunkte. Es gibt ja am Ende maximal 90 Individualpunkte, jedenfalls, nein, also stimmt

nicht ganz, also 100 Prozent der Individualpunkte liegen bei 90 Punkten. Es gibt ja ein Blatt noch,

was da nicht mehr zuzählt und für 80 von diesen 90 Punkten gibt es Bonus 1,0 auf die Klausur und

das zählt sich dann in Schritten von 3 runter. Also bei 77 Punkten gibt es 0,9 und das rechnet sich

runter, sodass es aufhört. Ich hoffe, ich habe mich nicht verrechnet bei 53, da gibt es dann noch 0,1.

Naja, haben oder nicht haben. Die Klausurnote wird ja zunächst mal als Krummezahl berechnet,

also auch ein Bonus von 0,1 kann einem noch helfen. Und zwar, wie gesagt, das ist also alles nur aus

den Individualpunkten. Die Gruppenpunkte gehen da gar nicht ein, nein. Wenn Sie auf die Statistik

der Gruppenpunkte sehen, dann wissen Sie warum. Also Gruppenpunkte sind üblicherweise nicht das

Problem. Gut, ja noch weitere Fragen dazu. Gut.

Ja, ok zurück zum Material. Gut, letzte Woche haben Sie sich mit Hangurin vertragen,

haben Sie Fragen zum Material letzter Woche. Alle glücklich? Gut.

Vollständigkeit, also Vollständigkeit im Sinne von vollständige Probleme für

gegebenen Problemklassen. Ein solches Problem kennen Sie schon aus BFS, da wurde gezeigt,

SAT ist vollständig für NP. Wir machen heute die gesamte Stunde nur das, was man allgemein

Abstract Nonsense nennt. Also Sie sehen keine nicht trivialen Algorithmen, also ich schreibe

einen Algorithmus irgendwann mal an, aber der ist also voll trivial. Es gibt also nur abstrakte

Begriffe und hin und her täuschen auf sehr trivialer Ebene mit diesen abstrakten Begriffen.

Ein solch recht abstrakter Begriff ist der der Reduktion, na gut das ist fast noch das

konkreteste, was wir heute machen. Also die Idee an Reduktion ist, ja das was man sich

denkt, ja ich habe ein Problem schon gelöst und ich reduziere ein anderes darauf. Und das

heißt im Falle von Programmieren eben, ich habe schon mal ein Programm für ein Problem

geschrieben und ich habe jetzt ein anderes Problem und ich reduziere dieses andere Problem

auf das, was ich schon mal ausprogrammiert habe. Was muss ich dazu tun? Ich programmiere

eine Reduktionsfunktion, so genauer sollte ich sagen, eine Reduktionsfunktion auf Bitstrings,

das heißt also eine die Bitstrings in andere Bitstrings übersetzt, heißt im Allgemeinen

natürlich die Probleminstanz für ein Problem in Instanzen eines anderen Problems übersetzt.

Das dient uns ja nur dazu komplizierte Daten wie Grafen oder Zahlen oder was weiß ich was

zu kodieren. So, also ich programmiere eine solche Reduktionsfunktion mit folgender Eigenschaft,

x ist in D genau dann, wenn fx in C ist. Wir erinnern uns ein Problem ist ja nichts als

eine Menge von Bitstrings oder wenn man will eine zweiewertige Funktion, eine wahr falschwertige