1. Αρχική σελίδα
  2. Αναζήτηση

Τεχνικές Σχεδίασης και Ανάλυσης Άμεσων Αλγορίθμων για Προβλήματα σε Μετρικούς Χώρους

Το τεκμήριο παρέχεται από τον φορέα :
Εθνικό Μετσόβιο Πολυτεχνείο   

Αποθετήριο :
Ψηφιακό Αποθετήριο της Κεντρικής Βιβλιοθήκης του ΕΜΠ | Dspace@NTUA   

δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*



Τεχνικές Σχεδίασης και Ανάλυσης Άμεσων Αλγορίθμων για Προβλήματα σε Μετρικούς Χώρους (EL)
Techniques for Design and Analysis of Algorithms for Metric Spaces Problems (EN)
Νάκος, Βασίλειος Δ. (EL)
Nakos, Vasileios D. (EN)
Φωτάκης, Δημήτριος (EL)
Ζάχος, Ευστάθιος (EL)
Παγουρτζής, Άρης (EL)
bachelorThesis
2013-01-25T09:02:46Z
2012-11-05
2012-11-19
2013-01-25
73 σ. (EL)
Βασίλειος Δ. Νάκος (EL)
Στη συγκεκριμένη διπλωματική μελετάμε προβλήματα άμεσων αλγορίθμων και τεχνικές σχεδίασης και ανάλυσης τους, κυρίως σε μετρικούς χώρους, χώρους δηλαδή όπου ισχύει η τριγωνική ανισότητα. Άμεσος λέγεται ένας αλγόριθμος όταν δεν έχουμε διαθέσιμη όλο την είσοδο από την αρχή, αλλά πρέπει να πάρουμε αποφάσεις με έλλειψη πληροφορίας. Πιο συγκεκριμένα, μελετάμε το πρόβλημα του "κ-Εξυπηρετητή" και τον πρόσφατο αλγόριθμο που είναι πολυλογαριθμικό στο πλήθος των εξυπηρετητών και των απαιτήσεων. Παράλληλα, εξετάζουμε τεχνικές σχεδίασης αποδοτικών κλασματικών άμεσων αλγορίθμων με δύο μεθόδους : με καθαρά συνδυαστικά επιχείρηματα και μέσω του δυϊκου - πρωτεύοντας. Τέλος, έξετάζουμε δύο καινούρια προβλήματα, το "Eπαυξητικό Aκτινοάθροισμα Συστάδων" και το "Άμεση Κινητή Χωροθέτηση Υπηρεσιών" και δίνουμε κάποια αποτελέσματα σε γενικούς μετρικούς χώρους αλλά και σε κάποιες ειδικές περιπτώσεις. (EL)
In this diploma thesis we study online problems and techniques for design and analysis for them, mainly in metric spaces, where the triangle inequality holds. Online is called an algorithm when the input is not available to it from the beggining, but we must make a decision with less information. More specifically,we study the k-server problem and the recent algorithm that is polylogarithmic in the number of demands and the number of servers. Moreover, we study techniques of design and analysis of online algorithm with two methods: with purely combinatorial methods and via a primal-dual approach. Last but not least, we also study two new problem, Incremental Sum-Raddii Clustering and Online Mobile Facility Location, where we give some results in general metric spaces and in some special occasions. (EN)
Εξυπηρετητής (EL)
Κλασματικός (EL)
Χωροθέτηση υπηρεσιών (EL)
Πρωτεύων (EL)
Μετρικός χώρος (EL)
Άμεσος αλγόριθμος (EL)
Δυϊκός (EL)
Συνδυαστικός (EL)
Facility location (EN)
Metric space (EN)
Server (EN)
Combinatorial (EN)
Online algorithm (EN)
Fractional (EN)
Primal (EN)
Dual (EN)
Εθνικό Μετσόβιο Πολυτεχνείο. Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών. Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών. Εργαστήριο Λογικής και Επιστήμης Υπολογιστών. (EL)
ETDFree-policy.xml (EN)
Εθνικό Μετσόβιο Πολυτεχνείο
Ψηφιακό Αποθετήριο της Κεντρικής Βιβλιοθήκης του ΕΜΠ | Dspace@NTUA
Κεντρική Βιβλιοθήκη Ε.Μ.Π.
Ιδρυματικό Αποθετήριο
Διπλωματικές Εργασίες



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.