|
Title: Αλγόριθμοι Post by: Angel C. on August 29, 2007, 00:14:45 am Μπορεί να μου εξηγήσει κάποιος πώς λειτουργεί ο αλγόριθμος διαίρει και βασίλευε; To floor τι κάνει; :-\
Title: Re: Αλγόριθμοι Post by: vasso on August 29, 2007, 01:21:49 am Διαίρει και βασίλευε είναι μια "οικογένεια" αλγορίθμων που δουλεύουν με μια συγκεκριμένη γραμμή.
Η γραμμή αυτή έχει ως εξής: Παίρνουν το πρόβλημα και το διαιρούν σε 2 μικρότερα υποπροβλήματα τα οποία προφανώς είναι ευκολότερο να λυθούν. Αυτό αλλιώς λέγεται υποδιπλασιασμός της υπολογιστικής πολυπλοκότητας. Τώρα το κάθε υποπρόβλημα, μπορεί πάλι να διαιρεθεί σε 2 μικρότερα προβληματάκια. Ένας αλγόριθμος τύπου δ&β διαιρεί το πρόβλημα ξανά και ξανά μέχρι τα προβληματάκια που θα μείνουν στο τέλος να είναι προβλήματα 1 πράξης (πχ 1 σύγκριση) , δηλαδή πολυπλοκότητας 1. Στη συνέχεια, παίρνει τις λύσεις των προβλημάτων της κάτω κάτω σειράς και τα συνθέτει προς τα πάνω, ώστε στο τέλος να καταλήξει συνθέτοντας τα 2 πρώτα υποπροβλήματα να βρει την τελική λύση. πρόβλημα / \ υποπρόβλημα υποπρόβλημα / \ / \ ... ... ... ... ... ... ... / \ / \ / \ προβληματάκι προβληματάκι προβληματάκι προβληματάκι προβληματάκι προβληματάκι ακούγονται πιο περίπλοκοι, αλλά συχνά είναι πιο γρήγοροι και πιο απλοί σε πράξεις από τους άλλους. Title: Re: Αλγόριθμοι Post by: crystal on August 29, 2007, 22:29:15 pm To floor τι κάνει; :-\ Αν εχω καταλαβει καλα το φλορ διαιρει το αρχικο προβλημα σε υποπροβληματα.. Αν εχει καταλαβει κανεις κατι παραπανω η μπορει να διορθωσει....Help pleeease :) :) Title: Re: Αλγόριθμοι Post by: elmaya on August 29, 2007, 22:32:03 pm http://en.wikipedia.org/wiki/Floor_function
Title: Re: Αλγόριθμοι Post by: Άγνωστος Χ on February 09, 2008, 19:32:42 pm Μήπως θα μπορούσε κάποιος να εξηγήσει και να γράψει αναλυτικά τους αλγορίθμους 5 και 6 από τις σημειώσεις του Ντελόπουλου;
Title: Re: [Συστήματα Υπολογιστών] Αλγόριθμοι Post by: mxkrtg13 on February 09, 2008, 22:26:40 pm ) 2α) Έστω ότι ο Χ είναι πραγματικός αριθμός και ο Ν ακέραιος ίσος με κάποια δύναμη του 2 (Ν = 2n, η e Ζ). Εξηγήστε τι κάνει ο αλγόριθμος που περιγράφεται από τον παρακάτω ψευδοκώδικα:
function S := what(X, N); if (N>2) Τ := what(X, Ν/2) Υ := Τ2; else Υ: = Χ2; end S := Υ; (παρατηρήσεις: (α) Το σύμβολο ":=" σημαίνει "γίνεται ίσος", (β) Η εντολή "return(x)" έχει σαν αποτέλεσμα τον άμεσο τερματισμό της συνάρτησης και επιστροφή της τιμής του x ως αποτέλεσμα.) 2β. Ποια η υπολογιστική πολυπλοκότητα, f(n), του παραπάνω αλγορίθμου ως προς τον αριθμό των πραγματικών πολλαπλασιασμών που απαιτούνται και γιατί;. Υπολογισμοί: κάποιος που γνωρίζει μπορεί να δώσει απάντηση παρακαλώ? Title: Re: [Συστήματα Υπολογιστών] Αλγόριθμοι Post by: solli144 on February 10, 2008, 13:38:44 pm έχει καταλάβει κανείς πως δουλεύει η εντροπία στην συμπίεση ?
Title: Re: [Συστήματα Υπολογιστών] Αλγόριθμοι Post by: AgentCain on February 10, 2008, 13:46:04 pm Απότι έχω καταλάβει η εντροπία είναι ένας αριθμός-οδηγός και παράλληλα η βέλτιστη συμπίεση που μπορούμε να πετύχουμε.
Και το έχω σκεφτεί ως εξής Έστω ότι έχουμε μία ασπρόμαυρη εικόνα με διαφορετικές αποχρώσεις του γκρι Γεγονός είναι ότι στοιχειώδη τμήματα της εικόνας έχουν ίδια ή παραπλήσια απόχρωση Η εντροπία μας λέει κατά κάποιο τρόπο ποιός είναι ο καλύτερος συνδιασμός αυτών των τμημάτων ώστε α)η γενικότερη εικόνα να μειωθεί σε μέγεθος β)να μη χαθεί-παραμορφωθεί πληροφορία που μπορεί να τη διακρίνει ο άνθρωπος Μάλλον γιαυτό στον τύπο εμφανίζεται και η "πιθανότητα εμφάνισης του τάδε συμβόλου" Title: Re: [Συστήματα Υπολογιστών] Αλγόριθμοι Post by: solli144 on February 10, 2008, 14:04:24 pm σε θεωρητικό επίπεδο το έχω καταλάβει. Σε πρακτικό επίπεδο οχι. Τεσπα δε νομίζω να βαλει τίποτα τέτοιο.
ευχαριστώ για τη βοήθεια σήμερα AgentCain Title: Re: [Συστήματα Υπολογιστών] Αλγόριθμοι Post by: xrysiss on February 10, 2008, 17:17:37 pm ) 2α) Έστω ότι ο Χ είναι πραγματικός αριθμός και ο Ν ακέραιος ίσος με κάποια δύναμη του 2 (Ν = 2n, η e Ζ). Εξηγήστε τι κάνει ο αλγόριθμος που περιγράφεται από τον παρακάτω ψευδοκώδικα: function S := what(X, N); if (N>2) Τ := what(X, Ν/2) Υ := Τ2; else Υ: = Χ2; end S := Υ; (παρατηρήσεις: (α) Το σύμβολο ":=" σημαίνει "γίνεται ίσος", (β) Η εντολή "return(x)" έχει σαν αποτέλεσμα τον άμεσο τερματισμό της συνάρτησης και επιστροφή της τιμής του x ως αποτέλεσμα.) 2β. Ποια η υπολογιστική πολυπλοκότητα, f(n), του παραπάνω αλγορίθμου ως προς τον αριθμό των πραγματικών πολλαπλασιασμών που απαιτούνται και γιατί;. Υπολογισμοί: κάποιος που γνωρίζει μπορεί να δώσει απάντηση παρακαλώ? Επαναφερω αυτο το ερώτημα. Δεν γνωριζει κανεις να απαντησει? Τι είναι το Τ2 και το Χ2? Title: Re: [Συστήματα Υπολογιστών] Αλγόριθμοι Post by: Emfanever on February 10, 2008, 17:19:42 pm Και εγώ την ίδια απορία έχω! Μήπως είναι λάθος στην τελική? Δε βγάζει νόημα!
Title: Re: [Συστήματα Υπολογιστών] Αλγόριθμοι Post by: xrysiss on February 10, 2008, 17:22:59 pm και όταν ζητάει υπ.πλυπλοκότητα με βάση των αριθμό των πολ/σμων μήπωςΤ2 είναι Τ*2???
Title: Re: [Συστήματα Υπολογιστών] Αλγόριθμοι Post by: vasso on February 10, 2008, 20:01:01 pm υπάρχει περίπτωση να είναι ένας τρόπος "μπακάλικος" για να βρίσκεις τετραγωνική ρίζα...
κάτι τέτοιο μου θύμισε αυτό με το ν/2... τώρα πραγματικά, αν δεν ξέρεις τι κάνει η what δεν έχει πολύ νόημα να ψάξεις τι παίζει με τον αλγόριθμο... Title: Re: [Συστήματα Υπολογιστών] Αλγόριθμοι Post by: solli144 on February 10, 2008, 20:21:13 pm ελπίζω να μη βαλει να γράψουμε κανέναν αλγόριθμο όπως ταξινόμιση με διαίρει και βασίλευε γιατί δεν καταλαβαίνω όλους τους συμβολισμούς της γλώσσας MATLAB που χρησιμοποιεί, όπως :
A(p:q):=merge[A(p:r),A(r+1:q),r-p,q-r-1] ΤΙ ΕΙΝΑΙ ΑΥΤΑ ????? ειδικά το A(p:q) δεν έχω ιδέα τι είναι :-X Title: Re: [Συστήματα Υπολογιστών] Αλγόριθμοι Post by: ion on February 10, 2008, 20:25:35 pm merge είναι ένας αλγόριθμος που διατύπωσε προηγουμένως
και Α(p:q) είναι ο πίνακας Α απο p ως q Title: Re: Αλγόριθμοι Post by: ion on February 10, 2008, 20:26:44 pm To floor τι κάνει; :-\ Αν εχω καταλαβει καλα το φλορ διαιρει το αρχικο προβλημα σε υποπροβληματα.. Αν εχει καταλαβει κανεις κατι παραπανω η μπορει να διορθωσει....Help pleeease :) :) το φλορ δίνει τον αμέσως προηγούμενο ακέραιο δηλ αν ι+j/2=3.5 τότε φλορ αυτού είναι 3 Title: Re: [Συστήματα Υπολογιστών] Αλγόριθμοι Post by: λήθη on February 10, 2008, 20:30:02 pm ελπίζω να μη βαλει να γράψουμε κανέναν αλγόριθμο όπως ταξινόμιση με διαίρει και βασίλευε γιατί δεν καταλαβαίνω όλους τους συμβολισμούς της γλώσσας MATLAB που χρησιμοποιεί, όπως : A(p:q):=merge[A(p:r),A(r+1:q),r-p,q-r-1] ΤΙ ΕΙΝΑΙ ΑΥΤΑ ????? ειδικά το A(p:q) δεν έχω ιδέα τι είναι :-X χαλαρα :) οπως εχει ειπωθει ξανα..δε χρειαζεται να μαθουμε απεξω τους αλγοριθμους αυτους απλα τη φιλοσοφια τους δεν πιστευω να ζητησει κατι τετοιο..και αν το ζητησει θα ειναι σε στυλ εξηγηστε τι κανει αυτο εδω και φυσικα οι εξηγησεις των συναρτησεων.. αυτα, ως προσωπικη αποψη και σταση απεναντι στο μαθημα μην παρω και κανενα στο λαιμο μου :P Title: Re: Αλγόριθμοι Post by: Casino Royale on December 03, 2009, 15:00:30 pm βάζει θέματα με τις πολυπλoκότητες?
|