Formale Systeme (WS2021): Unterschied zwischen den Versionen
Dörthe Arndt (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Dörthe Arndt (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 306: | Zeile 306: | ||
}} | }} | ||
{{Vorlesung Zeiten | {{Vorlesung Zeiten | ||
|Lehrveranstaltungstype= | |Lehrveranstaltungstype=Übung | ||
|Title=10. Übungsblatt | |Title=10. Übungsblatt | ||
|Room=-- | |Room=-- | ||
|Date=2021/12/16 | |Date=2021/12/16 | ||
|DS=terminlos | |DS=terminlos | ||
|Download=Blatt-10.pdf | |Download=Blatt-10.pdf | ||
}} | }} | ||
Version vom 17. Dezember 2021, 18:22 Uhr
Formale Systeme
Lehrveranstaltung mit SWS 4/2/0 (Vorlesung/Übung/Praktikum) in WS 2021
Dozent
Tutor
- Dörthe Arndt
- Jonas Karge
- Anton Claußnitzer
Umfang (SWS)
- 4/2/0
Module
Leistungskontrolle
- Klausur
Vorlesungsreihe
Die Lehrveranstaltung Formale Systeme vermittelt eine Einleitung in die Gebiete der formalen Sprachen, Automatentheorie und Aussagenlogik. Dies beinhaltet einige der wichtigsten Grundlagen der Informatik, wie z.B. reguläre Ausdrücke, formale Grammatiken sowie Methoden zur praktischen Lösung von "schweren" (NP-vollständigen) Problemen. Damit bildet die Vorlesung die Grundlage für die Vorlesung Theoretische Informatik und Logik und für viele vertiefende Vorlesungen.
Vorlesungen
Vorlesungstermine:
- Mo 3. DS
- Do 4. DS
Die Vorlesung wird virtuell (über Zoom) durchgeführt. Der Link zu den Zoom-Terminen findet sich in der OPAL-Seite der Lehrveranstaltung. Die 1. Vorlesung findet am 11. Oktober 2021 statt.
Übungen
Es wird dieses Semester sowohl virtuelle Übungsgruppen als auch Übungen in Präsenz geben.
Die Einschreibung in die Übungsgruppen erfolgt über die OPAL-Seite der Lehrveranstaltung. Für die Teilnahme an einer Übungsgruppe ist die Einschreibung in dieser Gruppe verpflichtend. Studierenden ohne Einschreibung kann die Teilnahme an einer selbstgewählten Übung nicht garantiert werden. Übungsleiter:innen sind berechtigt, nicht eingeschriebene Studierende bei Überfüllung aus der (digitalen) Übung zu verweisen. Übungsleiter:innen von Präsenzgruppen sind berechtigt und verpflichtet, die Einhaltung der 3G-Regeln zu überprüfen sowie Beschränkungen der Personenanzahl in den Übungsräumen durchzusetzen.
Übungsgruppen finden ab dem 18. Oktober 2021 zu ihren jeweiligen Terminen statt. Die Übungen werden digital über das an der TU Dresden gehostete System BigBlueButton abgehalten. Links auf die entsprechenden digitalen Räume werden über OPAL bekanntgegeben. Übungsblätter können in OPAL abgerufen werden.
Individuelles Feedback für Ihre Lösungen: Als zusätzliche Hilfe bieten wir in diesem Semester an, von Studierenden eingereichte Lösungsansätze zu sichten und Ihnen dazu eine Rückmeldung zu geben. Die Details (Abgabetermin & Umfang) werden von den Tutor:innen festgelegt. Unterlagen können per E-Mail an die Tutor:innen abgegeben werden (als digitales Dokument, egal ob Handyfoto der eigenen Handschrift oder am Computer geschriebener Text).
Kontakt
Zur Kommunikation unter Vorlesungsteilnehmer:innen der TU Dresden stehen ein OPAL-Diskussionsforum und ein Matrix-Kanal zur Verfügung.
Persönliche Fragen können auch direkt an das Organisationsteam (siehe Links oben) gestellt werden, falls sie aus einem zwingenden Grund nicht über andere Kanäle gerichtet werden können. Allgemeine Fragen sollten Sie aber immer in geteilten Kanälen stellen, damit auch Ihre Kommiliton:innen davon profitieren (oder vielleicht sogar direkt helfen können).Allgemein sind die Vorlesungsfolien und Übungsunterlagen ausreichend detailliert für das Studium. Weitere Lehrmaterialien können dennoch hilfreich sein, um Details nachzuschlagen oder sich weiter im Thema zu vertiefen.
Formale Sprachen, Komplexität und Entscheidbarkeit
Lehrbücher
- Uwe Schöning: Theoretische Informatik -- kurz gefasst. Spektrum Akademischer Verlag.
- (deutschsprachiger Standardtext; in der Tat ziemlich kurz gefasst)
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in Automatentheorie, Formale Sprachen und Berechenbarkeit. Pearson Studium.
- (aus dem Englischen übertragenes Standardwerk; Original ev. besser)
- Michael Sipser: Introduction to the Theory of Computation. Cengage Learning.
- (Standardtext zu Sprachen und Berechnungskomplexität; leider nur auf Englisch)
Online verfügbare Skripte
Die Vorlesungen haben kleine Abweichungen von diesem Text, stimmen aber in vielen wichtigen Punkten überein.
- Christel Baier, Manuela Berg, Walter Nauber: Formale Systeme WS2011/2012: Skript zur Vorlesung. TU Dresden.
Aussagenlogik
Die Vorlesungsfolien sollten bei diesem Thema ausreichen. Wer dennoch weitere Details nachschlagen will, dem nützen eventuell die folgenden Bücher:
- Uwe Schöning: Logik für Informatiker. Spektrum Akademischer Verlag.
- (leichte Abweichungen in Notation und Darstellung)
- Martin Kreuzer, Stefan Kühling: Logik für Informatiker. Pearson Studium.
- (sehr knapp und informell; eventuell interessant als Quelle für Übungsaufgaben)
- Steffen Hölldobler: Logik und Logikprogrammierung. Synchron Verlag.
- (Schwerpunkt auf Logikprogrammierung und Prädikatenlogik, aber auch einiges zur Aussagenlogik)
- Steffen Hölldobler, Sebastian Bader, Bertram Fronhöfer, Ursula Hans, Pascal Hitzler, Markus Krötzsch, Tobias Pietzsch: Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen Synchron Verlag
- (Aufgabensammlung aus den Logikvorlesungen vergangener Jahre)
Veranstaltungskalender abonnieren (icalendar)
| Vorlesung | 1. Vorlesung: Formale Sprachen | DS3, 11. Oktober 2021 in Videokonferenz | Datei 1, Datei 2 |
| Vorlesung | 2. Vorlesung: Grammatiken und die Chomsky-Hierarchie | DS4, 14. Oktober 2021 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 1. Übungsblatt | Datei | |
| Vorlesung | 3. Vorlesung: Endliche Automaten | DS3, 18. Oktober 2021 in Videokonferenz | Datei 1, Datei 2 |
| Vorlesung | 4. Vorlesung: Nichtdeterministische Endliche Automaten | DS4, 21. Oktober 2021 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 2. Übungsblatt | Datei | |
| Vorlesung | 5. Vorlesung: Abschlusseigenschaften regulärer Sprachen | DS3, 25. Oktober 2021 in Videokonferenz | Datei 1, Datei 2 |
| Vorlesung | 6. Vorlesung: Reguläre Ausdrücke | DS4, 28. Oktober 2021 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 3. Übungsblatt | Datei | |
| Vorlesung | 7. Vorlesung: Reguläre Ausdrücke (2) | DS3, 1. November 2021 in Videokonferenz | Datei 1, Datei 2 |
| Vorlesung | 8. Vorlesung: Minimale Automaten | DS4, 4. November 2021 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 4. Übungsblatt | Datei | |
| Vorlesung | 9. Vorlesung: Minimale Automaten (2) | DS3, 8. November 2021 in Videokonferenz | Datei 1, Datei 2 |
| Vorlesung | 10. Vorlesung: Grenzen regulärer Sprachen / Probleme regulärer Sprachen | DS4, 11. November 2021 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 5. Übungsblatt | Datei | |
| Vorlesung | 11. Vorlesung: Von regulären zu kontextfreien Sprachen | DS3, 15. November 2021 in Videokonferenz | Datei 1, Datei 2 |
| Vorlesung | 12. Vorlesung: Das Wortproblem für kontextfreie Sprachen | DS4, 18. November 2021 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 6. Übungsblatt | Datei | |
| Vorlesung | 13. Vorlesung: Das Pumping-Lemma für kontextfreie Sprachen | DS3, 22. November 2021 in Videokonferenz | Datei 1, Datei 2 |
| Vorlesung | 14. Vorlesung: Abschlusseigenschaften kontextfreier Sprachen | DS4, 25. November 2021 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 7. Übungsblatt | Datei | |
| Vorlesung | 15. Vorlesung: Kellerautomaten | DS3, 29. November 2021 in Videokonferenz | Datei 1, Datei 2 |
| Vorlesung | 16. Vorlesung: Kellerautomaten (2) | DS4, 2. Dezember 2021 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 8. Übungsblatt | Datei | |
| Vorlesung | 17. Vorlesung: Deterministische Typ-2-Sprachen / Probleme für kontextfreie Sprachen | DS3, 6. Dezember 2021 in Videokonferenz | Datei 1, Datei 2 |
| Vorlesung | 18. Vorlesung: Turingmaschinen | DS4, 9. Dezember 2021 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 9. Übungsblatt | Datei | |
| Vorlesung | 19. Vorlesung: Nichtdeterminismus und Unentscheidbarkeit | DS3, 13. Dezember 2021 in Videokonferenz | Datei 1, Datei 2 |
| Vorlesung | 20. Vorlesung: Typ 0 und Typ 1 | DS4, 16. Dezember 2021 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 10. Übungsblatt | Datei | |
| Vorlesung | 21. Vorlesung: Aussagenlogik | DS4, 6. Januar 2022 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 11. Übungsblatt | Datei | |
| Vorlesung | 22. Vorlesung: Äquivalenzen und Normalformen | DS3, 10. Januar 2022 in Videokonferenz | Datei 1, Datei 2 |
| Vorlesung | 23. Vorlesung: Logisches Schließen | DS4, 13. Januar 2022 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 12. Übungsblatt | Datei | |
| Vorlesung | 24. Vorlesung: Horn-Logik und Komplexitätstheorie | DS3, 17. Januar 2022 in Videokonferenz | Datei 1, Datei 2 |
| Vorlesung | 25. Vorlesung: NP-Vollständigkeit | DS4, 20. Januar 2022 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 13. Übungsblatt | Datei | |
| Vorlesung | 26. Vorlesung: Zusammenfassung und Ausblick | DS3, 24. Januar 2022 in Videokonferenz | Datei 1, Datei 2 |
| Übung | 14. Übungsblatt | Datei | |
| Übung | Probeklausur | Datei | |
| Übung | Lösung Probeklausur | DS3, 7. Februar 2022 in -- | Datei |
Kalender
