Συνδυαστική
Αντώνιος Οικονόμου
Η Συνδυαστική ασχολείται με τη μέτρηση του πλήθους των σχηματισμών που προκύπτουν από ένα σύνολο στοιχείων και έχουν καθορισμένη δομή και ιδιότητες. Στόχος της Συνδυαστικής είναι η ανάπτυξη μεθόδων, αναλυτικών και αλγοριθμικών τεχνικών ώστε η μέτρηση του πλήθους των σχηματισμών να γίνεται όσο το δυνατόν αποτελεσματικότερα.
Με απλά λόγια η Συνδυαστική απαντά σε προβλήματα του τύπου
-
Με πόσους τρόπους μπορώ να κάνω κάτι;
-
Πόσα αντικείμενα υπάρχουν με μια δοσμένη ιδιότητα;
Παραδείγματος χάριν:
-
Με πόσους τρόπους μπορώ να βάλω 10 διακεκριμένα αντικείμενα στη σειρά;
-
Πόσες διαφορετικές πενταμελείς επιτροπές μπορούν να φτιαχτούν από ένα σύνολο με 30 άτομα;
-
Πόσοι αριθμοί μεταξύ του 1 και του 1000 διαιρούνται είτε με το 3 είτε με το 5;
-
Πόσες είναι οι δυνατές στήλες ΠΡΟ-ΠΟ;
-
Πόσα είναι τα δυνατά αποτελέσματα των κληρώσεων του ΛΟΤΤΟ;
Επειδή τα προβλήματα καταμέτρησης σχηματισμών εμφανίζονται πολύ συχνά σε πειράματα με τυχαίο χαρακτήρα, η γνώση της Συνδυαστικής είναι απαραίτητη για να διευκολυνθεί κάποιος στην κατανόηση της Θεωρίας Πιθανοτήτων. Επιπλέον συνδυαστικές ιδέες διατρέχουν όλα τα μαθηματικά.
Η Συνδυαστική Ι εισάγει τους φοιτητές στα βασικά συνδυαστικά προβλήματα και τις μεθόδους που έχουν αναπτυχθεί για την επίλυσή τους.
Το μάθημα απευθύνεται σε πρωτοετείς φοιτητές Μαθηματικών, Στατιστικής, Φυσικών Επιστημών και Πολυτεχνικών Σχολών. Το μάθημα δεν έχει προαπαιτούμενα, εκτός ίσως από το τελευταίο μέρος του που προϋποθέτει μερικές βασικές γνώσεις από τον Απειροστικό Λογισμό (δυναμοσειρές και ιδιαίτερα τη γεωμετρική και την εκθετική σειρά).
Λιγότερα
Η Συνδυαστική ασχολείται με τη μέτρηση του πλήθους των σχηματισμών που προκύπτουν από ένα σύνολο στοιχείων και έχουν καθορισμένη δομή και ιδιότητες. Στόχος της Συνδυαστικής είναι η ανάπτυξη μεθόδων, αναλυτικών και αλγοριθμικών τεχνικών ώστε η μέτρηση του πλήθους των σχηματισμών να γίνεται όσο το δυνατόν αποτελεσματικότερα.
Με απλά λόγια η Συνδυαστική απαντά σε προβλήματα του τύπου
-
Με πόσους τρόπους μπορώ να κάνω κάτι;
-
Πόσα αντικείμενα υπάρχουν με μια δοσμένη ιδιότητα;
Παραδείγματος χάριν:
-
Με πόσους τρόπους μπορώ να βάλω 10 διακεκριμένα αντικείμενα στη σειρά;
-
Πόσες διαφορετικές πενταμελείς επιτροπές μπορούν να φτιαχτούν από ένα σύνολο με 30 άτομα;
-
Πόσοι αριθμοί μεταξύ του 1 και του 1000 διαιρούνται είτε με το 3 είτε με το 5;
-
Πόσες είναι οι δυνατές στήλες ΠΡΟ-ΠΟ;
-
Πόσα είναι τα δυνατά αποτελέσματα των κληρώσεων του ΛΟΤΤΟ;
Επειδή τα προβλήματα καταμέτρησης σχηματισμών εμφανίζονται πολύ συχνά σε πειράματα με τυχαίο χαρακτήρα, η γνώση της Συνδυαστικής είναι απαραίτητη για να
Η Συνδυαστική ασχολείται με τη μέτρηση του πλήθους των σχηματισμών που προκύπτουν από ένα σύνολο στοιχείων και έχουν καθορισμένη δομή και ιδιότητες. Στόχος της Συνδυαστικής είναι η ανάπτυξη μεθόδων, αναλυτικών και αλγοριθμικών τεχνικών ώστε η μέτρηση του πλήθους των σχηματισμών να γίνεται όσο το δυνατόν αποτελεσματικότερα.
Με απλά λόγια η Συνδυαστική απαντά σε προβλήματα του τύπου
-
Με πόσους τρόπους μπορώ να κάνω κάτι;
-
Πόσα αντικείμενα υπάρχουν με μια δοσμένη ιδιότητα;
Παραδείγματος χάριν:
-
Με πόσους τρόπους μπορώ να βάλω 10 διακεκριμένα αντικείμενα στη σειρά;
-
Πόσες διαφορετικές πενταμελείς επιτροπές μπορούν να φτιαχτούν από ένα σύνολο με 30 άτομα;
-
Πόσοι αριθμοί μεταξύ του 1 και του 1000 διαιρούνται είτε με το 3 είτε με το 5;
-
Πόσες είναι οι δυνατές στήλες ΠΡΟ-ΠΟ;
-
Πόσα είναι τα δυνατά αποτελέσματα των κληρώσεων του ΛΟΤΤΟ;
Επειδή τα προβλήματα καταμέτρησης σχηματισμών εμφανίζονται πολύ συχνά σε πειράματα με τυχαίο χαρακτήρα, η γνώση της Συνδυαστικής είναι απαραίτητη για να
Περίγραμμα
Περιεχόμενο μαθήματος
Το μάθημα στοχεύει στην ανάπτυξη βασικών δεξιοτήτων για την μαθηματική ανάλυση συνδυαστικών προβλημάτων. Η δομή του έχει ως εξής:
-
Εισαγωγικά προβλήματα απαρίθμησης γεωμετρικών και αλγεβρικών σχηματισμών.
-
Οι βασικές αρχές απαρίθμησης.
-
Η πολλαπλασιαστική αρχή και οι εφαρμογές της στην απαρίθμηση διατάξεων, συνδυασμών και μεταθέσεων.
-
Επαγωγική σκέψη στη συνδυαστική και οι εφαρμογές της στην εύρεση αναγωγικών σχέσεων (αναδρομικών σχημάτων) για την απαρίθμηση διατάξεων, συνδυασμών και μεταθέσεων.
-
Πλήθος ακέραιων λύσεων γραμμικής εξίσωσης με μοναδιαίους συντελεστές.
-
Γενικευμένα παραγοντικά και διωνυμικοί συντελεστές.
-
Τεχνικές υπολογισμού πεπερασμένων αθροισμάτων.
-
Η αρχή εγκλεισμού-αποκλεισμού και οι εφαρμογές της στην απαρίθμηση σχηματισμών.
-
Εισαγωγή στις γεννήτριες συναρτήσεις.
-
Γεννήτριες συνδυασμών και διατάξεων.
Μαθησιακοί στόχοι
Σκοπός του μαθήματος είναι η ανάπτυξη βασικών δεξιοτήτων για την επίλυση συνδυαστικών προβλημάτων, δηλαδή προβλημάτων καταμέτρησης σχηματισμών με δεδομένες ιδιότητες.
Στο τέλος του μαθήματος ο εκπαιδευόμενος-φοιτητής θα πρέπει να είναι σε θέση:
-
να χειρίζεται την πολλαπλασιαστική αρχή για τον υπολογισμό του πλήθους σχηματισμών που δημιουργούνται σε στάδια
-
να χειρίζεται την αρχή του αθροίσματος και την αρχή εγκλεισμού-αποκλεισμού για να υπολογίζει το πλήθος των σχηματισμών που ανήκουν στην ένωση δυο ή περισσοτέρων συνόλων
-
να έχει αναπτύξει την αναγκαία επαγωγική σκέψη για την εύρεση αναγωγικών σχέσεων για το πλήθος σχηματισμών
-
να μπορεί να υπολογίζει πεπερασμένα αθροίσματα σε κλειστή μορφή
-
να χρησιμοποιεί γεννήτριες συναρτήσεις για τον υπολογισμό του πλήθους σχηματισμών με συγκεκριμένες ιδιότητες, ιδιαίτερα τον υπολογισμό του πλήθους συνδυασμών και διατάξεων.
Προτεινόμενα συγγράμματα
1. Χαραλαμπίδη, Χ. (2000) Συνδυαστική Ι, Εκδόσεις Συμμετρία, Αθήνα.
2 . Κούτρα, Μ. Εισαγωγή στη Συνδυαστική, Εκδόσεις Σταμούλη, Πειραιάς.
Ομάδα στόχος
Προπτυχιακοί φοιτητές Τμημάτων Μαθηματικών, Στατιστικής, Πληροφορικής και Πολυτεχνικών Σχολών
Μέθοδοι διδασκαλίας
Διδασκαλία καθ΄ έδρας – Ασκήσεις
Μέθοδοι αξιολόγησης
Εξετάσεις (2 ώρες και 30 λεπτά)
Βιβλιογραφία
-
Βιβλία- κείμενα (Textbooks)
-
Συγγράμματα:
-
Χαραλαμπίδη, Χ. (2000) Συνδυαστική Ι, Εκδόσεις Συμμετρία, Αθήνα.
-
Κούτρα, Μ. (2006) Εισαγωγή στη Συνδυαστική, Εκδόσεις Σταμούλη, Πειραιάς.
-
Βιβλιογραφία:
-
Charalambides, Ch. (2002) Enumerative Combinatorics, Chapman and Hall.
-
Niven, I.M. (1975) Mathematics of Choice: How to count without counting, Mathematical Association of America.
-
Online readings
-
Πηγές στο Διαδίκτυο:
http://www.unipi.gr/faculty/mkoutras/synd.htm
-
Πηγές στη βιβλιοθήκη του ιδρύματος:
-
Χαραλαμπίδη, Χ. (1993) Ασκήσεις συνδυαστικής: με ανασκόπηση θεωρίας και λύσεις, Συμμετρία, Αθήνα.
-
Μωυσιάδης, Χ. (2002) Συνδυαστική απαρίθμηση: η τέχνη να μετράμε χωρίς μέτρημα. Εκδόσεις Ζήτη, Θεσσαλονίκη.
-
Άλλα σχετικά ανοικτά μαθήματα άλλων ιδρυμάτων εσωτερικού ή εξωτερικού
-
Combinatorics: The Fine Art of Counting MITOpenCourseware:
http://ocw.mit.edu/high-school/mathematics/combinatorics-the-fine-art-of-counting/index.htm
Διδάσκοντες
Αντώνης Οικονόμου
Αναπληρωτής Καθηγητής
Καποδιαστριακό Πανεπιστήμιο Αθηνών
Τμήμα Μαθηματικών, Τομέας Στατιστικής και Επιχειρησιακής Έρευνας
Ο Αντώνης Οικονόμου είναι μέλος ΔΕΠ στον Τομέα Στατιστικής και Επιχειρησιακής Έρευνας του Τμήματος Μαθηματικών του Πανεπιστημίου Αθηνών από το 2001.
Σπουδές: Πτυχίο Μαθηματικών Πανεπιστημίου Αθηνών (1993), Μεταπτυχιακό στα Θεωρητικά Μαθηματικά UCLA (1994), Μεταπτυχιακό στη Στατιστική και Επιχειρησιακή Έρευνα Πανεπιστημίου Αθηνών (1997) και Διδακτορικό στα Μαθηματικά Πανεπιστημίου Αθηνών (1998). Ερευνητικά ενδιαφέροντα: Πιθανότητες, Επιχειρησιακή Έρευνα, Μαθηματική Βιολογία. Ειδικότερα, προβλήματα υπολογισμών, στοχαστικών συγκρίσεων και βελτιστοποίησης σε στοχαστικές διαδικασίες με εφαρμογές στη θεωρία συστημάτων εξυπηρέτησης (θεωρία ουρών) και στα στοχαστικά πρότυπα εξέλιξης πληθυσμών.
Το μάθημα στοχεύει στην ανάπτυξη βασικών δεξιοτήτων για την μαθηματική ανάλυση συνδυαστικών προβλημάτων. Η δομή του έχει ως εξής:
-
Εισαγωγικά προβλήματα απαρίθμησης γεωμετρικών και αλγεβρικών σχηματισμών.
-
Οι βασικές αρχές απαρίθμησης.
-
Η πολλαπλασιαστική αρχή και οι εφαρμογές της στην απαρίθμηση διατάξεων, συνδυασμών και μεταθέσεων.
-
Επαγωγική σκέψη στη συνδυαστική και οι εφαρμογές της στην εύρεση αναγωγικών σχέσεων (αναδρομικών σχημάτων) για την απαρίθμηση διατάξεων, συνδυασμών και μεταθέσεων.
-
Πλήθος ακέραιων λύσεων γραμμικής εξίσωσης με μοναδιαίους συντελεστές.
-
Γενικευμένα παραγοντικά και διωνυμικοί συντελεστές.
-
Τεχνικές υπολογισμού πεπερασμένων αθροισμάτων.
-
Η αρχή εγκλεισμού-αποκλεισμού και οι εφαρμογές της στην απαρίθμηση σχηματισμών.
-
Εισαγωγή στις γεννήτριες συναρτήσεις.
-
Γεννήτριες συνδυασμών και διατάξεων.
Σκοπός του μαθήματος είναι η ανάπτυξη βασικών δεξιοτήτων για την επίλυση συνδυαστικών προβλημάτων, δηλαδή προβλημάτων καταμέτρησης σχηματισμών με δεδομένες ιδιότητες.
Στο τέλος του μαθήματος ο εκπαιδευόμενος-φοιτητής θα πρέπει να είναι σε θέση:
-
να χειρίζεται την πολλαπλασιαστική αρχή για τον υπολογισμό του πλήθους σχηματισμών που δημιουργούνται σε στάδια
-
να χειρίζεται την αρχή του αθροίσματος και την αρχή εγκλεισμού-αποκλεισμού για να υπολογίζει το πλήθος των σχηματισμών που ανήκουν στην ένωση δυο ή περισσοτέρων συνόλων
-
να έχει αναπτύξει την αναγκαία επαγωγική σκέψη για την εύρεση αναγωγικών σχέσεων για το πλήθος σχηματισμών
-
να μπορεί να υπολογίζει πεπερασμένα αθροίσματα σε κλειστή μορφή
-
να χρησιμοποιεί γεννήτριες συναρτήσεις για τον υπολογισμό του πλήθους σχηματισμών με συγκεκριμένες ιδιότητες, ιδιαίτερα τον υπολογισμό του πλήθους συνδυασμών και διατάξεων.
1. Χαραλαμπίδη, Χ. (2000) Συνδυαστική Ι, Εκδόσεις Συμμετρία, Αθήνα.
2 . Κούτρα, Μ. Εισαγωγή στη Συνδυαστική, Εκδόσεις Σταμούλη, Πειραιάς.
Προπτυχιακοί φοιτητές Τμημάτων Μαθηματικών, Στατιστικής, Πληροφορικής και Πολυτεχνικών Σχολών
Διδασκαλία καθ΄ έδρας – Ασκήσεις
Εξετάσεις (2 ώρες και 30 λεπτά)
-
Βιβλία- κείμενα (Textbooks)
-
Συγγράμματα:
-
-
Χαραλαμπίδη, Χ. (2000) Συνδυαστική Ι, Εκδόσεις Συμμετρία, Αθήνα.
-
Κούτρα, Μ. (2006) Εισαγωγή στη Συνδυαστική, Εκδόσεις Σταμούλη, Πειραιάς.
-
Βιβλιογραφία:
-
-
Charalambides, Ch. (2002) Enumerative Combinatorics, Chapman and Hall.
-
Niven, I.M. (1975) Mathematics of Choice: How to count without counting, Mathematical Association of America.
-
Online readings
-
Πηγές στο Διαδίκτυο:
-
http://www.unipi.gr/faculty/mkoutras/synd.htm
-
Πηγές στη βιβλιοθήκη του ιδρύματος:
-
-
Χαραλαμπίδη, Χ. (1993) Ασκήσεις συνδυαστικής: με ανασκόπηση θεωρίας και λύσεις, Συμμετρία, Αθήνα.
-
Μωυσιάδης, Χ. (2002) Συνδυαστική απαρίθμηση: η τέχνη να μετράμε χωρίς μέτρημα. Εκδόσεις Ζήτη, Θεσσαλονίκη.
-
-
Άλλα σχετικά ανοικτά μαθήματα άλλων ιδρυμάτων εσωτερικού ή εξωτερικού
-
-
Combinatorics: The Fine Art of Counting MITOpenCourseware:
-
http://ocw.mit.edu/high-school/mathematics/combinatorics-the-fine-art-of-counting/index.htm
Αντώνης Οικονόμου
Αναπληρωτής Καθηγητής
Καποδιαστριακό Πανεπιστήμιο Αθηνών
Τμήμα Μαθηματικών, Τομέας Στατιστικής και Επιχειρησιακής Έρευνας
Ο Αντώνης Οικονόμου είναι μέλος ΔΕΠ στον Τομέα Στατιστικής και Επιχειρησιακής Έρευνας του Τμήματος Μαθηματικών του Πανεπιστημίου Αθηνών από το 2001.
Σπουδές: Πτυχίο Μαθηματικών Πανεπιστημίου Αθηνών (1993), Μεταπτυχιακό στα Θεωρητικά Μαθηματικά UCLA (1994), Μεταπτυχιακό στη Στατιστική και Επιχειρησιακή Έρευνα Πανεπιστημίου Αθηνών (1997) και Διδακτορικό στα Μαθηματικά Πανεπιστημίου Αθηνών (1998). Ερευνητικά ενδιαφέροντα: Πιθανότητες, Επιχειρησιακή Έρευνα, Μαθηματική Βιολογία. Ειδικότερα, προβλήματα υπολογισμών, στοχαστικών συγκρίσεων και βελτιστοποίησης σε στοχαστικές διαδικασίες με εφαρμογές στη θεωρία συστημάτων εξυπηρέτησης (θεωρία ουρών) και στα στοχαστικά πρότυπα εξέλιξης πληθυσμών.
Παρουσίαση εισαγωγικών προβλημάτων απαρίθμησης γεωμετρικών και αλγεβρικών σχηματισμών. Η επαγωγική προσέγγιση και η προσέγγιση κατασκευής σε στάδια. Οι βασικές αρχές απαρίθμησης: η πολλαπλασιαστική αρχή, η αρχή του αθροίσματος, η αρχή εγκλεισμού-αποκλεισμού. Η αρχή του περιστερεώνα.
Λέξεις-κλειδιά: Επαγωγή, στάδια, πολλαπλασιαστική αρχή, αρχή του αθροίσματος, αρχή εγκλεισμού – αποκλεισμού, αρχή περιστεραιών
Διάκριση διατάξεων και συνδυασμών, επαναληπτικών και μη. Η έννοια των μεταθέσεων. Εφαρμογή της πολλαπλασιαστικής αρχής στην απαρίθμηση διατάξεων, μεταθέσεων και συνδυασμών. Μεταθέσεις ν ειδών στοιχείων. Κατανομές σφαιριδίων σε διακεκριμένα κελιά. Αναγωγικές σχέσεις σε διατάξεις και συνδυασμούς. Το τρίγωνο του Pascal. Ο τύπος του Cauchy. Διαιρέσεις και διαμερίσεις συνόλου. Πλήθος ακέραιων λύσεων γραμμικής εξίσωσης με μοναδιαίους συντελεστές.
Λέξεις-κλειδιά: Διατάξεις, μεταθέσεις, συνδυασμοί, μεταθέσεις ν ειδών στοιχείων, διαιρέσεις, διαμερίσεις, κατανομέs σφαιριδίων σε κελιά
Ορισμός γενικευμένων παραγοντικών και σύνδεσή τους με τις δυνάμεις. Ορισμός διωνυμικών συντελεστών. Βασικές ταυτότητες. Το διωνυμικό θεώρημα και το πολυωνυμικό θεώρημα. Υπολογισμός αθροισμάτων με παραγώγιση και ολοκλήρωση βασικών σειρών. Υπολογισμός αθροισμάτων με χρήση ιδιοτήτων των διωνυμικών συντελεστών. Υπολογισμός αθροισμάτων σε άρτιους και περιττούς δείκτες. Υπολογισμός αθροισμάτων με επιχειρήματα συμμετρίας.
Λέξεις - Κλειδιά: Γενικευμένα παραγοντικά, διωνυμικοί συντελεστές, διωνυμικό θεώρημα, πολυωνυμικό θεώρημα, γεωμετρική σειρά, πεπερασμένα αθροίσματα
Η αρχή εγκλεισμού – αποκλεισμού για τον πληθάριθμο της ένωσης συνόλων. Αποδείξεις. Εφαρμογές στο πρόβλημα των μεταθέσεων χωρίς σταθερά σημεία, στην εύρεση του πλήθους ακέραιων λύσεων εξίσωσης με αμφίπλευρους περιορισμούς για τις τιμές των μεταβλητών κ.α.
Λέξεις - Κλειδιά: Αρχή εγκλεισμού – αποκλεισμού, μεταθέσεις χωρίς σταθερά σημεία
Η έννοια της γεννήτριας μιας ακολουθίας. Ισότητα και πράξεις γεννητριών. Χρήση των γεννητριών για την απαρίθμηση συνδυασμών και διατάξεων με περιορισμούς στον αριθμό των δυνατών εμφανίσεων κάθε στοιχείου.
Λέξεις - Κλειδιά: Γεννήτριες, γεννήτριες συνδυασμών, γεννήτριες διατάξεων, τυπικές δυναμοσειρές
Ανοικτό Ακαδ. Μάθημα
Αρ. Επισκέψεων : 0
Αρ. Προβολών : 0
Ημερολόγιο
Ανακοινώσεις
- - Δεν υπάρχουν ανακοινώσεις -
