Περιγραφή
Στο μάθημα θα συζητήσουμε ζητήματα Θεωρίας Γραφημάτων (οι βασικές έννοιες καλύφθηκαν στα Διακριτά Ι), Γεννήτριες Συναρτήσεις και εφαρμογές τους σε προβλήματα συνδυαστικής απαρίθμησης, και επίλυση αναδρομικών εξισώσεων.
Όσον αφορά στη Θεωρία Γραφημάτων, θα αναφερθούμε σε επίπεδα γραφήματα, δέντρα και επικαλύπτοντα δέντρα, διμερή γραφήματα, ταιριάσματα, χρωματισμό γραφημάτων, σύνολα ανεξαρτησίας και σύνολα κάλυψης. Για τις Γεννήτριες Συναρτήσεις, θα αναφερθούμε στις ιδιότητες των απλών και εκθετικών ΓΣ και στις μεθόδους κωδικοποίησης και επίλυσης προβλημάτων συνδυαστικής απαρίθμησης με ΓΣ. Θα μάθουμε πως να λύνουμε αναδρομικές εξισώσεις με τη μέθοδο της χαρακτηριστικής εξίσωσης και τη μέθοδο των ΓΣ. Επίσης θα αναφερθούμε στο θεώρημα του κυρίαρχου όρου (master theorem) για την επίλυση αναδρομικών εξισώσεων που προκύπτουν από αναδρομικούς αλγόριθμους διαίρει-και-βασίλευε.
Ύλη
Η ύλη περιλαμβάνει όλα τα ζητήματα που καλύφθηκαν στις παραδόσεις. Ένα σημαντικό μέρος της ύλης (αλλά όχι ολόκληρη) καλύπτεται από το βιβλίο του C.L. Liu "Στοιχεία Διακριτών Μαθηματικών". Ένα άλλο σημαντικό μέρος της ύλης (πάλι όχι ολόκληρη) συνοψίζεται στις σημειώσεις του διδάσκοντα (διαθέσιμες ηλεκτρονικά από αυτή τη σελίδα). Οι σημειώσεις συμπληρώνουν το βιβλίο δίνοντας έμφαση σε ζητήματα που δεν υπάρχουν ή δεν καλύπτονται επαρκώς σε αυτό. Για τις εξετάσεις, χρειάζεται να μελετήσετε τις παρακάτω ενότητες από το βιβλίο του Liu και τις σημειώσεις του διδάσκοντα.
Σημειώσεις: Με εξαίρεση τα φυλλάδια "Βασικές Έννοιες στη Θεωρία Γραφημάτων" και "Σύντομη Επανάληψη στη Στοιχειώδη Συνδυαστική", τα οποία επαναλαμβάνουν μέρος της ύλης από τα Διακριτά Ι, όλα τα φυλλάδια των σημειώσεων είναι στην ύλη για τις εξετάσεις.
Βιβλίο Liu:
Κεφάλαιο 5: μόνο ενότητες 5.9 και 5.10 (οι υπόλοιπες θεωρούνται γνωστές αφού καλύφθηκαν στα πλαίσια του Διακριτά Ι και επαναλάβαμε τα σημαντικότερα σημεία στα πλαίσια του μαθήματος). Στο μάθημα είπαμε πολύ περισσότερα πράγματα για επίπεδα γραφήματα από αυτά που υπάρχουν στο βιβλίο. Αυτά συνοψίζονται στο αντίστοιχο φυλλάδιο σημειώσεων. Επίσης στο μάθημα μιλήσαμε για χρωματισμό γραφημάτων, διμερή γραφήματα, πλήρη και μέγιστα ταιριάσματα, σύνολα ανεξαρτησίας, και σύνολα κάλυψης. Αυτά δεν υπάρχουν στο βιβλίο αλλά μόνο στις σημειώσεις.
Κεφάλαιο 6: όλο εκτός από την 6.8. Στο μάθημα εμβαθύναμε (σημαντικά περισσότερο από το βιβλίο) στον υπολογισμό ενός Ελάχιστου Επικαλύπτοντος Δέντρου. Το αντίστοιχο υλικό υπάρχει στις σημειώσεις.
Κεφάλαιο 9: όλο εκτός από την 9.3. Στο μάθημα αφιερώσαμε αρκετό χρόνο στις ιδιότητες των Γεννητριών Συναρτήσεων και στις εφαρμογές των ΓΣ στον υπολογισμό αθροισμάτων και την επίλυση προβλημάτων συνδυαστικής. Σχετικά παραδείγματα και ασκήσεις θα βρείτε τόσο στο βιβλίο όσο και στις σημειώσεις. Επίσης στο μάθημα μιλήσαμε για Εκθετικές Γεννήτριες Συναρτήσεις (δεν αναφέρονται στο βιβλίο - βλ. αντίστοιχο φυλλάδιο σημειώσεων).
Κεφάλαιο 10: όλο εκτός από τις 10.7, 10.8 και 10.9.
Επικοινωνία
Προσπαθήστε να παρακολουθείτε τις παραδόσεις. Η εμπειρία δείχνει ότι σε μαθήματα σαν και αυτό, η περιστασιακή και κατ' ιδίαν μελέτη δεν μπορεί να υποκαταστήσει την παρακολούθηση.Αν έχετε απορίες ή αντιμετωπίζετε δυσκολίες στη μελέτη σας, μη διστάσετε να τις συζητήσετε μαζί μου. Μπορείτε να με βρείτε στο γραφείο μου, στο 2ο όροφο του κτιρίου Λυμπέρη, ή στην τάξη.
Σημειώσεις - Διαλέξεις
Επίπεδα Γραφήματα. Επίσης μια συνοπτική απόδειξη του Θεωρήματος του Kuratowski.
Σύνολα Ανεξαρτησίας, Σύνολα Κάλυψης, και Χρωματικός Αριθμός.
Γεννήτριες Συναρτήσεις για την Επίλυση Προβλημάτων Συνδυαστικής.
Επίλυση Αναδρομικών Σχέσεων.
Η παράγραφος για τη λύση αναδρομικών σχέσεων με τη μέθοδο των Γεννητριών
Συναρτήσεων δεν είναι στην ύλη για τις εξετάσεις!
Εργασίες
Θα ανακοινωθούν δύο ατομικές, υποχρεωτικές εργασίες. Η πρώτη εργασία θα είναι σε Θεωρία Γραφημάτων και η δεύτερη σε Γεννήτριες Συναρτήσεις και Αναδρομικές Εξισώσεις. Οι ασκήσεις θα συνεισφέρουν συνολική βαθμολογία μεγαλύτερη από το 10 (bonus).
Εργασία 1. Ανακοινώθηκε 10/3/2005. Παράδοση 12/5/2005.
Ενδιάμεση Εξέταση - Βαθμολογία
Θα υπάρξει μία προαιρετική ενδιάμεση εξέταση (πρόοδος) με τη μορφή take-home exam στο χρονικό διάστημα από 7 - 22/4. Η ενδιάμεση εξέταση θα αποτελείται από δύο μέρη. Οι εκφωνήσεις θα μοιραστούν στα μαθήματα της 7/4 και 14/4, και οι λύσεις θα πρέπει να επιστραφούν στο διδάσκοντα στα μαθήματα της 14/4 και 21/4 αντίστοιχα. Η ενδιάμεση εξέταση δεν είναι υποχρεωτική, σας βοηθάει όμως να βελτιώσετε το βαθμό των γραπτών σας. Έστω ΒΓ ο βαθμός γραπτών, ΒΠ ο βαθμός της ενδιάμεσης εξέτασης, και ΒΕ ο βαθμός των εξετάσεων (Ιουνίου ή Σεπτεμβρίου). Ο βαθμός γραπτών είναι:
ΒΓ = max{ BE, 0.8 BE + 0.2 ΒΠ }
Αυτό σημαίνει ότι κάποιος μπορεί να έχει βαθμό γραπτών ίσο με 5 γράφοντας 4 στις τελικές εξετάσεις και 9 στην ενδιάμεση εξέταση.
Έστω Εργ1, Εργ2 ο βαθμός της πρώτης και δεύτερης εργασίας αντίστοιχα. Ο τελικός βαθμός είναι 0.8*ΒΓ + 0.1*Εργ1 + 0.1*Εργ2 αν ο βαθμός γραπτών είναι τουλάχιστον 5, και ΒΓ διαφορετικά. Για να περάσει κάποιος το μάθημα πρέπει να έχει τελικό βαθμό τουλάχιστον 5. Οι βαθμοί των εργασιών θα ισχύουν και το Σεπτέμβριο!
Μερικές Σχετικές Ιστοσελίδες
S. Britton. Graph Theory, Math 2009, The University of Sydney
T. Szabo and Y. Okamoto. Graph Theory, ETH.
Το Θεώρημα των Τεσσάρων Χρωμάτων: Η ιστορία της εικασία και οι ιδέες της απόδειξης.
Αν σας αρέσουν τα μαθηματικά και θέλετε να γίνετε πλούσιοι, κοιτάξτε τη σελίδα του
Βιβλιογραφία
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North Holland, 1976. (διαθέσιμο ηλεκτρονικά).
R. Diestel, Graph Theory, Springer, 2000. (διαθέσιμο ηλεκτρονικά).
F. Harary. Graph Theory. Addison-Wesley, 1972.
C.L. Liu. Introduction to Combinatorial Mathematics. McGraw-Hill, 1969.
C.L. Liu. Στοιχεία Διακριτών Μαθηματικών (μετ. Γραμμένου-Μπους). Πανεπιστημιακές Εκδόσεις Κρήτης, 2003.
Γ. Βουτσαδάκης, Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης. Διακριτά Μαθηματικά: Προβλήματα και Λύσεις. Gutenberg, 1994.