Από DistrSys
- 1o Θέμα [30%]
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού, μη-κατευθυνόμενου δικτύου με m κανάλια επικοινωνίας.
- Διατυπώστε το πρόβλημα της εκλογής αρχηγού.
- Προτείνετε μια αλγοριθμική λύση που να ελαχιστοποιεί τον αριθμό μηνυμάτων που ανταλλάσσουν οι διεργασίες, στην περίπτωση όπου οι διεργασίες δεν έχουν μοναδική ταυτότητα και δεν έχουν πρόσβαση σε κάποια γεννήτρια τυχαίων αριθμών. Αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και την πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- Προτείνετε μια αλγοριθμική λύση που να επιτρέπει την εκλογή δύο αρχηγών, στην περίπτωση όπου οι διεργασίες έχουν μοναδική ταυτότητα. Αναλύστε την ορθότητα του αλγόριθμου, την χρονική πολυπλοκότητα και την πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
- Ως αλγοριθμική λύση θεωρούμε είτε έναν αλγόριθμο (από την βιβλιογραφία) είτε μια συλλογή αλγορίθμων (από την βιβλιογραφία) είτε έναν νέο αλγόριθμο. Κατά την περιγραφή της πρότασης σας, αναφέρετε ξεκάθαρα όποιες επιπλέον υποθέσεις πρέπει να γίνουν ως προς τον τρόπο λειτουργίας του συστήματος πέρα από αυτές που αναφέρονται σε κάθε ερώτημα.
- 2o Θέμα [35%]
- Θεωρείστε ένα ασύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός δικτύου γραμμής. Οι διεργασίες μπορούν να ξεχωρίσουν τον δεξιό γείτονα τους από τον αριστερό και γνωρίζουν αν είναι στις άκρες του δικτύου. Κάθε διεργασία u δέχεται ως είσοδο έναν ακέραιο αριθμό iu και έχει σταθερού μεγέθους μνήμη. Προτείνετε μια αλγοριθμική λύση που να ταξινομεί τους αριθμούς μεταξύ των διεργασιών, όπου κάθε διεργασία u θα δίνει έξοδο έναν ακέραιο αριθμό ou και το σύνολο τιμών εξόδου είναι ίσο με το σύνολο τιμών εισόδου και o1 ≤ ... ≤ on. Προσπαθήστε να σχεδιάσετε τον πιο αποδοτικό αλγόριθμο ως προς την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αναλύστε την ορθότητα του αλγόριθμου και αποδείξτε τους ισχυρισμούς σας.
- 3o Θέμα [35%]
- Θεωρείστε ένα σύγχρονο κατανεμημένο σύστημα με n διεργασίες συνδεδεμένες μέσω ενός γενικού δικτύου. Κάθε διεργασία έχει μια μοναδική ταυτότητα και δεν γνωρίζει το σύνολο των διεργασιών ή την τοπολογία του δικτύου. Σχεδιάστε έναν όσο το δυνατόν αποδοτικότερο αλγόριθμο για την κατασκευή ενός επικαλυπτικού δέντρου ελαχίστου-ύψους. Ορίστε τις ιδιότητες του αλγόριθμου σας και αναλύστε την ορθότητά του, καθώς και την χρονική πολυπλοκότητα και πολυπλοκότητα μηνυμάτων. Αποδείξτε τους ισχυρισμούς σας.
|
Σχετικό υλικό:
Βαθμολογία:
| ΑΜ |
Ονοματεπώνυμο |
Βαθμός |
| 2861 | Κόλιας Βασίλειος | 4.5 |
| 2880 | Λυκοκανέλλος Φιλοποίμην | 5.5 |
| 2946 | Σιώκης Απόστολος | 8.5 |
| 2953 | Σπυρώνης Ιωάννης | 5 |
| 2980 | Χαρίση Ευνομία | 6 |
| 2989 | Τζαμπαζης Γιώργος | 6 |
| 3000 | Καναβός Ανδρέας | 5.5 |
| 3003 | Τόκης Θεόδωρος | 6 |
| 3007 | Γερούτης Γεώργιος | 2 |
| 3027 | Δημόπουλος Κωνσταντίνος | 9.5 |
| 3033 | Λαδάς Αλέξανδρος | 5 |
| 3050 | Ακριβόπουλος Ορέστης | 7 |
| 3055 | Αναστασίου Δημήτριος | 6 |
| 3061 | Βασιλάκης Νικόλαος | 8 |
| 3067 | Βλαχογιάννη Μαρία-Όλγα | 8 |
| 3068 | Βονιτσάνου Μαρία-Αλεξάνδρα | 6 |
| 3072 | Γερακιός Κώστας | 9.5 |
| 3091 | Δομένικου Αικατερίνη | 6.5 |
| 3092 | Δούβρης Αριστείδης | 6 |
| 3095 | Ζαγγανά Ελένη | 5.5 |
| 3102 | Καλοφωλιάς Γιάννης | 8.5 |
| 3119 | Κίσσα Μαρία | 6 |
| 3126 | Κόρδαρης Ιωάννης | 6 |
| 3128 | Κουκουλέτσος Δημήτρης | 8 |
| 3132 | Κουτσουπιά Μαργαρίτα | 7 |
| 3149 | Μαρίνος Ηλίας | 7.5 |
| 3179 | Ντάσιος Βαγγέλης | 5.5 |
| 3186 | Παπαπαναγιώτου Βασίλης | 9.5 |
| 3202 | Πουλημένος Προκόπιος | 7.5 |
| 3204 | Πυργέλης Απόστολος | 6.5 |
| 3221 | Σταμάτης Απόστολος | 9 |
| 3223 | Στάμου Σπύρος | 8 |
| 3236 | Τσώτας Σωτήριος | 6 |
| 3248 | Χατζηπρίμου Κλεοπάτρα | 5.5 |
| 3251 | Ανδρέου Ανδρέας | 8.5 |
| 3253 | Ηλιάδης Σωκράτης | 6.5 |
| 3255 | Σαββίδης Γρηγόρης | 7.5 |
| 3256 | Πασχαλίδης Χαράλαμπος | 8.5 |
| 3257 | Δημοσθένους Γιώργος | 5.5 |
| 3275 | Γεωργίου Δημήτριος | 6 |
| 3278 | Οικονόμου Γεώργιος | 7.5 |
| 3296 | Λιβαθινός Σπύρος | 3 |
| 3305 | Πίκουλας Γρηγόριος | 7 |
| 3312 | Ιωαννίδης Ιωάννης | 7 |
| 3316 | Κουτσουρίδης Χάρης | 8.5 |
| 3343 | Αντωνίου Μαρία | 7.5 |
| 3352 | Γεροσταμούλος Αθανάσιος | 9 |
| 3371 | Ευσταθίου Διονύσης | 9.5 |
| 3376 | Θηραιού Μαρία-Ειρήνη | 8 |
| 3385 | Καλοφωλιάς Βασίλης | 9.5 |
| 3408 | Κουρνούτου Μαρία | 6.5 |
| 3424 | Λούκας Ανδρέας | 10 |
| 3447 | Μπούσης Δημήτρης | 3 |
| 3451 | Νάφας Αλέξανδρος | 8.5 |
| 3476 | Πουλοκέφαλος Νικόλαος | 8 |
| 3488 | Σπύρου Δήμητρα | 9 |
| 3507 | Τσολάκος Λάμπρος | 5 |
| 3531 | Μαλλιαρός Φραγκίσκος | 9 |
| 3544 | Βούρκος Ανδρέας | 9.5 |
| 3545 | Αντωνίου Αθανάσιος | 7.5 |
| 3552 | Μάρκου Μάριος | 7.5 |
| 3555 | Πιερής Χρίστος | 5.5 |
