Übungsblatt 13 - SAT

Hier könnt ihr euch über die Inhalte der Übungsblätter austauschen und Fragen stellen.

Übungsblatt 13 - SAT

Beitragvon cmw » 17 Mär 2014, 20:55

Hallo zusammen,

auf dem Übungsblatt 13 gibt es zwei Aufgaben zum Thema NP - Vollständigkeit (A10 und A11). Diese decken jedoch bei Weitem nicht den Stoff von Schönings Kapitel 3 ab, welches ja komplett dem Übungsblatt zugeordnet ist. Gilt nun für die dritte Klausur
a) die gleiche Beschränkung "nach oben" wie in der zweiten Klausur ("Auch den letzten Vorlesungsteil über NP-Vollständigkeit werden wir nicht prüfen")
b) der gesamte Aufgabeninhalt von Übungsblatt 13 wird geprüft
oder c) das vollständige Kapitel 3 ist noch Teil der Klausur, d.h. wir müssen auch Reduktionen von SAT / 3SAT auf andere Probleme zeigen können?

Vielen Dank schonmal für die Antwort!

LG,
cmw
cmw
 
Beiträge: 1
Registriert: 22 Okt 2013, 08:14

Re: Übungsblatt 13 - SAT

Beitragvon jkaiser » 18 Mär 2014, 15:52

Wir habe in den letzten zwei Vorlesungen kurz über Reduktionen gesprochen, insbesonder über SAT, 3SAT, ... und dabei angerissen wie genau man von einem Problem zum nächsten reduziert. Die Reduktionen hier wurden jedoch nicht im vollen Umfang ausgearbeitet. Folglich sind die Reduktionen auf diesem intuitiven Level durchaus prüfbar, ebenso wie die Inhalte aller gestellten Übungsaufgaben zu diesem Thema.
jkaiser
 
Beiträge: 17
Registriert: 13 Okt 2013, 16:50


Zurück zu Übungsblätter

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron