[Ανάλυση Αλγορίθμων] Απορίες στις ασκησεις 2014

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

Για ανανέωση (ή προσθήκη νέου) avatar, πρέπει η μεγαλύτερη διάσταση της εικόνας να είναι 110 pixels.

[Exomag]

Topic που αφορά τις ασκήσεις του μαθήματος. Stay on topic!

[Cr0ne]

Άσκηση 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

[et3rn1ty]

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

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

[princess_of_the_dawn]

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

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

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

[Exomag]

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

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

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

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

[princess_of_the_dawn]

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

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

[Exomag]

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

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

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

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

[princess_of_the_dawn]

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

[Exomag]

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

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




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

[princess_of_the_dawn]

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

[princess_of_the_dawn]

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

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

[Exomag]

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

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

εγώ το γ βρήκα

αφού: πράξεις

[princess_of_the_dawn]

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

[Dealan]

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

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

[Exomag]

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

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