RUB » LMI » Lehre » Theoretische Informatik WS 2017/2018

Theoretische Informatik WS 2017/2018

LVR-Nr: 150 240
Veranstaltung: Theoretische Informatik
4 std.
HZO 70 Mo 10:00-12:00 und
HNC 20 Mi 10:00-12:00
Dozent: Hans U. Simon
Übungen: Daniel Pasler und Christoph Ries
2 std.
1. NB 5/99 Di 14:00-16:00 (Pasler) oder
2. NA 2/24 Di 14:00-16:00 (Ries) oder
3. NA 5/24 Mi 08:30-10:00 (Pasler) oder
4. NA 2/24 Mi 14:00-16:00 (Ries)
die erste Übung findet am 17.10. statt
Korrektur der Hausaufgaben: Lea Thiel
René Zeidler

News

  • Die Klausureinsicht findet am Dienstag, den 09. Oktober 2018, um 13 Uhr in NA 1/24.
  • Die Ergebnisse der Nachschreibklausur können ab sofort am schwarzen Brett bei NA 1 Nord eingesehen werden. Der Termin für die Einsicht wird noch bekannt gegeben.
  • Prüfung: Der Termin für die Nachschreibklausur steht jetzt fest (siehe Unterpunkt "Klausur"). Zudem gibt es einen weiteren Termin für mündliche Prüfungen (siehe Unterpunkt "Mündliche Prüfungen").
  • Die Klausureinsicht findet am Montag, den 16. April 2018, zwischen 14 und 15 Uhr in NA 1/24 statt.
  • Die Klausurergebnisse können ab sofort am schwarzen Brett bei NA 1 Nord eingesehen werden.
  • Die Vorlesungen am 29. Januar und am 31. Januar finden statt.
  • Die Vorlesung am 24. Januar entfällt!
    [Ob die Vorlesung nächste Woche (5. KW) stattfindet, wird am Ende der Woche hier bekanntgegeben.]
  • Am 30. und 31.01. finden keine regulären Übungen mehr statt. Sie werden durch Sprechstunden ersetzt und können für etwaige Fragen oder Probleme genutzt werden.
  • 13.12.17: In Aufgabe 9.2 b) wurde ein Fehler korrigiert.
  • Prüfung: Die Termine für die mündlichen Prüfungen stehen fest (siehe Unterpunkt "Mündliche Prüfungen").
  • Prüfung: Der Termin für die Klausur steht jetzt fest (siehe Unterpunkt "Klausur").
  • Bei Aufgabe 3.4 wurde der Aufgabentext angepasst (Die Aufgabe selbst blieb unverändert).
  • Blatt 3 wird am 30.10. hochgeladen und kann bis zum 07.11. abgegeben werden.
  • Bitte bearbeitet jede Übungsaufgabe auf einem einzelnen Zettel, sodass ihr sie nach Aufgaben getrennt in die Kästen auf NA02 werfen könnt!
  • Aufgrund der Feiertage am 31.10. und 01.11. verlängert sich die Abgabefrist für das zweite Blatt bis Donnerstag, 02.11., 12 Uhr.

Materialien

Übungsblätter

Präsenzblätter

Vorlesungsskript

Kapitel 1: Formale Sprachen

Kapitel 2: Berechenbarkeitstheorie

Kapitel 3: Komplexitätstheorie

Zusätzliche Kapitel

Informationen aus dem Vorlesungsverzeichnis

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 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.

In der Vorlesung ergeben sich fundamentale Einsichten zum Verhältnis zwischen Automaten und Grammatiken und zum Verhältnis von Determinismus und Nicht-Determinismus. Durch Einüben von Techniken wie wechselseitige Simulation oder (polynomiell) berechenbare Reduktionen soll die Einsicht reifen, dass an der Oberfläche verschieden aussehende Konzepte im Kern identisch sein können. Ziel ist zudem ein tieferes Verständnis von Komplexität. Auf den unteren Ebenen der sogenannten Chomsky-Hierarchie finden sich effizient lösbare Anwendungsprobleme der Textmanipulation und der Textanalyse. Auf den oberen Ebenen machen die Studierenden Bekanntschaft mit dem Phänomen der inhärenten Härte (oder gar Unentscheidbarkeit) eines Problems.

Literatur

Die Vorlesung orientiert sich in erster Linie an dem Buch "Theoretische Informatik - kurzgefasst" von Uwe Schöning (Spektrum, 2001) bzw. an einem Skriptum zur Vorlesung. Weitere Literaturvorschläge erfolgen in der ersten Vorlesungsstunde.

Übungsaufgaben

Im Laufe des Semesters sind wöchentlich Übungsaufgaben zu lösen. Es werden nur handschriftliche Abgaben gewertet. Bitte notiert auf jedem Blatt Namen, Matrikelnummern und die Übungsgruppennummer. Bei der Bearbeitung der Aufgaben kann in Gruppen zu maximal 3 Studierenden gearbeitet werden. Die erreichten Punkte werden dann jedem Gruppenmitglied angerechnet.

Jeder der in einer Übungsaufgabe allein oder in einer Gruppe Punkte erhält, sollte auch in den Übungen in der Lage sein die Lösung der Aufgabe an der Tafel vorzurechnen.

Termine

Die Übungsblätter werden jeden Dienstag auf dieser Seite veröffentlicht. Die Abgabe der bearbeiteten Aufgaben ist bis zum Dienstag, eine Woche nach Veröffentlichung, bis 12:00 Uhr möglich. Bitte werft die Aufgaben in den Abgabekasten auf NA 02 neben dem Eingang zum Rechenzentrum. Die Rückgabe der korrigierten Zettel erfolgt in den Übungsgruppen.

Korrektur

Die Korrekteure sind Lea Thiel, lea.thiel@rub.de (Sprechstunde: Do, 14-15 Uhr in NA 2/58) , und René Zeidler, rene.zeidler@rub.de (Sprechstunde: Di, 12-13 Uhr in NA 03/32) .

Bonuspunkte

Jedes Übungsblatt hat 4 Aufgaben, bei denen je 4 Punkte zu erreichen sind (sollte die Anzahl an Abgaben unsere Kapazität überschreiten, werden eventuell nicht alle Aufgaben bewertet). Die erworbenen Punkte in den Übungsblättern werden bei der Klausur anteilig als Bonuspunkte gutgeschrieben. Dabei entsprechen 100% Punkte in den Übungsaufgaben 10% Punke in der Klausur. Die maximal erreichte Punktezahl in der Abschlussklausur kann 100% nicht übersteigen. Dieser Bonus gilt nur für die erste Klausur zum Wintersemester 17/18 und nicht für spätere Klausuren.

Teilnahmeschein

Eine unbenotete Bescheinigung über eine erfolgreiche Teilnahme erhält, wer mindestens die Hälfte der Hausaufgabenpunkte erreicht, in den Übungen mindestens einmal vorrechnet und regelmäßig an den Übungen teilnimmt.

Klausur

Die Prüfung besteht aus der Semesterabschlussklausur. Die einzige Ausnahme gilt für Studierende, die "Theoretische Informatik" im Hauptfach des B.Sc. Mathematik belegen (siehe unten).

Die Klausur wird dreistündig sein und am Montag, den 26. März 2018, in HZO 20 ab 10 Uhr s.t. stattfinden.

Der Termin für die dreistündige Nachschreibklausur ist Dienstag, der 24. Juli 2018, ab 14:00 Uhr in HNB. Dabei ist zu beachten, dass für die Nachschreibklausur keine Bonuspunkte aus Übungsaufgaben angerechnet werden können.

Zugelassene Hilfsmittel sind das Vorlesungsskript und das Buch "Theoretische Informatik - kurzgefasst" von Uwe Schöning (HTb, 2001), sowie auf dieser Seite veröffentlichte Materialien (mit Ausnahme der Übungsblätter und Beispiele) zugelassen.

Alle Klausurteilnehmer melden sich bei dem Prüfungsamt ihrer eigenen Fakultät nach den dort geltenden Regeln und Fristen an (und ggf. ab). Bei Fragen zur Anmeldung wenden Sie sich bitte auch an das zuständige Prüfungsamt.

Alle Studierenden die das Fach im Optionalbereich belegen melden sich bitte zusätzlich bei Christoph Ries an.

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 17/18 eine mündliche Prüfung angeboten. Zur Wahl stehen die folgenden zwei Termine:

  • Dienstag, den 6. Februar 2018
  • Montag, den 9. April 2018

Ein weiterer Termin für mündliche Prüfungen wird am Donnerstag, den 19. Juli 2018, angeboten.

Anmeldungen zur mündlichen Prüfung müssen von allen Studierenden schriftlich in ihrem jeweiligen Prüfungsamt vorgenommen werden, sonst können keine Leistungsnachweise ausgestellt werden.

Achtung: Vor der Anmeldung im Prüfungsamt lassen Sie sich bitte einen Termin mit Uhrzeit von Christoph Ries geben.

Die Anmeldung muss mindestens zwei Wochen vor der jeweiligen Prüfung erfolgen. Ein Rücktritt von einer angemeldeten Prüfung ist bis zu drei Tage vor der Prüfung in schriftlicher Form ohne Angabe von Gründen im Prüfungsamt (Container N-Süd OG/37) möglich.

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