Μονάδα:
Τμήμα Πληροφορικής & ΤηλεπικοινωνιώνΠληροφορική
Ημερομηνία κατάθεσης:
2024-01-22
Στοιχεία επιβλεπόντων καθηγητών:
Χρήστος Τζάμος, Αναπληρωτής Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ
Πρωτότυπος Τίτλος:
Prophet Inequality Problem: A Comprehensive Analysis of Research and Findings
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Το Πρόβλημα της Ανισότητας του Προφήτη: Μία Επισκόπηση της Έρευνας και των Αποτελεσμάτων
Περίληψη:
Αυτή η πτυχιακή διερευνά το Πρόβλημα της Ανισότητας του Προφήτη στα πεδία της Θεωρίας Βέλτιστης Διακοπής και του Σχεδιασμού Μηχανισμών, στοχεύοντας σε μια ολοκληρωμένη ανάλυση των θεμελιωδών εννοιών και της επιρροής του στη σύγχρονη διαδικασία λήψης αποφάσεων. Το πρόβλημα παρουσιάστηκε από τους Krengel και Sucheston στη δεκαετία του 1970, και περιστρέφεται γύρω από έναν παίκτη που συναντά μια ακολουθία αντικειμένων με αξίες που προκύπτουν ανεξάρτητα από γνωστές κατανομές. Με την άφιξη του κάθε στοιχείου, η αξία του αποκαλύπτεται και ο παίκτης είτε το αποδέχεται και το παιχνίδι τελειώνει, είτε το απορρίπτει αμετάκλητα και συνεχίζει στο επόμενο αντικείμενο. Στόχος είναι η μεγιστοποίηση της αξίας του επιλεγμένου στοιχείου και ο ανταγωνισμός με την αναμενόμενη μέγιστη τιμή όλων των αντικειμένων. Στην παρούσα πτυχιακή παρέχουμε αρχικά μια επισκόπηση των βασικών εννοιών της βέλτιστης θεωρίας διακοπής, του σχεδιασμού μηχανισμών, των μηχανισμών τιμών και των διαφόρων στατιστικών εργαλείων και μετρικών που είναι απαραίτητα για την αξιολόγηση αλγορίθμων. Στη συνέχεια, παρουσιάζουμε τα ευρήματα που σχετίζονται με την μεγιστοποίηση του κέρδους, και την ελαχιστοποίηση του κόστους, επισημαίνoντας τις δυσκολίες αυτής. Η ανάλυση επεκτείνεται σε διάφορες παραλλαγές του προβλήματος, όπως ταίριασμα, πολλαπλές επιλογές και μητροειδής ανισότητα του προφήτη. Ειδικότερα, δόθηκε έμφαση στην κατανόηση του προβλήματος του προφήτη γραμματέα και της περίπτωσης όπου οι αξίες των αντικειμένων προέρχονται από άγνωστες κατανομές.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λέξεις-κλειδιά:
Online αλγόριθμοι, Ανισότητα του προφήτη, Σχεδιασμός μηχανισμού, Βέλτιστη θεωρία διακοπής, Θεωρία Παιγνίων
Αρ. σελίδων ευρετηρίου:
5
Αρ. βιβλιογραφικών αναφορών:
39
