Μεταπτυχιακές εργασίες ειδίκευσης
Τρέχουσα Εγγραφή: 48 από 127
|
Κωδικός Πόρου |
000439132 |
Τίτλος |
Monotone paths on polytopes |
Άλλος τίτλος |
Μονότονα μονοπάτια σε πολύτοπα |
Συγγραφέας
|
Αποστολάκης, Σήφης
|
Σύμβουλος διατριβής
|
Τζανάκη, Ελένη
|
Μέλος κριτικής επιτροπής
|
Κολουντζάκης, Μιχαήλ
Φραντζικινάκης, Νικόλαος
|
Περίληψη |
Η εργασία αυτή αποτελείται από τρία μέρη. Το πρώτο μέρος, Κεφάλαιο 1, περιέχει μία σύντομη εισαγωγή σε κυρτά πολύτοπα, καθώς και διάφορους βασικους ορισμους. Πιο συγκεκριμένα, δίνουμε τους δύο ισοδύναμους ορισμούς ενός κυρτού πολυτόπου. Συνεχίσουμε με μία συντομη αλγοριθμική προσέγγιση και τέλος παρουσιαζουμε μερικά παραδείγματα ορισμένων ευρέως γνωστών πολυτόπων. Στο δεύτερο μέρος, Κεφάλαιο 2, προυσιάζουμε και αποδεικνύουμε τρία σημαντικά και πολυ γνωστά αποτελέσματα στην θεωρία πολυτόπων: τον τύπο του Euler, καθώς και τα θεωρήματα μεγίστου και ελαχίστου φράγματος (πάνω στον αριθμό όψεων) σε πολύτοπα. Τέλος, στο Κεφάλαιο 3, παραθέτουμε μέρος των αποτελεσμάτων ενός προσφατου άρθρου, των Χ. Α. Αθανασιάδη, J. De Loera και Z. Zhang[3]. Πιο συγκεκριμένα, επιλύουμε κάποια αριθμητικά προβλήματα, η φύση των οποίων σχετίζεται με την καταμέτρηση μονότονων μονοπατιών και υπογραφημάτων του γραφήματος ενός πολυτόπου, δομές οι οποίες είναι στενά συνδεδεμένες με τον γραμμικό προγραμματισμό και τον αλγόριθμο simplex. Στο πρώτο μέρος του κεφαλαίου ασχολούμαστε με το πρόβλημα υπολογισμού ελαχίστου και μεγίστου αριθμού μονότονων μονοπατιών στο προσανατολισμένο γράφημα ενός πολυτόπου, ο προσανατολισμός του οποίου προκύπτει μέσω μίας γραμμικής συνάρτησης, σε γενική θέση σχετικά με το πολύτοπο. Στη συνέχεια, μελετάμε τα δενδρώματα (f-arborescenses), δηλαδή άκυκλα υπογραφήματα του προσανατολισμένου γραφήματος ενός πολυτόπου. Ο υπολογισμός φραγμάτων για τον αριθμό των δενδρωμάτων, μας παρέχει μία εκτίμηση σχετικά με το μέγεθος του αλγορίθμου simplex. Θα θέλαμε να ευχαριστήσουμε τον Χρήστο Αθαναδιάδη ο οποίος μας διέθεσε μια προκαταρκική μορφή του άρθρου [3].
|
Φυσική περιγραφή |
55 σ. ; : ; 30 εκ. |
Γλώσσα |
Αγγλικά |
Θέμα |
Geometry |
|
Graph-theory |
|
Γεωμετρία |
|
Θεωρία γραφημάτων |
Ημερομηνία έκδοσης |
2021-03-26 |
Συλλογή
|
Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Μαθηματικών και Εφαρμοσμένων Μαθηματικών--Μεταπτυχιακές εργασίες ειδίκευσης
|
|
Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
|
Μόνιμη Σύνδεση |
https://elocus.lib.uoc.gr//dlib/0/1/8/metadata-dlib-1618225747-312054-4229.tkl
|
Εμφανίσεις |
988 |