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 Automatisierungstechnik und Ingenieur-Informatik im 4. Semester mit 3 CP (Credit Points) bei 1+1+0 SWS (Wochenstunden).

Termine

• Vorlesung und Übung: Mittwoch, 8.00-9.30 Uhr, Raum 5.105
• Beginn: Mittwoch, 16.3.2011
• Klausur: Montag, 4.7.2011, 8.00-9.30 Uhr, Raum 9.129 (Audimax) (Beispiel)
• Vorbereitungstermin: Dienstag, 21.6.2011, 13.30-15.00 Uhr, Raum 5.105

Gliederung

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

Literatur

• 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.
• Michael Sipser: Introduction to the Theory of Computation. Course Technology, 2nd edition, 2005.
• Ingo Wegener: Komplexitätstheorie - Grenzen der Effizienz von Algorithmen. Springer, Berlin, Heidelberg, New York, 2003.
• Gottfried Vossen, Kurt-Ulrich Witt: Grundkurs Theoretische Informatik. Vieweg Friedrich & Sohn, 3. Auflage, 2004.
• Ingo Wegener: Theoretische Informatik - eine algorithmische Einführung. Teubner, Stuttgart, 1999.