TU Wien:Theoretische Informatik VU (Fermüller)/Prüfung 2024-26-01

5 Beispiele zu je 12 Punkten

1) (10 + 2 Punkte) Semi-Entscheidbarkeit Prozedur für 2-Halteproblem zeigen und "beweisen" anhand von positiven und negativen Instanzen.

2) (12 Punkte) Pumping Lemma - Vorgefertigter Beweis nur noch Beispiel Wort einsetzen, Länge anschreiben, passendes i finden und argumentieren warum das neue Wort xy^iz nicht in der gegebenen Sprache liegt.

3) (2+2+4+6 Punkte) Pr-Funktionsausdruck auswerten, beschreiben was es macht, (noch irgendwas), argumentieren ob eine Turing-maschine das Problem auch berechnen kann

4) (12 Punkte) Reduktion von 3-Färbbarkeit und 3-Färbbarkeit-S (symmetrischer Graph) beweisen

5) (12 Punkte) Totale Korrektheit für ein Programm mit while Schleife mittels Annotation Schreibweise zeigen.