www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Sonstiges" - Ungleichung - liminf
Ungleichung - liminf < Sonstiges < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Ungleichung - liminf: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 17:21 Mo 28.04.2008
Autor: ski-freak

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.

        
Bezug
Ungleichung - liminf: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:20 Mi 30.04.2008
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]