Vorwort

Diese Arbeit ist im Rahmen meiner Bachelorarbeit angefertigt worden. Sie enthält drei Videos aus dem Bereich der NP-Schwere bzw. NP- Vollständigkeit. Über die Videos wurde auch ein Blogpost im tu digit Praxisblog veröffentlicht.


Video 1

In der ersten Lehreinheit steht die Vermittlung von Grundlagen im Mittelpunkt. Dies ist notwendig, da die Hörer von TheGI 2 zum Teil noch nicht alle benötigten Grundlagen kennen. Die Grundlagen müssen an dieser Stelle vermittelt werden, da die genutzten Beispiele auf dem Grundlagenwissen aufbauen. Die Beispiele sind jedoch so gewählt, dass nur eine kurze Zusammenfassung der Grundlagen nötig ist um die Inhalte nachvollziehen zu können. Durch die Zusammenfassung der Grundlagen sind die Videos auch außerhalb von TheGI 2 nutzbar, gleichwohl die Videos für TheGI 2 Hörer und vorlesungsergänzend konzipiert sind. Das Grundlagenwissen wird in Lehreinheiten 2 und 3 benötigt.

Video zum Download (LE1_Grundlagen.mp4, 74M)


Video 2

In Lehreinheit 2 geht es um den Begriff der Reduktion. Hierfür wird am Beispiel WM2-Sat auf Vertex Cover reduziert. Außerdem wird neben der Definition der Reduktion auch auf die Korrektheit, die Transitivität und die Zeitkomponente von Reduktionen eingegangen.

Video zum Download (LE2_Reduktion.mp4, 115M)


Video 3

In der letzten Lehreinheit werden die Komplexitätsklassen P und NP eingeführt und aufbauend darauf die NP-Schwere und die NP-Vollständigkeit definiert. Neben dem P =? NP Problem und weiteren Reduktionen werden mehrere NP-schwere Probleme vorgestellt.

Video zum Download (LE3_NP_Schwere.mp4, 164M)


Präsentation

Für eine Präsentation im Tutorium habe ich noch eine LaTeX Beamer Präsentation erstellt die im Schnelldurchlauf das Problem P =? NP motiviert. Die Folien allein sind nicht selbsterklärend. Mit dem Wissen aus den Videos können die Folien benutzt werden um anderen das Problem P =? NP zu erläutern. Sowohl die PDF-Folien als auch die Quellen sind unter dem Bild als Download verfügbar.

Beamer Präsentation

Präsentation zum Download (Komplexitaet_Jungnickel.pdf, 230K) Quellen


cc-by-sa