Polytope Membership in High Dimension

Διπλωματική Εργασία uoadl:1672490 459 Αναγνώσεις

Μονάδα:
Κατεύθυνση Λογική και Θεωρία Αλγορίθμων και Υπολογισμού
Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2017-06-19
Έτος εκπόνησης:
2017
Συγγραφέας:
Αναγνωστόπουλος Ευάγγελος
Στοιχεία επιβλεπόντων καθηγητών:
Ιωάννης Εμίρης, Καθηγητής, τμήμα Πληροφορικής, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Δημήτρης Γουνόπουλος, Καθηγητής, τμήμα Πληροφορικής, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Βασίλης Ζησιμόπουλος, Καθηγητής, τμήμα Πληροφορικής, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Πρωτότυπος Τίτλος:
Polytope Membership in High Dimension
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Έλεγχος Μέλους σε Πολύτοπα Υψηλής Διάστασης
Περίληψη:
Τα πολύτοπα σε προβλήματα βελτιστοποίησης και δειγματοληψίας δίνονται συνήθως από μια έμμεση αναπαράσταση μέσω μιας μηχανής οracle. Η πιο βασική μηχανή oracle είναι ο έλεγχος μέλους σε πολύτοπα που μπορεί να απαντήσει στο αν ένα σημείο επερώτησης q βρίσκεται μέσα στο P ή όχι, και χρησιμοποιείται συχνά ως βάση για πιο σύνθετες μηχανές oracle, όπως η μηχανή oracle διαχωρισμού και η μηχανή oracle συνόρου. Σε αυτή τη δουλειά στοχεύουμε στο σχεδιασμό, στην υλοποίηση και στην ανάλυση αλγορίθμων για μια προσεγγιστική μηχανή oracle για τον έλεγχο μέλους σε πολύτοπα που δίνονται ως η τομή ημιχώρων σε υψηλή διάσταση, ανταλλάσσοντας ακρίβεια για ταχύτητα.
Προηγούμενες απόπειρες βασίζονταν σε κλασικές τεχνικές προσέγγισης πολυτόπων που έχουν όμως εκθετική εξάρτηση στη διάσταση και είναι ως εκ τούτου μη αποδοτικές σε υψηλή διάσταση. Αποδεικνύουμε μια ευθεία αναγωγή από το πρόβλημα του προσεγγιστικού έλεγχου μέλους σε πολύτοπα στο πρόβλημα του προσεγγιστικού πλησιέστερου γείτονα σε σημεία και αποκτούμε έτσι πολυωνυμικά, ως προς τη διάσταση, όρια στη πολυπλοκότητα, εκμεταλλευόμενοι πρόσφατη πρόοδο στη πολυπλοκότητα της αναζήτησης του πλησιέστερου γείτονα. Στη συνέχεια χρησιμοποιούμε τη νέα δομή για έλεγχο μέλους σε πολύτοπα για να αποκτήσουμε μια λύση για το oracle συνόρου σε υψηλή διάσταση. Τέλος, αναλύουμε τους αλγορίθμους μας πειραματικά και παραθέτουμε τα αποτελέσματα.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λοιπές θεματικές κατηγορίες:
Αλγόριθμοι υπολογιστών
Λέξεις-κλειδιά:
πολύτοπο,υψηλή διάσταση
Ευρετήριο:
Ναι
Αρ. σελίδων ευρετηρίου:
1
Εικονογραφημένη:
Ναι
Αρ. βιβλιογραφικών αναφορών:
19
Αριθμός σελίδων:
34
MscAnagnostopoulos.pdf (812 KB) Άνοιγμα σε νέο παράθυρο