Einführung in die theoretische Informatik

Prof. Tobias Nipkow, Sommersemester 2019

Neuigkeiten

  • 25.09.: Die Hörsaaleinteilung für die Wiederholungsklausur finden sie nun im Abschnitt „Wiederholungsklausur“. Die Sitzordnung wird an den Hörsaaltüren aushängen.
  • 16.07.: Xiaohu Wang (王小虎) hat Knobelaufgabe 1.1 gelöst (eigentlich schon am 04.06., aber die Übungsleitung war zu faulbeschäftigt).
  • 27.06.: Die Wiederholungsklausur wird am 01.10.2019 stattfinden.
  • 05.06.: Beachten Sie bei der Hausaufgabe 6.4 dass mit dem "Bestimmen" der Äquivalenzklassen gemeint ist dass Sie explizit angeben sollen welche Wörter in den jeweiligen Klassen enthalten sind. Geben Sie also insbesondere nicht nur die Repräsentanten der Klassen an.
  • 28.05.: Dongwoo Oh (오동우) hat Knobelblatt 1 komplett gelöst. Wir sind dennoch bis zum Ende des Semesters weiterhin an anderen Lösungen interessiert.
  • 23.05.: Johannes Neubrand hat Knobelaufgaben 1.1–1.3 gelöst.
  • 23.05.: Radu Vintan hat Knobelaufgabe 1.3 gelöst (Sprachen über einelementigen Alphabeten).
  • 20.05.: Hausaufgabenblatt 4 wurde angepasst: Aufgrund technischer Probleme werden auf die AutomataTutor Aufgaben auf diesem Blatt keine Punkte vergeben, als Ersatz wurde bei Aufgabe 4.3 die Teilaufgabe (c) hinzugefügt.
  • 17.05.: Johannes Neubrand und später auch Radu Vintan haben korrekte Lösungen für die folgende Knobelaufgabe eingeschickt: Sei L = {ww | w ∈ Σ*}. Zeigen Sie, dass für jedes Paar von Wörtern u, v ∈ Σ* gilt: u ≡Lvu = v (d.h. jedes Wort bildet eine eigene Myhill–Nerode-Klasse).
  • 06.05.: Die Übungsgruppen am Mittwoch den 08.05. von 10-12 Uhr entfallen aufgrund der Fachschaftsvollversammlung. Bitte verteilen Sie sich auf die restlichen Übungsgruppen.
  • 03.05.: Die Übungsgruppe Do-10-●-(2) wurde aufgrund eines Raumkonflikts in den Seminarraum 03.11.018 verlegt.
  • 23.04.: Informationen zu Übungen, Hausaufgaben und Klausur.
  • 12.03.: Erstellung der Website.

Material

Folien

Vorlesungsaufzeichnungen (TeleTeaching)

Vorlesungsaufzeichnungen (RBG)

Klausurangabe vom 9.8.2019

Musterlösung zur Klausur vom 9.8.2019

Klausurangabe vom 1.10.2019

Musterlösung zur Klausur vom 1.10.2019

Übungsbetrieb

Übungsblätter

  1. Angabe | Lösung
  2. Angabe | Lösung
  3. Angabe | Lösung
  4. Angabe | Lösung
  5. Angabe | Lösung
  6. Angabe | Lösung
  7. Angabe | Lösung
  8. Angabe | Lösung
  9. Angabe | Lösung
  10. Angabe | Lösung
  11. Angabe | Lösung
  12. Angabe | Lösung
  13. Angabe | Lösung

Knobelblätter

  1. Angabe (Update 26.5.)
  2. Angabe (Update 11.7.)

Anmeldung zu den Tutorgruppen

Die Anmeldung zu den Tutorgruppen findet auf TUMonline statt. Die Anmeldung beginnt am 25.04. um 19 Uhr (Mi und Do Gruppen) bzw. 19:30 Uhr (restliche Gruppen), und endet am 06.05. um 23:59 Uhr. Die Plätze werden nach dem first come, first served Prinzip vergeben.

Vom 29.04. bis 01.05 ist TUMonline aufgrund von Wartungsarbeiten nicht verfügbar, in diesem Zeitraum können sie sich nicht für die Tutorgruppen anmelden.

Tutorgruppen

Es werden zwei Arten von Tutorgruppen angeboten: Übungsgruppen (●) und Vertiefungsgruppen (■). Die mit (E) markierten Gruppen werden auf Englisch gehalten.

Beide Arten von Gruppen enthalten alle wichtigen Inhalte, um die Klausur zu bestehen; sie unterscheiden sich aber in ihrem Schwerpunkt, Ziel und in den bearbeiteten Aufgaben. Während Übungsgruppen größtenteils das Anwenden der Vorlesungsinhalte üben (Typen C und D), ist in Vertiefungsgruppen Zeit für Aufgaben, die es von Ihnen verlangen Erlerntes in neuen Kontexten anzuwenden (Typ E).

Alle Tutorgruppen setzen voraus, dass Sie sich bereits mit dem Stoff auseinandergesetzt haben. Dazu befinden sich auf jedem Übungsblatt Definitionen und Begriffe, die sie kennen und verstehen sollten und leichte Anwendungsaufgaben (Typen A und B). Diese sollten Sie vor den Tutorübungen durcharbeiten.

Melden Sie sich für den Gruppentyp an, den Sie vermehrt besuchen wollen. Sie haben jede Woche die Möglichkeit, sich innerhalb des von Ihnen gewählten Slots frei für eine Tutorübung zu entscheiden.

Auf TUMonline sind die Tutorgruppen in eine Veranstaltung für Mi und Do Gruppen und eine Veranstaltung für Mo, Di, und Fr Gruppen aufgeteilt.

TagvonbisNameOrtTutor
MO12:0014:00Mo-12-■00.08.059Paul Bachmann
MO12:0014:00Mo-12-●-(1)00.08.038Niklas Kemper
MO12:0014:00Mo-12-●-(2)02.07.023Leo Tappe
MO12:0014:00Mo-12-●-(3)02.07.014Philipp Hagenlocher
MO12:0014:00Mo-12-●-(4) (E)02.07.034Arin Mirza
MO16:0018:00Mo-16-■03.09.012Fabian Reiter
MO16:0018:00Mo-16-●-(1) (E)03.11.018Arin Mirza
MO16:0018:00Mo-16-●-(2)00.13.036Herbert Ehler
MO16:0018:00Mo-16-●-(3)03.09.014Alexander Taepper
DI08:0010:00Di-08-●-(1)00.08.059Ina Seidel
DI08:0010:00Di-08-●-(2)01.06.020Alexander Taepper
DI10:0012:00Di-10-●00.08.053Benedikt Seidl
DI16:0018:00Di-16-●02.13.010Philipp Hagenlocher
MI10:0012:00Mi-10-●-(1)02.13.010Maximilian Schäffeler
MI10:0012:00Mi-10-●-(2)00.13.036Martin Schonger
MI10:0012:00Mi-10-●-(3)00.08.053Paul Bachmann
MI10:0012:00Mi-10-●-(4)00.08.036Patrick Lederer
MI12:0014:00Mi-12-●-(1)01.06.011Leo Tappe
MI12:0014:00Mi-12-●-(2)01.11.018Maximilian Schäffeler
MI12:0014:00Mi-12-●-(3)03.09.014Patrick Lederer
MI12:0014:00Mi-12-■02.13.010Jonas Rädle
MI14:0016:00Mi-14-■01.09.014Stefan Jaax
MI14:4516:15Mi-14-●MW2235Benedikt Seidl
MI16:0018:00Mi-16-●00.08.053Christian Herzog
DO08:0010:00Do-08-■00.08.036Manuel Eberl
DO08:0010:00Do-08-●-(1)03.09.014Adrián Löwenberg
DO08:0010:00Do-08-●-(2)00.13.036Ina Seidel
DO10:0012:00Do-10-●-(1)00.08.038Martin Schonger
DO10:0012:00Do-10-●-(2)03.11.018Jakob Schulz
DO12:0014:00Do-12-●-(1)02.07.014Jakob Schulz
DO12:0014:00Do-12-●-(2)01.07.023Adrián Löwenberg
DO12:0014:00Do-12-●-(3)03.09.012Niklas Kemper
DO12:0014:00Do-12-■03.09.014Simon Wimmer
FR10:0012:00Fr-10-●03.11.018Mariia Stankevych
FR12:0014:00Fr-12-●00.08.038Mariia Stankevych

Notenbonus

Durch Bearbeiten der Hausaufgabenblätter können Sie einen Notenbonus erhalten. Der Notenbonus wird nur im Falle des Bestehens der Klausur (Klausurnote ≤ 4,0) eingerechnet. Der Notenbonus kann also nicht zum Bestehen der Klausur verwendet werden. Die Endnote kann durch den Notenbonus maximal auf 1,0 verbessert werden. Der Notenbonus gilt ausschließlich für die beiden Klausuren im Sommersemester 2019. D.h. bei Nichtbestehen der Erstklausur bleibt der Notenbonus auch für die Nachholklausur bestehen.

In den Hausaufgaben können maximal 60 Punkte erreicht werden. Der Notenbonus staffelt sich wie in der folgenden Tabelle dargestellt:

Bonus Von (Punkte) Bis (Punkte)    
0.0 0 39.5    
0.3 40 46.5    
0.6 47 53.5    
1.0 54 60    

Hausaufgaben

Hausaufgabenblätter

Die Hausaufgaben (sowohl zur schriftlichen Abgage als auch Programmierabgaben) werden in der Regel am Montag nach der Vorlesung online sein, und sind bis zum Beginn der Vorlesung am darauffolgenden Montag abzugeben.

Achtung: Plagiate bei Hausaufgaben führen zum sofortigen Verwirken des Notenbonus.

Beachten Sie auch die weiterführenden Hinweise zu den Programmieraufgaben.

Abgabeblatt Template Lösung Abgabe bis
Programmieraufgabe 1 templates_ha_01.tar.gz solutions_ha_01.tar.gz 06.05.2019, 14:00
Schriftliche Hausaufgabe 2 Lösung 13.05.2019, 14:00
Programmieraufgabe 3 templates_ha_03.tar.gz solutions_ha03.tar.gz 20.05.2019, 14:00
Schriftliche Hausaufgabe 4 Lösung 27.05.2019, 14:00
Programmieraufgabe 5 templates_ha_05.tar.gz solutions_ha05.tar.gz 03.06.2019, 14:00
Schriftliche Hausaufgabe 6 Lösung 13.06.2019, 14:00
Programmieraufgabe 7 templates_ha_07.tar.gz solutions_ha07.tar.gz 18.06.2019, 14:00
Programmieraufgabe 8 templates_ha_08.tar.gz solutions_ha08.tar.gz 24.06.2019, 14:00
Schriftliche Hausaufgabe 9 Lösung 01.07.2019, 14:00
Schriftliche Hausaufgabe 10 Lösung 08.07.2019, 14:00
Schriftliche Hausaufgabe 11 Lösung 15.07.2019, 14:00
Schriftliche Hausaufgabe 12 Lösung 22.07.2019, 14:00

Handschriftliche Abgaben

In jeder zweiten Woche gibt es ein Hausaufgabenblatt, das Sie handschriftlich bearbeiten.

Die Hausaufgaben müssen in die Briefkästen in der Magistrale eingeworfen werden.

Damit die Abgabe korrigiert wird, sind folgende Punkte zu beachten:

Bei Nichtbeachtung dieser Punkte besteht (aus organisatorischen Gründen) kein Anspruch auf Korrektur bzw. Wertung der Abgabe.

Programmieraufgaben

In jeder zweiten Woche gibt es statt eines handschriflichen Abgabeblattes eine Programmieraufgabe. Dabei sollen Sie die grundlegenden Strukturen und Algorithmen der theoretischen Informatik sowie einige Anwendungen des Gelernten implementieren.

Die Programmieraufgaben werden nicht in Teams bearbeitet. Jeder Student muss seine Abgabe selbst verfassen und hochladen.

Für die Korrektur Ihrer Programmierabgaben wird TUMjudge verwendet. Auf dem ersten Hausaufgabenblatt werden die für Sie relevanten Funktionen des Webinterfaces erklärt. Weitere Details finden Sie auf den Folien des Praktikums “Algorithms for Programming Contests von 2017”.

Wiederholungsklausur

Die schriftliche Wiederholungsklausur findet am 01.10.2019 von 08-11 Uhr statt. Als Hilfsmittel sind ein beidseitig handschriftlich beschriebenes DIN A4 Blatt und ein Wörterbuch Deutsch-Muttersprache ohne Anmerkungen erlaubt. Die Hörsaaleinteilung entnehmen sie der folgenden Tabelle.

RaumcodeRaumbezeichnungNachnamen
5508.01.801MW1801A-Em
5510.EG.001MW0001En-Na
5620.01.101Interims I Hörsaal 1Ne-Stei
5620.01.102Interims I Hörsaal 2Stem-Z