Hinweis: Die Unterlagen zur Veranstaltung Theoretische Informatik
im Masterstudiengang Informatik/Mobile
Systeme sind unter Stud.IP zu finden.
Einführung in die Theoretische Informatik
Prof. Dr. Frieder Stolzenburg -
Sommersemester 2011 - Hochschule Harz
in Wernigerode
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
- Theorie der Berechenbarkeit
- Intuitive Berechenbarkeit
- Turing-Maschinen
- Halteproblem
- Übungsaufgaben (Abgabe bis 4.4.2011)
- Einführung in die Komplexitätstheorie
- Aufwand von Rechen-Verfahren
- Die O-Notation
- Die Klassen P und NP
- Übungsaufgaben (Abgabe bis 2.5.2011)
- Reguläre Sprachen
- Kontextfreie Sprachen
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.