Account
Edit tools
Internal
SucheSearch
Deutsch

Formale Systeme

From International Center for Computational Logic

Formale Systeme

Course with SWS 4/2/0 (lecture/exercise/practical) in WS 2016

Lecturer

Tutor

SWS

  • 4/2/0

Modules

Examination method

  • Written exam

Lecture series


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.

Informationen zur Einsichtnahme in die Wiederholungsklausur

Die Einsichtnahme in die Wiederholungsklausur ist am 13.10.2017 in der Zeit von 9:00 bis 10:00 im Raum APB/3027 möglich. Eine Anmeldung ist in jedem Fall notwendig – bitte melden Sie sich dazu per E-Mail bei Stefan Borgwardt.

Wichtige Hinweise zur Wiederholungsklausur

Voraussetzung für die Teilnahme an der Wiederholungsklausur Formale Systeme ist eine ordnungsgemäße Einschreibung!

Die Klausur findet am 08.08.2017 um 09:20 Uhr im ZEU/LICH/H statt. Die Plätze sind spätestens 10 Minuten vor Beginn einzunehmen. Für die Bearbeitung der Klausur stehen 90 Minuten zur Verfügung. Es sind keine Hilfsmittel zugelassen. Bitte vergessen Sie nicht, Ihren Studentenausweis und einen Lichtbildausweis mitzubringen.

Termine

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

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


mit Ausnahme von Mo, 31.10., (Reformationstag) und der vorlesungsfreien Zeit zum Jahreswechsel (keine Vorlesungen vom 22.12.2016 bis zum 3.1.2017). Die Prüfung findet am 14.2.2017 statt. Alle Studierende müssen sich mittels der in ihrem Studiengang verwendeten Verfahren anmelden.

Hinweise

Mathematikstudenten, welche die Vorlesung im Rahmen ihres Nebenfachs besuchen, melden sich bitte so schnell wie möglich per E-Mail bei Herrn Borchmann.

Übungen

Die Einschreibungen in die Übungsgruppen erfolgt über JExam.

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. Die Einschreibung ist nur noch bis Montag, den 17. Oktober möglich.
  • Die Übung am Donnerstag in der 1. DS findet im Raum APB E008 statt, die Übung am Freitag in der 3. DS findet im Raum APB E006 statt. Zu beiden Zeitslots finden insbesondere keine Übungen im HSZ statt.
  • Die Übungen beginnen aber der 2. Vorlesungswoche (42. KW), also ab dem 17. Oktober.
  • Die Übung am Mittwoch in der 6. Doppelstunde findet nicht mehr in der E009 statt, sondern in der E006.
  • Die Übung am Freitag, den 18. November, in der 5. DS im Raum E009 findet einmalig nicht statt.
  • Die Übungen finden auch in der letzten Vorlesungswoche statt, bis also einschließlich 03.02.2017.

Übungsblätter

Repetitorien

Musterklausur

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

Lernraum

Es wird zur Prüfungsvorbereitung ein Lernraum angeboten. Dieser findet am 10.02.2017 statt. Bitte beachten dazu Sie die aktuellen Aushänge in der Fakultät.

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.

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/FS2016, 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. Auch Hinweise zu Tippfehlern in den Vorlesungsfolien sollten am besten direkt an die Liste 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 diesen Skripten, 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)

Subscribe to events of this course (icalendar)

Lecture Willkommen/Einleitung formale Sprachen DS3, October 10, 2016 in HSZ/0002 File 1,  File 2
Lecture Grammatiken und die Chomsky-Hierarchie DS4, October 13, 2016 in HSZ/0003 File 1,  File 2
Lecture Endliche Automaten DS3, October 17, 2016 in HSZ/0002 File 1,  File 2
Lecture Nichtdeterministische endliche Automaten DS4, October 20, 2016 in HSZ/0003 File 1,  File 2
Lecture Abschlusseigenschaften regulärer Sprachen DS3, October 24, 2016 in HSZ/0002 File 1,  File 2
Lecture Reguläre Ausdrücke (1) DS4, October 27, 2016 in HSZ/0003 File 1,  File 2
Lecture Reguläre Ausdrücke (2) DS4, November 3, 2016 in HSZ/0003 File 1,  File 2
Lecture Minimale Automaten DS3, November 7, 2016 in HSZ/0002 File 1,  File 2
Lecture Minimale Automaten (2) DS4, November 10, 2016 in HSZ/0003 File 1,  File 2
Lecture Grenzen regulärer Sprachen/Probleme für Automaten DS3, November 14, 2016 in HSZ/0002 File 1,  File 2
Lecture Von regulären zu kontextfreien Sprachen DS4, November 17, 2016 in HSZ/0003 File 1,  File 2
Lecture Das Wortproblem kontextfreier Sprachen DS3, November 21, 2016 in HSZ/0002 File 1,  File 2
Lecture Das Pumping Lemma kontextfreier Sprachen DS4, November 24, 2016 in HSZ/0003 File 1,  File 2
Lecture Abschlusseigenschaften kontextfreier Sprachen DS3, November 28, 2016 in HSZ/0002 File 1,  File 2
Lecture Kellerautomaten DS4, December 1, 2016 in HSZ/0003 File 1,  File 2
Lecture Kellerautomaten und Typ-2-Grammatiken DS3, December 5, 2016 in HSZ/0002 File 1,  File 2
Exercise Repetitorium 1 DS4, December 8, 2016 in HSZ/0003 File
Lecture Deterministische Typ-2-Sprachen / Entscheidungsprobleme DS3, December 12, 2016 in HSZ/0002 File 1,  File 2
Lecture Turingmaschinen DS4, December 15, 2016 in HSZ/0003 File 1,  File 2
Lecture Nichtdeterminismus und Unentscheidbarkeit DS3, December 19, 2016 in HSZ/0002 File 1,  File 2
Lecture Typ-0- und Typ-1-Sprachen DS4, January 5, 2017 in HSZ/0003 File 1,  File 2
Lecture Aussagenlogik DS3, January 9, 2017 in HSZ/0002 File 1,  File 2
Lecture Äquivalenz und Normalformen DS4, January 12, 2017 in HSZ/0003 File 1,  File 2
Lecture Logisches Schließen DS3, January 16, 2017 in HSZ/0002 File 1,  File 2
Lecture Horn-Logik / Komplexität DS4, January 19, 2017 in HSZ/0003 File 1,  File 2
Lecture NP-Vollständigkeit DS3, January 23, 2017 in HSZ/0002 File 1,  File 2
Exercise Besprechung Musterklausur DS4, January 26, 2017 in HSZ/0003 File
Exercise Repetitorium 2 DS3, January 30, 2017 in HSZ/0002 File
Lecture Zusammenfassung und Ausblick DS4, February 2, 2017 in HSZ/0003 File 1,  File 2


Calendar


Retrieved from "https://iccl.inf.tu-dresden.de/w/index.php?title=Formale_Systeme_(WS2016)/en&oldid=20961"