Lehrstuhl Mathematik & InformatikTheoretische Informatik WS 2011/2012
| LVR-Nr: | 150 240 |
|---|---|
| Veranstaltung: | Theoretische Informatik 4 std. NA 01/99 Mo 10.00-12.00 und NA 6/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 Do 10:00-11:00 in NA 5/76 |
| Anmeldung zur Vorlesung | über VSPL vom 01.10.2011 - 31.10.2011 |
News
Einsicht und Ergebnisse der Klausur im Sommersemester
Die Einsicht zur Klausur im Sommersemester findet am 08.10.2012 von 18-19 Uhr in NA 1/64 statt.
Die Klausurergebnisse können ab sofort an Aushängen in NA 1 Nord (Fahrstuhlbereich und vor Raum 1/72) eingesehen werden.
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 sind bereits abgeschlossen.
Die Korrektur von Blatt 12 kann ab Montag den 06.02.2012 um 10:00 Uhr bei
Annette Ilgen in NA 1/70 abgeholt werden.
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)
Vorlesung
- Kapitel 1.1 (pdf)
- Kapitel 1.2 (pdf)
- Kapitel 1.3 (pdf)
- Kapitel 1.4 (pdf)
- Kapitel 2.1 (pdf)
- Kapitel 2.2 (pdf)
- Kapitel 3 (pdf)
Der folgende Teil des Vorlesungsskriptes ist nicht prüfungsrelevant.
Beispiele
- 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 hängen in NA Nord, Ebene 1 am schwarzen Brett im
Vorraum zu den Aufzügen.
Die Klausureinsicht findet am 2.4.2012 von 18:00-19:00 Uhr in NA 1/64 statt.
Mündliche Prüfungen
Für die Studierenden, die "Theoretische Informatik" im Hauptfach des Bachelor of Science in der Mathematik belegen, wird im Anschluss an das Wintersemester 11/12 eine mündliche Prüfung angeboten.
Termine:
- Mi 15.02.2012
- Di 27.03.2012
Anmeldungen zur mündlichen Prüfung müssen von allen Studierenden schriftlich im Prüfungsamt vorgenommen werden.
Achtung: Vor der Anmeldung im Prüfungsamt lassen Sie sich bitte einen Termin mit Uhrzeit von Annette Ilgen geben.
Die Anmeldung muss mindestens zwei Wochen vor der jeweiligen Prüfung erfolgen. Ein Rücktritt von einer angemeldeten Prüfung muss mindestens drei Tage vor der Prüfung in schriftlicher Form ohne Angabe von Gründen im Prüfungsamt (NA 02/73) erfolgen.
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 5/76