GDI II Klausur vom Frühjahr 2007 Frage zu Aufgabe

holgman
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 175
Registriert: 15. Apr 2004 00:37

GDI II Klausur vom Frühjahr 2007 Frage zu Aufgabe

Beitrag von holgman »

Hallo,

hat jemand eine Idee oder einen Hinweis für mich, wie man am Besten bei Aufgabe 4 Theta berechnen kann.

Im Skript finde ich in Bezug auf Rekurrenzgleichungen immer nur eine Lösung für O-Notation.

Danke.

Grüße
holgman

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

ich bin da zwar auch nich so stark drin, aber vielleicht hilft dir das trotzdem:

1. Die Problemgröße feststellen (von was ist die Anzahl der Rekursionen abhängig)
bei 4 a) wäre das klar i: wenn i == 0 sind wir fertig mit der Rekusion, ansonsten rufen wir uns wieda selbst auf mit i-1

2. Dann mal schaun wie sich die Problemgröße entwickelt, im fall von 4a wird sie mit jedem aufruf um eins reduziert, d.h. wir hätten
T(1) = 1
T(n) = T(n-1) + 1

bei 4 b haben wir 2 Rekursive aufrufe, also wäre hier
T(n) = T(n-1) + T(n-1) + 1 = 2*T(n-1) + 1

bei c bin ich mir grad auch nich sicher, würde aber sagen:

T(n) = n + T(n / 2) + 1

Bin mir nich sicher ob die Iteration da einfach ignoriert wird weils ja ne Rekurrenzgleichung is

holgman
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 175
Registriert: 15. Apr 2004 00:37

Beitrag von holgman »

Danke für die Antwort.

Aber das erstellen der Rekurrenzgleichung ist ja laut Skript einigermaßen klar.
Aber im Skript wird dann gefolgert f ∈O(g).
Aber wie kann hierbei man f ∈Θ(g) bestimmen, oder resultiert das ganz einfach daraus?

Mich irritiert einfach, dass bei der Aufgabenstellung nach Θ(g) und nicht nach O(g) gefragt wird.

Grüße
holgman

neffs
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 16. Okt 2006 19:07
Kontaktdaten:

Beitrag von neffs »

ich kann mir es nur so erklären, dass sie ausschließen wollen, dass man überall \(2^{n}\) hinschreibet, was ja formal richtig wäre.

Schau mal in die 1. Übung, da sind Beispiele.

holgman
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 175
Registriert: 15. Apr 2004 00:37

Beitrag von holgman »

danke, jetzt habe ich es kapiert :)

Dutchie
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 8. Feb 2005 09:41

Beitrag von Dutchie »

Wie ist das mit dem logn zur Basis 10 und 2? Ist es die gleiche Theta-klasse, weil es die gleiche Funktion ist. Warum eigentlich?

danke, dutchie

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag von MisterD123 »

log_b(a) = log_c(a)/log_c(b)
log_c(b) ist hierbei konstant, folglich ist der logarithmus zu einer basis nur ein vielfaches des logarithmus einer anderen basis, also selbe komplexitätsklasse.

Werwolf
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 10. Sep 2004 10:25

Beitrag von Werwolf »

Ich häte da auch einige Fragen zur Klausur.
Ich mache gerade die Aufgabe 1 und weiß nicht, in wie weit die Antworten die ich gegeben hätte stimmen.

Hat jemand (oder weiß jemand) die richtigen Antworten zu den Fragen o bis t ?

Meine Antworten wären :

o) 0

p) gar nicht

r) 1 + 2 + 3 + 4 = 10

s) log_2k+1 (n)

t) Leider überhaupt keine Ahung ;)

Benutzeravatar
Maradatscha
Computerversteher
Computerversteher
Beiträge: 353
Registriert: 2. Okt 2006 18:53

Beitrag von Maradatscha »

hat die klausur jemand digital und wäre bereit sie mir zuzuschicken?

holgman
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 175
Registriert: 15. Apr 2004 00:37

Beitrag von holgman »

meine Meinung zu Aufgabe 1(verbessert bitte, falsch ich falsch liege):

o) 0
p) ich hätte jetzt gedacht 6
r) da es doch ein Trie OHNE Einwegverzweigung sein soll mst=1
s) O(log n)
t) q3 <= max(q1,q2)

sergiy_g
Neuling
Neuling
Beiträge: 7
Registriert: 24. Sep 2007 10:50

Beitrag von sergiy_g »

holgman hat geschrieben: o) 0
bei mir auch))
holgman hat geschrieben: p) ich hätte jetzt gedacht 6
ist plausibel... also im aller schlechtesten Fall hat ein knoten k+1 Soehne... und falls alle k+1 (bei uns 6) voll sind, dann muss man splitten...
ABER: wurzel als ausnahme kann z.B. genau 2 kinder haben... was wenn ich beide gefuellt habe und noch ein schluessel einfuege(splitfaktor>=3)?
Fuer solchen fall bin ich nicht sicher ob es in der Vorlesung ueberhaupt defeniert wuerde... was soll man da machen...
hat Jemand eine Idee? Oder wahrscheinlich herr Wach konnte was dazu sagen... das waere sehr gut.. danke...
holgman hat geschrieben: r) da es doch ein Trie OHNE Einwegverzweigung sein soll mst=1
Na ja falls so... dann 2... weil ((Knotenstufe+1)*4)/4... und liegen alle Schluessel auf ester stufe...
Aber ich wollte auch dazu noch fragen, ob mittlere suchtiefe fuer degital baueme defeniert wurde? ich hab mindestens es nirgendwo gefunden...

Waere es z.B. MIT Einwegverzweigungen... dann was sollen wir zaehlen, falls der Schluessel nicht im Blat(oder irgendwelchem anderen)knoten leigt sondern auf dem Pfad?

Und falls es ueberhaupt exestiert... dann noch interessantere Frage waere, was ist mit erfolglose Suche gedacht? sollte jede buchstabe aus TrieKnoten da zugezaehlt?
holgman hat geschrieben: s) O(log n)
ich hab O(nlog n)... so viel ich weiss... gibts kein SortierAlgorythmus der in logarithmische zeit arbeitet...
holgman hat geschrieben: t) q3 <= max(q1,q2)
bei mir auch)) ich hoffe, dass es auch so wirklich ist... muss mir noch die defenition von Maechtigkeit mir anschauen... weil bin nicht so sicher, dass es die Hoehe gemeint wurde...

Dutchie
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 8. Feb 2005 09:41

Beitrag von Dutchie »

was würdet ihr bei der A1 e.) antworten?
ich hätte gesagt Bubblesort gegenüber Quicksort vorziehen für kleine Eingaben n, also unter 50.???
:?:

sergiy_g
Neuling
Neuling
Beiträge: 7
Registriert: 24. Sep 2007 10:50

Beitrag von sergiy_g »

Dutchie hat geschrieben:was würdet ihr bei der A1 e.) antworten?
ich hätte gesagt Bubblesort gegenüber Quicksort vorziehen für kleine Eingaben n, also unter 50.???
:?:
ja ich auch... aber so in mehr allgemeinem Sinn... also fuer kleine Eingaben... und falls z.B. bei O-guenstigerem Algorythmus groessere konstanten stehen... so wie 1000000*logn ist natuerlich bei grossen n viel besser als n^8/100000... aber bei kleinen n umgekehrt....

Dutchie
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 8. Feb 2005 09:41

Beitrag von Dutchie »

und wie kommt man auf die Antwort bei der A1 q)?
Da wird meiner meinung nach gar nicht rotiert, sondern nur 2 mal gesplittet.

danke schon mal. :roll:

Benutzeravatar
Maradatscha
Computerversteher
Computerversteher
Beiträge: 353
Registriert: 2. Okt 2006 18:53

Beitrag von Maradatscha »

hab die klausur jetzt bekommen
bei q würde ich 4 mal rotieren
1 mal splitten und dann bei 17-20 rotieren bis im linken knoten 1-9 stehen, in der wurzel 10 und rechts 11-20

Antworten

Zurück zu „Archiv“