Vorlesung Grundlagen der Theoretischen Informatik (SS 2020)

Klausurergebnisse

Noten	Min. Punkte	Anzahl
NB	0	11
4,0	40	4
3,7	46	2
3,3	52	8
3,0	58	2
2,7	64	5
2,3	70	1
2,0	76	2
1,7	82	1
1,3	88	5
1,0	94	4

Aktuelles

Während der Zeit der des universitären Minimalbetriebs werden wir Ihnen wöchentlich per email Arbeitspakete zum Selbststudium schicken.

Bitte stellen Sie sicher, dass Sie im unisono-System für die Vorlesung angemeldet sind, damit Sie alle emails erhalten.

Sollten Sie nicht angemeldet sein, melden Sie sich bitte mit Ihrer Matrikelnummer bei unserer Sekretärin Cristina Böttcher (cristina.boettcher@uni-siegen.de).

Arbeitspakete zum Selbststudium

• Woche 06.4-10.4: Folie 1-43 (Buch von Schöning, Seite 3-18)

• Woche 13.4-17.4: Folie 44-80 (Buch von Schöning, Seite 19-27)

• Woche 20.4-24.4: Folie 81-110 (Buch von Schöning, Seite 27-31)

• Woche 27.4-01.5: Folie 111-141 (Buch von Schöning, Seite 31-34 sowie Abschnitt 1.2.6)

• Woche 04.5-08.5: Folie 142-175 (Buch von Schöning, Seite 34-43 ohne Abschnitt 1.2.6)

• Woche 11.5-15.5: Folie 176-195 sowie 205-220 (Buch von Schöning, Seite 43-46 und 49-55)

• Woche 18.5-22.5: Folie 221-260 (Buch von Schöning, Seite 55-64)

• Woche 25.5-29.5: Folie 261-301 (Buch von Schöning, Seite 64-71)

  Hinweis: Das Material zu deterministisch-kontextfreien Sprachen wird in der Klausur nicht geprüft.

• Woche 01.6-05.6: Folie 302-334 (Buch von Schöning, Seite 72-76)

• Woche 08.6-12.6: Folie 335-367 (Buch von Schöning, Seite 76-88)

• Woche 15.6-19.6: Folie 368-404 (Buch von Schöning, Seite 89-100)

• Woche 21.6-26.6: Folie 405-436 (Buch von Schöning, Seite 101-108)

• Woche 29.6-03.7: Folie 452-485 (Buch von Schöning, Seite 114-119)

  Hinweis: Folien 437-451 sind für die Klausur nicht relevant!

• Woche 06.7-10.7: Folie 486-518 (Buch von Schöning, Seite 120-128)

• Woche 06.7-10.7: Folie 519-527 (Buch von Schöning, Seite 128-133)

Organisatorisches

• Veranstalter: Prof. Dr. Markus Lohrey
• Vorlesungstermine:
  • Dienstag, 14:00-16:00, in AR-D 5103 (roter Hörsaal)
  • Donnerstag, 14:00-16:00, in H-C 3305
• Übungen:
  • Dienstag, 16:00-18:00, in H-F 116
  • Mittwoch, 12:00-14:00, in H-C 7326
  • Mittwoch, 16:00-18:00, in H-C 6336/37
  • Donnerstag, 10:00-12:00, in H-C 6336/37
  • Donnerstag, 16:00-18:00, in H-F 114

Es darf ein (beidseitig) handschriftlich beschriebenes DIN-A4-Blatt mit in die Klausur genommen werden.

Einige Themen

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

---

Folien (Version vom 10.07.2020)

---

Informationen zu den Übungen

Die Übungsblätter dienen dazu, die in der Vorlesung thematisierten Inhalte durch das Lösen konkreter Aufgaben anzuwenden.
Lösen Sie daher am besten die Aufgaben so gut es geht selbsttständig um den bestmöglichen Lerneffekt zu erzielen.

Um Ihnen das Arbeiten von zu Hause zu erleichtern, stellen wir Ihnen auch Musterlösungen zur Verfügung.
Es ist jedoch weiterhin empfehlenswert, sich zuerst selbstständig am Lösen der Aufgaben zu versuchen und die eigenen Lösungen anschließend mit unseren Lösungen zu vergleichen.
Um diese Arbeitsweise zu unterstützen, werden die Lösungen zeitversetzt zu den Aufgaben veröffentlicht. Die ersten Lösungen finden Sie am 13.04 online, anschließend folgt jeden Montag eine weitere Musterlösung.

Wir empfehlen Ihnen das jeweilige Übungsblatt spätestens in der Woche vollständig zu bearbeiten, wenn die dazugehörige Lösung und das nächste Übungsblatt online gestellt werden.

 

Ü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

---