TU Wien:Logic and Computability VU (Ciabattoni, Fermüller)

From VoWi
Jump to navigation Jump to search
Similarly named LVAs (Resources):

Daten[edit]

Lecturers Agata Ciabattoni, Christian Fermüller
ECTS 6
Department Forschungsbereich Theory and Logic
Links tiss:185A45
Zuordnungen
Master Logic and Computation Pflichtmodul Logic and Computability

Mattermost: Channel "logic-and-computability"RegisterMattermost-Infos

Inhalt[edit]

Teil 1: Aussagelogik, PL1, Natürliches schließen, Herbrand Kalkül, Sequenzenkalkül

Teil 2: Automated Deduction, Modallogik, Intuitionistic Logic

Teil 3: Berechnungsmodelle (Turing Maschinen, Lambda Kalkül, rekursive Funktionen), Berechenbarkeit

Teil 4: Unvollständigkeit (Gödel's Unvollständigkeitssatz)

Ablauf[edit]

Von Oktober an zwei Mal pro Woche Vorlesung. Jede Vorlesung kann 60-120 Minuten dauern. Die Länge hängt hier immer sehr stark vom Thema und der Laune des Vortragenden ab.

Zusätzlich gibt es drei Übungsblätter (für Teil 1 bis 3) die alleine gelöst werden sollen. Eine Ausarbeitung in Latex bzw. Word wird verlangt.

Abgaben und Kommunikation mit den Vortragenden erfolgt per Email. Man kann auch Fragen zum Stoff per Email stellen. Es wird in der Regel schnell geantwortet.

Benötigte/Empfehlenswerte Vorkenntnisse[edit]

Grundkenntnisse über Logik etwa von TIL sind empfehlenswert. Prinzipiell wird aber alles erklärt. Wenn TIL nicht besucht wurde, gibt es im Laufe des Kurses noch ein Repetitorium zum Stoff von TIL.

Vortrag[edit]

Teils auf den Folien, Teils auf der Tafel (Beweise, Beispiele etc.). Vortrag ist bemüht und will interaktiv sein.

Teil 1 + 3 (Ciabattoni): Die Folien reichen zum Lernen alleine nicht aus. Es gibt aber für Teil 1 ein (sehr gutes) und für Teil 3 ein (mittelmäßig gutes) Skript.

Teil 2 + 4 (Fermüller): Die zwei Vorlesungen zum 4. Teil zu besuchen ist sehr empfehlenswert, sonst wird das Lernen des Themas echt hart.

Übungen[edit]

3 Übungsblätter für die jeweils 2-3 Wochen Zeit ist Bewertung ist sehr human. Man bekommt aber kein Feedback zugeschickt, sondern es gibt in einer der letzten Einheiten ein Q&A wo man ausführlich individuelles mündliches Feedback zur Abgabe erhält und die Bewertung erfährt.

Prüfung, Benotung[edit]

Schriftliche Prüfung, an die Übungsbeispiele angelehnt. Dann noch zwei mündliche Prüfungen (bei beiden Vortragenden getrennt). Es kann praktisch sein, da ein paar Tage dazwischen zu haben, um sich den Stoff bei Lernen aufteilen zu können.

January 2022: Notification about passing the written part was after 3 days. The first oral exam date was 7 days after the written exam. Prof. Fermüllers oral exam was directly after Ciabattoni's oral exam.

Ciabattoni:

  • Asked for clarifications about two answers (of the computability part) that I gave in the written exam
  • I apparently did bad in the computability theory part, so questions from the question catalog were only about computability:
    • Proof Equivalence between r.e. sets and semi-decidable sets
    • Proof of Rice Theorem (talking about the additional steps that she mentioned in the lecture video seemed well received)
    • Proof of Post theorem
    • It was important to know the theorems precisely

Fermüller:

  • Also asked for clarifications about the ADRF answer that I gave in the exam. Small errors in the automated deduction part in written exam were not too important.
  • Questions about what was not covered in exam: Intuitionistic logic & Incompleteness
    • Prove (G & F) -> (F v H) in BHK semantics. It is good to use the right words, not "it holds" (this is classical logic), talk about pairs & indicators for the OR, he often mentioned "there is an algorithm, a _concrete_ program that takes and transforms something"
    • Difference between Gödel-incompleteness (sentence that is neither in set of provable nor in set of refutable sentences) and incompleteness (we know the sentence is true, but not it is not provable). It was important to use precisely the definition from the slides. Talking about the definition from another course hasn't helped.

I messed up on the r.e./semi-decidability proof but think I did really good on the other proofs and Ciabattoni proposed a 3 because she still had the feeling that I haven't studied that part. Doing exceptionally well on the Fermüller part would have made it a 2, but doing "OK" left it at 3. So I think written and oral exam were not really separate grades as it seemed in the grading schema.

Dauer der Zeugnisausstellung[edit]

10 Min nach der mündlichen Prüfung (war aber der letzte).

Zeitaufwand[edit]

Hängt sehr stark vom Vorwissen und der Affinität für Logik und formale Themen ab, sollte aber auch ohne große Vorkenntnisse unter den 6 ECTS liegen.

Meine Erfahrung (mit Vorwissen und Interesse): 3*5h für die Übgungsblätter, 15 Stunden Lernen für die Prüfung für ein S1.

Unterlagen[edit]

Gutes Einführungsvideo zum 4. Teil: https://www.youtube.com/watch?v=O4ndIDcDSGc

Tipps[edit]

  • Es werden immer mehr oder weniger gute Abgaben von Studierenden als "Musterlösung" im TISS veröffentlicht. Da sich die Übungsaufgaben manchmal wiederholen, hilft es, mal im TISS in alte Semester zu schauen.
  • Es kommen immer alle Teilen zur mündlichen Prüfung. Einen Teil auslassen ist keine gute Idee.
  • Beim 3. Teil liegt der Schwerpunkt eindeutig auf dem was im Skript steht. Foliensatz 2 und 3 (Turing Maschinen und Lambda Kalkül wurden nicht geprüft.)
  • Übungsblätter selber machen, hilft für die schriftliche Prüfung.
  • Bei Teil 1 und 3 gibt es eine Liste von Beweisen die zur mündlichen Prüfung kommen. Die verlangten Beweise lernen.

Verbesserungsvorschläge / Kritik[edit]

  • Die Kommunikation mit den Studierenden könnte etwas verbessert werden. (Bei TISS und Email geht leider leicht was unter)
  • Anmeldung zur Prüfung: man darf sich zur mündlichen Prüfung im TISS nur anmelden, wenn man die schriftliche bestanden hat und auch nur beim entsprechenden Termin. Das wurde aber schlecht kommuniziert und TISS lässt aber alle anmelden.