3. Informatik Übungsaufgabe

Informatik Übungsaufgabe

  • R

    Hi,

    folgende Aufgabe stammt aus einer Vorlesung "Einführung in die Informatik", sie gehört zur Komplexitätstheorie.

    Gegeben sind 2 Funktionen f,g. Wir definieren eine Ordnung auf dieses beiden Funktionen wenn es ein n gibt ab dem gilt f(n)<g(n).

    1. Beweisen Sie (analytisch) dass log2n < n1/2 gilt!
    2. Beweisen Sie (durch vollständige Induktion) dass 2n < n! gilt!

    Also erstmal gilt diese Beziehung erst ab einem bestimmten n. Ich habe leider nicht wirklich einen Ansatz wie eine solche Aufgabe zu lösen ist, was ist z.B. ein analytischder Beweis? Vollständige Induktion kenn ich von der Summenformel, aber wie wende ich sie hier an?

    Als ich in meinen Büchern zu Komplexitätstheorie nachgeschaut habe habe ich auch nichts dergleichen finden können.

    0
  • E

    zur aufgabe 2 hab ich grad mal in den alten unterlagen nachgeschaut
    und ein paar brocken gefunden vielleicht hilfts dir:

    voraussetzung: n! > 2^n, fuer n >= 4
behauptung: (n+1)! > 2^(n+1)

beweis:
(n+1)! = (n+1)n!
-> (n+1)n! > 2^n (n+1) 
(nach induktions voraussetzung: n! > 2^n mit konstantem faktor (n+1) multipiziert)

(n+1)n! > 2^n (n+1)
da n nach voraussetzung >= 4 ist n+1 >= 4

-> 2^n(n+1) > 2^n * 2 (gilt da n+1 >= 4)
-> (n+1)n! > 2^n * 2 (=2^(n+1))
    0
  • R

    Danke! Denke hab es soweit verstanden.

    Aber Aufgabe 1 bereitet mir noch grössere Schwierigkeiten da ich noch nichtmal weiß wie so ein analytischer Beweis aussieht.

    0
  • D

    Real_PsychoDAD schrieb:

    Aber Aufgabe 1 bereitet mir noch grössere Schwierigkeiten da ich noch nichtmal weiß wie so ein analytischer Beweis aussieht.

    Funktion f(n) = ld(n) - sqrt(n) aufstellen, und mit mitteln der Kurvendiskussion herausfinden, wo f(n) < 0 ist?

    0
  • J

    Jo, vermutlich.
    Es genügt wohl den Punkt zu finden, ab dem die Kurve 0 ist und dann vielleicht rauszufinden, daß die Ableitung ab dort immer negativ ist und die Differenz damit immer weiter fällt.

    0
  • R

    Achso, danke, jetzt habe ich immerhin einen Ansatz.

    Aber mal noch ne Frage, analytisch heisst also immer mit Funktionen,Ableitungen und was noch zu ner Kurvendiskussion gehört?

    Was wäre ein algebraischer Beweis(falls es das überhaupt gibt)?

    0
Anmelden zum Antworten