Einführung in die Theoretische Informatik

Allgemeines

Diese Lehrveranstaltung führt in grundlegende Begriffe, Sätze, Methoden und Beweistechniken der Theoretischen Informatik ein. Die Lehrveranstaltung hat ihren festen Platz in den Bachelorstudiengängen Informatik und Intelligente Automatisierungssysteme im 4. Semester mit 3 CP (Credit Points) bei 1+1+0 SWS (Wochenstunden).

Termine

• Vorlesung und Übung:
  Donnerstag, 8.00-9.45 Uhr, Hörsaal HSC
• Beginn: Donnerstag, 12.4.07
  Zusatztermin: Dienstag, 15.5.07, 8.00-11.15 Uhr, Raum 5.101
• Klausur: Mittwoch, 25.7.07, 11.00-12.30 Uhr, Raum 4.001

Gliederung

1. Theorie der Berechenbarkeit
   • Intuitive Berechenbarkeit
   • Turing-Maschinen
   • Halteproblem
   • Übungsaufgaben (Abgabe bis 11.5.07)
2. Einführung in die Komplexitätstheorie
   • Aufwand von Rechen-Verfahren
   • Die O-Notation
   • Die Klassen P und NP
   • Übungsaufgaben (Abgabe bis 11.6.07)
3. Reguläre Sprachen
   • Formale Sprachen
   • Endliche Automaten
   • Reguläre Ausdrücke
   • Algorithmen für endliche Automaten
   • Übungsaufgaben (Abgabe bis 26.6.07)
4. Kontextfreie Sprachen
   • Kontextfreie Grammatiken
   • Kellerautomaten
   • Die Chomsky-Hierarchie
   • Übungsaufgaben (Abgabe bis 3.7.07)

Literatur

• Can Adam Albayrak: Grundzüge der Theoretischen Informatik. Fachbereich Automatisierung und Informatik, Hochschule Harz, 2006/7. Unterlagen zur Vorlesung.
• Katrin Erk, Lutz Priese: Theoretische Informatik. Springer, Berlin, Heidelberg, New York, 2nd edition, 2001.
• M. R. Garey, David S. Johnson: Computer and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
• Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Concrete Mathematics - A Foundation for Computer Science. Addison-Wesley, Reading, MA, 2nd edition, 1994.
• John Hopcroft, Jeffrey Ullman: Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 1979.
• Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization - Algorithms and Complexity. Dover Publications Inc., Mineola, NY, Dover edition, 1998.
• Uwe Schöning: Theoretische Informatik - kurzgefaßt. Spektrum Akademischer Verlag, Heidelberg, Berlin, 4th edition, 2001.
• Ingo Wegener: Komplexitätstheorie - Grenzen der Effizienz von Algorithmen. Springer, Berlin, Heidelberg, New York, 2003.
• Ingo Wegener: Theoretische Informatik - eine algorithmische Einführung. Teubner, Stuttgart, 1999.