Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Wanja

Junior Schreiberling

  • "Wanja" started this thread

Posts: 150

Date of registration: Feb 4th 2003

1

Monday, September 17th 2007, 4:57pm

KvA Ü1 Aufg 1 i) Frage

Wie geht man bei der Lösung vor?

mfG Wanja

Currywurst mit Pommes

Erfahrener Schreiberling

Posts: 438

Date of registration: Oct 14th 2002

2

Monday, September 17th 2007, 5:17pm

Ich würde sagen so:

Um die Gleichheit zu beweisen, musst du zeigen, dass
1) 2^n = O(3^n)
und
2) 3^n = O(2^n)
.

1) ist gleichbedeutend mit:
Es gibt ein c, n0 Element von N, so dass für alle n>=n0 gilt: 2^n <= c * 3^n

Das ist z.B. für c = 1 und n0 = 1 erfüllt.

2)
Es gibt ein c, n0 Element von N, so dass für alle n>=n0 gilt: 3^n <= c * 2^n

Dies ist für kein c,n0 erfüllbar, da 3^n immer stärker wächst.


Also Widerspruch.




Alternativ geht glaube ich auch:

lim für (n-->Unednlich) (3^n) / (2^n) müsste eine Konstante ergeben damit die Klassen gleich sind.

This post has been edited 1 times, last edit by "Currywurst mit Pommes" (Sep 17th 2007, 5:18pm)


Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

3

Monday, September 17th 2007, 5:49pm

Genau. Wenn f \in o(g(n)), dann folgt daraus g(n) \notin O(f(n)).
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Currywurst mit Pommes

Erfahrener Schreiberling

Posts: 438

Date of registration: Oct 14th 2002

4

Monday, September 17th 2007, 6:04pm

Quoted

Original von Arne
Genau. Wenn f \in o(g(n)), dann folgt daraus g(n) \notin O(f(n)).


Die lim Variante ist also ausreichend? Dann spart man sich das mit dem c, n0.

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

5

Monday, September 17th 2007, 6:32pm

Die Argumentation über c und n0 ist hilfreich, wenn man zeigen will, das f \in O(g(n)) gilt, weil man dort dann eine Konstante und ein n0 angibt. Wenn man zeigen möchte, dass es nicht gilt, dann ist es nicht so sinnvoll zu sagen, es gibt eben kein c und n0, sodass das gelten kann (weil man da über unendliche Mengen Aussagen macht und es könnte ja dennoch vielleicht irgendein c und n0 geben...). Wenn ich jetzt zeige, dass es _echt_ schwächer wächst, also f \in o(g(n)) gilt, dann kann g ja nicht mehr in O(f(n)) sein, da es echt stärker wächst, als die O-Natation es "verkraften" tut.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Wanja

Junior Schreiberling

  • "Wanja" started this thread

Posts: 150

Date of registration: Feb 4th 2003

6

Monday, September 17th 2007, 7:38pm

ok danke so haben wir es auch gedacht
Noch eine Frage : passt zu Aufg 8 a) eine Sprache die aus dem leeren Wort besteht

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

7

Monday, September 17th 2007, 8:24pm

ja
"NP - The class of dashed hopes and idle dreams." Complexity Zoo