Die mit "vorab" gekennzeichneten Dateien werden nach der jeweiligen Vorlesung gelöscht. Die tatsächlich in der Vorlesung gezeigten Folien können geringfügig davon abweichen, insbesondere wenn Fehler zu korrigieren sind oder Folien mit einer Übersicht/Wiederholung eingefügt werden. Diese Änderungen werden hier nicht näher erläutert. Falls Änderungen an den nicht mit "vorab" gekennzeichneten Folien nötig sind, werde ich diese hier genauer erklären. Um die korrigierten Versionen zu lesen, ist es eventuell erforderlich, den Cache des Browsers zu löschen. Alle pdf-Dateien sollten von acroread korrekt angezeigt werden. Dagegen werden z.B. bei kpdf oder xpdf Formeln nicht richtig angezeigt. Wer (was erstaunlicherweise vorkommt) acroread nicht benutzen kann, kann sich auch die Folien mit pdf2ps (in den gängigen Linux-Distributionen und z.B. MikTeX enthalten) in Postscript konvertieren. Änderungen und Korrekturen - Die Folien 220-222 aus der Vorlesung am 10.5. wurden auch am 12.5. gezeigt, so dass ich sie aus der "gti-2005-10-05.pdf" entfernt habe. Dabei wurden die Definitionen auf Folie 222 (jetzt Folie 223) etwas präzisiert. - Folien 502 und 503: Die Schlussregeln mussten modifiziert werden, um z.B. die folgede Situation korrekt zu handhaben. Es könnte vorkommen, dass die gegebene TM gestartet auf q_0w_1...w_n nicht akzeptiert (also w_1...w_n) verwirft, aber auf q_0Bw_1...w_n akzeptiert (was eigentlich irrelevant ist, da dies keine korrekte Startkonfiguration ist). Dies führt aber dazu, dass bei der vorher angegebenen Grammatik das Zwischenergebnis Lq_0Bw_1...w_nR aus S herleitbar war und hieraus w_1...w_n, obwohl die die TM w_1...w_n nicht akzeptiert. Mit den neuen Schlussregeln (und den zusätzlichen Variablen X und Y) wird überprüft, ob die durch das Rückwärtsrechnen erzeugte Konfiguration wirklich eine Startkonfiguration beschreibt. - Beim Beweis vom Ogden's Lemma fehlte auf Folie 568 das Argument, dass man nach der letzten Variablen sucht, die auf _Verzweigungsknoten_ doppelt vorkommt, also auf Knoten, bei denen in beiden Teilbäumen markierte Buchstaben vorkommen. - Folie 669: Die Folie wurde etwas umformuliert und insbesondere sind jetzt die Fälle m=0 und m>0 unterschieden, da bei m=0 der Allquantor vor dem q_{m+1} nicht "passt". Letzte Änderung: 19.7.2005 ----------------------------------------------------------------------- Fehler, die erst später auffallen, werden im Folgenden aufgeführt, aber nicht in den pdf-Dateien korrigiert. 2.1.2006, Folie 571: In der vorletzten Zeile muss "y" durch "x" ersetzt werden. 26.4.2006, Folie 154: In der drittletzten Zeile muss der Index l-2 von \bar{y} durch l-3 ersetzt werden. 16.10.2006, Folien 168-171: In der Vorlesung wurde (ohne dass es auf den Folien explizit erwähnt wird) argumentiert, dass jeder Hamiltonkreis in dem konstruierten Graphen die folgende Form haben muss: Wenn es in dem Hamiltonkreis eine Kante von dem Knoten v in der x_i-Komponente zum Knoten für C_j gibt, muss dieser Hamiltonkreis mit einer Kante vom Knoten für C_j zum Partner von v in der x_i-Komponente fortgesetzt werden; insbesondere führt die Kante vom Knoten für C_j nicht in die Komponente für eine andere Variable. Für die in der Vorlesung beschriebene Konstruktion trifft dies leider nicht zu, worauf Gereon Bartel mich dankenswerter Weise hingewiesen hat. Ein Beispiel, das dies zeigt, findet sich unter http://ls2-www.cs.uni-dortmund.de/lehre/sommer2005/gti/dhc1.ps (In dem Beispiel ist ein solcher Hamiltonkreis blau eingezeichnet. Weiterhin enthält jede Klausel abweichend von der auf den Folien angegebenen Reduktion nur zwei Literale; dies genügt aber, um den Fehler in der Argumentation zu zeigen.) Korrektur: Es genügt, zwischen den Paaren von zusammengehörenden Knoten in den doppelt verketteten Listen einen weiteren Knoten einzufügen, der keine Verbindungen zu Klauselknoten hat, vgl. http://ls2-www.cs.uni-dortmund.de/lehre/sommer2005/gti/dhc2.ps Die Knoten v_1 und v_4 (und analog weitere Knoten) sind nun nur in der doppelt verketteten Liste enthalten und haben keine Verbindungen zu weiteren Klauselknoten. Wenn es nun einen Hamiltonkreis in dem so konstruierten Graphen gibt, muss gelten, dass der Weg von v zu einem Klauselknoten am Partner von v fortgesetzt wird. Dies kann man leicht mit den Knotennamen im Bild erklären: - Wenn der Hamiltonkreis die Knotenfolge v_1, v_2, C_j enthält und von dort nicht zu v_3 zurückgegangen wird, kann v_3 nicht auf dem Hamiltonkreis liegen. Widerspruch. - Wenn der Hamiltonkreis die Knotenfolge v_4, v_3, v_2, C_j enthält, kann v_1 nicht mehr auf dem Hamiltonkreis liegen. Widerspruch. (Dieser zweite Fall fehlte in dem alten Korrektheitsbeweis.) 3.5.2007, Folie 244: Ergänze "a_i" hinter dem Summenzeichen.