|
Algebraische und Logische Aspekte der Automatentheorie (ALoA)7.5 ECTS (englische Bezeichnung: Algebraic and Logical Aspects of Automata Theory)
(Prüfungsordnungsmodul: Algebraische und Logische Aspekte der Automatentheorie)
Modulverantwortliche/r: Stefan Milius Lehrende:
Stefan Milius
Startsemester: |
WS 2019/2020 | Dauer: |
1 Semester | Turnus: |
unregelmäßig |
Präsenzzeit: |
45 Std. | Eigenstudium: |
180 Std. | Sprache: |
Deutsch |
Lehrveranstaltungen:
Empfohlene Voraussetzungen:
Es wird empfohlen, folgende Module zu absolvieren, bevor dieses Modul belegt wird:
Grundlagen der Logik in der Informatik (WS 2018/2019)
Berechenbarkeit und Formale Sprachen (WS 2018/2019)
Inhalt:
Automaten als mathematische Formalisierung zustandsbasierter Systeme gehören zu den wichtigsten Werkzeugen der Theoretischen Informatik und besitzen zahlreiche Anwendungen, von der Compilerentwicklung bis zur Verifikation reaktiver Systeme. In dieser Veranstaltung, die an die Anfängervorlesungen des Informatikstudiums anknüpft, werden wichtige Querverbindungen zwischen der Automatentheorie und Gebieten der Mathematik (Algebra, Topologie und Logik) hergestellt. Folgende Themen werden behandelt:
Erkennung von regulären Sprachen durch Monoide und Halbgruppen
Proendliche Gleichungen und Varietäten von Sprachen
Logische Beschreibung regulärer Sprachen, Ehrenfeucht-Fraïssé-Spiele
Automaten, Algebra und Logik auf unendlichen Wörtern und Bäumen
Lernziele und Kompetenzen:
- Fachkompetenz
- Wissen
- Die Studierenden geben elementaren Definitionen, Begriffe und Fakten der algebraischen Sprachtheorie wieder.
- Verstehen
- Die Studierenden
erläutern grundlegende Begriffe der Halbgruppentheorie und der Topologie
erklären die Äquivalenz zwischen monadischer Logik 2. Stufe und regulären Sprachen
erklären die Äquivalenz zwischen Monoid erkennbaren und regulären Sprachen
- Anwenden
- Die Studierenden
beschreiben mit Hilfe von logischen Formeln formale Sprachen
konstruieren algebraische Erkenner für reguläre Sprachen
spezifizieren Klassen von regulären Sprachen durch Folgen von Gleichungen oder proendliche Gleichungen
- Analysieren
- Die Studierenden analysieren mathematische Beweise, diskutieren die entsprechenden Argumentationen und legen diese schriftlich nieder.
- Evaluieren (Beurteilen)
- Die Studierenden
- Erschaffen
- Die Studierenden
- Lern- bzw. Methodenkompetenz
- Die Studierenden
beherrschen das grundsätzliche Konzept des Beweises als hauptsächliche Methode des Erkenntnisgewinns in der theoretischen Informatik. Sie überblicken abstrakte Begriffsarchitekturen.
vollziehen mathematische Argumentationen nach, erklären diese, führen diese selbst und legen sie schriftlich nieder.
- Sozialkompetenz
- Die Studierenden lösen Probleme in kollaborativer Gruppenarbeit und präsentieren erarbeitete Lösungen.
Literatur:
- J.-E. Pin: Mathematical Foundations of Automata Theory
D. Perrin, J.-E. Pin: Infinite Words, Academic Press, 2004
H. Straubing: Finite Automata, Formal Logic, and Circuit Complexity, Birkhäuser, 1994
E. Grädel, W. Thomas, T. Wilke: Automata, Logic, and Infinite Games, Springer, 2002
Bemerkung:
Webseite der Lehrveranstaltung: https://www8.cs.fau.de/course:aloa
Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:
- Informatik (Bachelor of Science)
(Po-Vers. 2009w | TechFak | Informatik (Bachelor of Science) | Wahlpflichtbereich (5. und 6. Semester) | Wahlpflichtmodule | Vertiefungsrichtung Theoretische Informatik | Algebraische und Logische Aspekte der Automatentheorie)
Dieses Modul ist daneben auch in den Studienfächern "Informatik (Master of Science)", "Mathematik (Bachelor of Science)" verwendbar. Details
Studien-/Prüfungsleistungen:
Algebraische und Logische Aspekte der Automatentheorie (Prüfungsnummer: 787141)
(englischer Titel: Algebraic and Logical Aspects of Automata Theory)
- Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 30, benotet, 7.5 ECTS
- Anteil an der Berechnung der Modulnote: 100.0 %
- Prüfungssprache: Deutsch
- Erstablegung: WS 2019/2020, 1. Wdh.: SS 2020 (nur für Wiederholer)
- Ort: Martenstr. 3, 11. Stock, Raum 11.152
|
|
|
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|