Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Grundbegriffe der Theoretischen Informatik

Sommersemester 2019

Prof. (apl) Dr. Beate Bollig


[Termine] [Hinweis] [Inhalt und Lernziele] [Literatur] [Moodle] [Prüfungen] [Übungen] [Veranstaltungsmaterialien] [Vorlesungsplan]


Termine

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.


Hinweis

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.


Inhalt und Lernziele

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.


Literatur

In dem Bereich Grundlagen der Theoretischen Informatik existieren eine Vielzahl von guten Lehrbüchern. Die Veranstaltung richtet sich im Wesentlichen nach den folgenden beiden Büchern. Der genaue Inhalt aus diesen, der in der Vorlesung behandelt wird, befindet sich hier.

  • Wegener, I. (2003).
    Komplexitätstheorie - Grenzen der Effizienz von Algorithmen.
    Springer.

    Das Buch ist in der Universitätsbibliothek der TU Dortmund verfügbar.

  • Wegener, I. (1999).
    Theoretische Informatik - eine algorithmenorientierte Einführung.
    2. Auflage, Teubner.

    Das Buch ist aus dem Hochschulnetz der TU Dortmund als pdf-Datei verfügbar.

Das folgende Buch ergänzt den Vorlesungsinhalt, indem wesentliche Ideen umgangssprachlich dargestellt werden. Es deckt den Veranstaltungsinhalt jedoch nicht vollständig ab.

  • Wegener, I. (1996).
    Kompendium der Theoretischen Informatik - eine Ideensammlung.
    Teubner.

    Das Buch ist in der Universitätsbibliothek der TU Dortmund verfügbar.

Einen gute Einführung in das Gebiet Automatentheorie und Formale Sprachen findet sich auch in dem folgenden Buch.

  • Schöning, U. (1997).
    Theoretische Informatik - kurzgefasst.
    Spektrum Akademischer Verlag.

    Das Buch ist in der Universitätsbibliothek der TU Dortmund verfügbar.

Hilfreich ist auch das folgende Lehrbuch.

  • Hopcroft, E., Motwani, R. und Ullman, J.D. (2002).
    Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie.
    Pearson.

    Das Buch ist in der Universitätsbibliothek der TU Dortmund verfügbar.


  • Prüfungen

    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.


    Übungen

    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.


    Veranstaltungsmaterialien

    Die aktuellen Veranstaltungsmaterialien finden sich bei Moodle.


    Vorlesungsplan

    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


    Seitenanfang

    Letzte Änderung: 11.07.2019 von B. Bollig