Informatik 3 Tutorium 13 & 15        Universität Karlsruhe      WS 2007/2008

David Münch      muenchdavid at gmail.com

VORSICHT: Die von mir erstellten Folien
koennen Fehler enthalten! (-> Mail an mich!)
Im Zweifel gilt immer das offizielle Skriptum!

Hier befinden sich die Folien zum Download:

Info3Tut1.pdf  31.10.2007  DEAs, NEAs, reguläre Ausdrücke

Tippfehler auf Folie Nr. 18 (bzw. 47): sollte eigentlich ((10)^m 0 1^m) heißen. Dann ex. auch kein m!
Formale Bezeichnung Aufgabe NEA wurde geändert.

Info3Tut2.pdf  07.11.2007  Übungsblatt 1, Potenzmengenkonstruktion, reg. Sprache -> NEA, epsilon-NEA -> NEA

Info3Tut3.pdf  14.11.2007  Übungsblatt 2, Pumping-Lemma, Automatenreduktion

Pumping-Lemma richtig in den Folien, aber falsch angesprochen im Tutorium.

Info3Tut4.pdf  21.11.2007  Übungsblatt 3, Nerode-Relation, Turingmaschine

Tippfehler Neroderelation und 5a wurden geaendert.

Info3Tut5.pdf  28.11.2007  Übungsblatt 4, Entscheidbarkeit

Info3Tut6.pdf  05.12.2007  Übungsblatt 5, Komplexitaetsklassen P und NP
UB5A2_update.pdf korrigierte Loesung der Aufgabe 2 vom 5. Uebungsblatt

Info3Tut7.pdf  12.12.2007  Übungsblatt 6, NP-Vollstaendigkeits-Beweise


Info3Tut8.pdf  19.12.2007  Weihnachtstutorium, Übungsblatt 7, weitere Komplexitaetsklassen
Loesung Blatt 7 Aufgabe 8 --> 2. http://www.csc.liv.ac.uk/~leslie/comp309/answersExtra.pdf
Loesung Blatt 7 Aufgabe 9 --> http://www.inf.fu-berlin.de/lehre/WS06/HA/skript/vorlesung25.pdf

Info3Tut9.pdf  09.01.2008  Übungsblatt 8, Approximationsalgorithmen

Info3Tut10.pdf  16.01.2008  Übungsblatt 9, Chomsky-0- und Chomsky-3-Grammatiken

Info3Tut11.pdf  23.01.2008  Übungsblatt 10, Chomsky-1- und Chomsky-2-Grammatiken, CYK, Chomsky-Normalform
Loesungsskizze zu Uebungsblatt 10: Seite 1, Seite 2

Info3Tut12.pdf  30.01.2008  Übungsblatt 11, Pumping-Lemma fuer kfG, entscheidbare Probleme fuer kfG

Info3Tut13.pdf  06.02.2008  Übungsblatt 12, Kellerautomaten, Greibach Normalform

Hinweis: Bitte konkrete Wuensche zur Klausurvorbereitung bis 09.02.08 per Email an mich schicken!
Info3Tut14.pdf  13.02.2008  Übungsblatt 13, Klausurwiederholung
Klausurwiederholung.pdf mit Loesungen

Tutorium Ende 13.02.2008.