Εθνικό Μετσόβιο Πολυτεχνείο Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών Διακριτά Μαθηματικά http://www.softlab.ntua.gr/~fotakis/discrete_math

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

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

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

Διαλέξεις: 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 

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

Γενικά

• Ώρες γραφείου διδασκόντων:

  • Δ. Φωτάκης: Δευτέρα 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η Σειρά: Γεννήτριες Συναρτήσεις και εφαρμογές τους στη συνδυαστική. Σχέδιο Λύσεων.

Γραπτές Εργασίες

• Εκφώνηση της 1ης γραπτής εργασίας. Σχέδιο λύσεων.
• Εκφώνηση της 2ης γραπτής εργασίας. Σχέδιο λύσεων.
• Εκφώνηση της 3ης γραπτής εργασίας. Παράδοση εργασιών μέχρι την Πέμπτη 6/7.

Διαλέξεις - Διαφάνειες

Παράδοση 3/3/2017

• Διαδικαστικά θέματα, εισαγωγή.
• Σύνολα και πράξεις συνόλων.

Παράδοση 6/3/2017

• Αριθμήσιμα και μη αριθμήσιμα σύνολα. Αρχή της Διαγωνιοποίησης.

Παράδοση 13/3/2017

• Μη υπολογισιμότητα, το παράδοξο του Russell.
• Διμελείς Σχέσεις: Βασικοί ορισμοί και ιδιότητες.

Παράδοση 17/3/2017

• Διμελείς Σχέσεις: Βασικοί ορισμοί και ιδιότητες, σχεσιακό μοντέλο Βάσεων Δεδομένων.
• Κλειστότητες, μεταβατική κλειστότητα.

Παράδοση 20/3/2017

• Κλειστότητες: αλγόριθμος Warshall.
• Σχέσεις Ισοδυναμίας.
• Σχέσεις Διάταξης.

Παράδοση 24/3/2017

• Σχέσεις Διάταξης.
• Στοιχεία Προτασιακής Λογικής.

Παράδοση 27/3/2017

• Στοιχεία Προτασιακής Λογικής.
• Προτασιακός Λογισμός.

Παράδοση 31/3/2017

• Στοιχεία Κατηγορηματικής Λογικής.

Παράδοση 3/4/2017

• Στοιχεία Κατηγορηματικής Λογικής.

Παράδοση 6/4/2017

• Αποδεικτικές Τεχνικές
• Μαθηματική Επαγωγή.

Παράδοση 7/4/2017

• Αρχή του Περιστερώνα.
• Βασικές έννοιες Θεωρίας Γραφημάτων.

Παράδοση 24/4/2017

• Γραφήματα: Βασικές Έννοιες: βαθμός κορυφής, διμερή γραφήματα, υπογραφήματα, αριθμοί Ramsey.

Παράδοση 28/4/2017

• Γραφήματα: συνεκτικότητα, κύκλος Euler.

Παράδοση 5/5/2017

• Γραφήματα: κύκλος Hamilton.
• Γραφήματα: αναπαράσταση γραφημάτων, ισομορφισμός γραφημάτων.

Παράδοση 8/5/2017

• Δέντρα, συνδετικά δέντρα.
• Ελάχιστο Συνδετικό Δέντρο.

Παράδοση 12/5/2017

• Ελάχιστο Συνδετικό Δέντρο. (παραδείγματα αλγορίθμων Kruskal και Prim).
• Επίπεδα γραφήματα.

Παράδοση 15/5/2017

• Χρωματικός αριθμός γραφημάτων.
• Σύνολα ανεξαρτησίας και καλύμματα κορυφών.
• Αρχή εγκλεισμού - αποκλεισμού.

Παράδοση 18/5/2017

• Συνδυαστική απαρίθμηση: κανόνες γινομένου και αθροίσματος, διατάξεις.

Παράδοση 19/5/2017

• Συνδυαστική απαρίθμηση: συνδυασμοί.
• Συνδυαστική απαρίθμηση: παραδείγματα και ασκήσεις.

Παράδοση 22/5/2017

• Συνδυαστική απαρίθμηση: παραδείγματα και ασκήσεις.
• Χρήση συνδυαστικής για τον υπολογισμό πιθανοτήτων σε διακριτούς δειγματοχώρους.

Παράδοση 26/5/2017

• Βασικές ιδιότητες δυωνυμικών συντελεστών.
• Γεννήτριες Συναρτήσεις: ορισμός και βασικές ιδιότητες.
• Γεννήτριες Συναρτήσεις: εφαρμογές στην απαρίθμηση συνδυασμών.

Παράδοση 29/5/2017

• Γεννήτριες Συναρτήσεις: εφαρμογές στην απαρίθμηση συνδυασμών.
• Εκθετικές γεννήτριες συναρτήσεις και απαρίθμηση διατάξεων.

Παράδοση 1/6/2017

• Εκθετικές γεννήτριες συναρτήσεις και απαρίθμηση διατάξεων.
• Διατύπωση αναδρομικών σχέσεων.
• Επίλυση αναδρομικών σχέσεων.

Παράδοση 9/6/2017

• Βασικές έννοιες θεωρίας αριθμών: πρώτοι αριθμοί, ΜΚΔ, αλγόριθμος Ευκλείδη, συνάρτηση Euler.

Παράδοση 12/6/2017

• Βασικές έννοιες θεωρίας αριθμών: αριθμητική modulo, αλγεβρικές δομές, μικρό θεώρημα Fermat, θεώρημα Lagrange.

Φροντιστηριακές Διαλέξεις

Φροντιστήριο 27/4/2017

• Σύνολα, Σχέσεις, Προτασιακή και Κατηγορηματική Λογική (διαφάνειες).

Φροντιστήριο 26/5/2017

• Ασκήσεις σε Θεωρία Γραφημάτων.

Φροντιστήριο 15/6/2017

• Ασκήσεις στη Συνδυαστική.