This post has been edited 2 times, last edit by "Jojo" (Sep 21st 2007, 6:09pm)
Quoted
Original von Joachim
Andersrum ist es vielleicht einfacher: Mache Dir zunächst klar, warum kein NP-vollständiges Problem (also z. B. SAT) auf Sigma^* und \emptyset reduziert werden kann.Quoted
Original von Arne
Tipp: zeig erstmal, dass alle anderen Sprachen (außer Sigma* und Emptyset) NP-hart sind. Dann überleg, warum das auf die beiden nicht zutrifft.
Quoted
Original von Jojo
@Currywurst mit Pommes : ich finde dass die beiden Algor. dasselbe machen.
Hat jemand irgendeinen Vorschlag fuer Aufg 35 ? Wie man PART auf Bin-Pack reduziert ?
Quoted
Original von Paulus
"Der Suchvorgang kann in endlicher Zeit geschehen, da die Anzahl der Wörter in A endlich ist."
Mir ist es nicht klar: warum ist A endlich???
Trainee
Date of registration: Oct 23rd 2005
Location: Ehemals Preußisches Gebiet
Occupation: Ehemals Studentenquäler. I'm finally done with school!
Senior Schreiberling
Date of registration: Feb 3rd 2003
Location: Ex-Europameisterland
Occupation: 4TheScience
Quoted
Original von Dot
Also ich hab da auch mal 2 Fragen.
-Bei Aufgabe 41, warum nimmt man da die Summe der größe der Objekte als Maßfunktion und als Goal die Minimierung? Ich würde das umgekehrt machen, die Summe der Objekte als Maß und Maximierung als Goal, bei Knapsack will man doch möglichst viele Objekte in den Sack packen und dabei nich ein bestimmtes Gewicht überschreiten oder?
Quoted
Original von Dot
-Bei Aufgabe 39, nimmt man da die Umbenennungsfunktion als Zertifikat? Und wenn ja, beim Algorithmus, muss ich da jede einzelne Zelle von G_1 mit G_2 vergleichen? Also in der Form:
--Überprüfe jede Zelle in G_1 mit G_2 (f(i),f(j)), wenn isomorpher Teilgraph in G_2 mit |E_2|´>=k, akzeptiere
Geht das so?
Quoted
Bei Aufgabe 41, warum nimmt man da die Summe der größe der Objekte als Maßfunktion und als Goal die Minimierung? Ich würde das umgekehrt machen, die Summe der Objekte als Maß und Maximierung als Goal, bei Knapsack will man doch möglichst viele Objekte in den Sack packen und dabei nich ein bestimmtes Gewicht überschreiten oder?
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Wenn es dort explizit steht, kann man doch wohl davon ausgehen, daß das stimmt, oder?Quoted
Original von Currywurst mit Pommes
Auf der THI Seite steht 13:00 genau wie für die Einzelklausur Theoretische Informatik. Stimmt das ?
Quoted
Original von Joachim
Wäre ja auch nicht besonders sinnvoll, die KvA-Leute später kommen zu lassen. Das erzeugt nur unnötige Unruhe (Platz suchen, Sachen rauslegen, ...) im Hörsaal.
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Das ist beim ThI anders. Schau Dir mal die alten Klausuren an, die auf der Website des ThI zu finden sind. Die Kombiklausur ist hier tatsächlich eine solche und nicht nur die Aneinanderreihung von zwei Einzelklausuren.Quoted
Original von Currywurst mit Pommes
Naja, ich kenn das bei Doppelklausuren bis lang nur so, dass nacheinander geschrieben wird und in der Mitte Pause ist.
Senior Schreiberling
Date of registration: Feb 3rd 2003
Location: Ex-Europameisterland
Occupation: 4TheScience
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Jeder DEA ist auch ein NEA.Quoted
Original von aliaatreides
kann man eine regulaere Sprache direkt von einem NEA ableiten, oder muss man den DEA erstmal in einen NEA umwandeln?
This post has been edited 1 times, last edit by "Joachim" (Sep 26th 2007, 8:01am)
Quoted
Original von aliaatreides
bei Widerholung hab ich gerade gesehen (GThI, Uebung 7, A1):
kann man eine regulaere Sprache direkt von einem NEA ableiten, oder muss man den DEA erstmal in einen NEA umwandeln?
This post has been edited 1 times, last edit by "Neutrino" (Sep 26th 2007, 10:25am)