Uni-Logo

Informatik III: Theoretische Informatik

Aktuelles Skript (github)Skript (WS2016/17)Altes Skript (WS2015/16)Übungsblätter ForumDaphne

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.2016Der Termin der Abschlussklausur ist inzwischen auf den 10.3.2017 festgelegt
21.11.2016Eine Musterlösung für uebung04 kann hier heruntergeladen werden.
27.10.2016Der Briefkasten zur Abgabe von Übungsblättern ist jetzt beschrifet: Informatik III WS2016/17
24.10.2016Korrektur der Übungsgruppen-Nummern. Sie entsprechen jetzt den Nummern im HISinOne.
19.10.2016Update der Homepage, Aktuelles Skript verlinkt
14.10.2016Vorlesungsmitschrieb WS2015/16 online.
11.10.2016Homepage online.

Lehrkräfte

Dozent Prof. Dr. Peter Thiemann thiemann@info...
ÜbungLuminous Fennellfennell@info...
Tutoren
  • Dominik Winterer
  • Jasmin Denk
  • Maya Schöchlin
  • Michael Steinle

Termine

Vorlesung Mittwoch, 14-16 c.t. HS 00 026, Geb. 101  
  Freitag, 14-16 c.t. HS 00 026, Geb. 101  
Übungsgruppe 1Dominik WintererMittwoch, 8-10 c.t.SR 00 031, Geb. 051
Übungsgruppe 2/3Jasmin DenkDonnerstag, 8-10 c.t.SR 00 031, Geb. 051
Übungsgruppe 4/5Michael SteinleDonnerstag, 16-18 c.t.SR 00-010/014, Geb. 101
Übungsgruppe 6Maya SchöchlinFreitag, 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:

Erfolgreiche Teilnahme an Übungen und Zwischenklausuren: 40 Prozent der Gesamtpunkte

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.