Informatik III: Theoretische Informatik
| Aktuelles Skript (github) | Skript (WS2016/17) | Altes Skript (WS2015/16) | Übungsblätter | Forum | Daphne |
Ankündigungen
| 03.03.2017 | Ein Übungsblatt aus WS2015 mit Lösung ist jetzt online. Es behandelt Komplexitätstheorie. |
|---|---|
| 23.02.2017 | Eine Musterlösung für Blatt 12 ist online. |
| 20.02.2017 | Die Zulassungsberechtigten haben knapp mehr als 55% der Übungspunkte erreicht :) Bei der Klausur sind zwei Din-A4 Blätter, beidseitig, handbeschrieben als Unterlagen erlaubt. |
| 28.11.2016 | Der Termin der Abschlussklausur ist inzwischen auf den 10.3.2017 festgelegt |
| 21.11.2016 | Eine Musterlösung für uebung04 |
| 27.10.2016 | Der Briefkasten zur Abgabe von Übungsblättern ist jetzt beschrifet: Informatik III WS2016/17 |
| 24.10.2016 | Korrektur der Übungsgruppen-Nummern. Sie entsprechen jetzt den Nummern im HISinOne. |
| 19.10.2016 | Update der Homepage, Aktuelles Skript verlinkt |
| 14.10.2016 | Vorlesungsmitschrieb WS2015/16 online. |
| 11.10.2016 | Homepage online. |
Lehrkräfte
| Dozent | Prof. Dr. Peter Thiemann | thiemann@info... |
| Übung | Luminous Fennell | fennell@info... |
| Tutoren |
|
Termine
| Vorlesung | Mittwoch, 14-16 c.t. | HS 00 026, Geb. 101 | ||
|---|---|---|---|---|
| Freitag, 14-16 c.t. | HS 00 026, Geb. 101 | |||
| Übungsgruppe 1 | Dominik Winterer | Mittwoch, 8-10 c.t. | SR 00 031, Geb. 051 | |
| Übungsgruppe 2/3 | Jasmin Denk | Donnerstag, 8-10 c.t. | SR 00 031, Geb. 051 | |
| Übungsgruppe 4/5 | Michael Steinle | Donnerstag, 16-18 c.t. | SR 00-010/014, Geb. 101 | |
| Übungsgruppe 6 | Maya Schöchlin | Freitag, 8-10 c.t. | SR 02-017, Geb. 52 | |
| 1. Zwischenklausur | Mittwoch, 23.11.2015, 14-16 c.t. | HS 00 026, Geb. 101 | ||
| 2. Zwischenklausur | Freitag, 20.01.2017, 14-16 c.t. | HS 00 026, Geb. 101 | ||
| Abschlussklausur | 10.03.2017, 09.00 s.t. | HS 00 026/036, Geb. 101 | ||
Übungsblätter
Neue Übungsblätter erscheinen freitags, in der Regel nach der Vorlesung. Die Abgabe der Übungsblätter erfolgt
bis zum Freitag in der darauffolgenden Woche, 14:00 s.t., in den Briefkasten mit Aufschrift Informatik III WS 2016/17
in Gebäude 051 (EG). Der Briefkasten ist der zweitunterste in der rechten Spalte.
Bitte die Nummer der Übungsgruppe auf die Lösung schreiben.
Die mit Ihren Abgaben erzielten Punkte können Sie mittels Daphne verfolgen.
Inhalte
Die Vorlesung gibt eine Einführung in die Theoretische Informatik. Sie führt in die Themen Endliche Automaten, Formale Sprachen und Grammatiken ein und liefert mehrere äquivalente präzise Fassungen des Berechenbarkeitsbegriffs. Es schließt sich eine Einführung in die Komplexitätstheorie, speziell die Theorie der NP-Vollständigkeit, an. Behandelt werden abstrakte Modelle von Maschinen und Sprachen, mit deren Hilfe Komplexitätsmaße wie Schrittzahl (Laufzeit) und Speicherbedarf von Algorithmen präzise definiert werden.
Literatur
Quellen:
- Ingo Wegener. Kompendium Theoretische Informatik, 3. Auflage. Teubner Verlag, 2005.
- Uwe Schoening. Theoretische Informatik kurz gefasst. BI Wissenschaftsverlag.
- Hartmut Noltemeier. Informatik 1: Einführung in Algorithmen und Berechenbarkeit. Hanser, 1993.
- Katrin Erk, Lutz Priese. Theoretische Informatik. 3. Auflage. Springer 2008.
Standardwerke (in Englisch):
- Hopcroft, Motwani, Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 2001.
- Salomaa. Formal Languages. Academic Press, 1973.
Voraussetzungen
Wir setzen Kenntnisse von Informatik I und Informatik II voraus.
Ziele
Übungsmodus
- ~ 12 bewertete Übungsblätter
- 2 Zwischenklausuren (Gewichtung: 3 Übungsblätter)
Zulassung zu Klausur
Eine erfolgreiche Teilnahme an der Veranstaltung (und somit die Zulassung zur Klausur) muss die folgenden Bedingung erfüllen:
Durch korrektes Vorrechnen einer Aufgabe in den Übungsgruppen werden Ihnen die Punkte der Aufgabe nochmals als Bonuspunkte angerechnet. Falls sich herausstellt, dass die zur Klausur zugelassenen Studierenden im Durchschnitt mehr als 55% erreicht haben, werden in der Klausur einen begrenzte Seitenanzahl selbstgeschriebener Unterlagen zugelassen. Ansonsten werden keine Hilfmittel erlaubt sein.
Tutorate (kleine Übungsgruppen)
Es finden wöchentliche Tutorate in kleinen Gruppen statt. Dabei werden die Lösungen der Übungsaufgaben besprochen und Sie haben Gelegenheit Ihre Lösung vorzustellen. Zeit und Ort Ihrer Übungsgruppe können Sie unter Ihrer Belegung im Campus Management entnehmen.
Kommunikation
Zur Kommunikation können die Teilnehmer und Teilnehmerinnen das Kurs-Forum verwenden. Die Anmeldung erfolgt mit den myAccount (RZ) Kenndaten. Wichtige Ankündigungen werden auch im Forum getätigt.