Εθνικό Μετσόβιο Πολυτεχνείο
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών
Διακριτά Μαθηματικά
http://www.softlab.ntua.gr/~fotakis/discrete_math |
Εθνικό Μετσόβιο Πολυτεχνείο Διακριτά Μαθηματικά http://www.softlab.ntua.gr/~fotakis/discrete_math |
Μάθημα Επιλογής Κορμού, 4ου Εξαμήνου, Κωδικός 3.4.3209.4
|
Εξάμηνο: |
Εαρινό 2020 | ||||||||||||||||
|
|
Ανακοινώσεις, Γενικά, Περιεχόμενα, Παλαιότερα Έτη, Βιβλιογραφία, Συμπληρωματικό Υλικό, Προτεινόμενες Ασκήσεις, Γραπτές Εργασίες, Διαλέξεις - Διαφάνειες Φροντιστηριακές Διαλέξεις
Διαλέξεις: 28/2 | 9/3 | 16/3 | 20/3 | 23/3 | 27/3 | 30/3 | 3/4 | 6/4 | 10/4 | 13/4 | 24/4 | 27/4 | 4/5 | 8/5 | 11/5 | 15/5 | 18/5 | 22/5 | 25/5 | 28/5 | 1/6 | 5/6 | 10/6 | 12/6
Φροντιστηριακές Διαλέξεις: 8/4 | 20/5 | 3/6
|
5/6/2020 |
Η εξέταση του μαθήματος “Διακριτά Μαθηματικά” (4ο εξάμηνο, επιλογής, κορμού) στη θερινή εξεταστική περίοδο θα διεξαχθεί σύμφωνα με τον τρόπο εξέτασης Β2γ (βλ. απόφαση της 6ης/2020 συνεδρίασης της Συγκλήτου του ΕΜΠ, 29/5/2020, όπως δημοσιεύθηκε στη Διαύγεια: ΑΔΑ: ΡΟ8Τ46ΨΖΣ4-ΟΒΓ). Πιο συγκεκριμένα, θα δοθεί ηλεκτρονική σύγχρονη εξ αποστάσεως εξέταση, συνολικής διάρκειας περίπου 2 ωρών, σε σπονδυλωτή μορφή, σύμφωνα με το πρόγραμμα των εξετάσεων της Σχολής. Η ταυτοποίηση των εξεταζομένων θα γίνει με τη χρήση των ηλεκτρονικών κωδικών του ΕΜΠ. Τα θέματα της εξέτασης θα είναι είτε πολλαπλής επιλογής είτε μικρές ερωτήσεις ανοιχτού τύπου και θα καλύπτουν όλη την ύλη του μαθήματος. Η τελική βαθμολογία θα προκύψει ως εξής:
|
|
5/6/2020 |
Ανακοινώθηκε η 6η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 6η Online άσκηση λήγει την Τετάρτη 17/6. Καλή Επιτυχία! |
29/5/2020 |
Την Τετάρτη 10/6, ώρα 12:45 - 14:30, θα γίνει διάλεξη αναπλήρωσης (μέσω του Microsoft Τeams) (θα αναπληρώσουμε τη διάλεξη της Δευτέρας 8/6, που δεν θα γίνει λόγω της αργίας του Αγ. Πνεύματος). |
29/5/2020 |
Την Τετάρτη 3/6, ώρα 12:45 - 14:30, θα γίνει φροντιστηριακή διάλεξη (μέσω του Microsoft Τeams). |
|
22/5/2020 |
Ανακοινώθηκε η 5η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 5η Online άσκηση λήγει την Πέμπτη 4/6. Καλή Επιτυχία! |
22/5/2020 |
Δίνεται παράταση στην προθεσμία για την παράδοση της 2ης γραπτής εργασίας μέχρι την Κυριακή 31 Μαϊου. |
15/5/2020 |
Την Τετάρτη 20/5, ώρα 12:45 - 14:30, θα γίνει φροντιστηριακή διάλεξη (μέσω του Microsoft Τeams). |
|
6/5/2020 |
Ανακοινώθηκε η εκφώνηση της 2ης γραπτής εργασίας. Η προθεσμία για την παράδοσή της λήγει την Κυριακή 24/5. Καλή Επιτυχία! |
|
27/4/2020 |
Ανακοινώθηκε η 4η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 4η Online άσκηση λήγει την Δευτέρα 11/5. Καλή Επιτυχία! |
|
27/4/2020 |
Ανακοινώθηκαν οι ενδεικτικές λύσεις της 1ης γραπτής εργασίας. |
|
10/4/2020 |
Ανακοινώθηκε η 3η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 3η Online άσκηση λήγει την Δευτέρα 27/4. Σχετικά με τις Online ασκήσεις, υπενθυμίζεται ότι έγκυρη θεωρείται μόνο η τελευταία υποβολή, εφόσον έχει άριστη βαθμολογία. Καλή Επιτυχία! |
6/4/2020 |
Την Μ. Δευτέρα 13/4, ώρα 12:45 - 14:30, και την Παρασκευή 24/4, ώρα 10:45 - 12:30, θα γίνουν διάλεξεις αναπλήρωσης (μέσω του Microsoft Τeams). |
6/4/2020 |
Την Τετάρτη 8/4, ώρα 12:45 - 14:30, θα γίνει φροντιστηριακή διάλεξη (μέσω του Microsoft Τeams). |
|
27/3/2020 |
Ανακοινώθηκε η εκφώνηση της 1ης γραπτής εργασίας. Η προθεσμία για την παράδοσή της λήγει την Δευτέρα 20/4. Δείτε εδώ για την ηλεκτρονική υποβολή της 1ης γραπτής εργασίας. Καλή Επιτυχία! |
|
19/3/2020 |
Ανακοινώθηκε η 2η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 2η Online άσκηση λήγει την Τρίτη 31/3. Σχετικά με τις Online ασκήσεις, υπενθυμίζεται ότι έγκυρη θεωρείται μόνο η τελευταία υποβολή, εφόσον έχει άριστη βαθμολογία. Καλή Επιτυχία! |
13/3/2020 |
Από την Δευτέρα 16/3, οι διαλέξεις του μαθήματος θα γίνονται διαδικτυακά, σύμφωνα με το ωρολόγιο πρόγραμμα, μέσω του περιβάλλοντος Microsoft Teams. Για να παρακολουθήσετε τις διαλέξεις, πρέπει να συνδεθείτε στο office365, μέσω του delos365.grnet.gr, χρησιμοποιώντας τον λογαριασμό που έχετε στο ΕΜΠ. Στη συνέχεια, ακολουθήστε τις οδηγίες που αναφέρονται εδώ. Ο κωδικός για την σύνδεση στην "ομάδα" του μαθήματος έχει σταλθεί στο email που δηλώσατε στο Gradiance. Οι διαλέξεις θα γίνονται record και θα είναι διαθέσιμες εκ των υστέρων μέσω του Teams. |
|
28/2/2020 |
Ανακοίνωση 1ης Online Ασκησης. Για να υποβάλλετε Online Ασκήσεις επισκεφθείτε το http://www.gradiance.com/services/servlet/COTC και δημιουργείστε λογαριασμό μέσω της επιλογής "Create New Account". Ως "Unique User ID" να χρησιμοποιήσετε το dm20_ΑριθμόςΜητρώου (π.χ. dm20_03118001), ως "First Name" να δώσετε το Ονοματεπώνυμό σας (με λατινικούς χαρακτήρες, π.χ. Dimitris Fotakis), και ως "Last Name" να δώσετε τον Αριθμό Μητρώου σας (π.χ. 03118001, βλ. επίσης εδώ). Αφού συνδεθείτε στο σύστημα με αυτά τα στοιχεία, κάνετε "Sign in" στο μάθημα χρησιμοποιώντας το "Class token" που δώσαμε στο μάθημα. Επιλέγοντας το μάθημα DM 2020 μπορείτε να δείτε την 1η Online Ασκηση, που έχει ήδη ανακοινωθεί, και αποτελείται από 7 απλά ερωτήματα στις βασικές έννοιες της Θεωρίας Συνόλων. Η προθεσμία για την υποβολή της λήγει την Παρασκευή 13/3. Σημειώνεται ότι έγκυρη θεωρείται μόνο η τελευταία υποβολή, εφόσον αυτή έχει άριστη βαθμολογία. Καλή Επιτυχία! |
|
28/2/2020 |
Ο τελικός βαθμός του μαθήματος υπολογίζεται ως εξής:
|
|
28/2/2020 |
Έναρξη μαθημάτων. Οι διαλέξεις του μαθήματος θα γίνονται κάθε Δευτέρα, ώρα 12:45-14:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 2, και κάθε Παρασκευή, ώρα 10:45-12:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 2. |
Ώρες γραφείου διδασκόντων:
Σύνολα και πράξεις συνόλων.
Αριθμήσιμα και μη αριθμήσιμα σύνολα, αρχή της διαγωνιοποίησης, μη υπολογισιμότητα, παράδοξο του Russell.
Σχέσεις και συναρτήσεις. Διμελείς σχέσεις, ιδιότητες διμελών σχέσεων, σχέσεις ισοδυναμίας, σχέσεις μερικής και ολικής διάταξης, κλειστότητες σχέσεων.
Στοιχεία προτασιακής και κατηγορηματικής λογικής.
Αποδεικτικές διαδικασίες, μαθηματική επαγωγή, αρχή του περιστερώνα.
Στοιχεία Θεωρίας Γραφημάτων. Είδη γραφημάτων, βαθμός κορυφής, υπογραφήματα, ισομορφισμός γραφημάτων, κλίκες και ανεξάρτητα σύνολα, χρωματικός αριθμός.
Διαδρομή, μονοκονδυλιά, μονοπάτι, απόσταση, συντομότερες διαδρομές, κυκλώματα και ίχνη Euler, χαρακτηρισμός γραφημάτων με κύκλωμα Euler, κύκλοι και μονοπάτια Hamilton, ικανές και αναγκαίες συνθήκες, θεώρημα Dirac.
Δέντρα χαρακτηρισμός δέντρων, συνδετικά δέντρα και ιδιότητες, εφαρμογές.
Επίπεδα γραφήματα, τύπος του Euler, θεώρημα Kuratowski.
Συνδεσιμότητα γραφημάτων, γέφυρες και σύνολα κοπής, σημεία κοπής και διαχωριστές, θεώρημα Menger, δίκτυα και ροές.
Αρχή εγκλεισμού-αποκλεισμού.
Συνδυαστική απαρίθμηση. Κανόνες γινομένου και αθροίσματος, εφαρμογές αρχής εγκλεισμού-αποκλεισμού, μεταθέσεις και διατάξεις, συνδυασμοί, δυωνυμικοί συντελεστές, τρίγωνο του Pascal, διανομή διακεκριμένων και μη-διακεκριμένων αντικειμένων σε υποδοχές, κατασκευή μεταθέσεων και συνδυασμών, στοιχεία διακριτής πιθανότητας, στοιχεία θεωρίας πληροφορίας.
Γεννήτριες Συναρτήσεις. Βασικές ιδιότητες, εφαρμογή στον υπολογισμό αθροισμάτων, εφαρμογή στην επίλυση συνδυαστικών προβλημάτων, εκθετικές Γεννήτριες Συναρτήσεις.
Επίλυση γραμμικών αναδρομικών εξισώσεων με σταθερούς συντελεστές. Χαρακτηριστική εξίσωση, ομογενής λύση, ειδική λύση, επίλυση με τη μέθοδο των Γεννητριών Συναρτήσεων.
Στοιχεία Θεωρίας Αριθμών. Διαιρετότητα και πρώτοι αριθμοί, αλγόριθμος Ευκλείδη, αριθμητική modulo, γραμμικές ισοτιμίες, Κινέζικο θεώρημα υπολοίπων.
Ασυμπτωτικός συμβολισμός και ασυμπτωτική εκτίμηση.
Ιστοσελίδα του μαθήματος για προηγούμενα ακαδ. έτη: 2018-2019, 2017-2018, 2016-2017, 2015-2016, 2014-2015, 2013-2014, 2012-2013, 2011-2012, 2010-2011, 2009-2010, 2008-2009.
Φ. Αφράτη, Γ. Παπαγεωργίου. Στοιχεία Διακριτών Μαθηματικών. Έκδοση Ε.Μ.Π., 1990.
C.L. Liu. Στοιχεία Διακριτών Μαθηματικών (απόδοση στα Ελληνικά: Κ. Μπους και Δ. Γραμμένος). Πανεπιστημιακές Εκδόσεις Κρήτης, 2003.
K.H. Rosen. Discrete Mathematics and its Applications (6th Edition). McGraw-Hill, 2007.
D.J. Hunter. Essentials of Discrete Mathematics (3rd Edition). Jones & Bartlett Learning, 2015.
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.
Μ. Κούτρας. Μάθημα Συνδυαστικής. Πανεπιστήμιο Πειραιά.
Μια χρήσιμη σύνοψη των περισσότερων βασικών εννοιών των Διακριτών Μαθηματικών (αναφέρεται και σε πολλές έννοιες που δεν θα συναντήσουμε στο μάθημα).
Σημειώσεις σχετικά με σύνολα και πράξεις συνόλων.
Σημειώσεις για την αποδεικτική τεχνική της Μαθηματικής Επαγωγής (Δ. Φωτάκης).
Κάποιες σημειώσεις σχετικά με το συντακτικό και την σημασιολογία της Πρωτοβάθμιας Λογικής (Δ. Φωτάκης).
Κάποιες σημειώσεις στις βασικές έννοιες της Θεωρίας Γραφημάτων (Δ. Φωτάκης). Δείτε ακόμη εδώ για αντίστοιχο υλικό.
Μια σύντομη απόδειξη του Θεωρήματος Kuratowski.
Κάποιες σημειώσεις στις βασικές έννοιες της συνδυαστικής (Δ. Φωτάκης), μια χρήσιμη σύνοψη σε μορφή διαγράμματος και η ίδια σύνοψη ενημερωμένη με τις αντίστοιχες Γεννήτριες Συναρτήσεις).
Κάποιες σημειώσεις στις βασικές ιδιότητες των Γεννητριών Συναρτήσεων (Δ. Φωτάκης) και στις εφαρμογές τους.
Τελευταία αλλαγή: 28/2/2020, 15:00
