Zum Hauptinhalt springen

Endliche Automaten und formale Sprachen

Modul - Informatik: Theoretische Informatik 1

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

 

In Kürze

Inhalt:
Die Automatentheorie und die Theorie der formalen Sprachen werden behandelt.

Niveau: Bachelor-Modul 

Veranstaltungsform:
Vorlesung + Übung

Semester: Wintersemester

Umfang: 9 CP

Modulverantwortung

Prof. Dr. C. Lutz

 

Lehrende

Prof. Dr. Sebastian Siebertz
Fachbereich Mathematik / Informatik

Prof. Dr. N. Megow
Fachbereich Mathematik / Informatik

 

 

 

Zielgruppe

  • Interessierte an den Arbeitsfeldern Informationstechnik und Medien.

Zugangsvoraussetzungen

  • Hochschulzugangsberechtigung

  • eine mindestens einjährige Berufspraxis

Veranstaltungsdetails

Veranstaltungsform:
Vorlesung + Übung

Dieses Modul besteht aus zwei Veranstaltungen:

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

Veranstaltungszeiten:
im Wintersemester

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

Information zur Bremer Bildungsprämie

Bewerbung

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

Bewerbungszeitraum:
1. August - 15. September 

Zugehörige Zertifikate:

Das Modul ist Bestandteil folgender Zertifikatsangebote:

Information & Beratung:

Sie interessieren sich für unser Angebot im Bereich "Informatik, Digitale Medien, Digitalisierung"? Wir beraten Sie gern:

Jörg Kastens

Telefon: 0421 - 218 61 617
eMail: jkastensprotect me ?!uni-bremenprotect me ?!.de

Hinweis:
Wegen der Corona-Pandemie arbeiten wir vermehrt im Home Office. Bitte schreiben Sie uns eine eMail oder sprechen Sie auf den Anrufbeantworter - wir rufen dann zurück!