THMMY.gr

Άσκηση 3 - 2.2-2 (Επιλεκτική αναζήτηση)

Στο λυμένο κομμάτι, στις γραμμές 5 και 6 του ψευδοκώδικα, στις Επαναλήψεις, τα όρια του αθροίσματος νομίζω πρέπει να είναι 1..(n-1) αντί για 2..n.

Άσκηση 8 - 2.3-5 (Διχοτομική αναζήτηση)

Στις γραμμές 3 και 5 του ψευδοκώδικα το A[mid] είναι λίγο άντε παοκάρα ή μου φαίνεται? Αν πάρεις τον πίνακα με τα στοιχεία π.χ. 2 και 8, στην πρώτη επανάληψη ελέγχεις με το Α(5). Ομοίως αν έχεις τα 1,2,3,4,5,100 στην πρώτη επανάληψη ελέγχεις με το Α(50). είναι δείκτες και όχι τιμές nvm

Στο κεφάλαιο 4.2, μία γενικότερη απορία για τις ασκήσεις:

Ποιά είναι η λογική πίσω από τον υπολογισμό του ύψους του δέντρου αναδρομής? Κυρίως δηλαδή για δέντρα που δεν είναι πλήρη, πώς σκεφτόμαστε? Το λέω γιατί βγάζει μερικά αποτελέσματα τα οποία καταλαβαίνω πάνω-κάτω γιατί είναι σωστά, αλλά δεν ξέρω πώς να τα βγάλω από μόνος μου...

Αυτό που θα γράψω είναι μάλλον βλακεία,μοναχή δηλ. βγήκα σ'αυτό το συμπέρασμα.
Έστω ότι έχεις την εξής αναδρομική σχέση:
Τ(n)=b*T(n/a)+f(n)

ύψος δέντρου:log_an

Μια απορία:
στην άσκηση 4.2-3 ,δε θα έπρεπε να είναι Τ(n)=c*n^2+Θ(n^2)=Θ(n^2) (και άρα ίσο με το Ο και το Ω);;;;

Εσύ έχεις βρει πως T(n) = 2cn²- cn, από εκεί και πέρα πως θα συνέχιζες;

Θα χρησιμοποιούσα τη μέθοδο της αντ/σης για να υποθέσω(αφού έχουμε τη σχέση 2cn²-cn ) ότι O(n²) και μετά για να το επαληθεύσω θα έλεγα,
2cn²-cn<=c₁n²=>(:n²>1) 
2c-(c/n)<=c₁ που ισχύει για αρκετά μεγάλο n και c₁>=2c
όχι;(είμαι μπετόστοκος,το ξέρω)

βασικά εγώ δε μπορώ να βγάλω αυτή τη σχέση που λες :-

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

Για αυτά που γράφεις, έχεις δίκιο. Έτσι μπορείς να αποδείξεις πως T(n) = O(n²), δηλαδή. Απλά η εκφώνηση σου λέει "Επαληθεύστε το φράγμα με την μέθοδο της αντικατάστασης." ;)

Εμ,αυτή τη σχέση δε μπορώ να βγάλω...:(

Κάνεις το αναδρομικό δέντρο, ύψους lgn, και αθροίζεις σε κάθε σειρά. Έπειτα αθροίζεις όλες τις σειρές, και βγαίνει:

(http://latex.codecogs.com/gif.download?%5Cdpi%7B120%7D%20T%28n%29%3Dcn%5Csum_%7Bi%3D0%7D%5E%7Blgn%7D2%5Ei%3Dcn%282%5E%7B1+lgn%7D-1%29%3Dcn%282n-1%29%3D2cn%5E2-cn)


Ακριβώς έτσι είναι και στις λυμένες ασκήσεις. Σε ποιό σημείο έχεις πρόβλημα;

α οκ,τώρα το κατάλαβα
βασικά έβγαλα μόνη μου ένα συμπέρασμα γενικό για το κόστος του δέντρου(έναν τύπο δλδ) στη σελ.69 και το έπαιρνα με βάση αυτόν τον τύπο
ευχαριστώ πολύ πολύ :-*

Πρόοδος 2007 1ο θέμα τί βρήκατε;
Το γ μήπως;

άκυρο,δεν είναι το γάμα
μάλλον το δ

εγώ το γ βρήκα :-\

αφού: πράξεις (http://www.wolframalpha.com/input/?i=lim%28x-%3Einf%29+%28lnx%29^x%2Fx)

αφού ρε πχ για n=3 και c=500 δεν ισχύει

Τότε βρίσκεις ένα n₀>3.

(Και εμένα το γ μου βγήκε...)

Δες λίγο ξανά ποιός είναι ο ορισμός του ω ;)

ε τον κοίταξα πάλι τον ορισμό,δεν καταλαβαίνωωωω   :(

βασικά αυτό με το όριο δεν το είχα σκεφτεί,εγώ απλά στην ανίσωση έβαλα νιοστές ρίζες και μετά έβαλα δυο τυχαίες τιμές για n kai c

Ο ορισμός λέει:
(http://latex.codecogs.com/gif.download?%5Cdpi%7B120%7D%20%5Comega%20%28g%28n%29%29%29%3D%5Cleft%20%5C%7B%20f%28n%29%3A%5Cexists%20n_0%3E0%2C0%5Cleq%20f%28n%29%2C0%3Cg%28n%29%2C%5Cforall%20n%5Cgeq%20n_0%2C%20lim_%7Bn%20%5Cmapsto%20%5Cinfty%20%7D%5Cfrac%7Bf%28n%29%7D%7Bg%28n%29%7D%3D%5Cinfty%20%5Cright%20%5C%7D)

Στο συγκεκριμένο θέμα, ικανοποιούνται όλες οι προϋποθέσεις αυτές, άρα είναι το γ.

Κοίτα να δεις ρε παιδί μου.Ενώ το βιβλίο το διάβασα αυτό με το όριο πρώτη φορά το είδα!
Ευχαριστώ!!

οκ σβήστηκα :P διορθώθηκα βασικά θα αυτοσβηστώ και σε λίγο :P ΔΙΑΦΑΝΕΙΕΣ

δεν καταλαβαινω απο την ασκηση 16-1 ασκ 7 στο φυλλαδιο με τις ασκησεις του κεφ 16 το τελευταιο ερωτημα...στα d ειναι μεσα και το μονολεπτο ? αυτο το c[j - di] πως υπολογιζεται ? κι η μοναδα που εχει στο 1+ c[..] ειναι στην ουσια το μονολεπτο ? αν καταλαβε κανεις ας βοηθησει...! τνξ

Τα κέρματά σου έχουν πάντα μονόλεπτο, αλλιώς δεν λύνεται η άσκηση για κάθε ποσό. Κάποιο από τα d₁ ...  d_k είναι μονόλεπτο.

Το ζητούμενο είναι να βρεις τον ελάχιστο αριθμό κερμάτων για κάθε ποσό. Όμως, ο ελάχιστος αριθμός για ένα ποσό εξαρτάται από τον ελάχιστο αριθμό κάποιων προηγούμενων ποσών, δηλαδή προηγούμενων λύσεων.
Οπότε τι κάνεις? Υπολογίζεις όλες αυτές τις προηγούμενες λύσεις, θέλοντας και μη, αφού τουλάχιστον μερικές από αυτές (εδώ όλες) σου χρειάζονται, και αποθηκεύεις κάπου τις λύσεις σου.

Το c είναι λοιπόν ο πίνακας που κουβαλάει τις λύσεις σου. Το κελί c[1] έχει τη λύση για ρέστα 1, το c[2] για ρέστα 2 κλπ... και το c[n] για ρέστα n, δηλαδή αυτό που θες.

Οπότε, ξεκινάς από κάτω προς τα πάνω (δηλαδή από το μικρότερό σου πρόβλημα, για ρέστα 0):
Προφανώς, το c[0] είναι 0, αφού τότε δίνεις 0 κέρματα για ρέστα.
Το c[1] είναι 1 κέρμα (αξίας 1 λεπτού) + την λύση για c[1-1] = 0... κλπ

Αν είχαμε μόνο μονόλεπτα θα ήταν εύκολη η ζωή μας (said no one ever), αλλά πες έχεις και δίλεπτα. Οπότε έχεις δύο επιλογές για το c[2]:
-Ή να δώσεις 1x1cent +{ την λύση για c[2-1] = c[1]=1 } (δύο κέρματα, άρα c[2] = 2)
-Ή να δώσεις 1x2cent + { την λύση για c[2-2] = c[0]=0 } (ένα κέρμα, άρα c[2]=1)
Ε, από αυτές τις λύσεις πάρε το minimum c.
Αυτό που έχω σε αγκύλες είναι το c[j-d_i] ουσιαστικά.


Έτσι προκύπτει το c[j] = 1 + min{c[j-d_i]}. d_i είναι η αξία του κέρματος.

να σαι καλα ρε φιλε γτ εχω μπερδευτει λιγο..

Η αλήθεια είναι ότι είναι λίγο περίεργος ο Δυναμικός. Εμένα με βοήθησαν τα

• http://people.cs.clemson.edu/~bcdean/dp_practice/ (http://people.cs.clemson.edu/~bcdean/dp_practice/)
• http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static (http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static)
• http://www.codechef.com/wiki/tutorial-dynamic-programming (http://www.codechef.com/wiki/tutorial-dynamic-programming)
  

στα θέματα 2007β(όχι ότι υπάρχουν και άλλα :P ) στο 1ο Θέμα τί βρήκατε;
επίσης αυτό δεν είναι ύλη α' προόδου;

Όλη η ύλη είναι μέσα και πιστεύω πως είναι το d

A!Στην αρχή νόμιζα ότι ήταν το β αλλά με μια δευτερη ματιά θαρρώ πως έχεις δίκιο.Θένκιου ε!

παιδια για το 3ο 8εμα που καναμε σημερα στο μαθημα ποια ηταν η λυση για το α ερωτημα τελικα?? :P

'Ασκηση 15.2 "καλαισθητη εκτύπωση"

προφανώς δεν μπορεί να κοπεί μια λέξη στα δύο αν δεν χωράει ολοκληρη στην γραμμή έτσι ?

Δεν κόβονται οι λέξεις

Στο θέμα 1 β πρόοδος στο α ερώτημα που ζητάει αλγόριθμο του Prim: θέλει να γράψουμε τον αλγόριθμο ή να πούμε ότι από το α με μια τομή S βλέπουμε ότι η γραμμή με το ελάχιστο κόστος είναι  η τάδε,οπότε πάμε στο β πχ κλπ;;;

εφαρμόστε λέει, οπότε ποιο είναι το αποτέλεσμα του νομίζω

εφοσον λέει εφαρμοστε απλα κανεις τν αλγοριθμο και τελειωνεις...

Ναι ρε, πρέπει να λες τί γίνεται σε κάθε επανάληψη και να δείξεις το τελικό αποτέλεσμα.

θενκς και στους 3