TU Wien:Theoretische Informatik VU (Fermüller)/Prüfung vom 26.01.2024
Zur Navigation springen
Zur Suche springen
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.