Account
Edit tools
Intern
SucheSearch
English

Formale Systeme

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Formale Systeme

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

Dozent

Tutor

Umfang (SWS)

  • 4/2/0

Module

Leistungskontrolle

  • Klausur

Vorlesungsreihe


Die Vorlesung 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.

Termine

Die erste Vorlesung ist am Montag, 09.10.2017. Weitere Termine sind jeweils:

  • montags 3.DS (11:10–12:40) HSZ/0002
  • donnerstags 4.DS (13:00–14:30) HSZ/0003


Achtung: Am Montag, dem 23.10.2017, findet keine Vorlesung statt.

WIEDERHOLUNGSKLAUSUR

Die Wiederholungsklausur findet am Dienstag den 7. August 2018 um 11:10 in Raum HSZ/0003 im Hörsaalzentrum (Bergstr. 64) statt (ohne Gewähr, Änderungen werden vom Prüfungsamt bekanntgegeben).

KLAUSUREINSICHT

Am Mittwoch den 11.04.2018 kann Einsicht in die Klausur genommen werden. Die Einsicht findet in Raum APB/E001 statt. Bitte kommen Sie zu Beginn eines Ihrem Nachnamen zugewiesenen Zeitfensters:

  • 13:00-13:15 A-B
  • 13:15-13:30 C-D
  • 13:30-13:45 E-F
  • 13:45-14:00 G-G
  • 14:00-14:15 H-J
  • 14:15-14:30 K-K
  • 14:30-14:45 K-K
  • 14:45-15:00 L-L
  • 15:00-15:15 M-Q
  • 15:15-15:30 R-R
  • 15:30-15:45 S-S
  • 15:45-16:00 S-S
  • 16:00-16:15 T-V
  • 16:15-16:30 W-Z

KLAUSUR

Die Klausur findet am 13. Februar 2018 um 9:20 im Hörsaalzentrum (Bergstr. 64) statt (ohne Gewähr, Änderungen werden vom Prüfungsamt bekanntgegeben). Bitte beachten Sie die Aufteilung auf zwei Hörsäle: 

* Nachnamen beginnend mit A-M: HSZ/AUDI/H (Audimax)
* Nachnamen beginnend mit N-Z: HSZ/0003/H

Lernräume: In Vorbereitung auf die Klausur wird es folgende Termine für Lernräume geben:

  • 06.02.2018, 14-16:00 Uhr, E007
  • 06.02.2018, 16-18:00 Uhr, E006

Diese können zur angegeben Zeit ohne vorherige Terminabsprache besucht werden.

Übungen

Die Einschreibungen in die Übungsgruppen erfolgt über JExam. Sollten Sie keinen Zugang zu JExam haben schreiben Sie bitte eine kurze Email.

Bitte beachten Sie:

  • 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 sind berechtigt, nicht eingeschriebene Studierende bei Überfüllung aus der Übung zu verweisen.

Übungsblätter

Musterklausur

Als Prüfungsvorbereitung wird eine Musterklausur zur Verfügung gestellt. Diese wird am 01.02. in der Vorlesungszeit vorgerechnet werden.

Unterlagen

Die vollständigen Foliensätze zur Vorlesung erscheinen spätestens kurz nach der Vorlesung online (siehe Termine und Unterlagen). Weiterführende Literatur ist unter Literatur angegeben. Die Quellen der Vorlesungsfolien sind auf github verfügbar: https://github.com/mkroetzsch/FormaleSysteme

Alle Foliensätze der Vorlesungen können entsprechend den Lizensbedingungen von Creative Commons CC By 3.0 Deutschland genutzt, weitergegeben und modifiziert werden. Als Namensnennung ist folgende Angabe einzufügen: 

(C) Markus Krötzsch, https://iccl.inf.tu-dresden.de/web/FS2017, CC BY 3.0 DE

Bildrechte können davon abweichen und sind gesondert angegeben. Die Foliensätze enthalten keinerlei Texte, die aus Werken entnommen sind, für welche die VG Wort Verwertungsrechte vertritt.

Kontakt

Für Fragen rund um den Stoff und Vorlesungsbetrieb ist eine Mailingliste eingerichtet worden, auf der sich Teilnehmer_innen der Vorlesung einschreiben können. Dazu muss nur das Anmeldeformular ausgefüllt werden. Fast alle Fragen sollten auf diesem Weg gestellt werden.

Kommentare und Bug Reports können gern auch direkt über die entsprechenden Seiten auf github gepostet werden: https://github.com/mkroetzsch/FormaleSysteme Alternativ können Hinweise zu Tippfehlern in den Vorlesungsfolien auch an die Mailingliste geschickt werden.

Persönliche Fragen können auch direkt an das Organisationsteam (siehe Links oben) gestellt werden, falls sie aus einem zwingenden Grund nicht an die Mailingliste gerichtet werden können. Allgemein Fragen sollten Sie aber immer an die Liste richten, damit auch Ihre Kommilitonen 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.

Andere Scripte scheinen zurzeit nicht (mehr) online verfügbar zu sein. Hinweise zu weiteren Links auf sinnvolle Materialien sind willkommen.

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 Willkommen/Einleitung formale Sprachen DS3, 9. Oktober 2017 in HSZ/0002 Datei 1,  Datei 2
Vorlesung Grammatiken und die Chomsky-Hierarchie DS4, 12. Oktober 2017 in HSZ/0003 Datei 1,  Datei 2
Vorlesung Endliche Automaten DS3, 16. Oktober 2017 in HSZ/0002 Datei 1,  Datei 2
Vorlesung Nichtdeterministische endliche Automaten DS4, 19. Oktober 2017 in HSZ/0003 Datei 1,  Datei 2
Vorlesung Abschlusseigenschaften regulärer Sprachen DS4, 26. Oktober 2017 in HSZ/0003 Datei 1,  Datei 2
Vorlesung Reguläre Ausdrücke DS3, 30. Oktober 2017 in HSZ/0002 Datei 1,  Datei 2
Vorlesung Reguläre Ausdrücke (2) DS4, 2. November 2017 in HSZ/0003 Datei 1,  Datei 2
Vorlesung Minimale Automaten DS3, 6. November 2017 in HSZ/0002 Datei 1,  Datei 2
Vorlesung Minimale Automaten (2) DS4, 9. November 2017 in HSZ/0003 Datei 1,  Datei 2
Vorlesung Grenzen regulärer Sprachen/Berechnungsprobleme DS3, 13. November 2017 in HSZ/0002 Datei 1,  Datei 2
Vorlesung Von regulären zu kontextfreien Sprachen DS4, 16. November 2017 in HSZ/0003 Datei 1,  Datei 2
Vorlesung Das Wortproblem kontextfreier Sprachen DS3, 20. November 2017 in HSZ/0002 Datei 1,  Datei 2
Vorlesung Das Pumping Lemma kontextfreier Sprachen DS4, 23. November 2017 in HSZ/0003 Datei 1,  Datei 2
Vorlesung Abschlusseigenschaften kontextfreier Sprachen DS3, 27. November 2017 in HSZ/0002 Datei 1,  Datei 2
Vorlesung Kellerautomaten DS4, 30. November 2017 in HSZ/0003 Datei 1,  Datei 2
Vorlesung Kellerautomaten und Typ-2-Grammatiken DS3, 4. Dezember 2017 in HSZ/0002 Datei 1,  Datei 2
Vorlesung Deterministische Typ-2-Sprachen / Entscheidungsprobleme DS4, 7. Dezember 2017 in HSZ/0003 Datei 1,  Datei 2
Vorlesung Turingmaschinen DS3, 11. Dezember 2017 in HSZ/0002 Datei 1,  Datei 2
Übung Repetitorium 1 DS4, 14. Dezember 2017 in HSZ/0003 Datei 1,  Datei 2
Vorlesung Nichtdeterminismus und Unentscheidbarkeit DS3, 18. Dezember 2017 in HSZ/0002 Datei 1,  Datei 2
Vorlesung Typ-0- und Typ-1-Sprachen DS4, 4. Januar 2018 in HSZ/0003 Datei 1,  Datei 2
Vorlesung Aussagenlogik DS3, 8. Januar 2018 in HSZ/0002 Datei 1,  Datei 2
Vorlesung Äquivalenz und Normalformen DS4, 11. Januar 2018 in HSZ/0003 Datei 1,  Datei 2
Vorlesung Logisches Schließen DS3, 15. Januar 2018 in HSZ/0002 Datei 1,  Datei 2
Vorlesung Horn-Logik / Komplexität DS4, 18. Januar 2018 in HSZ/0003 Datei 1,  Datei 2
Vorlesung NP-Vollständigkeit DS3, 22. Januar 2018 in HSZ/0002 Datei 1,  Datei 2
Übung Repetitorium 2 DS4, 25. Januar 2018 in HSZ/0003 Datei
Vorlesung Zusammenfassung und Ausblick DS3, 29. Januar 2018 in HSZ/0002 Datei 1,  Datei 2
Übung Besprechung Musterklausur DS4, 1. Februar 2018 in HSZ/0003 Datei


Kalender
















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