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

  • Γενικά

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

    • Φόρουμ εικονίδιο
      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.

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

    Η πρώτη διάλεξη για το εαρινό εξάμηνο του 2024 θα γίνει την Παρασκευή 16 Φεβρουαρίου, 10:40 - 12:30 μέσω Webex. 


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

    Το μάθημα περιλαμβάνει 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, γραμμικές ισοτιμίες, Κινέζικο θεώρημα υπολοίπων.
    • Ασυμπτωτικός συμβολισμός και ασυμπτωτική εκτίμηση.

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



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


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

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


  • Διαλέξεις

    • Διάλεξη 16/2/2024. Διαδικαστικά θέματα, εισαγωγή, Gradiance. Σύνολα και πράξεις συνόλων.
    • Διάλεξη 19/2/2024. Αριθμήσιμα και μη αριθμήσιμα σύνολα.
    • Διάλεξη 23/2/2024. Τεχνικές απαρίθμησης αριθμήσιμων συνόλων. Αρχή Διαγωνιοποίησης. Μη υπολογισιμότητα.
    • Διάλεξη 26/2/2024. Μη υπολογισιμότητα, παράδοξο Russel. Στοιχεία Κατηγορηματικής Λογικής: συντακτικό.
    • Διάλεξη 1/3/2024. Στοιχεία Κατηγορηματικής Λογικής: συντακτικό, ελεύθερες και δεσμευμένες μεταβλητές, εναλλαγή ποσοδεικτών, ερμηνεία, διατύπωση προτάσεων στην Πρωτοβάθμια γλώσσα.
    • Διάλεξη 4/3/2024. Στοιχεία Κατηγορηματικής Λογικής: ερμηνεία, διατύπωση προτάσεων στην Πρωτοβάθμια γλώσσα, παραδείγματα (διαφάνειες με επιπλέον παραδείγματα που χρησιμοποιήσαμε στο μάθημα).
    • Διάλεξη 11/3/2024. Στοιχεία Κατηγορηματικής Λογικής: ερμηνεία, ορισμός αλήθειας Tarski, σημασιολογική προσέγγιση, λογική εγκυρότητα (διαφάνειες με επιπλέον παραδείγματα που χρησιμοποιήσαμε στο μάθημα).
    • Διάλεξη 15/3/2024. Στοιχεία Κατηγορηματικής Λογικής: λογική εγκυρότητα, ιδιότητες ποσοδεικτών, κανονική ποσοδεικτική μορφή. Σχέσεις. Σχεσιακό Μοντέλο Βάσεων Δεδομένων.
    • Διάλεξη 19/3/2024. Σχέσεις, διμελείς σχέσεις, ιδιότητες. 
    • Διάλεξη 26/3/2024. Kλειστότητες, μεταβατική κλειστότητα, Υπολογισμός Μερικής Κλειστότητας. Σχέσεις Ισοδυναμίας.
    • Διάλεξη 26/3/2024. Σχέσεις Ισοδυναμίας, Κλάση Ισοδυναμίας, Εκλέπτυνση Ισοδυναμίας. Σχέσεις Μερικής Διάταξης.
    • Διάλεξη 29/3/2024. Αποδεικτικές τεχνικές, αναφορά στην έννοια του σταθερού σημείο, τρίγωνο Sperner. Μαθηματική επαγωγή, επαγωγή - αναδρομή - διάταξη - απαρίθμηση.
    • Διάλεξη 1/4/2024. Μαθηματική επαγωγή.  
    • Διάλεξη 5/4/2024. Μαθηματική επαγωγή. παραδείγματα αναδρομικών ορισμών - σχέσεων.
    • Διάλεξη 8/4/2024. Αρχή περιστερώνα.  
    • Διάλεξη 12/4/2024. Βασικές έννοιες θεωρίας γραφημάτων. Βασικοί ορισμοί, μέγιστο ανεξάρτητο σύνολο, χαρακτηρισμός διμερών γραφημάτων, υπερκύβος, παραδείγματα εφαρμογής πιθανοτικής μεθόδου σε γραφήματα.  
    • Διάλεξη 15/4/2024. Βασικές έννοιες θεωρίας γραφημάτων: αριθμοί Ramsey, διαδρομές, μονοκονδυλιές, μονοπάτια, συνεκτικότητα, ισχυρή συνεκτικότητα, ισχυρές συνεκτικές συνιστώσες και αποδόμηση διμελών σχέσεων με βάση ισχυρά συνεκτικές συνιστώσες, κύκλωμα Euler. 
    • Διάλεξη 19/4/2024. Βασικές έννοιες θεωρίας γραφημάτων: κύκλωμα Euler, χαρακτηρισμός Eulerian γραφημάτων, επαγωγική απόδειξη του χαρακτηρισμού (μέσω αποδόμησης σε κύκλους και μέσω απλοποίησης μονοπατιών μήκους 2, βλ. παράδειγμα), κύκλος Hamilton, ικανές και αναγκαίες συνθήκες.  
    • Διάλεξη 22/4/2024. Βασικές έννοιες θεωρίας γραφημάτων: κύκλος Hamilton, απόδειξη θεωρήματος Ore, απόδειξη ύπαρξης μονοπατιού Hamilton σε tournaments. Μετασχηματισμοί γραφημάτων, αναπαράσταση γραφημάτων, ισομορφισμός, αυτοσυμπληρωματικά γραφήματα, αυτομορφισμός (διαφάνειες). 
    • Διάλεξη 23/4/2024. Επίπεδα γραφήματα. Βασικός χαρακτηρισμός δέντρων. 
    • Διάλεξη 26/4/2024. Συνδετικά δέντρα. Ανεξάρτητα σύνολα και καλύμματα κορυφών. Χρωματικός αριθμός. 

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

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

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