Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14094
Title: Άμεσοι Αλγόριθμοι
Authors: Σπυρίδων Ρ. Αντωνακόπουλος
Ζάχος Ευστάθιος
Keywords: άμεσοι αλγόριθμοι
ανταγωνιστική ανάλυση
k-εξυπηρετητές
σελιδοποίηση
πιθανοτικές εμφυτεύσεις
Issue Date: 21-Jul-2004
Abstract: Η παρούσα διπλωματική εργασία εστιάζει στην ερευνητική περιοχή των άμεσων (online) αλγορίθμων, δηλαδή εκείνων που καλούνται να επιλύσουν ένα πρόβλημα βελτιστοποίησης δίχως να έχουν εκ των προτέρων γνώση όλων των σχετικών δεδομένων. Στο πρώτο κεφάλαιο ορίζονται οι βασικές έννοιες της ανταγωνιστικής ανάλυσης, η οποία αποτελεί το πλέον κοινά αποδεκτό κριτήριο αξιολόγησης της επίδοσης άμεσων αλγορίθμων. Ως παράδειγμα εφαρμογής των προηγουμένων, μελετώνται διεξοδικά δύο κλασικά online προβλήματα. Το δεύτερο κεφάλαιο πραγματεύεται τεχνικές σχεδίασης αιτιοκρατικών άμεσων αλγορίθμων. Μάλιστα, έμφαση δίνεται στο σκεπτικό που υποκρύπτεται πίσω από καθεμία τεχνική, το οποίο συνήθως διατυπώνεται ως κάποια «αρχή». Επιπλέον, εξετάζονται οι κυριότερες μέθοδοι ανάλυσης online αλγορίθμων, οι οποίες έχουν χρησιμοποιηθεί ευρέως στη σχετική βιβλιογραφία. Το τρίτο κεφάλαιο ασχολείται με randomized άμεσους αλγορίθμους, οι οποίοι παρουσιάζουν εξαιρετικό ενδιαφέρον διότι η αναμενόμενη επίδοσή τους ως προς την ανταγωνιστική ανάλυση είναι καλύτερη εκείνης των αντίστοιχων αιτιοκρατικών. Τέλος, το τέταρτο κεφάλαιο εστιάζει στο διάσημο πρόβλημα των k-εξυπηρετητών. Συγκεκριμένα, παρατίθενται, αναλύονται και συγκρίνονται ορισμένοι από τους πιο γνωστούς αλγορίθμους που έχουν προταθεί για το πρόβλημα αυτό. Περιγράφεται επίσης η γενικότερη μέθοδος κατασκευής νέων τέτοιων αλγορίθμων μέσω αιτιοκρατικών και ιδίως πιθανοτικών εμφυτεύσεων μετρικών χώρων.
URI: http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14094
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File Description SizeFormat 
DT2004-0136.ps1.14 MBPostscriptView/Open
DT2004-0136.pdf960.78 kBAdobe PDFView/Open


Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.