Rekurrenzgleichung und alles was dazu gehört

Mojito Mix
DON'T PANIC
Beiträge: 42
Registriert: 10. Okt 2007 18:28

Rekurrenzgleichung und alles was dazu gehört

Beitrag von Mojito Mix » 12. Dez 2007 20:41

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?

ChRiZz88
Mausschubser
Mausschubser
Beiträge: 87
Registriert: 7. Nov 2007 18:09
Kontaktdaten:

Beitrag von ChRiZz88 » 12. Dez 2007 21:10

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...

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Beitrag von s!mon » 12. Dez 2007 21:48

Kannst dir ja auch mal in How To Design Programs Kapitel 29 anschauen. Werde ich auch noch tun..

gismo
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 10. Jan 2007 17:06
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von gismo » 12. Dez 2007 21:53

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

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Beitrag von Krümelmonster » 12. Dez 2007 22:42

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.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

n-finity
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 101
Registriert: 22. Dez 2006 15:38
Kontaktdaten:

Beitrag von n-finity » 12. Dez 2007 23:45

Ü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.

gismo
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 10. Jan 2007 17:06
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von gismo » 12. Dez 2007 23:46

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.

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Beitrag von Krümelmonster » 12. Dez 2007 23:47

Ok.

Danke für die Erklärungen.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Beitrag von s!mon » 14. Dez 2007 17:51

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?

ChRiZz88
Mausschubser
Mausschubser
Beiträge: 87
Registriert: 7. Nov 2007 18:09
Kontaktdaten:

Beitrag von ChRiZz88 » 15. Dez 2007 11:07

(vector) bezeichnet hierbei doch einen leeren Vector, also quasi das empty am Ende, oder? Steht bei der Definition von myinput..

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Beitrag von Krümelmonster » 15. Dez 2007 15:10

Code: Alles auswählen

(vector)
...bezeichnet einen leeren Vector.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Benutzeravatar
s!mon
Computerversteher
Computerversteher
Beiträge: 373
Registriert: 20. Okt 2007 18:24
Wohnort: Höchst i. Odw

Beitrag von s!mon » 16. Dez 2007 22:17

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?

Benutzeravatar
giftnudel
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 112
Registriert: 3. Mai 2005 11:26

Beitrag von giftnudel » 16. Dez 2007 22:19

Das ist nicht so einfach, sollte eigentlich auch erst in GDI 2 drankommen

Antworten

Zurück zu „Archiv“