Termine

Aufgrund der aktuellen Pandemie findet in dieser Vorlesungszeit keine Präsenzlehre statt.
Bitte für weitere Informationen in den Moodle-Arbeitsraum einschreiben. Die Anmeldung erfolgt über LSF.

Die Veranstaltung beginnt in der ersten Vorlesungswoche.

Hinweise

Aktuell planen wir die Modulprüfungen in Präsenz. Die weiter unten angegebenen Räume sind die zunächst vorgesehenen Räume. Diese können sich noch ändern. Auch die Uhrzeit kann sich noch ändern.

Diese Veranstaltung ersetzt im Sommersemester 2021 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 mit besonderen Bedürfnissen (Nachteilsausgleich) und Schülerstudierende 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 aus dem Hochschulnetz der TU Dortmund als pdf-Datei verfügbar.

• Wegener, I. (2005).
  Theoretische Informatik - eine algorithmenorientierte Einführung.
  3. 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.

Prüfungen

• 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üfungsgrundlage ist der Inhalt der GTI-Veranstaltung des Sommersemesters 2021.

   

  	Wann?	Wo?
  Klausur I:	04.08.2021, 12:30-15:45 Uhr	Audimax, HG2/HS2, HG2/HS4-7, EF50/HS3
  Klausur II:	29.09.2021, 12:30-15:45 Uhr (geplant)	Audimax, EF50/HS1-3

  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 jeweils in der gleichen Woche wie die jeweilige Klausur 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 online stattfindet.

  Nützliche Hinweise zum Thema mündliche Prüfungen sowie eine Liste mit möglichen Prüfungsfragen hat Detlef Sieling 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

Der Übungsbetrieb beginnt in der zweiten Vorlesungswoche.

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

Veranstaltungsmaterialien

Die aktuellen Veranstaltungsmaterialien finden sich bei Moodle.