RUB » LMI » Lehre » Theoretische Informatik WS 2015/2016

Theoretische Informatik WS 2015/2016

LVR-Nr: 150 240
Veranstaltung: Theoretische Informatik
4 Std.
HZO 90 Mo 10:00-12:00 und
HNC 20 Mi 10:00-12:00
Dozentin: Maike Buchin
Übungen: Maike Gruchot und Stef Sijben
2 Std.
NB 5/99 Di 14:00-16:00 oder
NA 3/99 Mi 8:30-10:00 oder
NA 2/24 Mi 14:00-16:00

Für den Besuch der Übungen ist eine Anmeldung via Blackboard erforderlich. Die Anmeldung wird nach dem ersten Vorlesungstermin freigeschaltet. Die erste Übung findet am 27.10. statt.
Korrektur der Hausaufgaben: Maike Gruchot und Simon Pflips

News

  • Die Ergebnisse zur Nachklausur sind in Blackboard eingetragen. Wer sein Ergebnis nicht sieht, kann sich an Stef Sijben wenden.
  • Die Einsicht zur Nachklausur findet am Freitag, den 29.07.2016, von 10 bis 11 Uhr in NA 2/64 statt.
  • Die Nachklausur findet am 20.7.2016 von 12 bis 15 Uhr im HIB statt.

Materialien

Übungsblätter

Anmerkung zu Aufgabe 7.3: Beachten Sie, dass beim Bestimmen der Endlichkeit der Sprache eine Grammatik ohne Ketten- und epsilon-regeln gesäubert wird. Die gegebene Grammatik enthält noch solche Regeln. Diese lassen sich leicht entfernen, indem die Regel A->epsilon gelöscht und die Regel B->a hinzugefügt wird, sowie die Regeln S -> B|C durch die Regeln S-> Aa|cCD ersetzt werden. Beachten Sie auch, dass beim Säubern erst die nicht generierenden Variablen gelöscht werden, bevor die erreichbaren Variablen bestimmt werden.

Vorlesungsskript

Kapitel 1: Formale Sprachen

Kapitel 2: Berechenbarkeitstheorie

Kapitel 3: Komplexitätstheorie

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 an dem Buch "Theoretische Informatik - kurzgefasst" von Uwe Schöning (Spektrum, 5. Auflage, 2009). Weitere empfehlenswerte Bücher sind:

  • Ingo Wegener: Theoretische Informatik – Eine algorithmenorientierte Einführung, 3. Auflage, Teubner, 2005
  • Ingo Wegener: Kompendium theoretische Informatik – Eine Ideensammlung, Teubner, 1996 (als Ergänzung)
  • John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexität, Pearson Studium, 3. Auflage, 2011
  • Michael Sipser: Introduction to the Theory of Computation, 2nd ed., Thomson Course Technology, 2006 (geht über den Stoff der Vorlesung hinaus)

Ebenfalls empfehlenswert ist das Vorlesungsskript aus dem WS 2012/2013, welches Sie hier finden. Dieses Skript enthält zusätzliche Materialien und Beispiele.

Ü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 Übungsgruppe (Di, Mi 14-16 oder Mi 8-10). 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 Mittwoch, acht Tage nach Veröffentlichung bis 10:00 möglich. Bitte werfen Sie 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 Maike Gruchot, Maike.Gruchot@rub.de, und Simon Pflips, Simon.Pflips@rub.de.

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 bzw. mündlichen Prüfung anteilig als Bonuspunkte gutgeschrieben. Dabei entsprechen 100% Punkte in den Übungsaufgaben 10% Punkte in der Klausur. Die maximal erreichte Punktezahl in der Abschlussklausur kann 100% nicht übersteigen. Dieser Bonus gilt nur für die Klausur bzw. mündliche Prüfung zum Wintersemester 15/16 und nicht für Klausuren in späteren Semestern.

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 am Donnerstag, den 25.02.2016 von 14:15 bis 17:15 in HGA10 und HGB10 stattfinden. Die Klausureinsicht ist am Donnerstag, den 03.03.2016von 10 bis 12 Uhr in NA 2/64.

Der Termin für die Nachschreibklausur ist Mittwoch, der 20.07.2016, von 12:00 bis 15:00 Uhr im HIB. 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, 2009), sowie auf dieser Seite veröffentlichte Materialien (mit Ausnahme der Übungsblätter und Beispiele) zugelassen. Notizen im Buch und Skript sind nicht zugelassen, Markierungen sind erlaubt.

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.

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

  • Mittwoch, den 24.2.2016
  • Mittwoch, den 6.4.2016

Bonuspunkte aus den Übungen werden nur am ersten Termin berücksichtigt.

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 Stef Sijben 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 (NA 02/73) 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.