Lehrstuhl Mathematik & InformatikTheoretische Informatik WS 2009/2010
| LVR-Nr: | 150 240 |
|---|---|
| Veranstaltung: | Theoretische Informatik 4 std. NA 01/99 Mo 10.00-12.00 NA 01/99 Mi 10.00-12.00 |
| Dozent: | Hans U. Simon |
| Übungen: | Annette Ilgen 4 std. NA 1/64 Mo 08:30-10:00 NA 1/64 Mi 12:00-14:00 |
| Korrektur: | Mukadder Korkmaz Sprechstunde Do 14:00 - 15:00 NA 1/70 |
| Anmeldung zur Vorlesung | über VSPL vom 12.10.2009 - 30.11.2009 |
| Helpdesk | In der vorlesungsfreien Zeit: Täglich montags bis donnerstags von 13:00 bis 16:00 Uhr in NA 3/51 und NA 3/58 |
News
Die Klausurergebnisse sind da.
Details siehe unten.
Voraussetzungen
Nützlich (aber nicht zwingend erforderlich) sind elementare Grundkenntnisse in Informatik und Diskreter Mathematik sowie Vertrautheit mit mindestens einer Programmiersprache.
Kommentar
Die Vorlesung richtet sich an Studierende der Mathematik, der Angewandten Informatik und (als Wahlpflichtfach) an Studierende der IT-Sicherheit. Sie ist weiterhin ein wählbares Modul im Optionalbereich. Sie liefert eine Einführung in die Theorie der Grammatiken (insbesondere kontextfreie Grammatiken) und Automaten (endlicher Automat, Kellerautomat, Turing-Maschine). Sie gibt ferner einen Einblick in die Berechenbarkeits- und NP-Vollständigkeitstheorie, wo es um die Frage geht, welche Rechenprobleme (überhaupt bzw. mit vertretbarem Aufwand) gelöst werden können. Es wird sich zeigen, dass es inhärent schwere Probleme gibt, die von Rechnern nicht zufriedenstellend gelöst werden können.
Literatur
Die Vorlesung orientiert sich haupsächlich an dem Buch "Theoretische Informatik - kurzgefasst" von Uwe Schöning (HTb, 2001). Zur Vertiefung des Stoffes kann sowohl das Buch "Introduction to Automata Theory, Languages, and Computation" von John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman (Addison Wesley, 2000) als auch "Introduction to the Theory of Computation" von M. Sipser (PWS Publishing Company, 1997) dienen.
Übungsaufgaben
Die Übungen zur Vorlesung sind bereits abgeschlossen.
Klausur
Die Ergebnisse der Klausur vom 03.09.2010 hängen ab sofort vor NA 1/72 aus.
Die Einsichtnahme in die Klausur findet am 13.10.2010 von 18:00 bis 19:00 Uhr im Raum NA 1/64 statt.
Mündliche Prüfungen
Die mündlichen Prüfungen sind bereits abgeschlossen.
Materialien
Übungsblätter
- Aufwärmblatt (pdf)
- Blatt 1 (pdf)
- Blatt 2 (pdf)
- Blatt 3 (pdf)
- Blatt 4 (pdf)
- Blatt 5 (pdf)
- Blatt 6 (pdf)
- Blatt 7 (pdf)
- Blatt 8 (pdf)
- Blatt 9 (pdf)
- Blatt 10 (pdf)
- Blatt 11 (pdf)
- Blatt 12 (pdf)
- Blatt 13 (pdf)
Vorlesung
- Kapitel 1.1 (pdf)
- Kapitel 1.2 (pdf)
- Kapitel 1.3 (pdf)
- Kapitel 1.4 (pdf)
- Kapitel 2.1 (pdf)
- Kapitel 2b (pdf)
- Kapitel 3 (pdf)
Skript zu den Vorlesungen am 27.1.2010 und 3.2.2010. Dieser Teil der Vorlesung ist nicht prüfungsrelevant.
Beispiele
Eine Sammlung von Beispielen zur Vorlesung.
- Beispiele zu Kapitel 1.1 (pdf)
- Beispiele zu Kapitel 1.2 (pdf)
- Beispiele zu Kapitel 1.3 (pdf)
- Beispiele zu Kapitel 1.4 (pdf)
- Beispiele zu Kapitel 3 (pdf)
Kontakt
- Hans U. Simon, NA 1/73
- Annette Ilgen, NA 1/70
- Mukadder Korkmaz