Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/13241
Τίτλος: | Αλγόριθμοι Τοπικού Υπολογισμού Και Εφαρμογές Τους |
Συγγραφείς: | Ματίκας Γεώργιος Φωτάκης Δημήτριος |
Λέξεις κλειδιά: | local computation algorithms sublinear algorithms maximal independent set hypergraph 2-coloring mechanism design algorithms and complexity |
Ημερομηνία έκδοσης: | 9-Σεπ-2016 |
Περίληψη: | Τα τελευταια χρονια παρατηρειται το φαινομενο τα συνολα δεδομενων που δινονται ως εισοδοι σε αλγοριθμους προς επεξεργασια να ειναι ασυλληπτα μεγαλα. Λογικο ειναι, λοιπον, ο χρονος που θα κανει ο αλγοριθμος να τα επεξεργαστει να ειναι εξισου πολυς. Πολλες φορες, ομως, χρειαζομαστε τα αποτελεσματα σε συντομο χρονικο διαστημα ωστε να παρουμε αμεσα καποια αποφαση. Γι' αυτο και το ενδιαφερον εχει στραφει πλεον προς τους αλγοριθμους που τρεχουν σε υπογραμμικο χρονο σε σχεση με το μεγεθος της εισοδου. Στην περιπτωση που δεν μας ενδιαφερει ολοκληρη η λυση του προβληματος, αλλα αρκουμαστε σε ενα μικρο μερος αυτης καθε φορα, μπορουμε να χρησιμοποιησουμε εναν αλγοριθμο τοπικου υπολογισμου οι οποιοι παρουσιαζονται στην εργασια αυτη. Παρουσιαζονται δυο παραλληλοι αλγοριθμοι που τρεχουν σε υπογραμμικο χρονο. Στη συνεχεια δινονται αλγοριθμοι τοπικου υπολογισμου για αρκετα σημαντικα γραφοθεωρητικα προβληματα που βασιζονται στους προηγουμενους, και συγκεκριμενα για τα προβληματα του maximal independent set, του 2-χρωματισμου υπεργραφου και του maximal matching. Συζητουνται, επισης, εφαρμογες αυτου του ειδους αλγοριθμων σε διαφορες περιοχες της Επιστημης Υπολογιστων, οπως ο Σχεδιασμος Μηχανισμων και το Probabilistic Inference. |
URI: | http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/13241 |
Εμφανίζεται στις συλλογές: | Διπλωματικές Εργασίες - Theses |
Αρχεία σε αυτό το τεκμήριο:
Αρχείο | Μέγεθος | Μορφότυπος | |
---|---|---|---|
DT2016-0224.pdf | 2.26 MB | Adobe PDF | Εμφάνιση/Άνοιγμα |
Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.