Nachhilfe BFS

[system]

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.

[if24emun]

Nachhilfe BFS
Hallo,

Ich bin Masterstudent und suche nach jemanden der mir in BFS Reduktionen, NFA to Reg erklären kann.
Natürlich würde die Person dafür bezahlt werden.

Danke,
Choro

[zge]

---

Ich hatte auch zunächst Schwierigkeiten Reduktion zu verstehen, habe aber meine Notizen dazu aufgeschrieben die mir geholfen haben. Vielleicht hilft dir das auch: https://wwwcip.cs.fau.de/~oj14ozun/notizen/reduktion.html, wenn es irgendwie verständlich ist.

[Jonas_S]

---

@zge

Ich hatte auch zunächst Schwierigkeiten Reduktion zu verstehen, habe aber meine Notizen dazu aufgeschrieben die mir geholfen haben. Vielleicht hilft dir das auch: Kommentare zur Reduktion, wenn es irgendwie verständlich ist.

Ich hab deine Notizen nur kurz überflogen, habe aber einige Fehler gefunden:

• Wenn in der Vorlesung von „Problemen“ gesprochen wird ist die Sprache selbst das Problem nicht die Frage x \in L.
• Reduktionsfunktionen müssen nicht injektiv sein. (Das Wort injektiv kommt kein einziges Mal im Skript vor)
• In deinem Kapitel 2, bei der Definition von der Sprache muss das x durch das w getauscht werden.
• Deine Definiton von rekursiver Aufzählbarkeit ist falsch. Eine TM muss halten für Wörter aus der Sprache, es ist egal was bei anderen Wörtern passiert.
• Die Def vom initial Halteproblem: unbedingt einen ganzen Satz draus machen, also zB „die gestartet mit leerem Band hält“
• Deine Beispielreduktion H auf H_epsilon ist unsauber, am besten einfach an den Reduktionen aus der Vorlesung orientieren

[yq53ykyr]

---

@zge

Ich hatte auch zunächst Schwierigkeiten Reduktion zu verstehen, habe aber meine Notizen dazu aufgeschrieben die mir geholfen haben. Vielleicht hilft dir das auch: Kommentare zur Reduktion, wenn es irgendwie verständlich ist.

Ich bin da vorhin auch kurz drübergegangen und hab noch eine Ungenauigkeit im letzten Punkt gefunden. Du schreibst:

@https://wwwcip.cs.fau.de/~oj14ozun/notizen/reduktion.html

Beachtet das dieses nicht bedeutet das [m]Anf_Ungleich_End[/m] in NP ist. Die Tatsache das einfache Probleme, komplex formuliert werden können ist ein gesellschaftliches, nicht mathematisches. Das obige Problem kann auch ohne Reduktion (wie auch alle anderen Probleme in NP) gelöst werden:

bool Anf_Ungleich_End(char *w) {
     char *first = strtok(w, '#');
     char *last, *next;
     while (next = strtok(NULL, '#'))
          last = next;
     return !!strcmp(first, last);
}

sollte in O(n), ohne Umweg über SAT auf die gleiche Lösung kommen.

Das Problem ist hierbei dein Berechnungsmodell. In der Klausur, wenn die Frage kommt, ob [m]Anf_Ungleich_End[/m] ein Element von P ist, sollte man mittels deterministischen 1-Band-TM argumentieren. Analog geht auch über RAM oder Mehrband-TM. In Fällen, in denen man Algorithmen für andere Berechnungsmodelle angeben soll, muss man immer noch die Konvertierung mitberücksichtigen. Sprich für RAM-Simulation durch eine det. 3-Band-TM in O(t(n)³) (Satz 1.10) und dann s(n)-platzbeschränkte det. k-Band-TM in det. 1-Band-TM in O(t(n) * s(n)) (Satz 1.7).

Dein Programm oben arbeitet aber mit einem anderen Befehlssatz als die in der Vorlesung definierte RAM und sollte deswegen nicht als Begründung in Klausur/Hausaufgaben verwendet werden.
Generell könnte man das ganze durch eine det. 2-Band-TM lösen, welche die Zeichen bis zum ersten ‚#‘ auf das zweite Band schreibt, dann auf dem zweiten Band zum Beginn des Wortes geht, auf dem ersten Band bis zum Ende des Bands und danach zum letzten ‚#‘ geht und jetzt Zeichen für Zeichen vergleicht. Dann kommt man auch darauf, dass die det. 2-Band-TM linear platzbeschränkt ist und unsere Simulation in O(n²) laufen sollte. Damit ist das Problem dann in P.

Für das generelle Verständnis ist ein solcher Ansatz sicherlich sinnvoll, aber gerade in Klausurvorbereitungen finde ich es dann doch eher verwirrend. Gerade weil in Klausuren dafür sicherlich Punkte abgezogen werden können.

[Inf2017]

---

Braucht man bei BFS als Masterauflage nicht nur eine 4,0, also 1/3 der Punkte? Ich würde da gar nicht erst versuchen Dinge tiefer zu verstehen oder Geld für Nachhilfe aus dem Fenster zu werfen.

[Jegon]

---

@Jonas S

• Deine Definiton von rekursiver Aufzählbarkeit ist falsch. Eine TM muss halten für Wörter aus der Sprache, es ist egal was bei anderen Wörtern passiert.

Das ist leider nicht ganz richtig.

In der Vorlesung wird erst (vgl. Def. 1.3) folgende Definition von rekursiver Aufzählbarkeit verwendet:
Es muss zu einer rekursiv Aufzählbaren Sprache eine TM geben, die genau mit den Wörtern der Sprache als Eingabe gestartet akzeptierend hält (die TM darf gestartet mit allen anderen Wörtern als Eingabe also nicht akzeptierend halten oder gar nicht halten, aber es ist nicht egal was passiert).

Später (vgl. Def 1.18) wird die Definition von rekursiver Aufzählbarkeit etwas abgeändert:
Es muss zu einer rekursiv Aufzählbaren Sprache eine TM geben, die genau mit den Wörtern der Sprache als Eingabe gestartet hält und am Danach nur eine „1“ auf dem Band steht und gestartet mit allen anderen Wörtern als Eingabe nicht hält.

Dass diese beiden Definition von rekursiver Aufzählbarkeit jedoch die selbe Menge an Sprachen beschreiben wird deutlich, wenn man die TM aus der ersten Definition nimmt und so erweitert, dass im Falle eines eigentlich nicht akzeptierenden Haltens eine Endlosschleife ausgeführt wird und im Falle eines akzeptierenden Haltens das Band vorher noch aufgeräumt wird und eine „1“ auf das Band geschrieben wird.

[Marcel_Inf]

---

@Inf2017

Braucht man bei BFS als Masterauflage nicht nur eine 4,0, also 1/3 der Punkte? Ich würde da gar nicht erst versuchen Dinge tiefer zu verstehen oder Geld für Nachhilfe aus dem Fenster zu werfen.

Taucht das im Transcript of Records später auf?

[zge]

---

@yq53ykyr

@zge

Ich hatte auch zunächst Schwierigkeiten Reduktion zu verstehen, habe aber meine Notizen dazu aufgeschrieben die mir geholfen haben. Vielleicht hilft dir das auch: Kommentare zur Reduktion, wenn es irgendwie verständlich ist.

Ich bin da vorhin auch kurz drübergegangen und hab noch eine Ungenauigkeit im letzten Punkt gefunden. Du schreibst: …

Ich sollte die Fehler ausbessern, das ich alles ein paar Tage vor meiner Klausur geschrieben worden. Was mich und andere verwirrt hat war wieso ein einfaches Problem auf ein schwierigeres „Reduziert“ wird. Ob ich hier C oder eine andere Sprache benutze um zu zeigen, dass es nur die Aufgabenstellung ist die das fordert, und nicht das Problem an sich, ist an sich egal.

Aber ja, es bringt immer mehr Seine eigenen Notizen zu machen, als die von anderen zu lesen.

[Inf2017]

---

[quote=Marcel[Inf]]Taucht das im Transcript of Records später auf?
[/quote]Bei genug Punkte für die 4,0 wurde bei den Leuten mit Masterauflage bei uns damals nicht weiterkorrigiert.

[yq53ykyr]

---

@Marcel[Inf

Taucht das im Transcript of Records später auf?

M.W.n. nur als + oder - unter dem Punkt „88888 Auflage (lt. Zulassungsbescheid zum Masterstudium)“. Sprich ohne Note und nur als „Bestanden/Nicht Bestanden“. Deswegen keine weitere Korrektur, deswegen könnte man auch ohne viel Verständnis an die Klausur rangehen.

Ob man diesen Weg wählen will, muss jeder für sich selbst entscheiden. Aber an sich ist die Materie sicherlich in gewisserweise relevant in weiterführenden Veranstaltungen, wenn über P-NP-Probleme oder PSPACE gesprochen wird. Entscheidet man sich aber für eine „reine 4,0“, wie Inf2017 das vorgeschlagen hat, hat das später keinerlei Konsequenzen IIRC.

[yq53ykyr]

---

@zge

Ich sollte die Fehler ausbessern, das ich alles ein paar Tage vor meiner Klausur geschrieben worden. Was mich und andere verwirrt hat war wieso ein einfaches Problem auf ein schwierigeres „Reduziert“ wird. Ob ich hier C oder eine andere Sprache benutze um zu zeigen, dass es nur die Aufgabenstellung ist die das fordert, und nicht das Problem an sich, ist an sich egal.

Nun ja, du möchtest meistens kein schwieriges Problem haben, was du in der Klausur unter Stress versuchen musst in Polynomzeit zu reduzieren. Weil in dem Moment, in dem ein „Vernunftsansatz“ bei der Reduktion nicht mehr wirklich funktioniert, sondern man ausgefallene Kodierungen und Varianten braucht, damit die Berechnung der Polynomfunktion (bzw. eigentlich dessen Ergebnis) in polynomieller Zeit geht, wird es wahrscheinlich schwieriger in der Klausur immer noch alles richtig zu machen und auf die Sonderfälle und Formulierungen aufzupassen.

Sicherlich kein schönes Beispiel für Polynomzeitreduktion und deren Anwendung, weswegen ich auch gemeint habe, dass die Verwendung von C (oder anderen Hochsprachen) zum grundlegenden Verständnis passt, aber in der Klausur und bei Übungsabgaben nicht als Begründung für eine Mitgliedschaft in P verwendet werden sollte.

[Marcel_Inf]

---

@yq53ykyr

Mitgliedschaft in P verwendet werden sollte.

SAT so: hey, die in P grenzen mich aus! Die sagen zwar nicht offiziell, dass ich kein Mitglied bin, aber ein vollwertiges Mitglied scheine ich auch nicht zu sein.