Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 0 Minuspunkte
117 Aufrufe

 Auf Seite 333 , die Formel in letzte Zeile:tX(w) = pf (∣w∣) + tY (∣f (w)∣) + pg(∣fY(f (w))∣) habe ich Frage auf dem dritte Term.
da die Funktion tT(w) auf Seit 6 als Zeitbadarf def. Soll tY auch als Funktion von ein Eingabe Wort def.oder?Wie versteht man die  Betrag in tY steht? also tY von ein Zahl nicht einen Eingabewort. Kann das ein Schreibfehler sein? also tY(f(w)).  

PS:die folgende Beweiseschritt haben wir die  Abschätzung auch auf dieser Basis. und bis zum letzt Schritt auf die letzte Formel auf Seite 335 haben wir nun tY als Polynom angenommen. Wenn es echt ein Fehler ist ,werde die Zwischenschritten auch ein Problem. 

Es wäre hilfreich wenn jemand einmal checken könnte.
Vielen Dank


 
 
in Kapitel 7 von ueexe ueexe Lernwillige(r) (170 Punkte)  
0 0
Ich werde es überprüfen, bin heute allerdings mit der Bonusklausur beschäftigt. Auf den ersten Blick denke ich, dass es $t_X(|w|)$ vor dem Gleichzeichen heißen müsste und die Funktionen $t_X, t_Y$ nicht auf Wörtern sondern auf Wortlängen, also Zahlen arbeiten. Es ist also irgendwo ein Fehler, aber ich denke ein kleiner.

1 Eine Antwort

1 Pluspunkt 0 Minuspunkte
Sie haben da leider (für uns - aber gut für Sie, dass Sie so ein scharfes Auge haben!) einen kleinen Fehler entdeckt. In der Formel soll es nur um Wortlängen gehen, daher müsste es $t_X(|w|)$ heißen. Aber ich gebe zu, dass zusätzlich die Bezeichnungen irreführend sind, denn $t$ hatten wir zuvor für den Zeitbedarf einer Turingmaschine genutzt, und dieser war auf Wörtern, nicht Wortlängen definiert. Besser wäre also ein anderer Variablenname gewesen.

Sie müssen sich mit dieser Berechnung aber gar nicht unnötig lange aufhalten - es geht nur darum zu zeigen, dass die Lösung eines Problems über den Umweg einer Polynomialzeitreduktion nicht mehr als um einen polynomiellen Faktor länger dauern kann als die Lösung des Problems, auf das reduziert wurde. Das ist ja nun nicht so schwierig einzusehen - vielleicht versuchen Sie das einfach mal selbst herzuleiten...

Diese Stelle im Lehrbuch finde ich gerade nicht mehr so ganz gelungen - bei einer Neuauflage werden wir das schöner machen :-)

Danke, dass Sie uns auf die Ungenauigkeit aufmerksam gemacht haben!
von Dozent (10.1m Punkte)  
1 0
Vielen Dank für Ihre Antwort.  Naja, ich bin nicht sicher ob ich  "bis zum polynomiale Faktoren" richtig verstehe, und versuch die genaue Beweisen zu schauen. Dann bin gesperrt bei die t Funktion . Jetzt ist es ganz klar!
1 0
Damit meine ich nur, dass wir bei der Lösung über die Reduktion in der Klasse $P$ bleiben, wenn das Problem, auf das reduziert wurde, ebenfalls in $P$ liegt. Wir bleiben also polynomiell und werden nicht plötzlich exponentiell oder so.
...