Einführung in die Theoretische Informatik
Prof. Dr. Frieder Stolzenburg -
Sommersemester 2007 - 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
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
- Theorie der Berechenbarkeit
- Intuitive Berechenbarkeit
- Turing-Maschinen
- Halteproblem
- Übungsaufgaben (Abgabe bis 11.5.07)
- Einführung in die Komplexitätstheorie
- Aufwand von Rechen-Verfahren
- Die O-Notation
- Die Klassen P und NP
- Übungsaufgaben (Abgabe bis 11.6.07)
- Reguläre Sprachen
- Kontextfreie Sprachen
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.