Automaten und formale Sprachen sowie Algorithmentheorie

Die Theoretische Informatik beschäftigt sich auf systematische Weise und unter Verwendung mathematischer Mittel mit zentralen Fragen der Informatik und stellt eine wichtige Grundlage für viele andere Teilgebiete der Informatik dar. Sie besteht aus mehreren Teildisziplinen, von denen in dieser Veranstaltung hauptsächlich die Automatentheorie und die Theorie der formalen Sprachen behandelt werden. Dabei stehen sogenannte Wörter im Mittelpunkt, mit deren Hilfe viele Objekte der Informatik wie z.B. Programme und verschiedene Datenstrukturen beschrieben werden können. Eine formale Sprache ist dann einfach eine Menge von Wörtern. Wir studieren verschiedene Mittel, um formale Sprachen zu beschreiben (insb. Automaten und Grammatiken), untersuchen Eigenschaften von wichtigen Klassen formaler Sprachen und studieren zentrale algorithmische Probleme, die im Zusammenhang mit Wörtern und formalen Sprachen stehen.

Lernergebnisse

• Formale Grundlagen und elementare Fragestellungen der Informatik kennen und die fundamentale Rolle der Theorie in der Informatikverstehen.
• Konzepte zur formalen Beschreibung und Analyse von Informatiksystemen kennen.
• Beherrschung der grundlegenden Methoden aus den Bereichen der Automatentheorie, formalen Sprachen und Algorithmen.
• Beherrschung elementarer Beweistechniken und Beweise selbst durchführen können.
• Probleme analysieren, von spezifischen Gegebenheiten abstrahieren und formale Modelle in mathematischen Definitionen darstellenkönnen.
• Algorithmen für diese Probleme kennen und auf neue Problemvarianten anwenden können.
• Korrektheit von Algorithmen beweisen und Eigenschaften von Algorithmen analysieren können.
• Eigenständig und in Gruppen Lösungsstrategien für formale Problemstellungen entwickeln können und Lösungen verständlichpräsentieren.

Inhalte

A) Automaten und formale Sprachen

1. Endliche Automaten und Reguläre Sprachen:

• Definition und Grundbegriffe
• Nichtdeterminismus
• Nichterkennbarkeit von Sprachen und Pumping-Lemma
• Abschlusseigenschaften
• Potenz- und Produktautomat
• Leerheits-, Wort- und Äquivalenzproblem
• regulare Ausdrucke
• Minimale Automaten und Nerode-Rechtskongruenz
• Rechtslineare Grammatiken 

2. Kontextfreie Sprachen:

• Grammatiken und Chomsky-Hierarchie
• kontextfreie Grammatiken
• Chomsky Normalform
• Leerheits-, Wort- und Äquivalenzproblem
• CYK-Algorithmus
• Abschlusseigenschaften
• Pumping-Lemma
• Kellerautomaten

B) Algorithmentheorie

• Algorithmenbegriff
• Korrektheit und Komplexität von Algorithmen
• Suchen und Rekursionen
• Sortieren
• Graphen und elementare Graphenalgorithmen: Graphdurchläufe, MST und SP
• Algorithmen Paradigmen: Divide and Conquer, Greedy Algorithmen, Dynamische Programmierung

Lehrende

Prof. Dr. Sebastian Siebertz
Fachbereich Mathematik / Informatik

Veranstaltungsdetails

Veranstaltungsform:
Vorlesung + Übung

Dieses Modul besteht aus zwei Veranstaltungen:

• 03-IBGT-THI1-AFS Automaten und formale Sprachen
• 03-IBGT-AT Algorithmentheorie

Veranstaltungszeiten:
im Wintersemester | Termine folgen

Prüfungen & Abschluss

Prüfung:

• i. d. R. Bearbeitung von Übungsaufgaben und Fachgespräch

Abschluss:

• Modulzertifikat

Umfang

Dauer: 1 Semester

Arbeitsaufwand:
84 Std. Präsenzveranstaltungen
+ 186 Std. angeleitetes Selbststudium
(entspricht 9 CP)

Teilnahmeentgelt

675 Euro (= 75 Euro pro CP)

Mitglieder des Alumni-Vereins der Universität Bremen erhalten 5 % Rabatt.

Bewerbung

Eine Bewerbung ist zum jetzigen Zeitpunkt leider nicht möglich.

Bewerbungszeitraum:
1. August - 15. September