RUB » LMI » Lehre » Theoretische Informatik WS 2019/2020

Theoretische Informatik WS 2019/2020

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: Maike Buchin
Übungen: Daniel Pasler und Christoph Ries
2 std.
Gruppe 1: Di 14:00-16:00 in IA 1/63 (Ries) oder
Gruppe 2: Di 14:00-16:00 in NB 5/99 (Pasler) oder
Gruppe 3: Mi 08:30-10:00 in IA 1/181 (Pasler) oder
Gruppe 4: Mi 14:00-16:00 in IA 1/63 (Ries)
die erste Übung findet am 15.10. bzw. 16.10. statt
Korrektur der Hausaufgaben: Lea Thiel

News

  • 04.09.2020   Die Einsicht zur Nachklausur findet am 22.09.2020 ab 11 Uhr unter den aktuellen Corona-Regeln im Raum IA 02/445 statt. Bitte kommen Sie entsprechend des ersten Buchstaben Ihres Nachnamens um folgende Uhrzeit: A-F 11:00, G-M 11:10, N-Z 11:20 Uhr. Bitte denken Sie daran Abstand zu halten und eine Maske zu tragen.
  • 01.09.2020   Die Ergebnisse der Klausur stehen nun fest. Die eigene Note kann unter dem Link https://www.ruhr-uni-bochum.de/lmi/lehre/ti_ws1920/ke/<Ziffern>.txt eingesehen werden. Statt <Ziffern> sind die letzten fünf Ziffern der eigenen Matrikelnummer einzusetzen. Zum Bestehen sind 50% der Punkte erforderlich.
  • 13.07.2020   Die Nachklausur am 15.7.20 findet unter den aktuellen Corona-Regeln statt. Insbesondere sollten Sie Abstand halten (auch vor dem Hörsaal), eine MundNasenBedeckung tragen (während der Klausur dürfen Sie diese ablegen) und pünktlich um 10:00 Uhr am Hörsaal HGB 10 sein, damit die Klausur um 10:15 Uhr starten kann. Näheres finden Sie hier und wird auch bei der Klausur angekündigt.
  • 18.06.2020   Die Einsicht zur ersten Klausur findet statt am Donnerstag, den 25.6.20, ab 12 Uhr im Hörsaal HMA 40. Dabei sind die Abstandsregeln unbedingt einzuhalten. Bitte kommen Sie entsprechend des ersten Buchstaben Ihres Nachnamen: A-D 12:00 - 12:10, E-H 12:10 - 12:20, I-L 12:20 - 12:30, M-P 12:30-12:40, Q-U 12:40-12:50, V-Z 12:50-13:00 Uhr.
  • 10.06.2020   Die Nachklausur findet statt am Mittwoch, den 15.7.20, ab 10 Uhr im Hörsaal HGB 10.
  • 16.03.2020   Die Klausureinsicht entfällt wegen der Schließung der RUB bis auf Weiteres. Falls sie doch stattfinden kann, wird dies hier bekanntgegeben.
  • 05.03.2020   Die Ergebnisse der Klausur stehen nun fest. Die eigene Note kann unter dem Link https://www.ruhr-uni-bochum.de/lmi/lehre/ti_ws1920/kn/<Ziffern>.txt eingesehen werden. Statt <Ziffern> sind die letzten fünf Ziffern der eigenen Matrikelnummer einzusetzen. Zum Bestehen sind 50% der Punkte erforderlich. Beachte für die Einsicht das nachfolgende Dokument mit Anmerkungen zur Klausur (Anmerkungen). Beachte weiter, dass die Einsicht dazu da ist, die eigene Klausur zu prüfen, und nicht dazu da ist, um korrekte Lösungen zu erfragen. Es stehen jedem bei der Einsicht maximal 10 Minuten zur Verfügung.

    Sie haben das Recht, nach Ablauf der Aufbewahrungsfrist von 2 Jahren die Klausur ausgehändigt zu bekommen. Wenn Sie davon Gebrauch machen wollen, melden Sie Ihr Interesse innerhalb der sechs Monate vor Ablauf der Frist per Mail an Katharina.Weissman@rub.de mit dem Betreff „Klausurrückgabe“. Bitte nennen Sie in der Mail die Veranstaltung und das Datum, an dem die Klausur geschrieben wurde. Sie werden nach Ablauf der Aufbewahrungsfrist per Mail kontaktiert. Bitte beachten Sie, dass es nach Rücknahme der Klausur nicht erlaubt ist, diese zu veröffentlichen.

  • 06.02.2020   Die Einsicht zur Klausur vom 05.02.2020 findet am Freitag, den 03.04.2020, um 13 Uhr in IA 1/63 statt. Sobald die Ergebnisse der Klausur feststehen, wird dies hier bekannt gegeben.
  • 04.02.2020   Der zweite Termin für die mündlichen Prüfungen steht nun fest - siehe Unterpunkt "Mündliche Prüfungen".
  • 31.01.2020   Die korrigierten Abgaben zu Blatt 12 liegen nun vor. Sie können heute, Fr, zwischen 13 und 16 Uhr, sowie Mo zwischen 14 und 16 Uhr in IB 3/147 abgeholt werden.
  • 24.01.2020   Die Vorlesung am 29. Januar 2020 entfällt.
  • 23.01.2020   Die Übungen am 28. und 29. Januar 2020 entfallen. Sie werden durch Sprechzeiten ersetzt. Christoph ist in dem jeweiligen Übungsraum und Daniel in seinem Büro anzutreffen.
  • 22.01.2020   Beachte: Bei den Aufgaben von Blatt 12 muss gezeigt werden, dass die Reduktionsabbildung in polynomieller Zeit berechenbar ist.
  • 22.01.2020   Einen Hinweis zu seinen erreichten Punkten bei den Hausaufgabenblättern erhält man bis zum 05. Februar 2020 unter dem Link https://www.ruhr-uni-bochum.de/lmi/lehre/ti_ws1920/hap/<Ziffern>.txt. Statt <Ziffern> sind die letzten fünf Ziffern der eigenen Matrikelnummer einzusetzen.
  • 08.01.2020   Bei Aufgabe 10.4 wurde in der Definition von Sigma der Schneemann durch einen Schlitten ersetzt.
  • 04.12.2019   Die Beschreibung der KNF im Skript wurde korrigiert.
  • 02.12.2019   Zu Aufgabenblatt 7: In der KNF dürfen auch Kettenregeln genutzt werden.
  • 02.12.2019   Studierende der AI evaluieren die Vorlesung bitte auch "hier "
  • 08.11.2019   Bei Aufgabenblatt 4 wurde bei 4 a) die Angabe L durch T(M) ersetzt.
  • 07.11.2019   Der Termin für die mündlichen Prüfungen steht fest - siehe Unterpunkt "Mündliche Prüfungen".
  • 31.10.2019   Der Klausurtermin steht fest - siehe Unterpunkt "Klausur".
  • 22.10.2019   Die Hausaufgaben sind nach Aufgaben getrennt abzugeben. Für die Abgabe sind nur die Formate DIN A4 oder DIN A5 zulässig.
  • 16.10.2019   Übungsgruppe 1 ist voll. In Übungsgruppe 2 sind noch Plätze frei. In Gruppe 3 gibt es ein paar freie Plätze. Gruppe 4 ist voll, aber wenige zusätzliche Stühle könnten eventuell aufgetrieben werden.
  • 16.10.2019   Neue Version von Blatt 1 verfügbar: Eine fehlende Regel wurde bei Aufgabe 1 ergänzt.
  • 21.08.2019   Die erste Vorlesung findet bereits am Montag, 07.10.2019, in HGA 30 statt.

Materialien

Übungsblätter

Präsenzblätter

Vorlesungsskript

Kapitel 1: Formale Sprachen

Kapitel 2: Berechenbarkeitstheorie

Kapitel 3: Komplexitätstheorie

Zusätzliche Kapitel

Dieser Teil des Vorlesungsskriptes ist nicht prüfungsrelevant

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

Übungsaufgaben

Im Laufe des Semesters sind wöchentlich Übungsaufgaben zu lösen. Es werden nur handschriftliche Abgaben gewertet. Nutzen Sie dabei einen dokumentenechten Stift. Bitte notieren Sie 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 werfen Sie die Aufgaben in den Abgabekasten auf IA 0 neben dem Eingang. Die Rückgabe der korrigierten Zettel erfolgt in den Übungsgruppen.

Korrektur

Die Korrektur wird von Lea Thiel, lea.thiel@rub.de übernommen (Sprechstunde: n.V.).

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 19/20 und nicht für spätere Klausuren. Bei einer mündlichen Prüfung wird bei Erreichen von 60% der Punkte in den Übungen ein Bonus von -0,3 gewährt, wobei die Bestnote von 0,7 nicht verbessert werden kann. Dieser Bonus gilt nur für mündliche Prüfungen am ersten Termin.

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 dreistündige Klausur findet am Mittwoch, den 05. Februar 2020, ab 10 Uhr s.t. in HNC 10 statt.

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 19/20 eine mündliche Prüfung angeboten. Der Termin für die mündlichen Prüfungen ist Dienstag, der 04. Februar 2020.

Der zweite Termin für die mündlichen Prüfungen ist Donnerstag, der 02. April 2020.

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 (IB 1/111) 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