TU Wien:Theoretische Informatik VU (Fermüller)/TI Schummelzettel 2024W Gedankengang/Erklärung

Diese Seite bezieht sich auf meinen hochgeladenen Schummelzettel von 2024W, die auf der Wiki Seite angehängt sind und erklärt meine Gedankengänge, wieso ich welche Beispiele am Zettel stehen habe.

Vorderseite 2024W mit Stoff zu Teil 1 und Teil 3

Rückseite 2024W mit Stoff zu Teil 4, Teil 2 und Teil 5

Das wichtigste für den Schummelzettel ist, dass ihr "alles" drauf schreiben dürft. Daher könnt ihr ganze Lösungsverfahren der Altprüfungs-Musterlösungen aufschreiben, die ihr nur adaptieren müsst und beim Stress in der Prüfung nicht nachdenken müsst, was beim Lösungsschema als nächstes kommt (die Zeit ist sehr knapp bei der ganzen Prüfung).

Die Themen sind bei mir am Zettel nicht hintereinander. Ich hatte Teil 1 und 3 zuerst aufgeschrieben da der Umfang relativ klar war für den Schummelzettel.

Bei Teil 1 sind die Semi Entscheidungsprozedur und die Reduktion sehr wichtig. Schreibt diese so auf, dass ihr dann eine komplett neue machen könnt. Häufig ist die Lösung immer sehr ähnlich-> Ihr schachtelt eure Instanz vom Halteproblem in euer Programm und called diese dann.

Bei Teil 3 am wichtigsten ist Pr und RM, Lambda hatte ich zwar aufgeschrieben, kam aber bisher noch nie bei einer TI Prüfung. Für den Satz von Rice habe ich viel Platz unten gelassen, da dieser in einer Form immer zur Prüfung kam als kleine Verständnisfrage. Daher habe ich mir ein paar Beispiele aufgeschrieben und den "Die Menge ist eine extensionale ... Eigenschaft" Satz -> Gratis Punkte.

Bei Teil 4 habe ich eine gesamte Reduktionskorrektheit aufgeschrieben und das Weitergeben von P/NP bei Reduktionen. Versucht auf jeden Fall hier die Altlösungen zu verstehen bei den Reduktionen, da man hier "schwer" die Lösung auswendig lernen kann.

Bei Teil 2 war mir wichtig, einige common Pumping Lemma Beispiele rechts zu haben, die häufig kamen vom Schema her: mehr Symbole rechts als links, Schachtelung, gleichviele Symbole, Spiegelung, geschachtelte Spiegelung). Typ-i Grammatiken Chomsky Hierarchie und Abschlusseigenschaften auch sehr wichtig, diese sind immer "geschenkte" Punkte da ihr nur in den Tabellen nachsehen müsst. Bei Typ-i Grammatiken am besten alte Beispiele ansehen, damit ihr schnell erkennen könnt, was kontextsensitiv ist etc, das ist von der Definition manchmal nicht ganz klar.

Teil 5 hatte ich die Regeln aufgeschrieben. Ein Beispiel mit wlp hätte ich mir unbedingt aufschreiben sollen, das kam in der ersten 2024W Prüfung als "neues" Beispiel. Wichtig ist die Umformung rechts unten, für "if"s. Die, und "Konditionale rauf"(bei mir am Zettel) ist so nicht direkt in den Slides bei den Definitionen sondern erst ganz am Ende der Slides und diese hatte ich übersehen, bis der Prof sie bei der Übungsbesprechungsaufzeichnung ganz casual beim Annotieren verwendet hat.

Nehmt die Erklärungen hier nicht als Gospel, wenn ihr manche Beispiele "frei herunterschreiben" könnt, könnt ihr ruhig andere Beispiele aufschreiben. Bei mir hat es mit dem Schummelzettel und (viel) lernen auf 44/60 Pkt gereicht.