Vorlesung Theoretische Grundlagen der Informatik

1. Übungsblatt (PDF   /   postscript)
   Formale Sprachen, reguläre Sprachen, deterministische endliche Automaten, Potenzmenge, Induktion
   
   
2. Übungsblatt (PDF   /   postscript)
   Reguläre Ausdrücke und Sprachen, deterministische und nichtdeterministische endliche Automaten
   
   
3. Übungsblatt (PDF   /   postscript)
   Von regulären Ausdrücken zu endlichen Automaten und umgekehrt
   
   
4. Übungsblatt (PDF   /   postscript)
   Pumping Lemma für reguläre Sprachen, Äquivalenzklassenautomat, DEA aus Potenzmengenkonstruktion kann minimal sein
   [Lösungen zu Aufgaben 1.3, 1.4, 2 und 4 in PDF und postscript.]
   
   
5. Übungsblatt (PDF   /   postscript)
   Potenzmengenkonstruktion, Pumping Lemma für reguläre Sprachen, Nerode-Relation
   [Lösungen zu Aufgaben 3 und 4 in PDF und postscript.]
   
   
6. Übungsblatt (PDF   /   postscript)
   Turingmaschinen, Entscheidbarkeit
   
   
7. Übungsblatt (PDF   /   postscript)
   Post'sches Korrespondenzproblem, (Semi-)Entscheidbarkeit, Halteproblem, Turingmaschinen
   [Lösungen zu Aufgaben 2 und 4a in PDF und postscript.]
   
   
8. Übungsblatt (PDF   /   postscript)
   (Semi-)Entscheidbarkeit, Optimierungs-/Entscheidungsproblem, Kodierungsschema
   [Lösungen zu Aufgaben 1, 3, 4b und 4c in PDF und postscript.]
   
   
9. Übungsblatt (PDF   /   postscript)
   3SAT, CLIQUE, 2SAT
   
   
10. Übungsblatt (PDF   /   postscript)
    Achtung: Dies ist die zweite, korrigierte Version. Auf der ersten Version war eine fehlerhafte Definition des Problems VERTEX COVER abgedruckt.
    CLIQUE, VERTEX COVER, HAMILTON CYCLE, HAMILTON PATH
    
    
11. Übungsblatt (PDF   /   postscript)
    PARTITION, relativer Approximationsalgorithmus für KNAPSACK, absoluter Approximationsalgorithmus für CLIQUE impliziert P=NP
    
    
12. Übungsblatt (PDF   /   postscript)
    Relativer Approximationsalgorithmus, Wiederholung
    [Lösungen in PDF und postscript.]
    
    
13. Übungsblatt (PDF   /   postscript)
    Grammatiken
    [Lösungen in PDF und postscript.]

• Folie zum Halteproblem [PDF]

• Dorothea Wagner, Marco Gaertler, Dagmar Handke:
  Theoretische Grundlagen der Informatik. Skript zur Vorlesung vom WS 98/99.
  Konstanzer Schriften in Mathematik und Informatik, Nr. 123, 2000.
  Verfügbar als PDF und postscript und als Kopiervorlage im Vorraum des Sekretariats E 212.
  Bibliothek: mat 2.80/k66 und kid 2.80/k66.
  
• Ingo Wegener:
  Theoretische Informatik.
  B.G. Teubner Verlag Stuttgart, 1993.
  Bibliothek: lbs 840/w23.
  
• Michael R. Garey, David S. Johnson:
  Computers and Intractability: A Guide to the Theory of NP-Completeness.
  Freeman San Francisco / New York, 1979.
  Bibliothek: lbs 840/g17.
  
• Uwe Schöning:
  Theoretische Informatik - kurzgefasst.
  Hochschultaschenbuch, Spektrum Akademischer Verlag, 1997.
  Bibliothek: lbs 840/s23.