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

Περιγραφή θέματος

• 

  Γενικά

  • Ανακοινώσεις Φόρουμ

    Εδώ αναρτώνται οι γενικές ανακοινώσεις από τους διδάσκοντες προς τους εγγεγραμμένους φοιτητές, οι οποίοι τις λαμβάνουν και στην ηλεκτρονική τους διεύθυνση.
    
    
  • Forum Ερωτήσεων/Απαντήσεων Φόρουμ

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

    Οι φοιτητές μπορούν να δηλώσουν με την εγγραφή τους αν θέλουν να ενημερώνονται για τις αναρτώμενες ερωταπαντήσεις.

    
    

• 

  Διδάσκοντες - Βοηθοί Διδασκαλίας

  • Δημήτρης Φωτάκης, Καθηγητής ()
  • Δώρα Σούλιου, Ε.ΔΙ.Π ()

  
  

  Ώρες Γραφείου Διδασκόντων

  • Δημήτρης Φωτάκης: Δευτέρα 14:30 - 15:15, στο γραφείο 1.1.10, (Παλαιό) Κτήριο Ηλεκτρολόγων.
  • Δώρα Σούλιου: Τρίτη 15:10 - 17:00, στο γραφείο 1.1.30, (Παλαιό) Κτήριο Ηλεκτρολόγων.
    

  
  
• 

  Γενικές Πληροφορίες

  Οι διαλέξεις του μαθήματος γίνονται:
  
  

  • κάθε Δευτέρα, ώρες 12:40-14:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 2.
  • κάθε Παρασκευή, ώρες 10:40-12:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 2.

  Η πρώτη διάλεξη για το εαρινό εξάμηνο του 2023 θα γίνει την Παρασκευή 24 Φεβρουαρίου, 10:40 - 12:30, στο Αμφ. 2.

  Οι διαλέξεις αναπλήρωσης, που τυχόν θα χρειαστούν, ή επιπλέον διαλέξεις για την επίλυση ασκήσεων θα γίνονται Τρίτη, ώρες 15:10 - 17:00, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 2.
• 

  Βαθμολογικό Σχήμα

  Το μάθημα περιλαμβάνει 6 σειρές online ασκήσεων που εκπονούνται στο σύστημα gradiance και 3 σειρές γραπτών ασκήσεων. Ο τελικός βαθμός του μαθήματος υπολογίζεται ως εξής: 
  
  

  • Τελικός βαθμός = 0.8*(Βαθμός Τελικής Εξέτασης) + 0.2*(Βαθμός Online Ασκήσεων) + 0.15*(Βαθμός Γραπτών Ασκήσεων), αν 0.8*(Βαθμός Τελικής Εξέτασης) + 0.2*(Βαθμός Online Ασκήσεων) >= 5.0.
  • Τελικός βαθμός = 0.8*(Βαθμός Τελικής Εξέτασης) + 0.2*(Βαθμός Online Ασκήσεων), διαφορετικά.
• 

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

  • Φ. Αφράτη, Γ. Παπαγεωργίου. Στοιχεία Διακριτών Μαθηματικών. Έκδοση Ε.Μ.Π., 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.
  • Μ. Κολουντζάκης και Χ. Παπαχριστόδουλος. Διακριτά μαθηματικά. Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις, 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.
  • Μ. Κούτρας. Μάθημα Συνδυαστικής. Πανεπιστήμιο Πειραιά.
  • Κ. Δημητρακόπουλος. Σημειώσεις Μαθηματικής Λογικής. Πανεπιστήμιο Αθηνών, 1999. 

  
  
• 

  Περιεχόμενα

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

  
  
• 

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

  • Ιστοσελίδα του μαθήματος για προηγούμενα ακαδημαϊκά έτη: 2021-2022, 2020-2021, 2019-2020, 2018-2019, 2017-2018, 2016-2017, 2015-2016, 2014-2015, 2013-2014, 2012-2013, 2011-2012, 2010-2011, 2009-2010, 2008-2009.
  • Στην ιστοσελίδα του μαθήματος για το ακαδ. έτος 2020-2021, μπορείτε να βρείτε βιντεοσκοπημένες διαλέξεις. 

  
  
  
• 

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

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

  
  
• 

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

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

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

  
  
• 

  Διαλέξεις

  • Διάλεξη 24/2/2023. Διαδικαστικά θέματα, εισαγωγή, Gradiance. Σύνολα και πράξεις συνόλων.
  • Διάλεξη 6/3/2023. Αριθμήσιμα και μη αριθμήσιμα σύνολα.
  • Διάλεξη 10/3/2023. Τεχνικές απαρίθμησης αριθμήσιμων συνόλων. Αρχή Διαγωνιοποίησης. Μη υπολογισιμότητα.
  • Διάλεξη 13/3/2023. Στοιχεία Κατηγορηματικής Λογικής: συντακτικό, ελεύθερες και δεσμευμένες μεταβλητές, εναλλαγή ποσοδεικτών, διατύπωση προτάσεων στην Πρωτοβάθμια γλώσσα.
  • Διάλεξη 20/3/2023. Στοιχεία Κατηγορηματικής Λογικής: ερμηνεία, διατύπωση προτάσεων στην Πρωτοβάθμια γλώσσα.
  • Διάλεξη 24/3/2023. Στοιχεία Κατηγορηματικής Λογικής: διατύπωση προτάσεων στην Πρωτοβάθμια γλώσσα.
  • Διάλεξη 27/3/2023. Στοιχεία Κατηγορηματικής Λογικής: ερμηνεία, ορισμός αλήθειας Tarski, σημασιολογική προσέγγιση, λογική εγκυρότητα, ιδιότητες ποσοδεικτών, κανονική ποσοδεικτική μορφή.
  • Διάλεξη 31/3/2023. Σχέσεις, διμελείς σχέσεις, ιδιότητες, κλειστότητες, μεταβατική κλειστότητα.
  • Διάλεξη 3/4/2023. Mεταβατική κλειστότητα, υπολογισμός μεταβατικής κλειστότητας. Σχέσεις ισοδυναμίας.
  • Διάλεξη 4/4/2023. Σχέσεις διάταξης.
  • Διάλεξη 7/4/2023. Σχέσεις διάταξης. Διατύπωση αναδρομικών σχέσεων. Με΄γιστη αύξουσα υπακολουθία.
  • Διάλεξη 24/4/2023. Αποδεικτικές τεχνικές. Μαθηματική επαγωγή.
  • Διάλεξη 25/4/2023. Μαθηματική επαγωγή. Αρχή περιστερώνα. 
  • Διάλεξη 28/4/2023. Αρχή περιστερώνα. Βασικές έννοιες θεωρίας γραφημάτων: εισαγωγικά, βαθμός κορυφής, ανεξάρτητο σύνολο, υπολογισμός μέγιστου ανεξάρτητου συνόλου.
  • Διάλεξη 2/5/2023. Βασικές έννοιες θεωρίας γραφημάτων: διμερή γραφήματα, υπογραφήματα, ασκήσεις. 
  • Διάλεξη 5/5/2023. Βασικές έννοιες θεωρίας γραφημάτων: αριθμοί Ramsey, συνεκτικότητα, ασκήσεις. κύκλος Euler, κύκλος Hamilton, ασκήσεις.
  • Διάλεξη 8/5/2023. Βασικές έννοιες θεωρίας γραφημάτων: κύκλος Euler, κύκλος Hamilton, ασκήσεις.
  • Διάλεξη 12/5/2023. Αναπαράσταση γραφημάτων, ισομορφισμός γραφημάτων, αυτοσυμπληρωματικά γραφήματα, αυτομορφισμός.
  • Διάλεξη 15/5/2023. Επίπεδα γραφήματα. Δέντρα. 
  • Διάλεξη 16/5/2023. Συνδετικά δέντρα, υπολογισμός Ελάχιστου Συνδετικού Δέντρου. Χρωματικός αριθμός. 
  • Διάλεξη 22/5/2023. Ανεξάρτητα σύνολο και καλύμματα κορυφών. Ταιριάσματα σε διμερή γραφήματα, θεώρημα Konig-Hall (απλή αναφορά). Εγκλεισμός Αποκλεισμός.  
  • Διάλεξη 26/5/2023. Συνδυαστική απαρίθμηση: κανόνες αθροίσματος και γινομένου, διατάξεις, συνδυασμοί. 
  • Διάλεξη 29/5/2023. Συνδυαστική απαρίθμηση: διατάξεις και συνδυασμοί, παραδείγματα και ασκήσεις.
  • Διάλεξη 2/6/2023. Συνδυαστική απαρίθμηση και διακριτή πιθανότητα, ιδιότητες διωνυμικών συντελεστών. Γεννήτριες συναρτήσεις, βασικές ιδιότητες υπολογισμός αθροισμάτων. 
  • Διάλεξη 6/6/2023. Εφαρμογή γεννητριών συναρτήσεων στη συνδυαστική, συνήθεις γεννήτριες συναρτήσεις και απαρίθμηση συνδυασμών. 
  • Διάλεξη 9/6/2023. Εφαρμογή γεννητριών συναρτήσεων στη συνδυαστική, εκθετικές γεννήτριες συναρτήσεις και απαρίθμηση διατάξεων. Διατύπωση και επίλυση γραμμικών αναδρομικών σχέσεων με τη μέθοδο των γεννητριών συναρτήσεων. 
• 

  Φροντιστήρια

  • Φροντιστήριο 4/4/2023. Κατηγορηματική Λογική.
• 

  Γραπτές Ασκήσεις

  • Θα ανακοινωθούν τρεις (3) σειρές γραπτών ασκήσεων. 
  • Οι γραπτές ασκήσεις υποβάλλονται στη σελίδα του μαθήματος, στο helios. Δεν γίνεται δεκτή η παράδοση ασκήσεων με e-mail.
  • Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά, π.χ. αφού αφιερώσετε ικανό χρόνο ατομικής προσπάθειας), αλλά τελικά κάθε φοιτητής πρέπει να διατυπώσει μόνος του τη λύση. Πανομοιότυπες διατυπώσεις θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές ασκήσεων.
    

  
  

  Εκφωνήσεις Γραπτών Ασκήσεων

  • 1η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 4/5/2023. 
  • 2η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 27/5/2023. 
  • 3η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 22/6/2023.