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 sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten 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 klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

1 Pluspunkt 0 Minuspunkte
113 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.
...