last day (17 days later) » 

evinda
evinda
12:32
Hello!!! From which region of Greece are you?
 
3 hours later…
Stef
Stef
15:27
Athens! Have you been in Greece? Where are you from?
 
3 hours later…
evinda
evinda
18:18
@Stef I also live in Greece... Are you a student?
Stef
Stef
18:36
Hmmm, yes and no. I am a PhD student but I am not in the typical age of a student. I am 33 now. Do you just live in greece or are you greek? Are you a student "too" :)?
evinda
evinda
@Stef I am also greek.. I am an undergraduate student..
In which field is your master?
Stef
Stef
In statistics. At which university are you an undergraduate?
evinda
evinda
@Stef University of crete
@Stef Have you had subjects related to algorithms?
Stef
Stef
18:52
Να μιλάμε ελληνικά?
ναι είχα, αλλά όχι πολλά! τι ακριβώς θες?
evinda
evinda
Εντάξει
Σκεφτείτε το πρόβλημα της συναλλαγής για ν σεντς, χρησιμοποιώντας το μικρότερο
αριθμό κερμάτων.
Ας υποθέσουμε ότι η αξία του κάθε νομίσματος είναι ένας ακέραιος .
Περιγράψτε ένα άπληστο αλγόριθμο ο οποίος θα κάνει συναλλαγές που αποτελούνται από 25σεντς ,10σεντς , 5σεντς , και 1σεντ .
Αποδείξτε ότι ο αλγόριθμος σας δίνει μια βέλτιστη λύση.
Σκέφτηκα έναν αλγόριθμο αλλά δεν ξέρω πως να δείξω ότι δίνει μια βέλτιση λύση
Να σου πω τον αλγόριθμο;
Stef
Stef
πες μου, ναι, αλλά δεν ξέρω αν μπορώ να σε βοηθήσω.
evinda
evinda
Επιλέγουμε το νόμισμα με την υψηλότερη αξία , αφαιρούμε την τιμή αυτή από το ποσό της συναλλαγής και επαναλαμβάνουμε την ίδια διαδικασία μέχρις ότου το ποσό της συναλλαγής είναι μηδέν.
Stef
Stef
Σωστό μου φαίνεται.
Για να δείξεις ότι η λύση είναι βέλτιστη μπορείς να βρεις τη βέλτιστη λύση και να διαπιστώσεις ότι είναι ίδια με αυτή που δίνει ο αλγόριθμος
Αν θέλεις να κάνεις συναλλαγή για ν σέντς τότε είναι προφανές (ή το δείχνεις εύκολα) ότι ο ελάχιστος αριθμός κερμάτων που χρειάζονται προκύπτει με το να διαιρέσεις τον αριθμό αυτό με το μεγαλύτερο σε αξία νομίσμα που χωράει (π.χ. μιά συναλλαγή 7 σέντς χωράει 1 νόμισμα των 5 σέντς) και μετά με το υπόλοιπο το ίδιο κ.ο.κ.
Δηλαδή ακριβώς αυτό που κάνει ο αλγόριθμός σου
Άλλη ερώτηση: είναι σίγουρα άπληστος αυτός ο αλγόριθμος?
(νομίζω πώς είναι όντως άπληστος, πάντως)
Έλα, δες εδώ: en.wikipedia.org/wiki/Greedy_algorithm Στη φωτό δεξιά έχει ακριβώς αυτό το παράδειγμα. Σωστή είσαι
evinda
evinda
19:34
@Stef Είναι ο μόνος τρόπος να δείξουμε ότι η λύση είναι βέλτιστη με το να δείξουμε ότι ο ελάχιστος αριθμός κερμάτων που χρειάζονται προκύπτει με το να διαιρέσεις τον αριθμό αυτό με το μεγαλύτερο σε αξία νομίσμα που χωράει και μετά με το υπόλοιπο το ίδιο κ.ο.κ. ?
Ή θα μπορούσαμε να δείξουμε ότι ικανοποιούνται κάποιες ιδιότητες?
 
3 hours later…
Stef
Stef
22:57
δε νομίζω ότι γίνεται αλλιώς, αλλά δεν είμαι και ειδικός στους αλγόριθμους...

  last day (17 days later) »