Lehrstuhl Mathematik & InformatikTheoretische Informatik WS 2010/2011
| 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 oder NA 1/64 Mi 12:00-14:00 |
| Korrektur: | Felix Heuer Sprechstunde Mo 12:00 - 14:00 Uhr NA 4/51 |
| Anmeldung zur Vorlesung | über VSPL vom 13.09.2010 - 31.10.2010 |
| Helpdesk | Termine werde noch bekanntgegeben |
News
Die Klausurergebnisse vom 15.8.2011 sind da (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.
Übungen
Die Übungen sind schon abgeschlossen.
Materialien
Übungsblätter
- 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)
Der folgende Teil des Vorlesungsskriptes 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)
Klausur
Die Klausurergebnisse zum SS 2011 vom 15.8.2011 können am schwarzen Brett in NA 1 Nord eingesehen werden.
Die Klausureinsicht findet am Di den 11.10.2011
um 18:00-19:00Uhr in NA 1/64 statt.
WICHTIG: Wer an der Klausureinsicht teilnehmen möchte meldet sich bitte per E-mail bis zum 1.10.2011
bei Annette Ilgen an.
Mündliche Prüfungen
Die mündlichen Prüfungen sind schon abgeschlossen.
Abschlussarbeiten
Im thematischen Umfeld der Vorlesung ist es möglich eine Abschlussarbeit zu erstellen. Nähere Informationen für Interessenten finden sich unter Abschlussarbeiten.
Kontakt
- Hans U. Simon, NA 1/73
- Annette Ilgen, NA 1/70
- Felix Heuer, NA 4/51