RUB »LMI »Lehre » Theoretische Informatik WS 2010/2011

Theoretische 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


Vorlesung

Der folgende Teil des Vorlesungsskriptes ist nicht prüfungsrelevant.


Beispiele

Eine Sammlung von Beispielen zur Vorlesung.

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