Please use this identifier to cite or link to this item: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/16811
Full metadata record
DC FieldValueLanguage
dc.contributor.authorΗλιόπουλος Φώτης
dc.date.accessioned2018-07-23T19:07:03Z-
dc.date.available2018-07-23T19:07:03Z-
dc.date.issued2014-1-13
dc.date.submitted2014-1-10
dc.identifier.urihttp://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/16811-
dc.description.abstractΣκοπός της διπλωματικής αυτής εργασίας είναι η μελέτη, η ανάλυση και η σχεδίασηπιθανοτικών αλγορίθμων τοπικής αναζήτησης για διακριτά προβλήματα περιορισμώνμε μεθόδους και τεχνικές που χρησιμοποιήθηκαν για την αλγοριθμική απόδειξη του"Lovasz Local Lemma". Συγκεκριμένα, θεωρούμε αλγορίθμους της εξής μορφής:- Αρχισε από μία τυχαία ανάθεση τιμών στις μεταβλητές του προβλήματος περιο-ρισμών.- Οσο υπάρχουν διαψευδούμενοι περιορισμοί, χρησιμοποίησε μια τυχαιοκρατικήδιαδικασία για να διαλέξεις έναν διαψευδούμενο περιορισμό c καθώς και νέεςτιμές για τις μεταβλητές τουΤόσο για την επιλογή του περιορισμού c όσο και για την επιλογή των τιμών στιςμεταβλητές του, υπάρχει πληθώρα ευρεστικών, αλλά όχι πολλά για να τις διαφορο-ποιήσουν πέρα από πειράματα. Στο paper του R. Moser για την κατασκευαστικήαπόδειξη του Lovasz Local Lemma στο STOC ’09 η επιλογή του c είναι αυθαίρετηενώ η επιλογή της ανάθεσης τιμών στις μεταβλητές γίνεται τυχαία και ομοιόρφα. Οτερματισμός του αλγορίθμου αποδεικνύεται δείχνοντας ότι μη τερματισμός θα σήμαινεκαθολική κωδικοποίηση ( universal compression ). Τόσο στη δουλειά του Moser όσοκαι στις μετέπειτα δουλειές, μια βασική απαίτηση είναι ότι θα πρέπει να υπάρχει έναπιθανοτικό μέτρο - γινόμενο (product measure) επί των μεταβλητών του προβλήματοςέτσι ώστε κάθε φορά που επαναδειγματοληπτούμε τις μεταβλητές ενός περιορισμο-ύ, οι τιμές που θα τις αναθέσουμε θα πρέπει να προκύπτουν μέσω ( της προβολήςτου) πιθανοτικού μέτρου ( στις μεταβλητές του περιορισμού). Αυτό έρχεται σε έντονηαντίθεση με τους αλγορίθμους της πράξης στους οποίους οι τιμές που δίνουμε στιςμεταβλητές εξαρτώνται από το πώς ο περιορισμός για τις μεταβλητές του οποίου δια-λέγουμε τιμές συσχετίζεται με τους γείτονές του, τόσο στατικά ( από τις μεταβλητέςπου μοιράζονται), όσο και " δυναμικά", δηλαδή από την τωρινή "κατάσταση" αυτώντων περιορισμών.Στην παρούσα διπλωματική δείχνουμε μία μέθοδο για να απαλλαχθεί κανείς από αυ-τή την απαίτηση. Συγκεκριμένα, δείχνουμε ότι η μέθοδος του Moser, δηλαδή το ναφράξουμε τον αριθμό των πιθανών άκαρπων τροχιών του αλγορίθμου χρησιμοποιών-τας ιδιότητες της εισόδου, για παράδειγμα το μέγιστο βαθμό του γράφου εξάρτησης,παραμένει πλήρως λειτουργική ακόμα και με την απουσία ενός πιθανοτικού μέτρου,δηλαδή όταν κάθε περιορισμός επιτρέπεται να αλλάξει τις μεταβλητές του με έναν "ιδιωτικό " τρόπο και στην πραγματικότητα, λαμβάνοντας υπόψιν τις τρέχουσες τιμέςτων μεταβλητών των γειτονικών περιορισμών. Επιπρόσθετα, παρατείθενται ορισμέναβιβλιογραφικά στοιχεία αναφορικά με τις αλγοριθμικές επεκτάσεις του Lovasz LocalLemma και μερικές αποδείξεις/ βελτιώσεις υπάρχοντων αποτελεσμάτων χρησιμποιών-τας την "εντροπική μέθοδο " του R. Moser.
dc.languageEnglish
dc.subjectprobabilistic method
dc.subjectentropic method
dc.subjectincompressibility method
dc.subjectlovasz local lemma
dc.subjectconstructive proof
dc.subjectentropic potential
dc.subjectrandomized algorithms
dc.subjectcompression
dc.subjectentropy
dc.subjectsource coding
dc.titleΑλγόριθμοι Εμπνευσμένοι Από Το Τοπικό Λήμμα Του Lovasz (algorithms Inspired By The Lovasz Local Lemma)
dc.typeDiploma Thesis
dc.description.pages66
dc.contributor.supervisorΖάχος Ευστάθιος
dc.departmentΤομέας Τεχνολογίας Πληροφορικής & Υπολογιστών
dc.organizationΕΜΠ, Τμήμα Ηλεκτρολόγων Μηχανικών & Μηχανικών Υπολογιστών
Appears in Collections:Διπλωματικές Εργασίες - Theses

Files in This Item:
File SizeFormat 
DT2014-0047.pdf550.84 kBAdobe PDFView/Open


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