Ungleichung - liminf < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei t eine berechenbare, totale Funktion mit der Eigenschaft [mm] \liminf_{n\rightarrow\infty}\bruch{t(n)}{n} > 1 [/mm] und sei c > 1.
Man bestimme m so, dass [mm] n + \bruch{1}{m}n + c\bruch{1}{m}t(n) \le t(n) [/mm] |
Hallo,
ich komme bei obiger Ungleichung einfach nicht auf das m (in Abhängigkeit von c - alles andere macht ja kaum Sinn)!
Der Hintergrund der Aufgabe: Diese Ungleichung stammt aus einem Beweis zur Zeitabschätzung von Turingmaschinen, und m ist die Blocklänge, die gewählt werden muss, damit man eine Turingmaschine erhält, die schneller rechnet als die Ursprüngliche. Man zeigt also sowas wie:
DTIME(t) = DTIME(ct) , wobei DTIME(t) die Menge aller Sprachen ist, die von einer Turingmaschine in Zeit <= t entschieden werden können.
Klar ist, dass man folgendes erhalten muss: Wenn t(n) = n gilt, dann muss m gegen unendlich streben. Das liegt ja daran, dass ich eine Turingmaschine niemals auf Linearzeit runterbrechen kann. D.h. der Satz gilt für t(n) = n nicht, was auch verständlich ist. Nur für die Funktionen t, welche die obige Bedingung erfüllen, muss eine endlichere Blocklänge rauskommen, nur wie macht man das genau? Ich kann die Gleichung natürlich soweit umformen, dass ich folgendes erhalte:
[mm] m \ge \bruch{1+c\bruch{t(n)}{n}}{\bruch{t(n)}{n}-1} [/mm]
Nur ist das irgendwie null aussagekräftig :(
Danke
Gruß, ski-freak
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Mi 30.04.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
