.
Η συνδυαστική είναι κλάδος των μαθηματικών που ασχολείται με τη μελέτη των πεπερασμένων και των άπειρων αλλά μετρήσιμων διακριτών δομών. Πτυχές με τις οποίες ασχολείται η συνδυαστική περιλαμβάνουν την καταμέτρηση των δομών ενός δεδομένου είδους και μεγέθους( απαριθμήσιμη συνδυαστική), την απόφαση πότε μπορούν να πληρούν ορισμένα κριτήρια, την κατασκευή και την ανάλυση των αντικειμένων που πληρούν τα κριτήρια(όπως τα συνδυαστικά σχέδια και την θεωρία Μάτροϊντ ) την εύρεση "μεγαλύτερου", "μικρότερου" ή "βέλτιστου" αντικειμένου (συνδυαστική extremal και συνδυαστική βελτιστοποίησης) και την μελέτη συνδυαστικών δομών που προκύπτουν σε ένα αλγεβρικό πλαίσιο ή ερφαμόζοντας αλγεβρικές τεχνικές σε προβλήματα συνδυαστικής (αλγεβρική συνδυαστική).
Προβλήματα συνδιαστικής προκύπτουν σε πολλές περιοχές των καθαρών μαθηματικών, ιδίως στην άλγεβρα,θεωρία πιθανοτήτων,τοπολογία και την γεωμετρία και η συνδυαστική έχει επίσης πολλές εφαρμογές στη μαθηματική βελτιστοποίηση, επιστήμη των υπολογιστών, ergodic θεωρία και στατιστική φυσική. Πολλές ερωτήσεις συνδυαστικής ιστορίκα έχουν εξεταστεί μεμονωμένα, δίνοντας μια ad hoc λύση σε ένα πρόβλημα που ανακύπτει σε κάποιο μαθηματικό πλαίσιο. Μετά τον εικοστό αιώνα, ωστόσο έχουν ανατπυχθεί ισχυρές και γενικά θεωρητικές μέθοδοι,καθιστώντας την συνδυαστική ανεξάρτητο κλάδο των μαθηματικών από μόνη της, Ένα από τα παλαιότερα και πιο προσβάσιμα μέρη της συνδυαστικής είναι η θεωρία γραφών, η οποία έχει επίσης πολλές φυσικές συνδέσεις με άλλες περιοχές. Η συδυαστική χρησιμοποίειται συχνά στην επιστήμη των υπολογιστών για την απόκτηση φόρμουλων και εκτιμήσεων για την ανάλυση των αλγορίθμων.
Ιστορία
Βασικές έννοιες συνδυαστικής και απαριθμλησιμων αποτελεσμάτων εμφανίστηκαν σε όλο τον αρχαίο κόσμο. Τον 6ο αιώνα π.Χ., η αρχαία ινδή γιατρός Sushruta ισχυρίστηκε στο Sushruta Samhita οτι 63 συνδυασμοί μπορούν να γίνουν από 6 διαφορετικές γεύσεις, λαμβάνοντας μια φορά, δύο φορές σε έναν χρόνο κλπ. ,υπολογίζοντας έτσι όλες 26-1 δυνατότητες. Ο έλληνας ιστορίκος Πλούταρχος συζήτησε ένα επιχείρημα μεταξύ Χρύσιππου(3ο αιώνα π.Χ) και Ίππαρχου(2ο αιώνα π.Χ) από ένα αρκετά λεπτό απαριθμήσιμο πρόβληνα, το οποίο αργότερα φαίνεται ότι σχετίζεται οι Schröder αριθμοί. Στο Οστομάχιον, ο Αρχιμήδης(3ος αιώνας π.Χ) θεωρεί μια πλακόστρωση παζλ.
Κατά τον Μεσαίωνα, η Συνδυαστική συνέχισε να μελετάται, σε μεγάλο βαθμό εκτός του ευρωπαϊκού πολιτισμού.Ο ινδός μαθηματικός Μαχαβίρα (850) παρήγαγε φόρμουλες για τον αριθμό των μεταθέσεων και των συνδυασμών,και αυτοί οι τύποι μπορεί να είχαν εξοικειωθεί με τους Ινδούς μαθηματικούς ήδη από τον 6ο αιώνα μ.Χ. Ο φιλόσοφος και αστρονόμος ραβίνος Αβραάμ ιμπν Έζρα(1140) θέσπισε τη συμμετρία των διωνυμικών συντελεστών,ενώ ένας κλειστός τύπος ελήφθη αργότερα από τον ταλμουδιστή και μαθηματικό Γερσονίδη (Gersonides) το 1321.Το αριθμητικό τρίγωνο- ένα γραφικό διάγραμμα που δείχνει τις σχέσεις μεταξύ των διωνυμικών συντελεστών- παρουσιάστηκε από τους μαθηματικούς σε πραγματείες που χρονολογούνται από τον 10ο αιώνα και τελικά θα γινόταν γνωστή ως τρίγωνο του Πασκάλ. Αργότερα, στη μεσαιωνική Αγγλία, παρέχονται παραδείγματα του τι είναι τώρα γνωστή ως κύκλοι Χάμιλτον σε ορισμένα γραφήματα Κέιλι (Cayley) για μεταθέσεις.
Κατά τη διάρκεια της Αναγέννησης, μαζί με το υπόλοιπο των μαθηματικών και των επιστημών, συνδυαστική απολαμβάνουν μια αναγέννηση. Έργα των Μπλεζ Πασκάλ, Ισαάκ Νεύτωνα, Γιακόμπ Μπερνούλλι, και Λέοναρντ Όιλερ, έγινε θεμελιώδεις στον αναδυόμενο τομέα.Στη σύγχρονη εποχή, οι εργασίες του Τζέιμς Τζόζεφ Συλβέστερ (James Joseph Sylvester, τέλη 19ου αιώνα) και Πέρσι Αλεξάντερ Μακμέιχον (Percy Alexander MacMahon, αρχές 20ου αιώνα) έθεσε τα θεμέλια για enumerative και αλγεβρική συνδυαστική.Η θεωρία γράφων απολαύσαμε επίσης μια έκρηξη ενδιαφέροντος, ταυτόχρονα, ειδικά σε σχέση με το πρόβλημα των τεσσάρων χρωμάτων.
Στο δεύτερο μισό του 20ου αιώνα, η συνδυαστική απόλαυσε μια ραγδαία ανάπτυξη, η οποία οδήγησε στην ίδρυση δεκάδων νέων περιοδικών και συνέδριων για το θέμα αυτό.Εν μέρει, η ανάπτυξη ήταν ωθούμενη από νέους συνδυασμούς και εφαρμογές σε άλλους τομείς, που κυμαίνονται από άλγεβρα σε πιθανότητα, από τη λειτουργική ανάλυση σε θεωρία αριθμών, κ.λπ.Αυτές οι συνδυασμοί έριξαν τα όρια μεταξύ της Συνδυαστικής και των μερών των μαθηματικών και της θεωρητικής επιστήμης των υπολογιστών, αλλά ταυτόχρονα οδήγησαν σε μερικό κατακερματισμό του τομέα.
Προσεγγίσεις και υποκατηγορίες συνδυαστικής
Απαριθμήσιμη Συνδυαστική
Απαριθμήσιμη συνδυαστική είναι η πιο κλασσική προσέγγιση της συνδυαστικής και επικεντρώνεται στην καταμέτρηση του αριθμού ορισμένων συνδυαστικών αντικειμένων. Αν και μετρώντας τον αριθμό των στοιχείων σε ένα σύνολο είναι ένα μάλλον ευρύ μαθηματικό πρόβλημα, που πολλά από τα προβλήματα που προκύπτουν σε εφαρμογές έχουν μια σχετικά απλή συνδυαστική περιγραφή. Οι αριθμοί Φιμπονάτσι είναι ένα βασικό πρόβλημα απαριθμήσιμης συνδυαστικής. Ο δωδεκαπλάσιος τρόπος παρέχει ένα ενιαίο πλαίσιο για την μέτρηση μεταθέσεων,συνδυασμών και χωρισμάτων.
Αναλυτική Συνδυαστική
Η αναλυτική Συνδυαστική αφορά την απαρίθμηση των συνδυαστικών δομών χρησιμοποιώντας εργαλεία από την ανάλυση και τη θεωρία πιθανοτήτων.Σε αντίθεση με απαριθμητική συνδυαστική που χρησιμοποιεί σαφείς συνδυαστικούς τύπους και παραγωγήσιμες συναρτήσεις για να περιγράψει τα αποτελέσματα, η αναλυτική Συνδυαστική στοχεύει στην απόκτηση ασυμπτωτικών μεθόδων.
Θεωρία κατανομής
Η θεωρία κατανομής μελετά διάφορα προβλήματα απαρίθμησης και ασυμπτωτικής που σχετίζονται με ακέραια χωρίσματα και συνδέεται στενά με q-σειρές,ειδικές λειτουργίες και ορθογώνια πολυώνυμα. Αρχικά ένα μέρος της θεωρίας αριθμών και ανάλυσης, θεωρείται πλέον ένα μέρος της συνδυαστικής ή ένα ανεξάρτητο πεδίο. Ενσωματώνει την bijective προσέγγιση και διάφορα εργαλεία στην ανάλυση, στην αναλυτική θεωρία αριθμών και έχει διασυνδέσεις με την στατιστική μηχανική.
Θεωρία γραφημάτων
Τα γραφήματα είναι βασικά αντικείμενα στη συνδυαστική.Οι ερωτήσεις κυμαίνονται από την καταμέτρηση (π.χ., ο αριθμός των γραφημάτων σε n κορυφές με ακμές k) σε διαρθρωτικές (π.χ., η οποία περιέχει γραφήματα κύκλους του Hamilton) σε αλγεβρικές ερωτήσεις (π.χ., δίνεται ένα γράφημα G και δύο αριθμοί x και y, κάνει το πολυώνυμο Τατ (Tutte) TG (x, y) έχει μια συνδυαστική ερμηνεία;).Θα πρέπει να σημειωθεί ότι, ενώ υπάρχουν πολύ ισχυρές συνδέσεις μεταξύ της θεωρίας γραφημάτων και της συνδυαστικής, αυτά τα δύο μερικές φορές θεωρούνται ως ξεχωριστά μαθήματα.
Πεπερασμένη γεωμετρία
Πεπερασμένη γεωμετρία είναι η μελέτη των γεωμετρικών συστημάτων που έχουν μόνο έναν πεπερασμένο αριθμό σημείων.Δομές ανάλογες με εκείνες που βρίσκονται σε συνεχείς γεωμετρίες (Ευκλείδειο επίπεδο, το πραγματικό προβολικό χώρο, κ.λπ.), αλλά ορίζονται συνδυαστικά είναι τα κύρια στοιχεία που μελετήθηκαν.Αυτή η περιοχή προσφέρει μια πλούσια πηγή παραδειγμάτων για την θεωρία σχεδιασμού. Δεν πρέπει να συγχέεται με τη διακριτή γεωμετρία (Συνδυαστική γεωμετρία).
Θεωρία Παραγγελίας
Θεωρία παραγγελίας είναι η μελέτη των μερικώς διατεταγμένων συνόλων των πεπερασμένων και απείρων. Διάφορα παραδείγματα της μερικής "παραγγελίας" εμφανίζονται στην άλγεβρα,στη γεωμετρία, θεωρία αριθμών και σε όλη την συνδυαστική και στη θεωρία γραφημάτων. Ξεχωριστές τάξεις και πραδείγματα της μερικής παραγγελίας περιλαμβάνουν πλέγματα και Boolean άλγεβρα.
Θεωρία Μάτροϊντ
Η θεωρία Μάτροϊντ (Matroid) γενικεύει κάποια μέρη της γεωμετρίας . Μελετά τις ιδιότητες των συνόλων (συνήθως , πεπερασμένα σύνολα ) των διανυσμάτων σε ένα διανυσματικό χώρο που δεν εξαρτώνται από τους ιδιαίτερους συντελεστές σε μια σχέση γραμμικής εξάρτησης.Οχι μονο η δομή αλλά και οι απαριθμητικές ιδιότητες ανήκουν στη θεωρία Μάτροϊντ. Η θεωρία εισήχθη από τον Χάσλερ Ουίτνι (Hassler Whitney) και μελετήθηκε ως μέρος της θεωρίας τάξης.Τώρα είναι ένας ανεξάρτητος τομέας της μελέτης με έναν αριθμό συνδέσεων με άλλα μέρη της Συνδυαστικής .
Extremal Συνδυαστική
Η extremal συνδυαστική μελετά extremal ερωτήσεις σχετικά με ενα σύνολο συστημάτων. Οι τύποι των ερωτησέων που απευθύνονται σε αυτή την περίπτωση είναι περίπου όσο το δυνατόν μεγαλύτερο γράφημα το οποίο πληρεί ορισμένες ιδιότητες, Για παράδειγμα, το μεγαλύτερο τρίγωνο χωρίς γράφημα για δυο κορυφές είναι ένα πλήρες διμερές γράφημα Kn,n . Συχνά είναι πολύ δύσκολο ακόμη και να βρείτε την extremal απάντηση f(n) ακριβώς και κάποιος μόνο μπορεί να δωσει ασυμπτωτική εκτίμηση.
Θεωρία Ramsey είναι ένα άλλο μέρος της extremal συνδυαστικής. Αναφέρει ότι κάθε αρκετά μεγάλη διαμόρφωση θα περιέχει κάποιο είδος της παραγγελίας. Πρόκειται για μια προηγμένη γενίκευση της αρχής της θυρίδας.
Πιθανολογική συνδυαστική
Στην πιθανολογική συνδυαστική, τα ερωτήματα είναι του εξής τύπου : ποια είναι η πιθανότητα σε μια ορισμένη ιδιότητα για ένα τυχαίο διακριτό αντικείμενο , όπως ένα τυχαίο γράφημα; Για παράδειγμα, τί είναι ο μέσος αριθμός των τριγώνων σε ένα τυχαίο γράφημα; Οι πιθανοτικές μέθοδοι που χρησιμοποιούνται επίσης για να διαπιστωθεί η ύπαρξη συνδυαστικών αντικειμένων με ορισμένες προδιαγεγραμμένες ιδιότητες ( για τις οποίες γίνονται σαφή παραδείγματα μπορεί να είναι δύσκολο να βρει κανείς), απλά με την παρατήρηση ότι η πιθανότητα τυχαίας επιλογής ενός αντικειμένου με τις ιδιότητες αυτές είναι μεγαλύτερη από μηδέν .Αυτή η προσέγγιση ( που συχνά αναφέρεται ως η πιθανολογική μέθοδος ) αποδείχθηκε ιδιαίτερα αποτελεσματική σε εφαρμογές της συνδυαστικής άκρων και της θεωρίας γραφημάτων . Μία στενά συνδεδεμένη περιοχή είναι η μελέτη των πεπερασμένων αλυσίδων Μαρκόφ, ειδικά σε συνδυαστικά αντικείμενα. Εδώ πάλι τα πιθανολογικά εργαλεία χρησιμοποιούνται για την εκτίμηση του χρόνου ανάμιξης.
Συχνά σχετίζεται με τον Πολ Έρντος ο οποίος έκανε την πρωτοποριακή εργασία σχετικά με το θέμα, πιθανολογική συνδυαστική παραδοσιακά θεωρούνταν ως ένα σύνολο εργαλείων για τη μελέτη των προβλημάτων σε άλλα μέρη της συνδυαστικής. Ωστόσο , με την αύξηση των αιτήσεων για την ανάλυση των αλγορίθμων στην επιστήμη των υπολογιστών , καθώς επίσης και την κλασική πιθανότητα πρόσθετης ύλης και τη πιθανολογική θεωρία αριθμών, η περιοχή πρόσφατα αναπτύχθηκε για να γίνει ένας ανεξάρτητος τομέας της Συνδυαστικής .
Αλγεβρική συνδυαστική
Η αλγεβρική συνδυαστική είναι μια περιοχή των μαθηματικών που χρησιμοποιεί την μέθοδο της αφηρημένης άλγεβρας, την θεωρία ομάδων και την θεωρία εκπροσώπησης, σε διάφορα συνδυαστικά πλαίσια και, αντιστρόφως, εφαρμόζονται τεχνικές συνδυαστικής για προβλήματα στην άλγεβρα. Η αλγεβρική Συνδυαστική συνεχώς επεκτείνεται στο πεδίο εφαρμογής της, και στα δύο θέματα και στις τεχνικές, και μπορεί να θεωρηθεί ως η περιοχή των μαθηματικών, όπου η αλληλεπίδραση της συνδυαστικής και των αλγεβρικών μεθόδων είναι ιδιαίτερα ισχυρή και σημαντική.
Συνδυαστική σε λέξεις
Η Συνδυαστική στις λέξεις ασχολείται με τις επίσημες γλώσσες . Προέκυψε ανεξάρτητα, εντός διαφόρων κλάδων των μαθηματικών , συμπεριλαμβανομένων της θεωρίας Αριθμών , της θεωρίας της ομάδας και των πιθανοτήτων . Έχει εφαρμογές σε απαριθμητική συνδυαστική , ανάλυση φράκταλ, θεωρητική επιστήμη των υπολογιστών , στη θεωρίας αυτομάτων και στη γλωσσολογία . Ενώ πολλές εφαρμογές είναι νέες, η κλασική ιεραρχία Τσόμσκι-Σάτσενμπέργκερ (Chomsky–Schützenberger) των ομάδων τυπικών γραμματικών είναι ίσως το καλύτερο γνωστό αποτέλεσμα στον τομέα .
Γεωμετρική Συνδυαστική
Η γεωμετρική Συνδυαστική σχετίζεται με κυρτά και με διακριτή γεωμετρία, ιδίως πολυεδρική Συνδυαστική.Ζητάει, για παράδειγμα, πόσες έδρες σε κάθε διάσταση μπορεί να έχει ένα κυρτό πολύτοπο. Οι μετρικές ιδιότητες polytopes διαδραματίζουν σημαντικό ρόλο, καθώς, π.χ. το θεώρημα του Cauchy για την ακαμψία των κυρτών polytopes. Ειδικές polytopes θεωρούνται επίσης, όπως permutohedra, associahedra και Birkhoff polytopes. Θα πρέπει να σημειώσουμε ότι η συνδυαστική γεωμετρία είναι ένα ντεμοντέ όνομα για διακριτή γεωμετρία.
Τοπολογική συνδυαστική
Η Συνδυαστική ανάλογα με τις έννοιες και μεθόδους της τοπολογίας χρησιμοποιούνται για τη μελέτη χρωματισμού γραφήματος ,τη δίκαιη κατανομή ,τα χωρίσματα ,τα μερικώς διατεταγμένα σύνολα ,τα δέντρα απόφασης , προβλήματα αλυσίδας και διακριτή Morse θεωρία . Δεν πρέπει να συγχέεται με τη συνδυαστική τοπολογία , που είναι ένα παλαιότερο όνομα για την Αλγεβρική Τοπολογία .
Αριθμητική συνδυαστική
Η αριθμητική συνδυαστική προέκυψε απο την αλληλεπίδραση μεταξύ θεωρίας αριθμών, συνδυαστική θεωρία, θεωρία ergodic και αρμονική ανάλυση. Πρόκειται για εκτιμήσεις συνδυαστικής που σχετίζοντια με αριθμητικές πράξεις (πρόσθεση,αφαίρεση,πολλαπλασιασμό και διαίρεση). Η πρόσθετη συνδυαστική αναφέρεται στην ειδική ερίπτωση, όταν μόνο οι πράξεις της πρόσθεσης και της αφαίρεσης εφαρμόζονται. Μια σημαντική τεχνική στην αριθμητική συνδυαστική είναι η ergodic θεωρία των δυναμικών συστημάτων.
Άπειρη συνδυαστική
Η άπειρη συνδυαστική ή θεωρία συνδυαστικών συνόλων, είναι μια επέκταση των ιδεών της Συνδυαστικής σε άπειρες σειρές. Είναι ένα μέρος της θεωρίας συνόλων, μιας περιοχής της μαθηματικής λογικής, αλλά χρησιμοποιεί τα εργαλεία και τις ιδέες τόσο από την θεωρία των συνόλων όσο και από την extremal Συνδυαστική.
Σχετικά πεδία
Συνδυαστική βελτιστοποίηση
Η Συνδυαστική βελτιστοποίηση είναι η μελέτη της βελτιστοποίησης σε διακριτά και συνδυαστικά αντικείμενα. Ξεκίνησε ως ένα μέρος της Συνδυαστική και της θεωρίας γραφημάτων, αλλά θεωρείται πλέον ως κλάδος των εφαρμοσμένων μαθηματικών και της επιστήμης [1] των υπολογιστών, που σχετίζονται με την επιχειρησιακή έρευνα,τη θεωρία αλγορίθμων και τη θεωρία πολυπλοκότητας.
Θεωρία κωδικοποίησης
Η θεωρία κωδικοποίησης ξεκίνησε ως ένα μέρος της θεωρίας του σχεδιασμού με πρώιμες κατασκευές σσυνδυαστικής των κωδικων διόρθωσης σφαλμάτων. Η κύρια ιδέα του θέματος είναι να σχεδιαστούν αποτελεσματικές και αξιόπιστες μέθοδοι μετάδοσης δεδομένων που πλέον είναι ένα μεγάλο πεδίο μελέτης, μέρος της θεωρίας της πληροφορίας.
Διακριτή και Υπολογιστική Γεωμετρία
Η Διακριτή Γεωμετρία (ονομάζεται επίσης συνδυαστική γεωμετρία) ξεκίνησε επίσης ένα μέρος της Συνδυαστικής, με τα πρώτα αποτελέσματα σχετικά με το κυρτό polytopes και τους αριθμούς φιλιά. Με την εμφάνιση των εφαρμογών της διακριτής γεωμετρίας στην υπολογιστική γεωμετρία, τα δύο αυτά πεδία εν μέρει συγχωνεύτηκαν και έγιναν ένα ξεχωριστό πεδίο μελέτης. Εξακολουθούν να υπάρχουν πολλές συνδέσεις με τη γεωμετρική και την τοπολογική Συνδυαστική, που οι ίδιες μπορούν να θεωρηθούν ως αποφύσεις της πρώιμης διακριτής γεωμετρίας.
Συνδυαστική και δυναμικά συστήματα
Πτυχές συνδυαστικής των δυναμικών συστημάτων είναι ένας άλλος αναδυόμενος τομέας. Εδώ δυναμικά συστήματα μπορούν να οριστούν ως ατικείμενα συνδυαστικής. Δείτε για παράδειγμα διάγραμμα δυναμικού συστηματος.
Συνδυαστική και φυσική
Υπάρχουν αυξανόμενες αλληλεπιδράσεις μεταξύ της Συνδυαστικής και της φυσικής, ιδιαίτερα της στατιστικής φυσικής. Παραδείγματα περιλαμβάνουν μια ακριβή λύση του μοντέλου Ising, και μια σύνδεση μεταξύ του μοντέλου Potts από τη μια μεριά, και της χρωματικής και των πολυωνύμων Tutte από την άλλη.
Παραπομπές
«Splitting a necklace with two cuts.».
Εξωτερικοί σύνδεσμοι
«Γρίφοι Συνδυασμών».
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
