Αλγόριθμοι

[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 με προσοχή στα ονόματα των αρχείων!

[Angel C.]

Μπορεί να μου εξηγήσει κάποιος πώς λειτουργεί ο αλγόριθμος διαίρει και βασίλευε; To floor τι κάνει; 

[vasso]

Διαίρει και βασίλευε είναι μια "οικογένεια" αλγορίθμων που δουλεύουν με μια συγκεκριμένη γραμμή.

Η γραμμή αυτή έχει ως εξής: Παίρνουν το πρόβλημα και το διαιρούν σε 2 μικρότερα υποπροβλήματα τα οποία προφανώς είναι ευκολότερο να λυθούν. Αυτό αλλιώς λέγεται υποδιπλασιασμός της υπολογιστικής πολυπλοκότητας.
Τώρα το κάθε υποπρόβλημα, μπορεί πάλι να διαιρεθεί σε 2 μικρότερα προβληματάκια.
Ένας αλγόριθμος τύπου δ&β διαιρεί το πρόβλημα ξανά και ξανά μέχρι τα προβληματάκια που θα μείνουν στο τέλος να είναι προβλήματα 1 πράξης (πχ 1 σύγκριση) , δηλαδή πολυπλοκότητας 1.

Στη συνέχεια, παίρνει τις λύσεις των προβλημάτων της κάτω κάτω σειράς και τα συνθέτει προς τα πάνω, ώστε στο τέλος να καταλήξει συνθέτοντας τα 2 πρώτα υποπροβλήματα να βρει την τελική λύση.

                                                   πρόβλημα
                                                   /           \
                                      υποπρόβλημα   υποπρόβλημα
                                        /            \       /            \
                                 ...               ...     ...             ...

                  ...                                     ...                                     ...
                 /    \                                 /    \                                /       \
προβληματάκι προβληματάκι προβληματάκι προβληματάκι προβληματάκι προβληματάκι


ακούγονται πιο περίπλοκοι, αλλά συχνά είναι πιο γρήγοροι και πιο απλοί σε πράξεις από τους άλλους.

[crystal]

To floor τι κάνει; 

Αν εχω καταλαβει καλα το φλορ διαιρει το αρχικο προβλημα σε υποπροβληματα.. Αν εχει καταλαβει κανεις κατι παραπανω η μπορει να διορθωσει....Help pleeease

[elmaya]

http://en.wikipedia.org/wiki/Floor_function

[Άγνωστος Χ]

Μήπως θα μπορούσε κάποιος να εξηγήσει και να γράψει αναλυτικά τους αλγορίθμους 5 και 6 από τις σημειώσεις του Ντελόπουλου;

[mxkrtg13]

) 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), του παραπάνω αλγορίθμου ως προς τον αριθμό των πραγματικών πολλαπλασιασμών που απαιτούνται και γιατί;. Υπολογισμοί:

κάποιος που γνωρίζει μπορεί να δώσει απάντηση παρακαλώ?

[solli144]

έχει καταλάβει κανείς πως δουλεύει η εντροπία στην συμπίεση ?

[AgentCain]

Απότι έχω καταλάβει η εντροπία είναι ένας αριθμός-οδηγός και παράλληλα η βέλτιστη συμπίεση που μπορούμε να πετύχουμε.
Και το έχω σκεφτεί ως εξής

Έστω ότι έχουμε μία ασπρόμαυρη εικόνα με διαφορετικές αποχρώσεις του γκρι
Γεγονός είναι ότι στοιχειώδη τμήματα της εικόνας έχουν ίδια ή παραπλήσια απόχρωση
Η εντροπία μας λέει κατά κάποιο τρόπο ποιός είναι ο καλύτερος συνδιασμός αυτών των τμημάτων ώστε
α)η γενικότερη εικόνα να μειωθεί σε μέγεθος
β)να μη χαθεί-παραμορφωθεί πληροφορία που μπορεί να τη διακρίνει ο άνθρωπος

Μάλλον γιαυτό στον τύπο εμφανίζεται και η "πιθανότητα εμφάνισης του τάδε συμβόλου"

[solli144]

σε θεωρητικό επίπεδο το έχω καταλάβει. Σε πρακτικό επίπεδο οχι. Τεσπα δε νομίζω να βαλει τίποτα τέτοιο.
ευχαριστώ για τη βοήθεια σήμερα AgentCain

[xrysiss]

) 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?

[Emfanever]

Και εγώ την ίδια απορία έχω! Μήπως είναι λάθος στην τελική? Δε βγάζει νόημα!

[xrysiss]

και όταν ζητάει υπ.πλυπλοκότητα με βάση των αριθμό των πολ/σμων μήπωςΤ2 είναι Τ*2???

[vasso]

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

κάτι τέτοιο μου θύμισε αυτό με το ν/2... τώρα πραγματικά, αν δεν ξέρεις τι κάνει η what δεν έχει πολύ νόημα να ψάξεις τι παίζει με τον αλγόριθμο...

[solli144]

ελπίζω να μη βαλει να γράψουμε κανέναν αλγόριθμο όπως ταξινόμιση με διαίρει και βασίλευε γιατί δεν καταλαβαίνω όλους τους συμβολισμούς της γλώσσας MATLAB που χρησιμοποιεί, όπως :
A(p:q):=merge[A(p:r),A(r+1:q),r-p,q-r-1]
ΤΙ ΕΙΝΑΙ ΑΥΤΑ ????? ειδικά το A(p:q) δεν έχω ιδέα τι είναι 

[ion]

 merge είναι ένας αλγόριθμος που διατύπωσε προηγουμένως

και Α(p:q) είναι ο πίνακας Α απο p ως q