Εθνικό Μετσόβιο Πολυτεχνείο
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών

Διακριτά Μαθηματικά

http://www.softlab.ntua.gr/~fotakis/discrete_math

Διακριτά Μαθηματικά

Μάθημα Επιλογής Κορμού, 4ου Εξαμήνου, Κωδικός 3.4.07.4

Εξάμηνο:

Εαρινό 2017

Διδάσκοντες:

Δημήτρης Φωτάκης		()		γρ. 1.1.10		τηλ: 210-772-4302
Δώρα Σούλιου		()		γρ. 1.1.30		τηλ: 210-772-1644

Ανακοινώσεις, Γενικά, Περιεχόμενα, Παλαιότερα Έτη, Βιβλιογραφία, Συμπληρωματικό Υλικό, Προτεινόμενες Ασκήσεις, Γραπτές Εργασίες, Διαλέξεις - Διαφάνειες, Φροντιστηριακές Διαλέξεις

Διαλέξεις: 3/3 | 6/3 | 13/3 | 17/3 | 20/3 | 24/3 | 27/3 | 31/3 | 3/4 | 6/4 | 7/4 | 24/4 | 28/4 | 5/5 | 8/5 | 12/5 | 15/5 | 18/5 | 19/5 | 22/5 | 26/5 | 29/5 | 1/6 | 9/6 | 12/6

Φροντιστηριακές Διαλέξεις: 27/4 | 26/5 | 15/6

Ανακοινώσεις

29/7/2017	Ανακοινώθηκε η βαθμολογία της εξέτασης του Ιουλίου (μαζί με τους βαθμούς από τις γραπτές εργασίες και τις online ασκήσεις - μόνο για όσους έδωσαν εξετάσεις, η βαθμολογία των εξετάσεων είναι με άριστα το 8, η βαθμολογία των online ασκήσεων είναι με άριστα το 2 και η βαθμολογία των γραπτών ασκήσεων είναι με άριστα το 15). Μπορείτε να δείτε τα γραπτά σας ή να ρωτήσετε σχετικά με την βαθμολογία σας την Δευτέρα 28 Αυγούστου, ώρα 16:00 - 18:00, στο Corelab (1.1.3, στο παλαιό κτήριο Ηλεκτρολόγων).
7/7/2017	Ανακοινώθηκε σχέδιο λύσεων για τα ερωτήματα της 3ης γραπτής εργασίας.
10/6/2017	Την Πέμπτη 15/6, ώρα 10:45 - 12:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 3, θα γίνει φροντιστηριακή διάλεξη.
31/5/2017	Ανακοινώθηκε η εκφώνηση της 3ης γραπτής εργασίας. Η προθεσμία για την παράδοσή της λήγει την Πέμπτη 6/7. Καλή Επιτυχία!
31/5/2017	Ανακοινώθηκε η 6η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 6η Online άσκηση λήγει την Δευτέρα 10/7. Καλή Επιτυχία!
23/5/2017	Αλλαγή ημερομηνίας διάλεξης: Η διάλεξη της Παρασκευής 2 Ιουνίου, θα γίνει την Πέμπτη 1 Ιουνίου, ώρα 14:45 - 16:30, στο Αμφιθέατρο 1.
23/5/2017	Την Παρασκευή 26/5, ώρα 15:15 - 17:00, στο Νέο Κτήριο Ηλεκτρολόγων, αίθουσα 007, θα γίνει φροντιστηριακή διάλεξη.
19/5/2017	Ανακοινώθηκε η 5η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 5η Online άσκηση λήγει την Δευτέρα 5/6. Καλή Επιτυχία!
10/5/2017	Ανακοινώθηκε η εκφώνηση της 2ης γραπτής εργασίας. Η προθεσμία για την παράδοσή της λήγει την Δευτέρα 29/5. Καλή Επιτυχία!
10/5/2017	Αλλαγή ημερομηνίας για τη διάλεξη αναπλήρωσης. Λόγω της ΓΣ του Φοιτητικού Συλλόγου, η διάλεξη αναπλήρωσης που έχουμε προγραμματίσει θα γίνει την Πέμπτη 18/5, ώρα 15:15 - 17:00, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 1.
5/5/2017	Ανακοινώθηκε η 4η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 4η Online άσκηση λήγει την Πέμπτη 18/5. Καλή Επιτυχία!
28/4/2017	Δίνεται μια μικρή παράταση στην προθεσμία για την παράδοση της 1ης γραπτής εργασίας μέχρι την Τετάρτη 3 Μαϊου. Μπορείτε να αφήσετε τις εργασίες σας στις θυρίδες των διδασκόντων.
24/4/2017	Την Πέμπτη 27/4, ώρα 15:15 - 17:00, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 1, θα γίνει φροντιστηριακή διάλεξη.
6/4/2017	Ανακοινώθηκε η εκφώνηση της 1ης γραπτής εργασίας. Η προθεσμία για την παράδοσή της λήγει την Παρασκευή 28/4. Καλή Επιτυχία!
6/4/2017	Ανακοινώθηκε η 3η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 3η Online άσκηση λήγει την Παρασκευή 28/4. Σχετικά με τις Online ασκήσεις, υπενθυμίζεται ότι έγκυρη θεωρείται μόνο η τελευταία υποβολή, εφόσον έχει άριστη βαθμολογία. Καλή Επιτυχία!
30/3/2017	Αλλαγή ημερομηνίας για τη διάλεξη αναπλήρωσης: Πέμπτη 6/4, ώρα 15:15 - 17:00, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 1, θα γίνει διάλεξη αναπλήρωσης.
23/3/2017	Ανακοινώθηκε η 2η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 2η Online άσκηση λήγει την Πέμπτη 6/4. Σχετικά με τις Online ασκήσεις, υπενθυμίζεται ότι έγκυρη θεωρείται μόνο η τελευταία υποβολή, εφόσον έχει άριστη βαθμολογία. Καλή Επιτυχία!
3/3/2017	Ανακοίνωση 1ης Online Ασκησης. Για να υποβάλλετε Online Ασκήσεις επισκεφθείτε το http://www.gradiance.com/services/servlet/COTC και δημιουργείστε λογαριασμό μέσω της επιλογής "Create New Account". Ως "Unique User ID" να χρησιμοποιήσετε το dm17_ΑριθμόςΜητρώου (π.χ. dm17_03115001), ως "First Name" να δώσετε το Ονοματεπώνυμό σας (με λατινικούς χαρακτήρες, π.χ. Dimitris Fotakis), και ως "Last Name" να δώσετε τον Αριθμό Μητρώου σας (π.χ. 03115001, βλ. επίσης εδώ). Αφού συνδεθείτε στο σύστημα με αυτά τα στοιχεία, κάνετε "Sign in" στο μάθημα χρησιμοποιώντας το "Class token" που δώσαμε στο μάθημα. Επιλέγοντας το μάθημα DM 2017 μπορείτε να δείτε την 1η Online Ασκηση, που έχει ήδη ανακοινωθεί, και αποτελείται από 7 απλά ερωτήματα στις βασικές έννοιες της Θεωρίας Συνόλων. Η προθεσμία για την υποβολή της λήγει την Κυριακή 19/3. Σημειώνεται ότι έγκυρη θεωρείται μόνο η τελευταία υποβολή, εφόσον αυτή έχει άριστη βαθμολογία. Καλή Επιτυχία!
3/3/2017	Ο τελικός βαθμός του μαθήματος υπολογίζεται ως εξής: όπου "ΤΒ" ο τελικός βαθμός, "Εξετ" ο βαθμός της τελικής εξέτασης, " Onl" ο βαθμός των Online ασκήσεων, και "ΓΑ" ο βαθμός των γραπτών εργασιών.
3/3/2017	Έναρξη μαθημάτων. Οι διαλέξεις του μαθήματος θα γίνονται κάθε Δευτέρα, ώρα 12:45-14:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 5, και κάθε Παρασκευή, ώρα 10:45-12:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 2. Οι διαλέξεις αναπλήρωσης, που τυχόν θα χρειαστούν, και οι φροντιστηριακές διαλέξεις θα γίνονται την Πέμπτη, ώρα 15:15 - 17:00.

Γενικά

Ώρες γραφείου διδασκόντων:
- Δ. Φωτάκης: Δευτέρα 15:00 - 16:00, στο (παλαιό) Κτήριο Ηλεκτρολόγων, γρ. 1.1.10, τηλ. 210-772-4302.
- Δ. Σούλιου: Τρίτη 12:45-14:45, στο (παλαιό) Κτήριο Ηλεκτρολόγων, γρ. 1.1.30, τηλ. 210-772-1644.

Περιεχόμενα

Σύνολα και πράξεις συνόλων.
Αριθμήσιμα και μη αριθμήσιμα σύνολα, αρχή της διαγωνιοποίησης, μη υπολογισιμότητα, παράδοξο του Russell.
Σχέσεις και συναρτήσεις. Διμελείς σχέσεις, ιδιότητες διμελών σχέσεων, σχέσεις ισοδυναμίας, σχέσεις μερικής και ολικής διάταξης, κλειστότητες σχέσεων.
Στοιχεία προτασιακής και κατηγορηματικής λογικής.
Αποδεικτικές διαδικασίες, μαθηματική επαγωγή, αρχή του περιστερώνα.
Στοιχεία Θεωρίας Γραφημάτων. Είδη γραφημάτων, βαθμός κορυφής, υπογραφήματα, ισομορφισμός γραφημάτων, κλίκες και ανεξάρτητα σύνολα, χρωματικός αριθμός.
Διαδρομή, μονοκονδυλιά, μονοπάτι, απόσταση, συντομότερες διαδρομές, κυκλώματα και ίχνη Euler, χαρακτηρισμός γραφημάτων με κύκλωμα Euler, κύκλοι και μονοπάτια Hamilton, ικανές και αναγκαίες συνθήκες, θεώρημα Dirac.
Δέντρα χαρακτηρισμός δέντρων, συνδετικά δέντρα και ιδιότητες, εφαρμογές.
Επίπεδα γραφήματα, τύπος του Euler, θεώρημα Kuratowski.
Συνδεσιμότητα γραφημάτων, γέφυρες και σύνολα κοπής, σημεία κοπής και διαχωριστές, θεώρημα Menger, δίκτυα και ροές.
Αρχή εγκλεισμού-αποκλεισμού.
Συνδυαστική απαρίθμηση. Κανόνες γινομένου και αθροίσματος, εφαρμογές αρχής εγκλεισμού-αποκλεισμού, μεταθέσεις και διατάξεις, συνδυασμοί, δυωνυμικοί συντελεστές, τρίγωνο του Pascal, διανομή διακεκριμένων και μη-διακεκριμένων αντικειμένων σε υποδοχές, κατασκευή μεταθέσεων και συνδυασμών, στοιχεία διακριτής πιθανότητας, στοιχεία θεωρίας πληροφορίας.
Γεννήτριες Συναρτήσεις. Βασικές ιδιότητες, εφαρμογή στον υπολογισμό αθροισμάτων, εφαρμογή στην επίλυση συνδυαστικών προβλημάτων, εκθετικές Γεννήτριες Συναρτήσεις.
Επίλυση γραμμικών αναδρομικών εξισώσεων με σταθερούς συντελεστές. Χαρακτηριστική εξίσωση, ομογενής λύση, ειδική λύση, επίλυση με τη μέθοδο των Γεννητριών Συναρτήσεων.
Στοιχεία Θεωρίας Αριθμών. Διαιρετότητα και πρώτοι αριθμοί, αλγόριθμος Ευκλείδη, αριθμητική modulo, γραμμικές ισοτιμίες, Κινέζικο θεώρημα υπολοίπων.
Ασυμπτωτικός συμβολισμός και ασυμπτωτική εκτίμηση.

Παλαιότερα Έτη

Ιστοσελίδα του μαθήματος για προηγούμενα ακαδ. έτη: 2015-2016, 2014-2015, 2013-2014, 2012-2013, 2011-2012, 2010-2011, 2009-2010, 2008-2009, 2007-2008.

Βιβλιογραφία

Φ. Αφράτη, Γ. Παπαγεωργίου. Στοιχεία Διακριτών Μαθηματικών. Έκδοση Ε.Μ.Π., 1990.
C.L. Liu. Στοιχεία Διακριτών Μαθηματικών (απόδοση στα Ελληνικά: Κ. Μπους και Δ. Γραμμένος). Πανεπιστημιακές Εκδόσεις Κρήτης, 2003.
K.H. Rosen. Discrete Mathematics and its Applications (6th Edition). McGraw-Hill, 2007.
L. Lovasz, J. Pelikan, K. Vesztergombi. Discrete Mathematics: Elementary and Beyond. Springer, 2003.
L. Lovasz, K. Vesztergombi. Discrete Mathematics. Lecture Notes, Yale University, 1999.
S. Epp. Discrete Mathematics with Applications. Wadsworth, 1990.
R.L. Grimaldi. Discrete and Combinatorial Mathematics: An Applied Introduction (5th Edition). Addison-Wesley, 2003.
C.L. Liu. Introduction to Combinatorial Mathematics. McGraw-Hill, 1969.
R.L. Graham, D.E. Knuth, O. Patashnik. Concrete Mathematics. Addison-Wesley, 1989.
Η. Κουτσουπιάς. Μαθηματικά της Πληροφορικής. ΕΚΠΑ, Οκτώβριος 2009.
Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης. Διακριτά Μαθηματικά: Τα Μαθηματικά της Επιστήμης των Υπολογιστών. Gutenberg, 1994.
Γ. Βουτσαδάκης, Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης. Διακριτά Μαθηματικά: Προβλήματα και Λύσεις. Gutenberg, 1994.
Α. Συμβώνης. Διαφάνειες και υλικό μαθήματος Θεωρία Γραφημάτων.
Δ. Θηλυκός. Σημειώσεις στη Θεωρία Γραφημάτων.
R. Diestel. Graph Theory (4th edition), Springer, 2010.
DiscreteMath@MIT.
Μ. Κούτρας. Μάθημα (και βιβλίο) Συνδυαστικής. Πανεπιστήμιο Πειραιά.

Συμπληρωματικό Υλικό - Σημειώσεις

Κάποιες σημειώσεις για τεχνικές επίλυσης αναδρομικών σχέσεων (Δ. Φωτάκης).
Κάποιες σημειώσεις στις βασικές ιδιότητες των Γεννητριών Συναρτήσεων (Δ. Φωτάκης) και στις εφαρμογές τους.
Κάποιες σημειώσεις στις βασικές έννοιες της συνδυαστικής (Δ. Φωτάκης), μια χρήσιμη σύνοψη σε μορφή διαγράμματος, και η ίδια σύνοψη ενημερωμένη με τις αντίστοιχες Γεννήτριες Συναρτήσεις).
Κάποιες σημειώσεις στις βασικές έννοιες της Θεωρίας Γραφημάτων (Δ. Φωτάκης). Δείτε ακόμη εδώ για αντίστοιχο υλικό.
Σημειώσεις σχετικά με σύνολα και πράξεις συνόλων.
Μια χρήσιμη σύνοψη των περισσότερων βασικών εννοιών των Διακριτών Μαθηματικών (αναφέρεται και σε πολλές έννοιες που δεν θα συναντήσουμε στο μάθημα).
Κάποιες σημειώσεις σχετικά με το συντακτικό και την σημασιολογία της Πρωτοβάθμιας Λογικής (Δ. Φωτάκης).
Σημειώσεις για την αποδεικτική τεχνική της Μαθηματικής Επαγωγής (Δ. Φωτάκης).

Προτεινόμενες Ασκήσεις

Οι προτεινόμενες ασκήσεις στοχεύουν στην (περαιτέρω) εξάσκηση των φοιτητών στο αντικείμενο του μαθήματος. Συνίσταται να τις λύνετε, αλλά δεν έχετε υποχρέωση να παραδώσετε τις λύσεις τους και οι λύσεις τους δεν βαθμολογούνται. Κάποιες από τις προτεινόμενες ασκήσεις θα συζητούνται στο φροντιστήριο. Ενδεικτικές λύσεις τους θα αναρτώνται δύο εβδομάδες περίπου μετά την ανακοίνωσή τους (ανάλογα και με την πρόοδο των διαλέξεων).

1η Σειρά: Σύνολα. Προτασιακή και Κατηγορηματική Λογική. Σχέδιο Λύσεων.
2η Σειρά: Κατηγορηματική Λογική. Μαθηματική Επαγωγή. Αρχή του Περιστερώνα. Σχέδιο Λύσεων.
3η Σειρά: Κατηγορηματική Λογική. Αλυσίδες και Αντιαλυσίδες. Γραφήματα. Σχέδιο Λύσεων.
4η Σειρά: Αρχή Εγκλεισμού-Αποκλεισμού. Συνδυαστική. Σχέδιο Λύσεων
5η Σειρά: Γεννήτριες Συναρτήσεις και εφαρμογές τους στη συνδυαστική. Σχέδιο Λύσεων.