Prof. (apl) Dr. Beate Bollig |
[Termine] [Hinweis] [Inhalt und Lernziele] [Literatur] [Moodle] [Prüfungen] [Übungen] [Veranstaltungsmaterialien] [Vorlesungsplan]
Wann? | Wo? | |
Vorlesung | Di 10:15 - 12:00 | HG2/HS 3 |
Vorlesung | Do 12:15 - 14:00 | HG2/HS 3 |
Die Veranstaltung beginnt am 02.04.19.
Die Tutorien beginnen am 09.04.19.
Diese Veranstaltung ersetzt im Sommersemester 2019 die Module INF-BSc-112 (Theoretische Informatik für Studierende der Angewandten Informatik) und INF-BL-105, INF-BL-112, INF-BL-113 (Theoretische Informatik für BK).
Studierende der Diplomstudiengänge Informatik melden sich bitte vorab elektronisch bei der Veranstalterin.
Die Veranstaltung Grundbegriffe der Theoretischen Informatik behandelt grundlegende Ergebnisse aus den Teilgebieten Automatentheorie, Grammatiken und Syntaxanalyse, Entscheidbarkeitstheorie und Komplexitätstheorie.
Im Bereich Automatentheorie und Formale Sprachen werden die Grenzen eingeschränkter Berechnungsmodelle durchleuchtet und Grammatiken als Grundlage von Programmiersprachen behandelt. In der Entscheidbarkeitstheorie geht es darum, welche algorithmischen Probleme sich überhaupt mit Rechnerhilfe lösen lassen und in der Komplexitätstheorie um die Grenzen, was Rechner unter gewissen Ressourcenbeschränkungen leisten können.
Die Studierenden lernen, Berechnungsprobleme nach ihrer inhärenten Schwierigkeit zu klassifizieren, sie erlangen Kenntnisse über Grenzen der Algorithmisierbarkeit und können einschätzen, ob ein Problem überhaupt lösbar oder ob es lösbar, jedoch schwierig ist. Der Vergleich der algorithmischen Schwierigkeit gehört zu ihrem Handwerkszeug. Sie können Reduktionen durchführen und analysieren. Sie kennen die grundlegenden Methoden zur Handhabung von (endlichen) Automaten und Maschinen und können diese anwenden.
Ziel der Lehrveranstaltung ist eine Einführung in die Begriffe, Methoden, Modelle und Arbeitsweisen der Theoretischen Informatik anhand der ausgewählten Teilgebiete. In der Theoretischen Informatik wird häufig von realen Problemen abstrahiert, um beweisbare Aussage zu erhalten. Viele der Aussagen in der Vorlesung sind negative Aussagen, etwa dass es für ein Problem keinen Algorithmus gibt. Auch eine solche Aussage ist für die Praxis relevant, da man sich die Zeit für die Suche nach einem Algorithmus, den es nicht gibt, sparen kann. Andererseits sind die Zwischenschritte, um zu solchen Aussagen zu kommen, an vielen Stellen abstrakter als in früheren Vorlesungen, was eine der neuen Herausforderungen beim Verständnis der Lehrinhalte der Veranstaltung ist. Für die exakte Formulierung von Aussagen sind formale Schreibweisen erforderlich. Insbesondere die Bearbeitung der Übungsaufgaben soll dabei helfen, im Umgang mit diesen formalen Schreibweisen Routine zu bekommen. Darüberhinaus schulen die Übungen die Problemlösungskompetenz und stärken die Kommunikationskompetenz, die notwendig ist, um Ideen und Lösungsvorschläge schriftlich und mündlich überzeugend präsentieren zu können.
Das folgende Buch ergänzt den Vorlesungsinhalt, indem wesentliche Ideen umgangssprachlich dargestellt werden. Es deckt den Veranstaltungsinhalt jedoch nicht vollständig ab.
Einen gute Einführung in das Gebiet Automatentheorie und Formale Sprachen findet sich auch in dem folgenden Buch.
Prüfungsgrundlage ist der Inhalt der GTI-Veranstaltung des Sommersemesters 2019.
Wann? | Wo? | |
Klausur I: | 24.07.19, 14:00 - 17:00 | HG2/HS1, HG2/HS2, HG2/HS3, HG2/HS5, HG2/HS6 |
Klausur II: | 01.10.19, 13:00 - 16:00 | Audimax, M/E29 |
Als erlaubtes Hilfsmittel ist in der Klausur ein selbst erstelltes beidseitig handschriftlich verfasstes DIN-A4-Blatt zugelassen. Auf der Vorder- und Rückseite ist ein oberer Rand von 2cm zu lassen und links oben ist der Name und die Matrikelnummer des Bearbeitenden einzutragen.
Termine für die mündlichen Modulprüfungen sind am 23.07.19 und 30.09.19 geplant.
Bitte schauen Sie in Ihre Prüfungsordnung und vereinbaren gegebenenfalls
rechtzeitig einen Prüfungstermin.
Nutzen Sie dafür die Sprechstunde, die während der Vorlesungszeit dienstags von 12:45-13:45 Uhr stattfindet.
Nützliche Hinweise zum Thema mündliche Prüfungen hat Detlef Sieling
hier
bereitgestellt.
Eine Liste mit möglichen Prüfungsfragen hat Detlef Sieling
hier
zusammengestellt. Bitte beachten, dass sich diese Fragen auf eine andere Lehrveranstaltung beziehen,
trotzdem kann diese Liste als Anhaltspunkt für typische Fragen dienen.
Das Kapitel 9.2 im Buch von Ingo Wegener, Theoretische Informatik- eine algorithmenorientierte Einführung, eignet sich als Einstieg zur Vorbereitung mündlicher Prüfungen und um zu überprüfen, ob man den Vorlesungsinhalt verstanden hat. Bitte beachten, dass die Fragen dort nicht den gesamten Stoff der Lehrveranstaltung abdecken.
Für die Anmeldung zu den Übungen wird das System AsSESS benutzt. Der Anmeldezeitraum beginnt am 02.04.19 um 12:00 Uhr.
Der Übungsbetrieb beginnt in der zweiten Vorlesungswoche ab dem 08.04.19. Das jeweils aktuelle Übungsblatt wird in der Regel donnerstags per Moodle bereitgestellt, die Abgabe der Bearbeitung erfolgt in der Regel bis zum darauffolgenden Donnerstag 10:00 Uhr in die Briefkästen zwischen OH 12 und OH 14.
Weitere Informationen zu den Übungen und den Tutorien finden sich bei Moodle.
Die aktuellen Veranstaltungsmaterialien finden sich bei Moodle.
Datum | Inhalt | Folienzeiger |
---|---|---|
02.04.19 | Motivation, Überblick über die Veranstaltung, Gebrauchsanweisung für Vorlesung und Übungen, Literatur, Organisatorisches, Begriffe Problem und Sprache, Entscheidungs- versus Suchproblem | Folie 46 |
04.04.19 | Registermaschinen, erweiterte Churchsche These, algorithmische Komplexität, Turingmaschinen (Definition), Exkurs Wahrscheinlichkeitstheorie [Eigener Foliensatz] | Folie 69 |
09.04.19 | Turingmaschinen (Beispiel), Sonderrolle polynomieller Rechenzeiten, Komplexitätsklasse P, Einführung randomisierte Algorithmen, Äquivalenztest für multilineare Ausdrücke | Folie 95 |
11.04.19 | Test auf perfektes bipartites Matching, Komplexitätsklassen bezüglich randomisierter Algorithmen, Wahrscheinlichkeitsverstärkung | Folie 120 |
16.04.19 | (Wahrscheinlichkeitsverstärkung), Zusammenhang zwischen den Komplexitätsklassen, Nichtdeterminismus | Folie 141 |
18.04.19 | Nichtdeterminismus, Komplexitätsklasse NP, Algorithmische Ähnlichkeit, Turing-Reduktionen, Entscheidungs- versus Optimierungsvarianten, Vergleich von verwandten Problemen | Folie 167 |
23.04.19 | Reduktionen zwischen verwandten Problemen, Reduktionen zwischen nicht verwandten Problemen | Folie 190 |
25.04.19 | Weitere Reduktionen zwischen nicht verwandten Problemen, Polynomielle Reduktionen als Spezialfall von Turing-Reduktionen, NP-Vollständigkeit, Charakterisierungen von NP | Folie 227 |
30.04.19 | Charakterisierung von co-NP, stereotype Turingmaschinen, Satz von Cook | Folie 256 |
02.05.19 | (Satz von Cook), NP-Vollständigkeitsbeweise | Folie 287 (noch ohne 277-279) |
07.05.19 | NP-Vollständigkeitsbeweise | Folie 307 |
09.05.19 | Entscheidbarkeitstheorie: Universelle Turingmaschine, Turing-Berechenbarkeit, rekursive und rekursive aufzählbare Sprachen, Churche These, Unentscheidbarkeit der Diagonalsprache, Halteproblem, Reduktionskonzept | Folie 336 |
14.05.19 | Satz von Rice, Abschlusseigenschaften rekursiver und rekursiv aufzählbarer Sprachen, Postschen Korrespondenzproblem (PKP), Reduktion von MPKP auf PKP | Folie 355 |
16.05.19 | Unentscheidbarkeit des Postschen Korrespondenzproblems, Selbsttest (Pingo) | Folie 364 |
21.05.19 | Deterministische endliche Automaten (DFAs), Pumping Lemma für reguläre Sprachen | Folie 397 |
23.05.19 | Minimierung von DFAs, (Satz von Nerode) | Folie 419 |
28.05.19 | Satz von Nerode, NFAs | Folie 437 |
04.06.19 | Umwandlung von NFAs in DFAs: Potenzmengenkonstruktion, Erweiterung von NFAs, Entscheidung von Spracheigenschaften bei gegebenen DFAs/NFAs, Abschlusseigenschaften regulärer Sprachen | Folie 461 |
06.06.19 | Abschlusseigenschaften regulärer Sprachen (Fortsetzung), reguläre Ausdrücke, Umwandlung von DFAs in äquivalente reguläre Ausdrücke | Folie 491 |
11.06.19 | Wiederholung reguläre Ausdrücke, Abschlusseigenschaften regulärer Sprachen (Fortsetzung), Selbsttest Automatentheorie | Folie 497 |
13.06.19 | Grammatiken und die Chomsky-Hierarchie | Folie 519 |
18.06.19 | Grammatiken und die Chomsky-Hierarchie (Fortsetzung), kontextfreie Sprachen: Beispiele, Eindeutig- und Mehrdeutigkeit | Folie 547 |
25.06.19 |
Chomsky-Normalform, CYK-Algorithmus, Pumping-Lemma für kontextfreie Sprachen | Folie 574 |
27.06.19 |
Beweis Pumping-Lemma, Ogdens Lemma, inhärente Mehrdeutigkeit, Algorithmische Lösungen für Probleme auf kontextfreien Sprachen | Folie 597 |
02.07.19 |
Abschlusseigenschaften kontextfreier Sprachen, Unentscheidbarkeitsresultate | Folie 618 |
04.07.19 |
Unentscheidbarkeitsresultate (Fortsetzung), kontextsensitive Sprachen, Greibach-Normalform | Folie 646 |
09.07.19 |
Kellerautomaten mit zwei verschiedenen Akzeptanzvarianten, Zusammenhang Kellerautomaten und kontextfreie Sprachen | Folie 664 |
11.07.19 |
Fortsetzung Tripelkonstruktion (Zusammenhang Kellerautomaten und kontextfreie Sprachen), Abschlusseigenschaften, DPDAs | Ende |