Seite 1 von 1

Rekurrenzgleichung und alles was dazu gehört

Verfasst: 12. Dez 2007 20:41
von Mojito Mix
Hi,
könnt ihr die ganzen Techniken zum Lösen von Rekurrenzgleichungen? Ich hab da noch so meine Probleme...selbst das Aufstellen der Gleichung find ich nicht einfach bzw verstehs nicht so richtig... Hat jemand alternative Quellen, die das Thema genauer erklären?

Verfasst: 12. Dez 2007 21:10
von ChRiZz88
Haben wir heute in unserer Übung ein bisschen geübt.. Im Wesentlichen besteht das Aufstellen solch einer Gleichung aber auch nur aus der Überlegung, wie viele Rekursionsschritte für n = 1,2,3,4 ... etc. benötigt werden. Daraus versucht man dann eine entsprechende Gleichung der Form T(n) = T(n-1) + 1 zu finden. Was das Lösen solcher Gleichungen betrifft, glaube (hoffe) ich nicht, dass wir das in der Klausur können werden müssen...

Verfasst: 12. Dez 2007 21:48
von s!mon
Kannst dir ja auch mal in How To Design Programs Kapitel 29 anschauen. Werde ich auch noch tun..

Verfasst: 12. Dez 2007 21:53
von gismo
Ihr könnt euch auch folgenden Foliensatz aus GdI2 ansehen, der geht komplett um Komplexität und auch halbwegs verständlich:

http://www.di.informatik.tu-darmstadt.d ... nalyse.pdf

Verfasst: 12. Dez 2007 22:42
von Krümelmonster
Ich habe ein paar Fragen zu Folie 16
des Foliensatzes von GdI2.

Warum ist es der beste Fall, wenn das
c gar nicht im Array ist?

Eigentlich ist es ja der beste Fall, wenn
das c gleich an der ersten Position im Array
steht.

Ich finde den Such-Algorithmus auch nicht effizient
implementiert, da _immer_ das gesamte Array
durchlaufen wird, bevor das Ergebnis ausgegeben wird.

Verfasst: 12. Dez 2007 23:45
von n-finity
Über die Effizienz der Implementierung lässt sich streiten. Darum ging es aber auch nicht.

Wenn c nicht im Array ist, werden 4 + 4 = 8 Vergleiche durchgeführt, 4 Zugriffe aufs Array und 4 Inkrementierungen = 16 Operationen.

Wenn c gleich an erster Stelle steht, werden 17 Operationen durchgeführt. Die 16 von eben plus eine Zuweisung, dass es gefunden wurde.

Verfasst: 12. Dez 2007 23:46
von gismo
Hast schon recht, dass es eigentlich am Besten wäre, wenn c an Pos. 1 wäre, allerdings ist der Algo halt so aufgebaut, dass er immer durchläuft und in dem Fall hat er halt noch eine Zuweisung zu verarbeiten.

Bei besserer Implementierung wäre es aber so, dass Pos. 1 = best case.

Bei dieser Implementierung ist es halt der best case, wenn es gar nicht vorkommt, weil dann nur vergleiche da sind und nie zuweisungen.

Wobei der ganze Algo eh in O(n) läuft, weil ja konstante Faktoren einfach entfallen.

Verfasst: 12. Dez 2007 23:47
von Krümelmonster
Ok.

Danke für die Erklärungen.

Verfasst: 14. Dez 2007 17:51
von s!mon
Hab auch mal noch ne Frage zur Probeklausur:

Neo der Aufgabe 6 ist bei 1. folgender Aufruf richtig:

(vector 1 2 (vector))

was macht denn (vector).. also was gibt das zurück? Ist doch ein parameterloser Funktionsaufruf oder nicht?

Verfasst: 15. Dez 2007 11:07
von ChRiZz88
(vector) bezeichnet hierbei doch einen leeren Vector, also quasi das empty am Ende, oder? Steht bei der Definition von myinput..

Verfasst: 15. Dez 2007 15:10
von Krümelmonster

Code: Alles auswählen

(vector)
...bezeichnet einen leeren Vector.

Verfasst: 16. Dez 2007 22:17
von s!mon

Code: Alles auswählen

(define(fast-expt b n)
 (cond
   [(= n 0) 1]
   [(even? n)(sqr(fast-expt b (/ n 2)))]
   [else (* b (fast-expt b (- n 1)))]))
Wie genau komme ich jetzt beispielsweise auf die Rekurenzgleichung für diese Funktion?

Verfasst: 16. Dez 2007 22:19
von giftnudel
Das ist nicht so einfach, sollte eigentlich auch erst in GDI 2 drankommen