• Home
• Theorie
  • Potenzmenge
  • Unendlichkeit der Primzahlen
  • Euler-Formel
  • Diagonalsprache
  • O-Kalkül
  • wp-Kalkül
  • Informationstheorie
  • Schnelle Fourier Transformation
  • Diskrete Kosinus Transformation
• Praxis
  • Huffman Kodierung
  • Primzahlen TM
• Aufschriebe
  • Papers
  • Mathematik
• Tutorien
  • Info III WS05/06
  • Info IV SS06
  • Info III WS06/07
  • Info IV SS07

Info III, Tutorium 3, WS 05/06

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

• Ort: Raum 301 im Informatik Neubau (Geb. 50.34)
• Zeit: Wöchentlich – Montag, 11:30 Uhr
• Kontakt: thomas.pajor (at) logn.de oder #uka.info1 im Quakenet

Einen Übungsschein könnt ihr erwerben. Hierfür sind ⅓ der zu erreichenden Punkte sowohl vor als auch nach Weihnachten nötig.

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 11:00 Uhr in die Einwurfsschlitze im Keller des Informatik Neubaus zu werfen. Bitte achtet darauf dass eure Blätter zusamengetackert sind.

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

Neues…

Zusatztutorium

Donnerstag, 23.02.2006, 19:40

Wie versprochen wird es ein Zusatztutorium geben, und zwar am

Mittwoch, 1. März 2006, 14.00 Uhr in Raum 301 (Geb. 50.34)

Ich bitte euch mir eine E-Post zu schreiben ob ihr vorhabt zu kommen, da ich das (falls nicht so viele Leute kommen) dann mit Tutorium 5 zusammenlegen könnte. Schickt mir außerdem Fragen oder Themen die euch beim Lernen auffallen, auf die ich nochmal eingehen sollte. Dann kann ich dazu nochmal was vorbereiten :)

Klausurbonus

Freitag, 17.02.2006, 13:06

Sodele, mit an Sicherheit grenzender Wahrscheinlichkeit wird der Klausurbonus wie folgt vergeben:

Erreichte Punkte:	Bonuspunkte:
0% - 33%	0 Punkte
33% - 44%	1 Punkt
44% - 55%	2 Punkte
55% - 66%	3 Punkte
ab 66%	4 Punkte

Hier gelten jedoch im Gegensatz zum Schein nicht Vor- und Nachweihnachten getrennt. Die Punkte werden zu den Punkten in der Klausur einfach dazuaddiert, sie helfen jedoch nicht zum Bestehen.

Ich werde das Punktestand Skript im Laufe des Tages noch updaten so dass eure erreichten Bonuspunkte auch mit angezeigt werden.

Aufgaben aus dem Tut

Dienstag, 14.02.2006, 10:51

Ich habe die Aufgaben von gestern hochgeladen, und die Aufgabe 1) mit dem Pumping Lemma verbessert.

Ich wurde außerdem noch gefragt wie man bei der Aufwandsabschätzung für die Konstruktion von Subgraphenisomorphie auf die Gleichung

$$|E| = \binom{|V|}{2}$$

kommt. Und zwar beschreibt der Binomialkoeffizient $\binom{n}{k}$ gerade die Anzahl $k$-elementiger Teilmengen von einer $n$-elementigen Menge. In unserem Fall also die Anzahl $2$-elementiger Teilmengen von $V$. Das sind aber nun gerade die maximal möglichen Kanten in einem Graph mit $\vert{}V\vert{}$ Knoten, und somit gilt diese Formel stets für einen vollständigen (einfachen!) Graph.

Wunschübungsblatt

Dienstag, 31.01.2006, 09:51

Für die, die gestern nicht im Tutorium waren, möchte ich das nochmal hier erwähnen:

Das letzte Übungsblatt (vermutlich ohne Korrektur) wird ein Wunschübungsblatt, das heißt ihr könnt bestimmen zu welchen Themen aus der Vorlesung ihr nochmal Übungsaufgaben haben wollt. Schickt mir dazu eure Wünsche am besten via eMail an thomas.pajor(at)logn.de

Fehler in den Tut Folien!

Donnerstag, 26.01.2006, 01:12

Es gibt einen (schweren) Fehler in den Tutfolien von letzter Woche, und zwar bei der Erklärung der Chomsky–Normalform!

Beim Eliminieren der Kettenproduktionen (4. Schritt) stand in den Folien, dass für jede gelöschte Kettenproduktion $A_k \rightarrow A_l$ alle Produktionen $A_l \rightarrow X$ durch $A_k \rightarrow X$ ersetzt werden müssen. Das ist falsch, und führt zu einer Grammatik, die u.U. nicht mehr alle Wörter erzeugen kann. Ihr müsst zwar die Kettenproduktion $A_k \rightarrow A_l$ löschen, aber dann müsst ihr für jede Regel $A_l \rightarrow X$ eine Regel $A_k \rightarrow X$ hinzufügen.

Noch ein kleines Beispiel damit es klar wird, warum es schief läuft: Sei $G$ mit folgenden Produktionen gegeben:

$$\begin{align*} P := \{ & S \rightarrow A \;|\; BB, \\ & B \rightarrow AA, \\ &A \rightarrow a \} \end{align*}$$

Wenden wir Schritt vier auf diese Grammatik an, so sortieren wir zunächst die Variablen topologisch. Eine gültige Sortierung ist zum Beispiel $V = \{S,A,B\}$. Nun suchen wir „rückwärts“ nach Kettenproduktionen. Die einzige derartige Produktion die Auftritt ist $S \rightarrow A$, also löschen wir diese, und fügen zu jeder Produktion $A \rightarrow X$ mit $X$ beliebig eine Produktion $S \rightarrow X$ hinzu. Dies führt zu

$$\begin{align*} P_2 := \{ & S \rightarrow BB, \\ &A \rightarrow a, \\& B \rightarrow AA,\\ &S \rightarrow a \} \end{align*}$$

Wäre die Produktion $A \rightarrow a$ gelöscht worden, so hätten wir außer dem Wort $a$ mit der neuen Grammatik nichts mehr erzeugen können, was die erzeugte Sprache offensichtlich verändert hätte ($w = aaaa$ könnte nicht mehr erzeugt werden).

Die Folien habe ich verbessert hochgeladen. Sorry für die Umstände :(

Danke an Daniel Dreke für den Hinweis!

Material von Heute / Extrapunkte / Chomsky-Typen

Montag, 23.01.2006, 22:47

Also es gibt heute ein paar Neuigkeiten:

• Die Aufgaben aus dem Tutorium heute sind online, und ich habe noch eine kleine Korrektur an der zweiten Aufgabe von letzter Woche gemacht (War nur ein „Tippfehler“ in einem Index)
• Eine (vielleicht) erfreuliche Nachricht: Da anscheinend eine Musterlösung der Aufgabe (1) von Übungsblatt 10 im Netz kursiert, wird es für eine merkbar eigenständig hergeleitete Lösung fünf Extrapunkte geben.

Zum Schluss noch folgendes: Ich wurde letzte Woche gefragt wie das mit dem Chomsky-Typ bei Grammatiken ist. Also es gilt:

Der (maximale) Chomsky-Typ einer Grammatik $G := (V, \Sigma, P, S)$ wird durch die konkrete Produktionsmenge $P$ der gegebenen Grammatik bestimmt. Der (maximale) Chomsky Typ der Sprache $\mathcal{L}(G)$ hingegen wird durch den maximalen Chomsky-Typ einer beliebigen Grammatik, die ebenfalls $\mathcal{L}(G)$ erzeugt, definiert.

Ein Beispiel zur Verdeutlichung: Gegeben sei die Grammatik $G := (\{S,A\}, \Sigma := \{a,b\}, P, S)$ mit

$$\begin{align*} P := \{ & S \rightarrow aAb \;|\; ab, \\ & aAb \rightarrow aaAbb \;|\; aabb \} \end{align*}$$

Offensichtlich ist diese Grammatik vom Typ CH-1 (kontextsensitiv), aber die erzeugte Sprache ist

$$\mathcal{L}(G) = \{a^nb^n \;|\; n \in \mathbb{N}\}$$

Und wie wir aus der Vorlesung wissen, gibt es dafür auch eine kontextfreie Grammatik (siehe Kapitel 5, Folie 13), also ist der Chomsky-Typ der Sprache CH-2.

Material von Heute

Montag, 16.01.2006, 10:44

Die Materialien aus dem Tutorium von gestern habe ich jetzt unter Material bereitgestellt. Dies beinhaltet unter anderem das Verfahren zur Herleitung der Chomsky-Normalform in den Folien.

Vielen Dank auch nochmal an euch für die Hinweise im Tut auf die Fehler in der Aufgabe beim Beweis $L = L(G)$. Ich habe die Aufgabe verbessert hochgeladen.

Frohe Weihnachten

Montag, 19.12.2005, 18:51

So, das letzte Tut in diesem Jahr ist vorbei, ich hoffe es hat euch auch Spaß gemacht.

Den Vortrag über die Einführung in die Rautavistik findet ihr auf der Webseite von Tutorium 5 oder hier unter Material.

Dann bleibt mir nurnoch ein frohes Weihnachtsfest und einen guten Rutsch ins neue Jahr zu wünschen! Das nächste Mal sehen wir uns am 09.01.2006.

Glühweintutorium

Freitag, 16.12.2005, 10:44

Also ich wollte es ja nochmal hier fest ankündigen. Am Montag, den 19.12.2005 mache ich ein Glühweintutorium. Ich bringe den Glühwein mit, aber Tassen oder Becher müsst ihr mitbringen. Außerdem könnt ihr gerne ein bisschen Gebäck oder Knabberkram mitbringen. :)

Da wir um 14.00 Uhr mit Tutorium 5 auch ein Glühwein-Tut machen wollen, wird unser Tut ausnahmsweise in Raum -120 stattfinden.

Also bis zum Montag!

Neue Revision des Pumpsatz Papiers

Dienstag, 13.12.2005, 12:30

Es gibt jetzt unter Material eine neue Revision des Papiers zum Pumping Lemma (siehe auch News vom 04.12.). Ich habe noch einen Abschnitt eingefügt der beschreibt wie man mit der Widerspruchsmethode kürzer (und schneller) beweisen kann – in der Klausur zählt ja schließlich jede Sekunde. ;) Ich habe auch nochmal explizit die Unterschiede zwischen den zwei Beweistechniken geschildert. Außerdem habe ich noch ein paar Bezeichner geändert, um mögliche Verwirrung zu vermeiden.

Aufgaben / Verlegung der Großen Saalübung

Dienstag, 13.12.2005, 12:03

Da ich gestern nicht mehr zu den Aufgaben gekommen bin, gibt es diese jetzt – wie immer – unter Material inkl. Lösung zum Download. Wenn ihr Interesse habt, dann erkläre ich euch die eine oder andere nächste Woche. Ich denke dass nicht mehr so viel neuer Stoff kommen wird bis nächste Woche.

Außerdem findet die große Saalübung diese Woche am Freitag (16.12.2005) nicht im Audimax sondern im Hörsaal am Fasanengarten statt.

Pumping Lemma

Sonntag, 04.12.2005, 21:08

Da es anscheinend immernoch ein paar Missverständnisse bezüglich des Pumping Lemmas gibt, vorallem da zwei verschiedene „Methoden“ existieren, mit denen man die Nichtregularität einer Sprache $L$ zeigen kann, habe ich ein sehr ausführliches Papier zusammengeschrieben, wo ich die Techniken nochmal genau erkläre.

Ihr findet es hier oder unter Material.

Die Erfindung der TMs!

Sonntag, 04.12.2005, 01:19

Nicht abgeholte Blätter

Dienstag, 29.11.2005, 02:10 Uhr

Ich wollte nur nochmal für die, die heute (gestern) nicht im Tut waren, verkünden, dass nicht abgeholte Übungsblätter jeweils ab Freitag im Sekretariat von Prof. Sanders (Raum 218, Info-Neubau) abgeholt werden können.

Punktestand und fehlende E-Mail Adressen

Dienstag, 22.11.2005, 21:15 Uhr

Ich habe den Punktestand wieder up2date gebracht. Bitte kontrolliert ob die Werte stimmen.

Dabei ist mir aufgefallen dass ich von folgenden Leuten, die bei mir abgeben, noch keine E-Mail Adressen habe:

• Andreas Gonschorek
• Jessica Kaufmann
• Florian Mickler
• Thang Vu

Falls ihr das lest, bitte ich euch mir eine eMail mit eurem Namen zu schicken, sodass ich eure Adressen auch habe. Dann kann ich nämlich eure Punkte auch (online) eintragen.

Material zum Tutorium

Montag, 21.11.2005, 14:41 Uhr

Die Aufgaben zum Tutorium von heute gibt es unter Material. Außerdem habe ich noch einige nette Spielereien verlinkt. Auf der Info III Webseite vom letzten Jahr gibt es außerdem eine Beschreibung zum Pumping Lemma sowie zur Nerode Relation. Leider ist die Seite im Moment gerade down (mySQL sei Dank), sonst hätte ich das auch noch verlinkt.

PS: Die Eintragung der Punkte für das 3. ÜB kommt etwas später, da ich an dem Skript noch etwas werkeln muss. Das Eintragen ist im Moment etwas umständlich.

Punkte und $\overline{\varepsilon}$-NEA-Konversion

Montag, 14.11.2005, 21:02 Uhr

Die Punkte für die Übungsblätter 1 und 2 sind jetzt eingetragen. Bitte kontrolliert ob die Werte mit euren Werten auf dem Übungsblatt übereinstimmen.

Außerdem habe ich noch was zur Konstruktion eines $\overline{\varepsilon}$-NEAs geschrieben, vorallem eine textuelle Beschreibung des „praktischen“ Verfahrens, da ja dazu im Tut heute leider keine Zeit war. Ihr findet das unter Material.

Geänderte Abgabezeit

Freitag, 11.11.2005, 20:49 Uhr

Die Abgabezeit der Übungsblätter hat sich auf 11 Uhr geändert, da auch für uns Tutoren der 10 Uhr Termin etwas arg früh war :-). Also ab jetzt habt ihr zeit bis Freitag, 11 Uhr die ÜBs einzuwerfen.

Material zum Tutorium

Montag, 07.11.2005, 14:13 Uhr

Die zusätzlichen Aufgaben aus dem heutigen Tut sowie die Folien gibt es ab jetzt unter „Material“ zum download.

Fehler in den Vorlesungsfolien

Donnerstag, 03.11.2005, 19:54 Uhr

Auf den Vorlesungsfolien gibt es leider einen Fehler, und zwar bei der Definition des positiven Abschlusses $L^+$. Die korrekte Definition lautet

$$L^+ := \bigcup_{i \geq 1} L^i$$

Dann klappt auch die Aufgabe 3b auf dem ersten Übungsblatt. :)

Abgabe des ersten ÜBs

Freitag, 28.10.2005, 20:45 Uhr

Die Abgabe des ersten Übungsblattes ist erst am 11.11.2005, und zwar zusammen mit dem zweiten ÜB, welches auch nur eine Korrekturaufgabe enthalten wird.

Danach erfolgt die Abgabe aber wöchentlich mit jeweils zwei Korrekturaufgaben.