Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Hauptinhalt

Grundbegriffe der Theoretischen Informatik

Sommersemester 2017

Prof. (apl) Dr. Beate Bollig


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


Termine

Wann? Wo?
Vorlesung Di 10:00 - 12:00 HG2/HS 3
Vorlesung Do 12:00 - 14:00 HG2/HS 3

Die Veranstaltung beginnt am 18.04.2017.


Hinweis

Diese Veranstaltung ersetzt im Sommersemester 2017 die Module INF-BSc-112 (Theoretische Informatik für Studierende der Angewandten Informatik) und INF-BL-105 (Theoretische Informatik für BK).

Studierende der Diplomstudiengänge Informatik melden sich bitte vorab elektronisch bei der Veranstalterin.


Aktuelles

In der Vorlesungszeit Sommer 2017 wird zweimal in der Woche ein zweistündiges GTI HelpDesk (Lernraumbetreuung) angeboten.

Wann? Wo?
GTI HelpDesk Mo 12:00 - 14:00 OH12/4.033
GTI HelpDesk Fr 14:00 - 16:00 OH12/4.033

Der GTI HelpDesk beginnt am 27.04.2017.


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 der folgenden Literatur.

  • 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.

  • 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.


Prüfungen

Prüfungsgrundlage ist der Inhalt der GTI-Veranstaltung des Sommersemesters 2017.
Wann? Wo?
Klausur I: 09.08.17, 8:00 - 11:00 SRG1/H.001, HG2/HS1, HG2/HS3, HG2/HS5
Klausur II: 05.10.17, 8:00 - 11:00 Audimax, M/E28 und 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 GTI-Prüfungen sind am 08.08.17 und 04.10.17. 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 bezieht, trotzdem kann diese Liste als Anhaltspunkt für typische Fragen dienen. Weitere mögliche Prüfungsfragen stehen im Kompendium der Theoretischen Informatik (siehe Literaturhinweise).


Übungen

Der Übungsbetrieb beginnt in der zweiten Vorlesungswoche ab dem 27.04.2017. Das jeweils aktuelle Übungsblatt wird dienstags per moodle bereitgestellt, die Abgabe der Bearbeitung erfolgt bis zum darauffolgenden Dienstag 10:00 Uhr in die Briefkästen zwischen OH 12 und OH 14. Sie erfolgt immer einzeln.

Weitere Informationen zu den Übungen und den Tutorien finden sich bei moodle.

Ergänzend zu den Vorlesungen, Übungen und dem GTI HelpDesk werden Tutorien angeboten, in denen der aktuelle Vorlesungsstoff hauptsächlich anhand geeigneter Beispiele wiederholt wird und die Gelegenheit geboten wird, individuelle Fragen zu besprechen.
Wann? Wo?
Tutorium B2 Mo 14:00 - 16:00 OH 12/1.055
Tutorium A1 Mi 14:00 - 16:00 OH 12/E.003
Tutorium A2 Do 10:00 - 12:00 OH 14/E23
Tutorium B1 Fr 12:00 - 14:00 OH 12/3.031
Die Tutorien beginnen am 21.04.2017. In den A-Tutorien sowie in den B-Tutorien werden jeweils die gleichen Themen behandelt. Die Tutorien A1 und B2 sind speziell für Studierende der Angewandten Informatik, sie können jedoch von allen Informatikstudierenden besucht werden, wenn genügend Plätze frei sind.


Veranstaltungsmaterialien

Die Veranstaltung orientiert sich an der Vorlesung Grundbegriffe der Theoretischen Informatik aus dem Sommersemester 2016 von Prof. Dr. Thomas Schwentick.

Die aktuellen Veranstaltungsmaterialien finden sich bei moodle.


Seitenanfang

Letzte Änderung: 09.05.2017 von B. Bollig