Μονάδα:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2015-05-06
Συγγραφέας:
Νέμπαρης Ιωάννης
Στοιχεία επιβλεπόντων καθηγητών:
Άρης Παγουρτζής Αναπλ. Καθηγητής (Επιβλέπων), Στάθης Ζάχος Καθηγητής, Δημήτρης Φωτάκης Επίκ. Καθηγητής
Πρωτότυπος Τίτλος:
Counting complexity: compressed Ηamming distance, vertex covers and recent highlights
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Μετρητική πολυπλοκότητα: συμπιεσμένη απόσταση Hamming, καλύμματα κορυφών και πρόσφατα επιτεύγματα
Περίληψη:
Σε αυτήν την εργασία αντιμετωπίζουμε το πρόβλημα της συμπιεσμένης απόστασης
Hamming. Η απόσταση Hamming είναι ένα εύκολο πρόβλημα, ωστόσο όταν τα δεδομένα
εισόδου είναι τεράστιου μεγέθους, χρειαζόαμστε μια συμπίεσή τους για να
μπορέσουμε να δημιουργήσουμε αποδωτικούς αλγορίθμους. Σ' αυτήν την εργασία
δίνουμε δύο αλγορίθμους για το πρόβλημα σε πιο γενικές και πιο συγκεκριμένες
περιπτώσεις. Εν συνεχεία ασχολούμαστε με την μέτρηση καλυμμάτων κορυφών σε
γραφηματα μονοπάτια,κύκλους και δένδρα και αναπτύσουμε περαιτέρω αλγορίθμους
μέτρησης. Τέλος αναφερόμαστε σε μεγάλα αποτελέσματα των τελευταίων ετών στον
τομέα.
Λέξεις-κλειδιά:
Συμπιεσμένη απόσταση Hamming, Καλύμματα κορυφών, Αποδοτικοί Αλγόριθμοι, Μέτρηση, Πολυπλοκότητα
Αρ. σελίδων ευρετηρίου:
2
Αρ. βιβλιογραφικών αναφορών:
30
