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

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

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

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

Διαλέξεις: 26/2 | 1/3 | 5/3 | 8/3 | 12/3 

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

Γενικά

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

  • Δ. Φωτάκης: Δευτέρα 14:30 - 15:00, στο WebEx meeting που γίνεται το μάθημα της Δευτέρας.
  • Δ. Σούλιου: Πέμπτη 16:00-17:00, στο WebEx link: .

  Περιεχόμενα

  • Σύνολα και πράξεις συνόλων.

  • Αριθμήσιμα και μη αριθμήσιμα σύνολα, αρχή της διαγωνιοποίησης, μη υπολογισιμότητα, παράδοξο του Russell.

  • Σχέσεις και συναρτήσεις. Διμελείς σχέσεις, ιδιότητες διμελών σχέσεων, σχέσεις ισοδυναμίας, σχέσεις μερικής και ολικής διάταξης, κλειστότητες σχέσεων.

  • Στοιχεία προτασιακής και κατηγορηματικής λογικής.

  • Αποδεικτικές διαδικασίες, μαθηματική επαγωγή, αρχή του περιστερώνα.

  • Στοιχεία Θεωρίας Γραφημάτων. Είδη γραφημάτων, βαθμός κορυφής, υπογραφήματα, ισομορφισμός γραφημάτων, κλίκες και ανεξάρτητα σύνολα, χρωματικός αριθμός.

  • Διαδρομή, μονοκονδυλιά, μονοπάτι, απόσταση, συντομότερες διαδρομές, κυκλώματα και ίχνη Euler, χαρακτηρισμός γραφημάτων με κύκλωμα Euler, κύκλοι και μονοπάτια Hamilton, ικανές και αναγκαίες συνθήκες, θεώρημα Dirac.

  • Δέντρα χαρακτηρισμός δέντρων, συνδετικά δέντρα και ιδιότητες, εφαρμογές.

  • Επίπεδα γραφήματα, τύπος του Euler, θεώρημα Kuratowski.

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

  • Αρχή εγκλεισμού-αποκλεισμού.

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

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

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

  • Στοιχεία Θεωρίας Αριθμών. Διαιρετότητα και πρώτοι αριθμοί, αλγόριθμος Ευκλείδη, αριθμητική modulo, γραμμικές ισοτιμίες, Κινέζικο θεώρημα υπολοίπων.

  • Ασυμπτωτικός συμβολισμός και ασυμπτωτική εκτίμηση.

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

  • Ιστοσελίδα του μαθήματος για προηγούμενα ακαδ. έτη: 2019-2020, 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.

  • DiscreteMath@MIT.

  • Μ. Κούτρας. Μάθημα Συνδυαστικής. Πανεπιστήμιο Πειραιά.

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

  • Μια χρήσιμη σύνοψη των περισσότερων βασικών εννοιών των Διακριτών Μαθηματικών (αναφέρεται και σε πολλές έννοιες που δεν θα συναντήσουμε στο μάθημα).

  • Σημειώσεις σχετικά με σύνολα και πράξεις συνόλων.

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

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

  • 1η Σειρά: Σύνολα. Προτασιακή και Κατηγορηματική Λογική.

   

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

  Παράδοση 26/2/2021

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

  Παράδοση 1/3/2021

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

  Παράδοση 5/3/2021

  • Μη υπολογισιμότητα.
  • Tο παράδοξο του Russell.

  Παράδοση 8/3/2021

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

  Παράδοση 12/3/2021

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

   

  Τελευταία αλλαγή: 22/2/2021, 19:00