Αλγόριθμοι

THMMY.gr > Forum > Μαθήματα Βασικού Κύκλου > 1ο Εξάμηνο > 1ο Εξάμηνο - ΠΠΣ > Συστήματα Υπολογιστών (Moderators: Tasos Bot, tzortzis) > Αλγόριθμοι

0 Members and 1 Guest are viewing this topic.

Pages: [1] 2

Author

Topic: Αλγόριθμοι (Read 4356 times)

Angel C.

Καταξιωμένος/Καταξιωμένη

Posts: 286

Αλγόριθμοι

« on: August 29, 2007, 00:14:45 am »

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


« Last Edit: October 08, 2008, 14:55:46 pm by Inquirer »	Logged

vasso

Καταστραμμένος

Gender:

Posts: 6672

Overambitious doer

Re: Αλγόριθμοι

« Reply #1 on: August 29, 2007, 01:21:49 am »

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

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

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

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

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

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


	Logged

Είναι τα βλέφαρά μου
διάφανες αυλαίες.
Όταν τα ανοίγω βλέπω
μπρος μου ό,τι κι αν τύχει.
Όταν τα κλείνω βλέπω
μπρος μου ό,τι ποθώ.

crystal

Veteran
Αbsolute ΤΗΜΜΥ.gr

Gender:

Posts: 2503

Re: Αλγόριθμοι

« Reply #2 on: August 29, 2007, 22:29:15 pm »

Quote from: xri_age on August 29, 2007, 00:14:45 am

To floor τι κάνει; Undecided

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


	Logged

elmaya

Guest

Re: Αλγόριθμοι

« Reply #3 on: August 29, 2007, 22:32:03 pm »

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


	Logged

Άγνωστος Χ

Καταξιωμένος/Καταξιωμένη

Posts: 190

Re: Αλγόριθμοι

« Reply #4 on: February 09, 2008, 19:32:42 pm »

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


	Logged

mxkrtg13

Καταξιωμένος/Καταξιωμένη

Posts: 292

Re: [Συστήματα Υπολογιστών] Αλγόριθμοι

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

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


	Logged

Ευχαριστώ πολύ,αλλά ξεχνάς μερικά.Το φαί μου το χαρτί μου την TV μου το ψυγείο μου την καφετιέρα μου το PC μου το κρεβάτι μου την ντουλάπα μου την παρέα μου την γυναίκα μου τη δουλειά μου την οικογένεια μου το χόμπυ μου κ αντε γαμήσου εσύ κ το σπρέυ σου.

solli144

Καταξιωμένος/Καταξιωμένη

Gender:

Posts: 271

Re: [Συστήματα Υπολογιστών] Αλγόριθμοι

« Reply #6 on: February 10, 2008, 13:38:44 pm »

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


	Logged

AgentCain

Αbsolute ΤΗΜΜΥ.gr

Gender:

Posts: 3587

Σοφράνο βρίσε, σταβέντο φτύσε!

Re: [Συστήματα Υπολογιστών] Αλγόριθμοι

« Reply #7 on: February 10, 2008, 13:46:04 pm »

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

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

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


	Logged

Ανάμεσα σ'αυτό που σκέφτομαι, σ'αυτό που θέλω να σας πω, σ'αυτό που πιστεύω ότι σας λέω, σ'αυτό που σας λέω, σ'αυτό που θέλετε να ακούσετε, σ'αυτό που ακούτε, σ'αυτό που πιστεύετε ότι καταλαβαίνετε, σ'αυτό που θέλετε να καταλάβετε και σ'αυτό που καταλαβαίνετε υπάρχουν τουλάχιστον 9 πιθανότητες να μην συννενοηθούμε.

solli144

Καταξιωμένος/Καταξιωμένη

Gender:

Posts: 271

Re: [Συστήματα Υπολογιστών] Αλγόριθμοι

« Reply #8 on: February 10, 2008, 14:04:24 pm »

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


	Logged

xrysiss

Νεούλης/Νεούλα

Posts: 27

Re: [Συστήματα Υπολογιστών] Αλγόριθμοι

« Reply #9 on: February 10, 2008, 17:17:37 pm »

Quote from: mxkrtg13 on February 09, 2008, 22:26:40 pm

Επαναφερω αυτο το ερώτημα.
Δεν γνωριζει κανεις να απαντησει?
Τι είναι το Τ2 και το Χ2?


	Logged

Emfanever

Καταστραμμένος

Gender:

Posts: 5284

Πολίτης

Re: [Συστήματα Υπολογιστών] Αλγόριθμοι

« Reply #10 on: February 10, 2008, 17:19:42 pm »

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


	Logged

xrysiss

Νεούλης/Νεούλα

Posts: 27

Re: [Συστήματα Υπολογιστών] Αλγόριθμοι

« Reply #11 on: February 10, 2008, 17:22:59 pm »

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


	Logged

vasso

Καταστραμμένος

Gender:

Posts: 6672

Overambitious doer

Re: [Συστήματα Υπολογιστών] Αλγόριθμοι

« Reply #12 on: February 10, 2008, 20:01:01 pm »

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

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


	Logged

solli144

Καταξιωμένος/Καταξιωμένη

Gender:

Posts: 271

Re: [Συστήματα Υπολογιστών] Αλγόριθμοι

« Reply #13 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) δεν έχω ιδέα τι είναι Lips Sealed


	Logged

ion

Θαμώνας

Gender:

Posts: 435

Re: [Συστήματα Υπολογιστών] Αλγόριθμοι

« Reply #14 on: February 10, 2008, 20:25:35 pm »

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

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


	Logged

Αυτόνομη Παρέμβαση στους Ηλ-Μηχ

http://aphm.espivblogs.net/

Pages: [1] 2

Jump to: