Vorlesung Grundlagen der Theoretischen Informatik (SS 2021)

 

Wichtige Informationen zur kommenden GTI-Klausur

Die Klausur wird als Take-Home-Exam am 16. August 2021 von 15:00-17:00 (Dauer: 2 Stunden!) stattfinden. Sie werden am 16. August 2021 bis 15:00 die Aufgaben an Ihre universitäre Email-Adresse (vorname.nachname@student.uni-siegen.de) geschickt bekommen.

Die Lösungen müssen mit der Hand geschrieben werden. Schreiben Sie bitte deutlich. Unleserliche Lösungen sind ungültig.

Es ist nicht notwendig, die Klausur auszudrucken: Sie können Ihre Lösungen gerne auf eigene (einfarbig weiße, linierte oder karierte) DIN-A4-Blätter schreiben.

Beschriften Sie jedes Blatt mit Ihrem Namen, Ihrer Matrikelnummer, und der Aufgabennummer.

Die fertigen Lösungen scannen oder fotografieren Sie. Achten Sie auf gute Lesbarkeit. Wir empfehlen die kostenlose App Adobe Scan zum einscannen der Seiten. Alternativ können Sie die Lösungen auch direkt auf einem Tablet mit der Hand schreiben und uns das PDF schicken.

Ihre Lösungen müssen bis spätestens 17:20 Uhr am 16. August 2021 bei einer der folgenden Email-Adressen ankommen:

• michael.figelius@uni-siegen.de (Nachnamen mit A-F)
• reh@eti.uni-siegen.de (Nachnamen mit G-L)
• seelbach@eti.uni-siegen.de (Nachnamen mit M-S)
• Andreas.Rosowski@uni-siegen.de (T-Z)

 

Zusammen mit Ihren Lösungen schicken Sie eine ausgefüllte und unterschriebene Erklärung über die eigenstandige Erbringung der Prüfungsleistung.

Alle Hilfsmittel sind erlaubt, bis auf die Hilfestellung durch eine andere Person.

Für Notfälle können Sie uns während der Klausur unter noch anzugebenden Telefonnummern erreichen. Wir können jedoch nicht garantieren, dass diese Nummern auch stets erreichbar sind.

 

Organisatorisches

• Veranstalter: Prof. Dr. Markus Lohrey
• Vorlesungstermine:
  • Dienstag, 14:15-15:45 über zoom
  • Donnerstag, 14:15-15:45 über zoom
• Der erste Vorlesungstermin ist am 13. April.
• Übungen (alle über Discord):
  • Montag, 10:15-11:45
  • Montag, 14:15-15:45
  • Mittwoch, 12:15-13:45
  • Donnerstag, 10:15-11:45
  • Donnerstag, 12:15-13:45
• Alle Übungsgruppen beginnen in der Woche von 19. April bis 23. April.

 

Einige Themen

• Formale Sprachen
• Chomsky Hierarchie
• Endliche Automaten
• Kontextfreie Grammatiken
• Kellerautomaten
• Berechenbarkeit und Unentscheidbarkeit
• Komplexität, insbesondere P versus NP

 

Folien

(Version vom 15.07.2021)

 

Videos

 

Übungsblätter 

• Blatt 1 (Lösung)
• Blatt 2 (Lösung)
• Blatt 3 (Lösung)
• Blatt 4 (Lösung)
• Blatt 5 (Lösung)
• Blatt 6 (Lösung)
• Blatt 7 (Lösung)
• Blatt 8 (Lösung)
• Blatt 9 (Lösung)
• Blatt 10 (Lösung)
• Blatt 11 (Lösung)
• Blatt 12 (Lösung)
• Blatt 13 (Lösung)
• Blatt 14 (Lösung)

 

Lehrbücher

• Uwe Schöning, Theoretische Informatik - kurz gefasst, Spektrum Akademischer Verlag
• Lutz Priese, Katrin Erk, Theoretische Informatik: Eine umfassende Einführung, Springer
• Alexander Asteroth, Christel Baier, Theoretische Informatik, Pearson Studium