Info III, Tutorium 11, WS 05/06

Dies ist die Homepage zum Informatik III Tutorium 11 im Wintersemester 06/07 an der Universität Karlsruhe (TH).

Einen Übungsschein könnt ihr erwerben. Hierfür sind ⅓ der zu erreichenden Punkte sowohl vor als auch nach Weihnachten nötig (Die genaue Zahl steht noch nicht fest). Einen Klausurbonus wird es nicht geben.

Die Abgabe in Zweiergruppen (nur aus dem gleichen Tutorium!) ist erwünscht. Die bearbeiteten Übungsblätter sind, versehen mit Name(n), Matrikelnummer(n) sowie der Tutoriumsnummer, bis Freitag 09:45 Uhr in die Einwurfsschlitze im Keller des Informatik Neubaus zu werfen. Bitte achtet darauf dass eure Blätter zusamengetackert sind, sonst gibt es ein Durcheinander.

Begleitend zur Vorlesung gibt es außerdem eine Newsgroup in der diskutiert und Fragen gestellt werden können.

Neues…

Letztes Tut

Dienstag, 13.02.2007, 18:15 Uhr

So, das letzte Tut ist nun auch vorbei, und damit das Semester so gut wie beendet. Ich hoffe es hat euch auch ein Spaß gemacht, und ihr fandet den theoretischen Stoff nicht zu ätzend.

Falls ihr noch Fragen zur Klausur habt, könnt ihr mir gerne per Mail schreiben, ich versuche alles so schnell wie möglich zu beantworten. Die Übungsblatt Punktetabelle werde ich morgen Nachmittag an Herrn Käufl übermitteln, also überprüft am besten bis dahin nochmal im Online-Punktestand ob alles richtig ist. Ansonsten noch ein goßes Dankeschön an Adam Taras für die regelmäßigen Aufzeichnungen!

Blatt 12, Aufgabe 1

Dienstag, 30.01.2007, 19:15 Uhr

Ich wurde ja mehrfach gefragt wie die Aufgabe 1 auf dem aktuellen Übungsblatt zu verstehen ist.

Also es geht darum den Satz von Cook (Folien, Kapitel 3, 34ff) mal konkret zu belegen. Dabei betrachtet ihr die Turingmaschine aus der Aufgabenstellung (malt die euch am besten mal hin wie die aussieht), und konstruiert die zugehörige aussagenlogische Formel wie im Beweis des Satzes aus den Folien. Dabei müsst ihr nur die Teilformeln für AA, U¨1Ü_1, U¨2Ü_2 und EE angeben.

Am besten ihr macht euch zunächst erstmal klar, warum die Sprache der Turingmaschine in NP\mathcal{NP} ist, gebt danach an, welche Variablen zusttz,posti,bandtia\text{zust}_{tz}, \text{pos}_{ti}, \text{band}_{tia} vorkommen, und konstruiert schließlich die Teilformeln A,U¨1,U¨2,EA, Ü_1, Ü_2, E.

Für den Beweis, dass für die Eingabe ε\varepsilon eure konstruierte Formel nicht erfüllbar ist (also keine Variablenbelegung existiert, die die Formel zu wahr auswertet), geht ihr am besten insofern „händewedelnd“ vor, dass ihr zeigt welche Teilformeln wahr sein müssen, was daraus für andere Teilformeln folgt, und warum deshalb die ganze Formel FF nicht wahr sein kann.

Es existierte wohl außerdem ein Fehler auf den Vorlesungsfolien. Auf Folie 38 in Kapitel 3 muss für ii gelten −p(n)≤i≤p(n)+1-p(n) \leq i \leq p(n) {\color{red}+ 1}. Das +1+1 müsst ihr ggf. ergänzen, wenn ihr einen alten Ausdruck der Folien habt.

Frohe Weihnachten und einen guten Rutsch!

Mittwoch, 20.12.2006, 01:02 Uhr

Ich wollte allen nochmal einen guten Rutsch und frohe Weihnachten wünschen!

Ich hoffe, dass euch das Glühwein-Tutorium Spaß gemacht hat. Die Folien von dem Rautavistik-Vortrag von Julian könnt ihr hier runterladen, und die Bilder, die wir geschossen haben, gibt es hier.

Wir sehen uns dann wieder am 9. Januar 2007 an gewohnter Stelle :)

Glühwein Tutorium

Montag, 18.12.2006, 18:33 Uhr

Ich wollte nochmal daran erinnern, dass es morgen im Tutorium Glühwein geben wird! Ich werde den Glühwein mitbringen, aber bringt bitte Tassen selbst mit. Ihr seid natürlich herzlich eingeladen Freunde etc. mitzubringen, wir haben vermutlich eh viel zu viel Glühwein gekauft. :-)

Zur aktuellen Aufgabe 1 auf ÜB 4

Donnerstag, 23.11.2006, 16:58 Uhr

Auf dem aktuellen Übungsblatt ist ja nach einem deterministischen EA gefragt der alle Wörter aus Σ:={a,b,c}\Sigma := \{a,b,c\} akzeptieren soll, die mit einer durch drei teilbaren Anzahl an aas beginnen.

Das ist in dem Sinne zu verstehen, dass das längste Prefix des Wortes, das nur aus aas besteht durch drei teilbar sein soll. Das Wort aabaab beispielsweise soll abgelehnt werden.

Am besten ihr formuliert einen regulären Ausdruck der die gesuchte Sprache beschreibt, und modelliert euren Automaten danach. Dann sollte es nicht so schwierig sein.

Aufzeichnung des Tuts

Donnerstag, 16.11.2006, 18:30 Uhr

Die die vorgestern im Tut waren, wissen dass das Tutorium aufgezeichnet wurde. Die Aufzeichnung (Fotos + Ton) könnt ihr euch anschauen, in dem ihr unter Material auf „Aufzeichnung“ klickt.

Falls ihr mehr Infos zu den Aufzeichnungen wissen wollt, schaut am besten mal auf dieser Seite vorbei.

Aufgabe 2 auf Blatt 3

Dienstag, 14.11.2006, 19:29 Uhr

Ich wurde heute nach dem Tutorium noch gefragt, wie der „Hinweis“ in der Aufgabe 2 auf dem aktuellen Übungsblatt zu verstehen ist. Ich muss ehrlich sagen, ich verstehe ihn auch nicht, und ich sehe auch nicht was er für die Lösung der Aufgabe sagen soll.

Ich empfehle euch einfach über die Länge von xx eine Induktion zu machen, um so die Kürzungsregel zu beweisen.

Material von Heute

Dienstag, 07.11.2006, 21:20 Uhr

Die Lösungen zu den Aufgaben, die ich heute nicht mehr im Tutorium geschafft habe, findet ihr unter der Kategorie „Material“.

Willkommen in meinem Tut!

Montag, 23.10.2006, 19:01 Uhr

Schonmal herzlich willkommen an die, die sich in mein Tutorium eingeschrieben haben. Das erste Tutorium wird am 31. Oktober um 15:45 stattfinden.

Auf dieser Seite könnt ihr euch informieren welche Themen im Tut behandelt werden, und ich werde auch nützliche Materialien wie Aufgaben (die ich im Tut rechne) und Ähnliches online stellen. Außerdem findet ihr unter Links weitere Links, die vielleicht von Nutzem sein könnten.

Bis nächsten Dienstag!