Account
Edit tools
Intern
SucheSearch
English

Formale Systeme (WS2024): Unterschied zwischen den Versionen

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
Hannes Straß (Diskussion | Beiträge)
Keine Bearbeitungszusammenfassung
Hannes Straß (Diskussion | Beiträge)
Keine Bearbeitungszusammenfassung
 
(35 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 18: Zeile 18:
Vorlesungstermine:
Vorlesungstermine:


* Mo 3. DS
* Mo 3. DS (BAR/SCHÖ/E)
* Do 4. DS
* Do 4. DS (HSZ/0003/H)


== Übungen ==
== Übungen ==


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 Übung zu verweisen.
Die Einschreibung in die Übungsgruppen erfolgt über die '''[https://bildungsportal.sachsen.de/opal/auth/RepositoryEntry/46372487170 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 Übung zu verweisen.


Übungsgruppen finden ab dem 21. Oktober 2024 zu ihren jeweiligen Terminen statt. Übungsblätter können in OPAL abgerufen werden.
Übungsgruppen finden ab dem 21. Oktober 2024 zu ihren jeweiligen Terminen statt. Übungsblätter können in OPAL abgerufen werden.
Zeile 32: Zeile 32:


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).
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).
== Prüfung ==
Nach aktueller [https://tu-dresden.de/ing/informatik/ressourcen/dateien/pruefungsamt/pruefungsplaene-wise/PP_Bachelor_Informatik-1.pdf?lang=de Prüfungsplanung] findet die Klausur (90min) am 18.02.2025 um 13:00 Uhr im Hörsaalzentrum statt. Zur Klausur sind keine Hilfsmittel zugelassen.
Die Raumaufteilung ist nach Anfangsbuchstaben des Familiennamens wie folgt:
* A–K: HSZ/AUDI/H
* L–R: HSZ/02/E
* S–Z: HSZ/03/H
|Literature=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.
|Literature=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.


Zeile 65: Zeile 74:
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
* [[Steffen Hölldobler]], [[Sebastian Bader]], [[Bertram Fronhöfer]], [[Ursula Hans]], [[Pascal Hitzler]], [[Markus Krötzsch]], [[Tobias Pietzsch]]: '''[[Book3001|Logik und Logikprogrammierung, Band 2: Aufgaben und Lösungen]]''' Synchron Verlag
: ''(Aufgabensammlung aus den Logikvorlesungen vergangener Jahre)''
: ''(Aufgabensammlung aus den Logikvorlesungen vergangener Jahre)''
 
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=1. Formale Sprachen
|Room=BAR/SCHÖ
|Date=2024/10/14
|DS=DS3
|Download=FS2024-Vorlesung-01.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=2. Grammatiken und die Chomsky-Hierarchie
|Room=HSZ/0003
|Date=2024/10/17
|DS=DS4
|Download=FS2024-Vorlesung-02.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=3. Endliche Automaten
|Room=BAR/SCHÖ
|Date=2024/10/21
|DS=DS3
|Download=FS2024-Vorlesung-03.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=4. Nichtdeterministische Endliche Automaten
|Room=HSZ/0003
|Date=2024/10/24
|DS=DS4
|Download=FS2024-Vorlesung-04.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=5. Abschlusseigenschaften regulärer Sprachen
|Room=BAR/SCHÖ
|Date=2024/10/28
|DS=DS3
|Download=FS2024-Vorlesung-05.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Reformationstag
|Room=--
|Date=2024/10/31
|DS=terminlos
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Keine Vorlesung
|Room=--
|Date=2024/11/04
|DS=DS3
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Entfällt
|Title=Keine Vorlesung
|Room=--
|Date=2024/11/07
|DS=DS4
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=6. Reguläre Ausdrücke
|Room=BAR/SCHÖ
|Date=2024/11/11
|DS=DS3
|Download=FS2024-Vorlesung-06.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=7. Reguläre Ausdrücke (2)
|Room=HSZ/0003
|Date=2024/11/14
|DS=DS4
|Download=FS2024-Vorlesung-07.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=8. Minimale Automaten
|Room=BAR/SCHÖ
|Date=2024/11/18
|DS=DS3
|Download=FS2024-Vorlesung-08.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=9. Minimale Automaten (2)
|Room=HSZ/0003
|Date=2024/11/21
|DS=DS4
|Download=FS2024-Vorlesung-09.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=10. Grenzen regulärer Sprachen / Probleme regulärer Sprachen
|Room=BAR/SCHÖ
|Date=2024/11/25
|DS=DS3
|Download=FS2024-Vorlesung-10.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=11. Von regulären zu kontextfreien Sprachen
|Room=HSZ/0003
|Date=2024/11/28
|DS=DS4
|Download=FS2024-Vorlesung-11.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=12. Das Wortproblem für kontextfreie Sprachen
|Room=BAR/SCHÖ
|Date=2024/12/02
|DS=DS3
|Download=FS2024-Vorlesung-12.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=13. Das Pumping-Lemma für kontextfreie Sprachen
|Room=HSZ/0003
|Date=2024/12/05
|DS=DS4
|Download=FS2024-Vorlesung-13.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=14. Abschlusseigenschaften kontextfreier Sprachen
|Room=BAR/SCHÖ
|Date=2024/12/09
|DS=DS3
|Download=FS2024-Vorlesung-14.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=15. Kellerautomaten
|Room=HSZ/0003
|Date=2024/12/12
|DS=DS4
|Download=FS2024-Vorlesung-15.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=16. Kellerautomaten & CFGs
|Room=BAR/SCHÖ
|Date=2024/12/16
|DS=DS3
|Download=FS2024-Vorlesung-16.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=17. Deterministische Typ-2-Sprachen / Probleme für kontextfreie Sprachen
|Room=HSZ/0003
|Date=2024/12/19
|DS=DS4
|Download=FS2024-Vorlesung-17.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=18. Turingmaschinen
|Room=BAR/SCHÖ
|Date=2025/01/06
|DS=DS3
|Download=FS2024-Vorlesung-18.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=19. Nichtdeterminismus und Unentscheidbarkeit
|Room=HSZ/0003
|Date=2025/01/09
|DS=DS4
|Download=FS2024-Vorlesung-19.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=20. Typ 0 und Typ 1
|Room=BAR/SCHÖ
|Date=2025/01/13
|DS=DS3
|Download=FS2024-Vorlesung-20.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=21. Aussagenlogik
|Room=HSZ/0003
|Date=2025/01/16
|DS=DS4
|Download=FS2024-Vorlesung-21.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=22. Äquivalenzen und Normalformen
|Room=BAR/SCHÖ
|Date=2025/01/20
|DS=DS3
|Download=FS2024-Vorlesung-22.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=23. Logisches Schließen
|Room=HSZ/0003
|Date=2025/01/23
|DS=DS4
|Download=FS2024-Vorlesung-23.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=24. Horn-Logik und Komplexitätstheorie
|Room=BAR/SCHÖ
|Date=2025/01/27
|DS=DS3
|Download=FS2024-Vorlesung-24.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=25. NP-Vollständigkeit
|Room=HSZ/0003
|Date=2025/01/30
|DS=DS4
|Download=FS2024-Vorlesung-25.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Vorlesung
|Title=26. Zusammenfassung und Ausblick
|Room=BAR/SCHÖ
|Date=2025/02/03
|DS=DS3
|Download=FS2024-Vorlesung-26.pdf
}}
{{Vorlesung Zeiten
|Lehrveranstaltungstype=Konsultation
|Title=Prüfungskonsultation
|Room=https://tu-dresden.zoom-x.de/j/65660531712?pwd=zsUs3MvvFzDNIDcaLYHp9uVOladRbd.1
|Date=2025/02/14
|DS=DS2
}}
}}

Aktuelle Version vom 17. Februar 2025, 11:48 Uhr

Formale Systeme

Lehrveranstaltung mit SWS 4/2/0 (Vorlesung/Übung/Praktikum) in WS 2024

Dozent

Tutor

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 (BAR/SCHÖ/E)
  • Do 4. DS (HSZ/0003/H)

Übungen

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 Übung zu verweisen.

Übungsgruppen finden ab dem 21. Oktober 2024 zu ihren jeweiligen Terminen statt. Übungsblätter können in OPAL abgerufen werden.

Kontakt

Im OPAL steht ein Forum zum Austausch mit anderen Kursteilnehmenden bereit.

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

Prüfung

Nach aktueller Prüfungsplanung findet die Klausur (90min) am 18.02.2025 um 13:00 Uhr im Hörsaalzentrum statt. Zur Klausur sind keine Hilfsmittel zugelassen. Die Raumaufteilung ist nach Anfangsbuchstaben des Familiennamens wie folgt:

  • A–K: HSZ/AUDI/H
  • L–R: HSZ/02/E
  • S–Z: HSZ/03/H

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.

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)
(Schwerpunkt auf Logikprogrammierung und Prädikatenlogik, aber auch einiges zur Aussagenlogik)
(Aufgabensammlung aus den Logikvorlesungen vergangener Jahre)

Veranstaltungskalender abonnieren (icalendar)

Vorlesung 1. Formale Sprachen DS3, 14. Oktober 2024 in BAR/SCHÖ Datei
Vorlesung 2. Grammatiken und die Chomsky-Hierarchie DS4, 17. Oktober 2024 in HSZ/0003 Datei
Vorlesung 3. Endliche Automaten DS3, 21. Oktober 2024 in BAR/SCHÖ Datei
Vorlesung 4. Nichtdeterministische Endliche Automaten DS4, 24. Oktober 2024 in HSZ/0003 Datei
Vorlesung 5. Abschlusseigenschaften regulärer Sprachen DS3, 28. Oktober 2024 in BAR/SCHÖ Datei
Entfällt Reformationstag
Entfällt Keine Vorlesung DS3, 4. November 2024 in --
Entfällt Keine Vorlesung DS4, 7. November 2024 in --
Vorlesung 6. Reguläre Ausdrücke DS3, 11. November 2024 in BAR/SCHÖ Datei
Vorlesung 7. Reguläre Ausdrücke (2) DS4, 14. November 2024 in HSZ/0003 Datei
Vorlesung 8. Minimale Automaten DS3, 18. November 2024 in BAR/SCHÖ Datei
Vorlesung 9. Minimale Automaten (2) DS4, 21. November 2024 in HSZ/0003 Datei
Vorlesung 10. Grenzen regulärer Sprachen / Probleme regulärer Sprachen DS3, 25. November 2024 in BAR/SCHÖ Datei
Vorlesung 11. Von regulären zu kontextfreien Sprachen DS4, 28. November 2024 in HSZ/0003 Datei
Vorlesung 12. Das Wortproblem für kontextfreie Sprachen DS3, 2. Dezember 2024 in BAR/SCHÖ Datei
Vorlesung 13. Das Pumping-Lemma für kontextfreie Sprachen DS4, 5. Dezember 2024 in HSZ/0003 Datei
Vorlesung 14. Abschlusseigenschaften kontextfreier Sprachen DS3, 9. Dezember 2024 in BAR/SCHÖ Datei
Vorlesung 15. Kellerautomaten DS4, 12. Dezember 2024 in HSZ/0003 Datei
Vorlesung 16. Kellerautomaten & CFGs DS3, 16. Dezember 2024 in BAR/SCHÖ Datei
Vorlesung 17. Deterministische Typ-2-Sprachen / Probleme für kontextfreie Sprachen DS4, 19. Dezember 2024 in HSZ/0003 Datei
Vorlesung 18. Turingmaschinen DS3, 6. Januar 2025 in BAR/SCHÖ Datei
Vorlesung 19. Nichtdeterminismus und Unentscheidbarkeit DS4, 9. Januar 2025 in HSZ/0003 Datei
Vorlesung 20. Typ 0 und Typ 1 DS3, 13. Januar 2025 in BAR/SCHÖ Datei
Vorlesung 21. Aussagenlogik DS4, 16. Januar 2025 in HSZ/0003 Datei
Vorlesung 22. Äquivalenzen und Normalformen DS3, 20. Januar 2025 in BAR/SCHÖ Datei
Vorlesung 23. Logisches Schließen DS4, 23. Januar 2025 in HSZ/0003 Datei
Vorlesung 24. Horn-Logik und Komplexitätstheorie DS3, 27. Januar 2025 in BAR/SCHÖ Datei
Vorlesung 25. NP-Vollständigkeit DS4, 30. Januar 2025 in HSZ/0003 Datei
Vorlesung 26. Zusammenfassung und Ausblick DS3, 3. Februar 2025 in BAR/SCHÖ Datei
Konsultation Prüfungskonsultation DS2, 14. Februar 2025 in Videokonferenz


Kalender

















Abgerufen von „https://iccl.inf.tu-dresden.de/w/index.php?title=Formale_Systeme_(WS2024)&oldid=40879“