Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Sammlung der Übungslösungen
Hey,
ich wollte mal fragen, ob Jemand zwecks Üben für die Klausur seine Übungslösungen irgendwo rumfliegen hat und hier verlinken kann. Ich hab zwar mehr oder weniger die Lösungen komplett, teilweise aber nur 2 Stichpunkte stehen.
Auch wenn nur teilweise was zusammen kommt, wirds sicherlich auch anderen helfen.
Schönen Dank euch!
ich würde gerne die aufgaben die ich richtig habe schon hochladen und verlinken 
Ich fang mal an: http://fau.phi1010.com/bfs/
Rest kommt noch - hoffentlich vor der Klausur.
Bei Unklarheiten, in der Korrektur und beim Ausbessern der Lösung übersehenen Fehlern, etc. einfach nachhaken…
3 „Gefällt mir“
Ich hätte da eine Frage zu Blatt 4 Aufgabe 18b:
Hier wird in der Aufgabenstellung angenommen, dass L1 entscheidbar ist, in der Lösung, dass das Halteproblem auf L1 projiziert wird, welches jedoch de facto nicht entscheidbar ist.
Liegt hier ein Fehler in der Lösung oder ein Verständnisfehler meinerseits vor?
Also ich sehe jetzt keinen Grund, warum die leere Menge eine Gödelnummer einer TM sein soll. Dann macht das so generell wenig Sinn.
Ich kenne aber eine ziemlich große Obermenge (L1) vom Halteproblem (L2), die ich mit einer ein-zeilen-TM entscheiden könnte 
Ja, die Lösung müsste die selbe wie für die a) sein, Korrektur online (04-18-v2.pdf).
für v1:
“Ist L2 entscheidbar und L1 ⊇ L2, ist dann L1 notwendigerweise entscheidbar?”, dann könnt’s wieder passen…
Schlechte Renderqualität? Ø⊆L1, nicht Ø∈L1 …
Fürchte das lag in dem Fall nicht am PDF-Viewer 
Aber ich bin mit der neuen Version einverstanden^^
So, alles mit TODO sowie ein bisschen Referenz für primitive Rekursion - hoffentlich ohne Fehler - sind online.
Jemand hat mich nach einer korrigierten Lösung für Blatt 14 gefragt, wär nett wenn da irgendwer was hochladen könnte.
Auch fehlen 04/22 (BusyBeaver-Beweis) und 10/49 (Chomsky-0-Grammatik aus 1-Band-DTM).
Hätte jemand evtl. eine Lösung für die Präsenzaufgabe aus Blatt 8 für mich? Die “Aufwärmfragen” + Begründungen?
Keine Musterlösung , sollte sich aber lösen lassen…
Ich pack’s mal da rein: http://pad.stuve.fau.de/p/bfs1314-08-40
=> Jeder kann korrigieren, Thread bleibt etwas übersichtlicher.
1 „Gefällt mir“
Übungsaufgabe 55
Hat jemand eine Lösung für Aufgabe 55?
Mh, da war doch irgendwas. Hab Blatt11 noch hochgeladen - die Korrektur habe ich nicht mehr gefunden, deshalb bitte selber drüberschauen, ob’s sinnvoll ist.
Hat jemand Lösungen für Blatt 14? Is sowas überhaupt klausurrelevant? also dieses neue Thema mit rekursion und loop, while, goto programmen? die übungen dazu waren nämlich nich wirklich ausführlich…
Mit den +++ auf dem Blatt sollte man das einschätzen können - falls es da auch welche gibt.
Zur primitiven Rekursion hab ich was online, in der Klausur sollte man dann aber wieder die Funktionsschreibweise verwenden.
die .txt zu prim rek hab ich schon gesehn, leider hilft mir die kein Stück weiter. Die Grundfunktionen sind ja auch im Vorlesungsskript und die sind auch leicht.
Ich würde nicht nach ner Lösung für die aufgabe fragen, wenn ich nicht schon ewig dran hängen würde… Also ich rede von Aufgaben 70 und 71
Die Aufgaben haben (++)bzw.(+++) als wichtigkeit, aber keine Ahnung was mir das sagen soll…
A70:
“Zeigen Sie dass … bijektiv ist”
n-'1 ist nur für n=0,1 nicht bijektiv, n=0 kommt aber nicht vor da 2^x >= 1 und 2y+1>=1 für x,y>0
2^x ist immer Potenz von 2, 2y+1 immer ungerade/nicht teilbar durch 2, die Einzelteile sind somit teilerfremd und durch Primfaktorenzerlegung bestimmbar - Teilen bis f(x,y)/2^n ungerade ist sollte auch reichen. (Die Einzelteile sind auch bijektiv berechnet.)
Den Algo zur Primfaktorisierung von 2 bis f(x,y) überlasse ich dir, wenn du Tupel weitergeben willst nimm die Codierung aus der Vorlesung dafür.
“Ist f primitiv rek.?” ist trivial.
A71:
"Diese Rekursion entspricht offensichtlich nicht der Definition einer primitiv rekursiven Funktion, bei der nur der unmittelbar vorhergehene Funktionswert herangezogen wird." irritierte mich eben, nachdem das Ganze mittels "Einsetzen von primitiv rekursiven Funktionen" (BFS_Kap4.pdf) doch gut machbar erschien, aber offenbar ist Einsetzen der eigenen Funktion hier nicht erlaubt (muss ich meine txt noch mal drauf hin überprüfen), deshalb Codierung, beschrieben wie hier: http://formal.iti.kit.edu/~beckert/teaching/TheoretischeInformatikII-WS0708/fib-pr.pdfMeine Vorstellung von Klausurrelevanz:
“+++++” gibt’s afaik nur einmal, sollte vom Lernverhalten keinen Unterschied zu “++++” ausmachen.
“++++” betrachte ich als Aufgabentypen und Themen, von denen 2-n, in der Tendenz wohl so viel wie möglich, ggf. mit Ankreuzen und begründen.
“+++” betrachte ich als Pool von Aufgabentypen und Themen, von denen 1-n drankommen werden.
“++” könnte möglicherweise drankommen, vermutlich nicht mehr als eine Aufgabe.
“+” sind Aufgaben wie Bohrtour, BusyBeaver, Maximale Zeitbedarfs-Optimierung, die vermutlich nur vor Augen führen sollten, wie schwer einige Dinge zu berechnen sind.
1 „Gefällt mir“
Besten Dank !
Blatt 12, Aufgabe 59:
Wenn man im Zustand q’SABE ist und ein a als Eingabe bekommt, müsste man dann nicht in den Zustand q’SBE wechseln (und nicht q’SAE)?