Einführung in die theoretische Informatik
Prof. Tobias Nipkow, Sommersemester 2019
- TUMonline: IN0011 SS19
- Vorlesung: Montag, 14:00–16:00, und Donnerstag, 14:00-16:00, jeweils in MW001
- Sprechstunde: Donnerstag 16:00-16:45 in MI HS1
- Übungsleitung: Manuel Eberl, Jonas Rädle, Simon Wimmer (Kontakt: theo-uebungsleitung (at) in.tum.de)
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 ≡L v ↔ u = 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
Vorlesungsaufzeichnungen (TeleTeaching)
Vorlesungsaufzeichnungen (RBG)
Musterlösung zur Klausur vom 9.8.2019
Musterlösung zur Klausur vom 1.10.2019
Übungsbetrieb
Übungsblätter
- Angabe | Lösung
- Angabe | Lösung
- Angabe | Lösung
- Angabe | Lösung
- Angabe | Lösung
- Angabe | Lösung
- Angabe | Lösung
- Angabe | Lösung
- Angabe | Lösung
- Angabe | Lösung
- Angabe | Lösung
- Angabe | Lösung
- Angabe | Lösung
Knobelblätter
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.
| Tag | von | bis | Name | Ort | Tutor |
|---|---|---|---|---|---|
| MO | 12:00 | 14:00 | Mo-12-■ | 00.08.059 | Paul Bachmann |
| MO | 12:00 | 14:00 | Mo-12-●-(1) | 00.08.038 | Niklas Kemper |
| MO | 12:00 | 14:00 | Mo-12-●-(2) | 02.07.023 | Leo Tappe |
| MO | 12:00 | 14:00 | Mo-12-●-(3) | 02.07.014 | Philipp Hagenlocher |
| MO | 12:00 | 14:00 | Mo-12-●-(4) (E) | 02.07.034 | Arin Mirza |
| MO | 16:00 | 18:00 | Mo-16-■ | 03.09.012 | Fabian Reiter |
| MO | 16:00 | 18:00 | Mo-16-●-(1) (E) | 03.11.018 | Arin Mirza |
| MO | 16:00 | 18:00 | Mo-16-●-(2) | 00.13.036 | Herbert Ehler |
| MO | 16:00 | 18:00 | Mo-16-●-(3) | 03.09.014 | Alexander Taepper |
| DI | 08:00 | 10:00 | Di-08-●-(1) | 00.08.059 | Ina Seidel |
| DI | 08:00 | 10:00 | Di-08-●-(2) | 01.06.020 | Alexander Taepper |
| DI | 10:00 | 12:00 | Di-10-● | 00.08.053 | Benedikt Seidl |
| DI | 16:00 | 18:00 | Di-16-● | 02.13.010 | Philipp Hagenlocher |
| MI | 10:00 | 12:00 | Mi-10-●-(1) | 02.13.010 | Maximilian Schäffeler |
| MI | 10:00 | 12:00 | Mi-10-●-(2) | 00.13.036 | Martin Schonger |
| MI | 10:00 | 12:00 | Mi-10-●-(3) | 00.08.053 | Paul Bachmann |
| MI | 10:00 | 12:00 | Mi-10-●-(4) | 00.08.036 | Patrick Lederer |
| MI | 12:00 | 14:00 | Mi-12-●-(1) | 01.06.011 | Leo Tappe |
| MI | 12:00 | 14:00 | Mi-12-●-(2) | 01.11.018 | Maximilian Schäffeler |
| MI | 12:00 | 14:00 | Mi-12-●-(3) | 03.09.014 | Patrick Lederer |
| MI | 12:00 | 14:00 | Mi-12-■ | 02.13.010 | Jonas Rädle |
| MI | 14:00 | 16:00 | Mi-14-■ | 01.09.014 | Stefan Jaax |
| MI | 14:45 | 16:15 | Mi-14-● | MW2235 | Benedikt Seidl |
| MI | 16:00 | 18:00 | Mi-16-● | 00.08.053 | Christian Herzog |
| DO | 08:00 | 10:00 | Do-08-■ | 00.08.036 | Manuel Eberl |
| DO | 08:00 | 10:00 | Do-08-●-(1) | 03.09.014 | Adrián Löwenberg |
| DO | 08:00 | 10:00 | Do-08-●-(2) | 00.13.036 | Ina Seidel |
| DO | 10:00 | 12:00 | Do-10-●-(1) | 00.08.038 | Martin Schonger |
| DO | 10:00 | 12:00 | Do-10-●-(2) | 03.11.018 | Jakob Schulz |
| DO | 12:00 | 14:00 | Do-12-●-(1) | 02.07.014 | Jakob Schulz |
| DO | 12:00 | 14:00 | Do-12-●-(2) | 01.07.023 | Adrián Löwenberg |
| DO | 12:00 | 14:00 | Do-12-●-(3) | 03.09.012 | Niklas Kemper |
| DO | 12:00 | 14:00 | Do-12-■ | 03.09.014 | Simon Wimmer |
| FR | 10:00 | 12:00 | Fr-10-● | 03.11.018 | Mariia Stankevych |
| FR | 12:00 | 14:00 | Fr-12-● | 00.08.038 | Mariia 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 handschriflichen Hausaufgaben werden in Zweier-Teams bearbeitet.
- Die Teams werden in der ersten Übungswoche mit Ihrem Tutor festgelegt.
- Sie dürfen auch gruppenübergreifend Teams bilden.
- Sollte dies bei Ihnen nicht funktionieren, kontaktieren sie die Übungsleitung unter theo-uebungsleitung(at)in.tum.de.
- Jedes Mitglied Ihres Teams muss 3 der 6 handschriftlichen Abgaben selbst geschrieben haben.
- Die Abgabe soll komplett von einem der Teammitglieder geschrieben sein. Sie dürfen trotzdem innerhalb eines Teams selbstverständlich die Lösung gemeinsam erarbeiten.
- Die Teams bestehen aus genau zwei Leuten; bei Einzelabgaben besteht kein Anspruch auf Korrektur, Dreier-Teams sind nicht erlaubt.
- Die Abgabe kann auf Deutsch oder Englisch verfasst sein.
Die Hausaufgaben müssen in die Briefkästen in der Magistrale eingeworfen werden.
Damit die Abgabe korrigiert wird, sind folgende Punkte zu beachten:
- Die Hausaufgaben müssen rechtzeitig bis zu dem auf dem jeweiligen Blatt angegebenen Zeitpunkt abgegeben werden.
- Die Abgabe findet dabei in den entsprechend gekennzeichneten Briefkästen im Untergeschoss des FMI Gebäudes statt.
- Bitte überprüfen Sie vor dem Einwerfen, dass Sie den richtigen Briefkasten vor sich haben. Falsch eingeworfene Abgaben können im Allgemeinen nicht beachtet werden.
- Die Abgabe muss geeignet geheftet sein.
- Folgendes Deckblatt muss vorne an Ihre Abgabe geheftet sein.
- Tragen Sie die Gruppe auf dem Deckblatt ein, in der Sie die Abgabe zurückbekommen möchten.
- Schreiben Sie beide Namen und Matrikelnummern auf das Deckblatt.
- Machen Sie kenntlich, wer die Abgabe verfasst hat.
- Die Abgabe muss handschriftlich verfasst sein.
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.
| Raumcode | Raumbezeichnung | Nachnamen |
| 5508.01.801 | MW1801 | A-Em |
| 5510.EG.001 | MW0001 | En-Na |
| 5620.01.101 | Interims I Hörsaal 1 | Ne-Stei |
| 5620.01.102 | Interims I Hörsaal 2 | Stem-Z |