TU Wien:Theoretische Informatik VU (Fermüller)

Daten

Zuordnungen

Bachelorstudium Informatik	Modul Theoretische Informatik (Pflichtfach)
Bachelorstudium Medieninformatik und Visual Computing	Modul Theoretische Informatik (Gebundenes Wahlfach)
Bachelorstudium Medizinische Informatik	Modul Theoretische Informatik (Pflichtfach)
Bachelorstudium Software & Information Engineering	Modul Theoretische Informatik (Pflichtfach)
Bachelorstudium Technische Informatik	Modul Theoretische Informatik (Pflichtfach)

Inhalt

Einführung in Berechenbarkeit und Entscheidbarkeit

• Entscheidbarkeit, Semi-Entscheidbarkeit, Halteproblem, Reduktionen

Formale Sprachen

• Turingmaschinen, Reguläre Sprachen, Grammatiken, Kontextfreie Grammatiken und Sprachen, Jenseits der Kontextfreiheit, Chomsky Hierarchie

Berechenbarkeit Vertiefung

• Turingmaschinen, Registermaschinen, Lambda-Kalkül, Satz von Rice

Einführung in die Komplexitätstheorie

• Komplexitätsklassen P und NP, NP-Vollständigkeit, Weitere Komplexitätsklassen, Reduktionen

Formale Semantik von Programmen

• Korrektheitsaussagen, Hoare-Kalkül

Ablauf

Die LVA ist in 4 Abschnitte geteilt:

1. Einführung in Berechenbarkeit und Entscheidbarkeit
2. a) Formale Sprachen b) Berechenbarkeit Vertiefung
3. Einführung in die Komplexitätstheorie
4. Formale Semantik von Programmen

Jeder Abschnitt wird von jemand anderem vorgetragen, und zu pro Abschnitt gibt es ein Übungsblatt (siehe weiter unten). Am Ende des Semesters gibt es einen Abschlusstest - es werden 4 Termine dafür angeboten und man darf 2 mal antreten.

Benötigte/Empfehlenswerte Vorkenntnisse

Die LVA hat inhaltlich viele Überschneidungen mit Formale Modellierung und Algodat, diese LVAs bereits besucht zu haben ist sicher ein Vorteil.

Vortrag

Es wechseln sich mehrere Vortragende ab, die Qualität des Vortrags (und auch der dazugrhörigen Folien) varriiert leider enorm.

Abschnitt 1 (Reinhard Pichler): Vortrag ist in Ordnung, man kann ihm gut folgen, die Unterlagen sind hilfreich für das erste Aufgabenblatt, legt viel Wert auf Ruhe im Hörsaal

Abschnitt 2a (Marion Oswald): Sehr guter Vortrag, rechnet viele Beispiele vor anstatt (wie die anderen) nur von den Folien abzulesen, gestaltet die Vorlesung interaktiver als sonst, Unterlagen sind gut und hilfreich

Abschnitt 2b (Chris Fermüller): Vortrag ist sehr chaotisch und schlecht, man kann ihm kaum folgen, er spricht oft Sätze nicht zu Ende. Seine Folien sind eine Katastrophe, voll von Fehlern und nicht hilfreich für die Aufgaben im Aufgabenblatt 2.

Zweitmeinung: Konnte ihm eigentlich ganz gut folgen und fand die Fehler in den Folien minimal (wären mir teilweise nichtmal aufgefallen) und eigentlich nicht relevant für das Aufgabenblatt obwohl man die wichtigsten Stellen öfter durchgehen muss bis man durchblickt. Die Aufgaben waren bis auf ein Beispiel ziemlich ähnlich zu denen in den Folien.

Andere Meinung: Konnte ihm zwar gut folgen und fand seinen Vortrag sehr motiviert und interessant, allerdings waren die Slides Müll - überall waren kleine Fehler, sodass man sich beim genauen Durchdenken oft fragt, ob das jetzt ein eigener Denkfehler ist oder ein Fehler in den Slides.

Noch eine andere Meinung: Wirklich kein guter Vortrag, nicht nur die Folien sind voller Fehler, sondern er verliert sich auch oft in dem was er sagt, und sagt dadurch auch oft falsche Sachen bzw. liest falsch vor oder vermischt das was er sagen will mit dem was auf den Folien steht (z.B. redet er im Kapitel über das Lambda-Kalkül plötzlich über "Lambda-Reduktionen" statt Alpha-Reduktionen - Lambda-Reduktionen existieren aber nicht.) Die Fehler in den Folien waren echt schlimm, sind aber nach und nach von ihm ausgebessert worden und in der neu hochgeladenen Version der Folien gibt es nur mehr weniger Fehler (aber immer noch welche), deswegen ist es vielleicht manchen nicht so aufgefallen. Wenn man während der Vorlesung die Folien verwendet hat um mitzuschreiben ist das natürlich zu spät wenn die korrekten Folien erst eine Woche danach zur Verfügung stehen.

Abschnitt 3 (Stefan Woltran): Vortrag ist ok. Wenn man AlgoDat bereits absolviert hat wird nicht viel neues vermittelt. Die Folien werden nicht minimized herausgegeben und sind generell etwas unübersichtlich. Er hat oft erwähnt wie er Leute im Hörsaal bevorzugt und daher Erklärungen die nicht in den Folien sind auf die Tafel schreibt. Abschnitt zu weiteren Komplexitätsklassen wie L, EXPSPACE,... interessant, aber nicht prüfungsrelevant.

Abschnitt 4 (Gernot Salzer): Vortrag ist gut. Gute allgemeine Strukturierung wobei man die einzelnen Teilbereiche gut differenzieren kann. Es lohnt sich aber gut aufzupassen, da einiges in den Folien nicht so ersichtlich ist wie wenn man seiner Erklärung folgt. Hat auch einige zusätzliche Unterlagen hochgeladen (Cheat-Sheets, Zusammenfassungen, etc.) was sehr hilfreich war. Trivial, wenn man bereits Programm- und Systemverifikation gemacht hat.

Übungen

Es gibt über das Semester verteilt 4 Aufgabenblätter, zu jedem der 4 Abschnitte der Vorlesung eines. Die Aufgabenblätter sind unterschiedlich umfangreich und bringen auch unterschiedlich viele Punkte, der Zeitaufwand variiert daher (jeweils mind. 2 Tage sollte man aber einplanen wenn man es gscheit machen will).

Eine Mindestpunktezahl gibt es dafür nicht, aber komplett ohne Übungsblätter ist es schwierig auf die Mindestpunktezahl der gesamten LVA zu kommen.

Man bekommt auch Punkte für Abgaben mit Fehlern, es werden nur "vernünftige Lösungsversuche" erwartet. Man bekommt eine LaTeX-Vorlage, mit der man die Ausarbeitung machen kann (genau wie in FMOD). Ab und zu war es leider ein bisschen inkonsistent für was man Punkte bekommt - teils wurden Punkte vergeben, wenn nur irgendwas dasteht, teils wurden (wenige) Punkte abgezogen, wenn ein Satz, der für den Bewertenden wichtig war, fehlte.

Aufgabenblätter sorgfältig zu machen zahlt sich in jedem Fall aus, da ähnliche Beispiele auch zur Prüfung kommen werden.

Prüfung, Benotung

Die LVA besteht aus

• dem Übungsteil (4 Aufgabenblätter, siehe oben) - max. 40 Punkte
• und einem Abschlusstest am Ende über den gesamten Stoff - max 60 Punkte

Man ist positiv wenn man auf die Prüfung mind. 30 Punkte, und auf die LVA insgesamt mind. 50 Punkte hat.

Dauer der Zeugnisausstellung

Semester	Prüfung	Zeugnis
2023W	26.01.2024	14.02.2024	3,5 Wochen

Zeitaufwand

noch offen

Unterlagen

noch offen

Tipps

noch offen

Highlights / Lob

noch offen

Verbesserungsvorschläge / Kritik

noch offen

Materialien

Neues Material hinzufügen

2

• 2023W UE1 Musterlösung.pdf (details)
• 2023W UE2 Musterloesung.pdf (details)
• 2023W UE3 Musterloesung.pdf (details)
• 2023W UE4 Muesterloesung.pdf (details)

P

• Pruefung 2024 01 26 Musterlösung.pdf (details)
• Prüfung 2024-26-01
• Prüfung 2024-01-26 Angabe.pdf (details)

T

• Thinf 3 stripped.pdf (details)
• Thinf all stripped23w.pdf (details)
• Thinf Cheatsheet 23W.pdf (details)
• Prüfung vom 26.01.2024

Z

• Zusammenfassung Altprüfungen TIL Hoare-Kalkül.pdf (details)