Section outline
-
-
Εδώ αναρτώνται οι γενικές ανακοινώσεις από τους διδάσκοντες προς τους εγγεγραμμένους φοιτητές, οι οποίοι τις λαμβάνουν και στην ηλεκτρονική τους διεύθυνση.
-
Σε αυτό το forum, μπορεί οποιοσδήποτε εγγεγραμμένος φοιτητής να αναρτά ερωτήσεις σχετικές με το μάθημα και να λαμβάνει απαντήσεις από τους διδάσκοντες. Οι ερωτήσεις και οι απαντήσεις θα είναι διαθέσιμες σε όλους τους φοιτητές.
Οι φοιτητές μπορούν να δηλώσουν με την εγγραφή τους αν θέλουν να ενημερώνονται για τις αναρτώμενες ερωταπαντήσεις.
-
-
- Δημήτρης Φωτάκης, Αναπλ. Καθηγητής ()
- Δώρα Σούλιου, Ε.ΔΙ.Π ()
Ώρες Γραφείου Διδασκόντων
- Δημήτρης Φωτάκης: Δευτέρα 14:30 - 15:15, στο γραφείο 1.1.10, (Παλαιό) Κτήριο Ηλεκτρολόγων.
- Δώρα Σούλιου: Τρίτη 15:10 - 17:00, μέσω Webex, στο link https://centralntua.webex.com/centralntua/j.php?MTID=m0660fa542846ea08f00824be38446ac4
-
Οι διαλέξεις του μαθήματος γίνονται:
- κάθε Δευτέρα, ώρες 12:40-14:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 2.
- κάθε Παρασκευή, ώρες 10:40-12:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 2.
Οι διαλέξεις αναπλήρωσης, που τυχόν θα χρειαστούν, και οι φροντιστηριακές διαλέξεις θα γίνονται Τρίτη, ώρες 15:10 - 17:00, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 2.
Τις Τρίτες, ώρες 15:10 - 17:00, για τις οποίες δεν έχει προγραμματιστεί φροντιστήριο ή διάλεξη αναπλήρωσης, μπορούν οι φοιτητές να συνδέονται στο Webex, στο link https://centralntua.webex.com/centralntua/j.php?MTID=m0660fa542846ea08f00824be38446ac4 , για ερωτήσεις πάνω στην ύλη ή επίλυση αποριών.
-
Το μάθημα περιλαμβάνει 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.
- 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, γραμμικές ισοτιμίες, Κινέζικο θεώρημα υπολοίπων.
- Ασυμπτωτικός συμβολισμός και ασυμπτωτική εκτίμηση.
-
- Ιστοσελίδα του μαθήματος για προηγούμενα ακαδημαϊκά έτη: 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η Σειρά: Γεννήτριες Συναρτήσεις και εφαρμογές τους στη συνδυαστική. Σχέδιο Λύσεων.
-
- Διάλεξη 28/2/2022. Διαδικαστικά θέματα, εισαγωγή, Gradiance. Σύνολα και πράξεις συνόλων.
- Διάλεξη 4/3/2022. Το μοντέλο SIR (μπορείτε να διαβάσετε περισσότερα για epidemics στο Κεφάλαιο 21, του βιβλίου "Networks, Crowds, and Markets: Reasoning About a Highly Connected World", των David Easley and Jon Kleinberg). Αριθμήσιμα και μη αριθμήσιμα σύνολα.
- Διάλεξη 11/3/2022. Τεχνικές απαρίθμησης αριθμήσιμων συνόλων. Αρχή Διαγωνιοποίησης. Μη υπολογισιμότητα.
- Διάλεξη 14/3/2022. Στοιχεία Προτασιακής Λογικής.
- Διάλεξη 18/3/2022. Στοιχεία Προτασιακής Λογικής (συνέχεια). Στοιχεία Κατηγορηματικής Λογικής.
- Διάλεξη 21/3/2022. Στοιχεία Κατηγορηματικής Λογικής: συντακτικό, ελεύθερες και δεσμευμένες μεταβλητές, εναλλαγή ποσοδεικτών, διατύπωση προτάσεων στην Πρωτοβάθμια γλώσσα.
- Διάλεξη 28/3/2022. Ερμηνεία, ορισμός αλήθειας Tarski, σημασιολογική προσέγγιση, λογική εγκυρότητα, ιδιότητες ποσοδεικτών, κανονική ποσοδεικτική μορφή.
- Διάλεξη 1/4/2022. Σχέσεις, διμελείς σχέσεις, ιδιότητες, κλειστότητες, μεταβατική κλειστότητα.
- Διάλεξη 4/4/2022. Υπολογισμός μεταβατικής κλειστότητας. Σχέσεις ισοδυναμίας.
- Διάλεξη 8/4/2022. Σχέσεις Διάταξης.
- Διάλεξη 11/4/2022. Σχέσεις Διάταξης. Αποδεικτικές Τεχνικές. Μαθηματική Επαγωγή.
- Διάλεξη 15/4/2022. Μαθηματική Επαγωγή. Αρχή Περιστερώνα.
- Διάλεξη 6/5/2022. Βασικές έννοιες Θεωρίας Γραφημάτων: εισαγωγικά, βαθμός κορυφής, διμερή γραφήματα, υπογραφήματα.
- Διάλεξη 9/5/2022. Βασικές έννοιες Θεωρίας Γραφημάτων: αριθμοί Ramsey, συνεκτικότητα, κύκλος Euler, ασκήσεις.
- Διάλεξη 13/5/2022. Βασικές έννοιες Θεωρίας Γραφημάτων: κύκλος Euler, κύκλος Hamilton, θεώρημα Ore, ασκήσεις.
- Διάλεξη 16/5/2022. Μετασχηματισμοί γραφημάτων, αναπαράσταση γραφημάτων, ισομορφισμός, αυτομορφισμός.
- Διάλεξη 17/5/2022. Επίπεδα γραφήματα, δέντρα, συνδετικά δέντρα.
- Διάλεξη 20/5/2022. Αλγόριθμοι υπολογισμού ελάχιστων συνδετικών δέντρων (διαφάνειες με παραδείγματα των αλγορίθμων), χρωματικός αριθμός, ταιριάσματα, κάλυμμα κορυφών.
- Διάλεξη 23/5/2022. Αρχή Εγκλεισμού - Αποκλεισμού. Βασικές έννοιες συνδυαστικής απαρίθμησης: κανόνας γινομένου, κανόνας αθροίσματος, διατάξεις και μεταθέσεις.
- Διάλεξη 27/5/2022. Βασικές έννοιες συνδυαστικής απαρίθμησης: διατάξεις με επανάληψη, συνδυασμοί, συνδυασμοί με επανάληψη.
- Διάλεξη 30/5/2022. Βασικές έννοιες συνδυαστικής απαρίθμησης: συνδυασμοί με επανάληψη, ασκήσεις. Παραδείγματα εφαρμογής συνδυαστικής σε διακριτή πιθανότητα.
- Διάλεξη 31/5/2022. Ιδιότητες δυωνυμικών συντελεστών. Αναπαράσταση ακολουθιών, γεννήτριες συναρτήσεις.
- Διάλεξη 3/6/2022. Γεννήτριες συναρτήσεις, βασικές ιδιότητες, εφαρμογή στον υπολογισμό αθροισμάτων, εφαρμογή γεννητριών συναρτήσεων για την επίλυση προβλημάτων συνδυασμών.
- Διάλεξη 6/6/2022. Εφαρμογή γεννητριών συναρτήσεων για την επίλυση προβλημάτων συνδυασμών, εκθετικές γεννήτριες συναρτήσεις, εφαρμογή εκθετικών γεννητριών συναρτήσεων για την επίλυση προβλημάτων διατάξεων.
- Διάλεξη 10/6/2022. Διατύπωση αναδρομικών σχέσεων. Ταιριάσματα σε διμερή γραφήματα. Θεώρημα του Hall.
-
- Φροντιστήριο 30/3/2022. Σύνολα, Αριθμησιμότητα Συνόλων, Προτασιακή και Κατηγορηματική Λογική.
- Φροντιστήριο 24/5/2022. Ασκήσεις σε Θεωρία Γραφημάτων.
-
- Θα ανακοινωθούν τρεις (3) σειρές γραπτών ασκήσεων.
- Οι γραπτές ασκήσεις υποβάλλονται στη σελίδα του μαθήματος, στο helios. Δεν γίνεται δεκτή η παράδοση ασκήσεων με e-mail.
- Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά, π.χ. αφού αφιερώσετε ικανό χρόνο ατομικής προσπάθειας), αλλά τελικά κάθε φοιτητής πρέπει να διατυπώσει μόνος του τη λύση. Πανομοιότυπες διατυπώσεις θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές ασκήσεων.
Εκφωνήσεις Γραπτών Ασκήσεων
- 1η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 28/4/2022.
- 2η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 3/6/2022.
- 3η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 24/6/2022.