Klausurrelevante Themen aus ThI zusammengefasst (inkl. Reduktion!)

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.

Klausurrelevante Themen aus ThI zusammengefasst (inkl. Reduktion!)
Hallo,

habe die letzten Tage eine Zusammenstellung von ThI 2+3 Stoff erstellt.

Besonderes Augenmerk liegt auf der von vielen wohl gehassten und
nur schwer verständlichen Reduktion aus ThI2. Ich habe versucht,
die Reduktion so generisch und klausurrelevant, wie möglich aufzuschreiben.

Trotz sorgfältiger Ausarbeitung kann ich natürlich keine Garantie
auf Vollständigkeit (das gewiss nicht! :wink: ) und Korrektheit geben!

Noch viel Erfolg beim Lernen.

Greetz

P.S.:
Fehlerhinweise sind gerne gesehen!
Korrekturen werde ich wohl aber, wenn überhaupt vor der Klausur,
nur zusammengefasst durchführen.

Neueste Fassung immer unter:
http://wwwcip.informatik.uni-erlangen.de/~silobuet/ThI-WS06-07_silobuet.pdf

Attachment:
ThI-WS06-07_silobuet.pdf: https://fsi.cs.fau.de/unb-attachments/post_49878/ThI-WS06-07_silobuet.pdf


Am Anfang isn Fehler: nicht entscheidbar heisst net zwangslaeufig, dass es rekursiv aufzaehlbar is


Von mir auf alle Fälle schonmal ein großes Dankeschön für diese Zusammenstellung!


Ja dem kann ich mich nur anschließen. Es besteht so langsam vielleicht doch ein bischen Hoffung das Ding zu bestehen… Vielen Dank!


Danke. Ist gut zusammengefasst.


Erstmal danke an MadDy für die Zusammenfassung, das ist wirklich hilfreich.

Wenn mit „nicht entscheidbar“ akzeptierbar bzw. semi-entscheidbar gemeint ist (ist es in der Zusammenfassung ja, wenn ich mich nicht verlesen habe), dann stimmt das laut Erk/Priese schon (Beweis auf Seite 293), also es gilt: semi-entscheidbar = rekursiv aufzählbar.


Bei best-case und Quickselect steht ja O(1) mit Fragezeichen…
Müsste das nicht rein intuitiv O(n) sein?
Denn ein einziges Mal muss ich doch wohl oder übel mit partition über die Eingabeliste laufen?
Also best-case: Ich rufe einmal partition auf und mein Pivotelement steht dann glücklicherweise genau an der Stelle, die ich haben möchte >> Element gefunden. Fertig. >> O(n)
Aber O(1) ? … Kann doch gar nicht gehen? :wink:


@Flow
semi-entscheidbar = rekursiv aufzaehlbar; ist das selbe das stimmt schon.
Aber Nicht entscheibar (oder unentscheidbar) kann rekursiv aufzaehlbar sein, muss es aber net (also Mengentechnisch gibts wohl nen nicht leeren Schnitt zwischen unentscheibaren und semi-entscheidbaren Problemen)

Version 0.2.2 aktuell
Danke für die Hinweise!

Ich bin das Dokument vorhin mit Christian Riess (miniwahr, ThI2/3-Übungsleiter) durchgegangen.
Habe daraufhin ein paar Fehler ausgemerzt und teilweise zusätzliche Kommentare eingefügt.

Die hier genannten Punkte O(1)/O(n) für Best-Case von Quickselect und Entscheidbarkeitsprobleme unentscheidbar gleich/ungleich semi-entscheidbar konnte ich dabei auch mit Christian klären. → Ihr hattet in beiden Fällen Recht!

Bei Quickselect ist im besten Fall das erste Pivot-Element das gesuchte, k-grösste, Element und braucht dann n Vergleiche, bis es als k-grösstes verifiziert werden kann - wächst also linear mit der Listenlänge.

Und bei Entscheidbarkeit wird prinzipiell zwischen ‘entscheidbar’ und ‘unentscheidbar’ unterschieden. ‘unentscheidbar’ unterteilt sich dann wieder in ‘rekursiv aufzählbar’ und ‘nicht rekursiv aufzählbar’.

Bei dem Beweis der ‘Unentscheidbarkeit’ einer Sprache kann man sich also aussuchen, ob man ‘rekursiv aufzählbar’ oder ‘nicht rekursiv aufzählbar’ beweist, da beides unter ‘unentscheidbar’ fällt. Lediglich über eine Vorgabe in der Aufgabenstellung, das z.B. das ‘Halteproblem H’ auf ‘L2’ reduziert werden soll, ist diese Auswahl beschränkt - in diesem Fall müsste z.B. der erstgenannte Algorithmus in meinem Dokument verwendet werden.

Die nun aktuelle, korrigierte Version ist 0.2.2

P.S.:
Christian legt auf den Kommentar wert, dass er nix mit meiner vereinheitlichten Version der Rekursion zu tun hat! gg


und auch nix mit den ziemlich pauschalen Reduktionen :wink:

Aber MadDy ist halt Statistiker :cool:


heisst es eigentlich fuer ein rekursiv aufzaehlbares Problem, dass es fuer alle nicht akzpetierenden Eingaben nicht halten darf ? (wenn das nicht so waere wuerden naemlich alle entscheidbaren Probleme gleichzeitig rekursiv aufzaehlbar sein)


Sind sie doch auch.
Die möglichen Eingaben werden halt im “timeslice”-Modus durchgenudelt…


Hi,

du hast auf Seite 8 bei der modularen Arithmetik noch die Formel

a^{\phi(n)} kongruent 1 mod n

vergessen.

Von meiner Seite und von den anderen ThI-Begeisterten auch ein herzliches Dankeschoen fuer die Zusammenfassung!


…falls a und n teilerfremd sind. :slight_smile:

NP: Independent Set
Bin in den Uebungen noch ueber ein NP-Vollstaendiges Problem gestolpert, das relevant sein koennte:

IS (Independent Set) :=
{<G, v> | G=(V, E) ist ein ungerichteter Graph, der eine unabhaengige Menge U “Teilmenge von” V mit |U|=v enthaelt}

Werd das aber erst nach der Pruefung integrieren - jetzt geht das Loesen der Aufgaben vor ;).


es darf auch halten, genauso gut kann es jedoch passieren, dass es nicht haelt. Insofern stimmt es schon, dass entscheidbare Probleme auch rekursiv aufzaehlbar sind.


Das Independent Set ist das Gegenteil der Clique. Du kannst das eine Problem also ganz leicht auf das andere abbilden, indem du einen neuen Graphen konstruierst, bei dem du mit einem vollständigen Graph beginnst, und für jede Kante im Ursprungsgraphen die korrespondierende Kante im neuen Graphen entfernst.


@Ford:
meinst du einfach Komplementgraph erstellen und dann das Clique Problem loesen ? (bzw so haett ichs auch verstanden)


Genau.