Informatiker Board | Suchergebnis

Informatiker Board » Suche » Suchergebnis

» Hallo Gast [Anmelden|Registrieren]

Zeige Beiträge 1 bis 9 von 9 Treffern

Autor

Beitrag

Thema: rekurrenzgleichung beweisen

xole_X

Antworten:	7
Hits:	9.282

29.04.2008 18:10

Forum: Theoretische Informatik

[quote]Original von Tobias
Deshalb schrieb ich ja schon, dass das Mastertheorem beweist, dass $[latex]T(n) \in \Theta(n)[/latex]$
[quote]

kann ich sagen, die aussage stimmt, da $[latex]T(n) \in \Theta(n) <= O(n*lg(n))[/latex]$

Thema: rekurrenzgleichung beweisen

xole_X

Antworten:	7
Hits:	9.282

29.04.2008 16:32

Forum: Theoretische Informatik

Zitat:

Original von Tobias

Dein Beweis benutzt Induktion über die Rekursionstiefe und ist auch gangbar, denke ich. Hier musst du dich aber etwas deutlicher an dem Vergehen der Induktion orientieren. Es fehlt z.B. der Induktionsanfang. Es ist dann nicht wichtig, ab welchem $[latex]n \geq n_0[/latex]$ dein Beweis gilt, sondern nur dass es irgendwann gilt. Dafür kannst du z.B. das +n am Ende auch durch $[latex]n \leq n\cdot \log n[/latex]$ abschätzen, dann ausklammern und die Konstante erhöhen:

$[latex]T(n) \leq \ldots \leq c \cdot n \lg(n) + n \leq c \cdot n \lg(n) + n \lg(n) = (c+1) n \cdot\lg(n) = c' \cdot n \cdot \lg(n)[/latex]$

wenn ich ehrlich bin, ich blick da noch net so 100% durch.
wie leite ich denn jetzt mein induktionsanfang her aus deiner abschätzung?
http://de.wikipedia.org/wiki/Substitutionsmethode
hab mich bisschen hierran orientiert, weil wir bisher nur mastertheorem und substitutionsmethode hatten. das mastertheorem aber nur so als absicherung und nicht als alleiniger beweis.
bis punkt4 beispiel1 in wikipedia bin ich mittlerweile gekommen, aber ich verstehe 5. Induktion nicht so ganz.wie kommen sie da auf den induktionsanfang n=2 und wieso ist da T(2) = 2 unglücklich

auch das mastertheorem scheint nicht so gut zu funktionieren:
damit n*log(n) gilt muss f(n)€ O(n^(lg1))
f(n) ist jedoch n, aber n ist nicht element von O(n^(lg1))

Thema: rekurrenzgleichung beweisen

xole_X

Antworten:	7
Hits:	9.282

29.04.2008 15:28

Forum: Theoretische Informatik

ja kenn das mastertheorem, aber was mach ich denn mit der 10 in T(n) = T(0.5n + 10)

Das Mastertheorem ist doch nur für Gleichungen der Form:

T(n) = a*T(n/b)+f(n)

a ist bei meiner gleichung : a=1 aber was ist b?

Thema: rekurrenzgleichung beweisen

xole_X

Antworten:	7
Hits:	9.282

rekurrenzgleichung beweisen 28.04.2008 22:43

Forum: Theoretische Informatik

Ich soll zeigen, dass
T(n) = T(0.5n + 10) + n in O(n*lg(n)) liegt...

wie mach ich das am besten?

ich habs folgender maßen probiert:

T(n)<=c* (0.5n+10)*lg(0.5n+10)+n

jetzt nehm ich als abschätzung 0.5n+10<=n gilt für alle n>= 20

<= c*(0.5n+10)*lg(n)+n<=c*n*lg(n) ----> aber ab welchem n gilt das hier bei c=1 zB...ab ca 300 hab am graph abgelesen, aber wie gesagt, abgelesen und nicht errechnet...naja das waren jetzt so meine erfolglosen versuche...hoffe mir kann jemand helfen

Thema: Komplexizität - O Notation

xole_X

Antworten:	2
Hits:	5.135

Komplexizität - O Notation 22.04.2008 20:05

Forum: Theoretische Informatik

Hallo
ich muss von einem code die komplexizität bestimmen, was ich auch bereits getan hab...mein Problem liegt eher darin, wie man das zeug sauber aufschreibt. den code darf ich hier leider net posten, aber hier einfach nur ein anderes beispiel (konsumiert 2 gleichgroße nxn matrizen und addiert diese)

1. public sum(int a[][],int b[][]){
2. int reihe = a.length;
3. int zeile = a[0].length;
4. int[][] summatrix = new int[reihe][zeile];
5.
6. for(int i = 0; i<reihe; i++)
7. for(int j = 0; j<zeile; j++)
8. summatrix[i][j] = a[i][j]+b[i][j]
9.
10. return summatrix;
11. }

ich hätte jetzt einfach bei meinem code gesagt:
zeile2: c1
zeile3: c2
zeile4: c3
zeile6: n
zeile7: n
zeile8: c4
zeile10: c5

T(n) = c1+c2+c3+n*(n+c4)+c5 € O(n²)

wie schreib ich das aber alles sauber auf? schreibt man da überhaupt für Konstante Aufrufe c hin oder schreib ich da ne 1 oder T(c1) oder T(1)...

Thema: Landau - ThetaNotation

xole_X

Antworten:	5
Hits:	6.485

20.04.2008 23:30

Forum: Theoretische Informatik

Zitat:

Original von Tobias
Mögliche Wahl ist z.B. $[latex]n \geq \max\{2(\log_2(c)+1), m \}[/latex]$

ich verstehe den rechten teil nicht so ganz...was soll das sein? eine methode, die das maximum zwischen 2log(c) +2 und m berechnet?

Thema: Landau - ThetaNotation

xole_X

Antworten:	5
Hits:	6.485

20.04.2008 22:00

Forum: Theoretische Informatik

Zitat:

Original von Tobias
Nun widerlegt man leicht $[latex]2^n \in \mathcal{O}(2^{\frac{n}{2}})[/latex]$ indem man zeigt, dass es kein c und kein m gibt, so dass gilt:
$[latex]2^n \leq c \cdot 2^{\frac{n}{2}} \quad \forall n \geq m[/latex]$

$[latex]\frac{2^n}{2^{\frac{n}{2}} } \leq c \quad \forall n \geq m[/latex]$

$[latex]2^{\frac{n}{2}} \leq c \quad \forall n \geq m[/latex]$

ein solcher Index n >m kann net existieren, da c eine feste konstante ist. aber wie beweis ich das?

Thema: Landau - ThetaNotation

xole_X

Antworten:	5
Hits:	6.485

Landau - ThetaNotation 20.04.2008 19:26

Forum: Theoretische Informatik

Hallo zuerst mal an alle großes Grinsen

ich soll folgendes beweisen bzw widerlegen: $[latex]2^{n} = \Theta(2^{\frac{n}{2} } )[/latex]$

Ich hab mir dazu folgendes überlegt: Damit ˜ - Notation stimmt, muss ja g(n)<=f(n)<=g(n) gelten. (f(n) = 2^n und g(n) 2^(0.5n))

Damit f(n) und g(n) gleichschnell wachsen, muss ja f(n)/g(n) = 1 für n-->inf

$[latex]\lim_{n \to \infty }\frac{2^n}{2^{n/2}} = \lim_{n \to \infty }{2^{n-n/2}} = \lim_{n \to \infty }2^{n/2} = \infty [/latex]$

die aussage ist also falsch? genügt dies als beweis soweit?

Thema: Scheme hilfe - cond

xole_X

Antworten:	0
Hits:	3.715

Scheme hilfe - cond 23.10.2007 21:56

Forum: Praktische Informatik

hi
ich wollte mit scheme gucken, was so mit (cond...) geht.

Das ganze funktioniert aber nicht so wie ich es will:

(define (eingabe l)
(cond
[(= l 10) (+ l l)]
[(= l 20) 'gut]
[(symbol=? l 'hallo) 'hi]
[else 'bye]))

wenn ich in der Laufzeit (eingabe 10) eingebe...dann zeigts mir wie gewünscht 20, bei (eingabe 20) auch wie gewünscht 'gut

Jedoch funktioniert meine dritte clause nicht. Bei (eingabe 'hallo)
kommt diese Fehlermeldun

=: expects type <number> as 1st argument, given: 'hallo; other arguments were: 10
dabei wird die zeile [(= l 10) (+ l l)] markiert.
wenn ich [(symbol=? l 'hallo) 'hi] als erste clause stehen habe, dann funktionierts, und ich bekomm 'hi raus, aber der rest geht dann nicht.
warum ist das so?

Zeige Beiträge 1 bis 9 von 9 Treffern