ΒΟΗΘΕΙΑ Σε Αναδρομικές Συναρτήσεις !!!

[chriss]

Τι συνάγετε για την κλειστή μορφή της όπου και επιπλέον:

a)
και
β)

το β μου είπαν οτι λύνετε με master theorem αλλά δε μπορώ να το εφαρμόσω. Το α δε γνωρίζω όποιος μπορεί ας βοηθήσει....Ευχαριστώ

[chris_gatos]

Kάτι δεν εκφράζεις σωστά αλλά πιστεύω πως δεν αντιγράφεις και σωστά.
Μα γίνεται ακολουθία με δείκτη n/4;;

[chriss]

και εμένα δε μου φαίνεται να στέκει αλλά αυτό θέλει...εχω αντιγράψει σωστά.Τι να σου πω....

[Mihalis_Lambrou]

Τι συνάγετε για την κλειστή μορφή της όπου και επιπλέον:

a)
και
β)

το β μου είπαν οτι λύνετε με master theorem αλλά δε μπορώ να το εφαρμόσω. Το α δε γνωρίζω όποιος μπορεί ας βοηθήσει....Ευχαριστώ

To β) έχει πρόβλημα.

Για το α) υπόδειξη:

Γράφουμε οπότε η δοθείσα γίνεται

και άρα




που λύνεται με στάνταρ μεθόδους.

Φιλικά (και βιαστικά)

Μιχάλης Λάμπρου

[antonis_math]

Απο όσο κατάλαβα, αυτά που έχεις να κάνεις αφορούν χρόνο εκτέλεσης αναδρομικών αλγορίθμων. Για το β έχεις οτι ο αλγόριθμος είναι γραμμικός.
Αν κάνω λάθος ας με διορθώσεις, αλλα το ν/4 όντως δεν μπορεί να έχει άλλο νόημα.
ίσως το γράφει T(n)=3T(n/4)+n

[chriss]

βασικά όπως και να την γράψεις το ίδιο δεν είναι? ειναι το ίδιο με το Τ(n).
Μας το δίνει όπως το έχω γράψει αλλα μας είπε οτι είναι το αντίστοιχο Τ(n) σε παλιότερες ασκήσεις. οπότε όπως και να το πεις είναι το ίδιο

[antonis_math]

Τελικά ελπίζω να βοηθήθηκες. Για το β με master theorem όπως σου είπαν

[chriss]

βασικά εκεί έχω πρόβλημα...δεν ξέρω αν κάνω λάθος στις πράξεις αλλά μου βγαίνει οτι δεν ανήκει σε καμία απο τις 3 περιπτώσεις του master theorem.

[antonis_math]

Επειδη lg3/ lg4 <1 , όπου 1 εκθέτης του n, θα είναι Τ(n) = Θ(n)

[chriss]

οκ ευχαριστώ πολύ!!!!!

[Mihalis_Lambrou]

Επειδη lg3/ lg4 <1 , όπου 1 εκθέτης του n, θα είναι Τ(n) = Θ(n)

Αντώνη προσοχή, δεν ισχύει .

Πάντως η δοθείσα ανανδρομική εμπίπτει στην περίπτωση 3 του Master Theorem
όπως περιγράφεται στο
http://en.wikipedia.org/wiki/Master_theorem
Πράγματι, με ε = έχουμε
(και μάλιστα με ακριβή ισότητα, χωρίς το μεγάλο Ω) και (ακολουθώντας τον συμβολισμό της wikipedia) είναι
με c < 1 (εδώ a=3, b=4, c=3/4)
Άρα ασυμπτωτικά Τ(n) = Θ(n)

Αντώνη, το ίδιο βρήκες και εσύ, αλλά νομίζω για τον λάθος λόγο. Εκτός αν κάνω ο ίδιος λάθος, οπότε θα χαρώ να το ακούσω.

Φιλικά,

Μιχάλης Λάμπρου

ΥΓ
Επειδή ο συμβολισμός δεν είναι ο καθιερωμένος, καλό είναι να γράψω μερικά σχόλια για όσους δεν έχουν ξαναδεί τέτοιες αναδρομικές σχέσεις.

Η αρχική αναδρομική σχέση έπρεπε να γραφόταν στην μορφή και να δηλωνώταν
ρητά ότι πρόκειται για αναδρομική που ζητά ασυμπτωτική συμπεριφορά εκτέλεσης αλγορίθμου. Αλλιώς που να το καταλάβουμε! Ευτυχώς που το επεσήμανε ο Αντώνης.

Εδώ (για τους μη γνωριζοντες) το μέσα στο T λαμβάνεται, σε αυτή την θεωρία, ως το
ακέραιο μέρος ή ως το .
Η δε λύση που ζητάμε δεν είναι ένας ακριβής τύπος αλλά "ασυπτωτικός".
Τέτοιες ασυμπτωτικές εκτιμήσεις είναι καλομελετημένες. Συνήθως η τελική απάντηση αυτού που ψάχνουμε εκφράζεται είτε ως Τ(n) = Ο(g(n)) είτε ως Τ(n) = Θ(g(n)), όπου g θετική συνάρτηση που την προσδιορίζουμε εμείς.
Το Ο(g(n)) και το Θ(g(n)) που έγραψα είναι συντομογραφία, αντίστοιχα, των φράσεων
"υπάρχει θετική σταθερά c με Τ(n) cg(n) για κάθε αρκούντως μεγάλο n" ή "υπάρχουν θετικές σταθερές c, d με dg(n) Τ(n) cg(n) για κάθε αρκούντως μεγάλο n" .

Ελπίζω να λύθηκε το μυστήριο.

[antonis_math]

Δεν είπα ότι
ειδική μορφή

10-2-2009 10-03-36 πμ.png

εκφράζει το χρόνο εκτέλεσης ενός αλγορίθμου αναδρομικού, που για να λυθεί ένα στιγμιότυπό του διασπάτε σε 3 υποπροβλήματα μεγέθους ν/4 και εκτελόνται ν "ουσιαστικά" βήματα του αλγορίθμου επιπλέον. Οτι lg3/lg4 <1 (στην "3η περιπτωση" πρέπει : το ν πολυωνυμικά μεγαλύτερο του ν^(lg3/lg4) και 3 ν/4 < cν, για κάποιο c<1) δείχνει οτι η επιβάρυνση για την λύση των υποπροβλημάτων είναι σχετικά πιο μικρή σε σχέση με την δαπάνη του ν. Και τελικά υπολογίζεται μόνο το ν.

[Mihalis_Lambrou]

Δεν είπα ότι

Αντώνη έχεις δίκιο. Νόμιζα ότι χρησιμοποιυούσες την Περίπτωση 1 του master theorem όπως αυτό διατυπώνεται στην ιστοσελίδα της wikipedia που παρέπεμψα. Εκεί η υπόθεση είναι . Δεν φαντάστηκα (αφού δεν ανέφερες) ότι είχες άλλη εκδοχή του θεωρήματος.
Ευχαριστώ για την ισχυρή και ενδιαφέρουσα μορφή του θεωρήματος που παρέθεσες.

Φιλικά,

Μιχάλης Λάμπρου