E-Locus - Ιδρυματικό Καταθετήριο Πανεπιστημίου Κρήτης - Μεταπτυχιακές εργασίες ειδίκευσης

Αρχική Συλλογές Σχολή/Τμήμα Σχολή Θετικών και Τεχνολογικών Επιστημών Τμήμα Μαθηματικών και Εφαρμοσμένων Μαθηματικών Μεταπτυχιακές εργασίες ειδίκευσης

Μεταπτυχιακές εργασίες ειδίκευσης

Εντολή Αναζήτησης : Συγγραφέας="Πλατής" Και Συγγραφέας="Ιωάννης"

Τρέχουσα Εγγραφή: 3 από 125

[Προσθήκη στο καλάθι]

Κωδικός Πόρου

000464368

Τίτλος

Μέθοδοι κοσκινίσματος

Άλλος τίτλος

Sieve methods

Συγγραφέας

Αθανασίου, Δημήτριος-Μάριος

Σύμβουλος διατριβής

Τζανάκη, Ελένη

Περίληψη

΄Οταν στην συνδυαστική αναφερόμαστε σε απαρίθμηση με τη μέθοδο κοσκινίσματος (sieve method), εννοούμε την διαδικασία με την οποία μετράμε τον πληθάριθμο ενός συνόλου S ξεκινώντας απο ένα μεγαλύτερο σύνολο και στη συνέχεια αφαιρούμε τα στοιχεία που δεν θέλουμε. Αυτή η διαδικασία μπορεί να χωριστεί σε δύο βασικές περιπτώσεις. Η πρώτη είναι η γνωστή μέθοδος εγκλεισμού-αποκλεισμού στην οποία προσεγγίσουμε την ζητούμενη απαρίθμηση μετρώντας κάτι μεγαλύτερο, μετά αφαιρούμε μία προσέγγιση των επιπλέον στοιχείων της απαρίθμησης και επανα- λαμβάνουμε τη διαδικασία όσες φορές χρειαστεί μέχρι να διορθώσουμε το ‘‘λάθος’’ της απόκλισης. Η δεύτερη μέθοδος αφορά και πάλι την απαρίθμηση ενός μεγαλύτερου συνόλου S′, με τη διαφόρα ότι τώρα στα στοιχεία του έχουμε θεωρήσει μία συνάρτηση βάρους. Η συνάρτηση βάρους ορίζεται με ‘‘φυσιολογικό’’ τρόπο που σχετίζεται με την συνδυαστική του προβλήματος και είναι επιλεγμένη έτσι ώστε αθροίζοντας όλα τα βεβαρυμένα στοιχεία του S′, να προκύπτουν απλοποιήσεις οι οποίες εν τέλει μας οδηγούν στη ζητούμενη απαρίθμηση. Η εργασία έχει την εξής δομή. Στο Κεφάλαιο 1 διατυπώνουμε την αρχή εγκλεισμού αποκλει- σμού στην γενική της μορφή. Στη συνέχεια παρουσιάζουμε μία ειδική περίπτωση στην οποία η μέθοδος παίρνει τη μορφή ορίζουσας. Πιο συγκεκριμένα, μελετάμε την απαρίθμηση του συνόλου των μεταθέσεων με βάση το σύνολο καθόδων, και στη συνέχεια την ακόμα πιο ειδική περίπτωση όπου θεωρούμε τις μεταθέσεις με βάση το σύνολο καθόδων και το πλήθος αντιστροφών. Στο Κεφάλαιο 2 μελετάμε περιπτώσεις μεταθέσεων στις οποιές έχουμε περιρισμούς ‘‘θέσεων’’. Το απλούστερο παράδειγμα είναι η περίπτωση των μεταθέσεων χωρίς σταθερά σημεία (derangements), η αμέσως επόμενη γενίκευση είναι γνωστή ως probl`eme des m´enages και τέλος ορίζουμε γενικά το σύνολο των k-ασύμφωνων μεταθέσεων. Για k = 1 και 2, οι k-ασύμφωνες μεταθέσεις ανάγονται στα δύο προβλήματα που αναφέραμε, derangements και menages αντίστοιχα. Στο Κεφάλαιο 3 παρουσίαζουμε μία μέθοδο λύσης του προβλήματος των k-ασύμφωνων μεταθέσε- ων, η οποιά εμπλέκει κατευθυνόμενα γραφήματα, πίνακες γειτνίασης και γραμμική αλγεβρα. Η μέθο- δος αυτή είναι γνωστή ως transfer matrix method και μετατρέπει το πρόβλημα των k-ασύμφωνων μεταθέσεων σε πρόβλημα καταμέτρησης κλειστών μονοπατιών σε κατευθυνόμενο γραφημα. Στο Κεφάλαιο 4 μελετάμε την μέθοδο της αυτοαντίστροφης απεικόνισης και δίνουμε κάποια κλασικά παραδείγματα. Στη συνέχεια παρουσιάζουμε μία πολύ ενδιαφέρουσα εφαρμογή, η οποία μετράει μή τεμνόμενα μονοπάτια σε γραφήματα.

Φυσική περιγραφή

43 σ. ; : ; 30 εκ.

Γλώσσα

Ελληνικά, Αγγλικά

Θέμα

Combinatorics

Discordant permutations

Inclusion -exclusion

Transfer matrix method

Ασύμφωνες μεταθέσεις

Αυτοαντίστροφη απεικόνιση

Εγκλεισμός-αποκλεισμός