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 澳门皇冠_皇冠足球比分-劲爆体育eren 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 澳门皇冠_皇冠足球比分-劲爆体育:

• 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