• 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

Nützliche Materialien

Hier wird es vielleicht später ein paar Zusatzmaterialien zum Tut geben.

Materialien von mir

• $\varepsilon$-NEA zu $\overline{\varepsilon}$-NEA Konversion
• Beweistechniken mit dem Pumping Lemma (für Reguläre Sprachen) [Revision 1.1]

Material zu den Tutorien

• Zusatztutorium, 01. März 2006
  • Zusatzaufgaben aus dem Tut
  • Folien
• Tutorium, 13. Februar 2006
  • Zusatzaufgaben aus dem Tut
  • Folien
• Tutorium, 06. Februar 2006
  • Zusatzaufgaben aus dem Tut
  • Folien
• Tutorium, 30. Januar 2006
  • Zusatzaufgaben aus dem Tut
  • Folien
• Tutorium, 23. Januar 2006
  • Zusatzaufgaben aus dem Tut
  • Folien
• Tutorium, 16. Januar 2006
  • Zusatzaufgaben aus dem Tut
  • Folien (inklusive der Beschreibung zur Herleitung der CNF)
• Tutorium, 09. Januar 2006
  • Zusatzaufgaben aus dem Tut
  • Folien
• (Glühwein-) Tutorium, 19. Dezember 2005
  • Zusatzaufgaben aus dem Tut
  • Folien
  • Rautavistische Algorithmen und Datenstrukturen – von Julian Hörst
• Tutorium, 12. Dezember 2005
  • Zusatzaufgaben aus dem Tut
  • Folien
• Tutorium, 05. Dezember 2005
  • Zusatzaufgaben aus dem Tut
  • Folien
• Tutorium, 28. November 2005
  • Zusatzaufgaben aus dem Tut
  • Folien
• Tutorium, 21. November 2005
  • Zusatzaufgaben aus dem Tut
  • Folien
• Tutorium, 14. November 2005
  • Folien
• Tutorium, 7. November 2005
  • Zusatzaufgaben aus dem Tut
  • Folien

Sonstige Materialien

• Äquivalenzklassenautomat / DEA Minimierung – Beschreibung aus dem WS 04/05 vom ITI Wagner
• Das Pumping Lemma für Reguläre Sprachen – Aus dem WS 04/05 vom ITI Wagner
• Nerode Relation mit Beispiel – Aus dem WS 04/05 vom ITI Wagner

Nützliches zum Spielen

• Complexity Zoo – Auflistung aller möglichen Komplexitätsklassen; Es gibt noch mehr als $\mathcal{P}$ und $\mathcal{NP}$
• GasTeX – Paket zum erzeugen schöner Graphen in LaTeX (zum Beispiel für Automaten, TMs, etc)
• JasTeX – Graphisches (Java-)Tool zum Erstellen von Graphen. Erzeugt GasTeX Code.
• JasTeX - Turing Machine Enabled – JasTeX mit integriertem TM Simulator!
• Turingmaschine die Primzahlen erkennt – Damals von mir zum Spaß gebaut, inkl. Poster mit Übergangsgraph :-)

Offizielle Sachen

• Vorlesungsskript und Folien
• Übungsblätter und Lösungsvorschläge
• Material vom Wintersemester 2004/2005 (Prof. Wagner) – Skript, Folien und Klausuren

Literaturempfehlungen

• Theoretische Informatik – kurzgefasst
  Uwe Schöning, 4. Auflage, Spektrum Verlag, 2001
• Theoretische Informatik – eine algorithmenorientierte Einführung
  Wegener, 2. Auflage, Teubner, 1999
• Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie
  Hopcroft, Motwani, Ullman, 2. Auflage, Addison-Wesley, 2002