Informatik III: Theoretische Informatik
| Vorlesungsmaterialien | Forum | Daphne |
Ankündigungen
| 08.03.2016 | Am Montag, 14.03.2016, 9-11 Uhr findet in Raum SR 00-019 in Geb. 079 die Klausureinsicht statt. |
|---|---|
| 17.02.2016 | Das Deckblatt (ohne Punkteverteilung) zur Abschlussklausur ist online. |
| 17.02.2016 | Zu Übungsblatt 12 stehen Lösungsskizzen online. |
| 11.02.2016 | Am Freitag, 12.2.2016 findet keine Vorlesung statt. |
| 09.02.2016 | Am 23.2.2016, 10-12 Uhr findet in Geb. 079, rechts neben Raum 00 007 und/oder in Raum SR 00-019 eine Sprechstunde statt. |
| 29.01.2016 |
Die 2. Zwischenklausur
ist korrigiert und wird analog zu den Übungsblättern
zurückgegeben. Die Punktewertung ist wie bei der 1. Zwischenklausur festgelegt. Auf Daphne werden wieder die bereits skalierten Punkte erscheinen. |
| 19.1.2015 |
Do 28.01.2016: Vorlesung nachgeholt vom 27.01.2016 in Raum HS 00 026, Geb. 101 von 18-20 |
| 11.1.2015 |
Da Aufgabe 6 auf Übungsblatt 5 nicht in allen Gruppen vollständig besprochen werden konnte, ist eine Lösungsskizze online. |
| 8.1.2015 |
Do 14.01.2016: Vorlesung vorgezogen vom 15.01.2016 in Raum HS 00 026, Geb. 101 von 8-10 |
| 02.12.2015 | Der Vorlesungsmitschrieb von Ralph Lesch ist verlinkt. Ohne Gewähr! |
| 30.11.2015 |
Mi 16.12.2015: keine Vorlesung Fr 18.12.2015: regulär Vorlesung Mo 21.12.2015: Vorlesung nachgeholt vom 16.12.2015 in Raum SR 00-010/14, Geb. 101 von 8-10 Di 22.12.2015: Vorlesung vorgezogen vom 23.12.2015 in Raum SR 02-016/18, Geb. 101 von 8-10 Mi 23.12.2015: keine Vorlesung |
| 26.11.2015 |
Die Zwischenklausur ist korrigiert und wird analog zu den
Übungsblättern zurückgegeben. Die Punktewertung ist wie folgt festgelegt: Von 103 erreichbaren Punkten sind 88 Punkte notwendig um die maximale Klausurwertung zu erreichen. Klausurpunkte gehen mit Faktor 0,5 skaliert in die Übungspunktewertung ein: Zwei Klausurpunkte entsprechen also einem Übungspunkt. Damit entsprechen 88 Klausurpunkte gerade 44 Übungspunkten, also etwa 3 Übungsblättern. Auf Daphne werden die bereits skalierten Punkte erscheinen. |
| 10.11.2015 | Jeweils bis zu 10 neue Exemplare der unten genannten Literaturempfehlungen sind in der Universitätsbibliothek eingetroffen. |
| 23.10.2015 | Das Vorlesungsskript aus dem letzten Jahr ist online. |
| 22.10.2015 | Bitte melden Sie sich bei Daphne an, um in Zukunft wichtige Ankündigungen im Kursforum abonnieren zu können. |
| 22.10.2015 | Die Gruppenverteilung wurde noch einmal leicht angepasst und wird sich nun voraussichtlich nicht mehr ändern. Wir konnten nahezu allen Studenten und Studentinnen die Gruppe gemäß erster oder zweiter Priorität zuweisen. |
Lehrkräfte
| Dozent | Prof. Dr. Peter Thiemann | thiemann@info... |
| Übung | Manuel Geffken | geffken@info... |
| Tutoren |
|
Termine
| Vorlesung | Mittwoch, 16-18 c.t. | HS 00 026, Geb. 101 | ||
|---|---|---|---|---|
| Freitag, 10-12 c.t. | HS 00 026, Geb. 101 | |||
| 1. Zwischenklausur | Freitag, 20.11.2015, 10-12 c.t. | HS 00 026, Geb. 101 | ||
| 2. Zwischenklausur | Freitag, 22.01.2016, 10-12 c.t. | HS 00 026, Geb. 101 | ||
| Abschlussklausur | Mittwoch, 02.03.2016, 9-12 | HS 00 026, Geb. 101 (Nachname Anfangsbuchstaben Alt-Schw) | SR 01-016/01-018 (Nachname Anfangsbuchstaben Sieg-Z) | |
| Sprechstunde | Jannis Limperg | Dienstag, 10-12 c.t. | rechts neben Raum 00 007, Geb. 079 | |
| Übungsgruppe 1 | Saskia Rabald | Montag, 16-18 c.t. | SR 01 016, Geb. 101 | 5. Briefkasten von unten links |
| Übungsgruppe 2 | Coroline Räther | Dienstag, 12-14 c.t. | SR 00 006, Geb. 051 | 4. Briefkasten von unten links |
| Übungsgruppe 3 | Adrian Grupp | Dienstag, 12-14 c.t. | SR 00 034, Geb. 051 | 3. Briefkasten von unten links |
| Übungsgruppe 4 | Joshua Marben | Mittwoch, 8-10 c.t. | HS 03 026, Geb. 051 | 2. Briefkasten von unten links |
| Übungsgruppe 5 | Michael Steinle | Mittwoch, 8-10 c.t. | SR 00 031, Geb. 051 | 1. Briefkasten von unten links |
Ü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, 10:00 s.t., in die Briefkästen in Gebäude 051.
Die mit Ihren Abgaben erzielten Punkte können Sie mittels Daphne verfolgen.
| Datum | Abgabetermin | Blatt |
|---|---|---|
| 21.10.2015 | keine Abgabe | Präsenzübung |
| 23.10.2015 | 30.10.2015 | Übung 1 |
| 30.10.2015 | 06.11.2015 | Übung 2 |
| 06.11.2015 | 13.11.2015 | Übung 3 |
| 20.11.2015 | 27.11.2015 | Übung 4 |
| 27.11.2015 | 04.12.2015 | Übung 5 (aktualisiert am 30.11.) Lösung Übung 5, Aufgabe 5 |
| 04.12.2015 | 11.12.2015 | Übung 6 |
| 11.12.2015 | 18.12.2015 | Übung 7 |
| 18.12.2015 | 08.01.2016 | Übung 8 (aktualisiert am 07.01.) |
| 08.01.2016 | 15.01.2016 | Übung 9 (aktualisiert am 12.01.) |
| 22.01.2016 | 29.01.2016 | Übung 10 |
| 29.01.2016 | 05.02.2016 | Übung 11 |
| 05.02.2016 | 12.02.2016 | Übung 12 Lösung 12 |
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 muss die folgenden Bedingungen erfüllen:
- Erfolgreiche Teilnahme an Übungen und Zwischenklausuren: 40 Prozent der Gesamtpunkte
- 1 mal Vorrechnen in den Tutoraten
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.