Friday, September 21st 2007, 7:10pm
Sunday, September 23rd 2007, 2:21am
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.
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.
igma*->Sigma* mitigma*->Sigma* mit
Sunday, September 23rd 2007, 2:24am
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 ?
Sunday, September 23rd 2007, 9:06am
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???
Monday, September 24th 2007, 12:32am
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?
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?
Monday, September 24th 2007, 8:48am
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?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, September 24th 2007, 5:31pm
Wenn es dort explizit steht, kann man doch wohl davon ausgehen, daß das stimmt, oder?
Original von Currywurst mit Pommes
Auf der THI Seite steht 13:00 genau wie für die Einzelklausur Theoretische Informatik. Stimmt das ?
Monday, September 24th 2007, 5:48pm
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.
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, September 24th 2007, 5:50pm
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.
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.
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Wednesday, September 26th 2007, 8:01am
Jeder DEA ist auch ein NEA.
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)
Wednesday, September 26th 2007, 10:24am
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)
