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

Διακριτές Μέθοδοι για την Επιστήμη των Υπολογιστών

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

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

Διαλέξεις: 9/3 | 16/3 | 23/3 | 26/3 | 30/3 | 2/4 | 3/4 | 20/4 | 23/4 | 27/4 | 30/4 | 4/5 | 7/5 | 11/5 | 14/5 | 18/5 | 21/5 | 22/5 | 25/5 | 28/5 | 4/6 | 8/6 | 11/6 | 15/6 | 18/6

Φροντιστηριακές Διαλέξεις: 24/4 | 8/5 | 5/6 

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

Γενικά

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

  • Δ. Φωτάκης: Δευτέρα 15:00 - 16:00 και Πέμπτη 15:00 - 16:00, στο (παλαιό) Κτήριο Ηλεκτρολόγων, γρ. 1.1.10, τηλ. 210-772-4302.
  • Δ. Σούλιου: Τετάρτη 14:30 - 16:30, στο (παλαιό) Κτήριο Ηλεκτρολόγων, γρ. 1.1.30, τηλ. 210-772-1644.

Περιεχόμενα

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

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

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

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

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

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

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

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

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

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

• Γλώσσες, γραμματικές, τύποι γραμματικών και γλωσσών, κανονικές γλώσσες, γλώσσες χωρίς συμφραζόμενα, πεπερασμένα αυτόματα ως μηχανές αναγνώρισης κανονικών γλωσσών, το Λήμμα 'Αντλησης για κανονικές γλώσσες.

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

• Ιστοσελίδα του μαθήματος για το ακαδ. έτος 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.

• H. Lewis and Ch. Papadimitriou. Elements of the Theory of Computation (2nd edition). Prentice-Hall, 1998. Κυκλοφορεί μεταφρασμένο στα Ελληνικά από τις εκδόσεις Κριτική.

• Μ. Sipser. Introduction to the Theory of Computation. Course Technology, 2005. Κυκλοφορεί μεταφρασμένο στα Ελληνικά από τις Πανεπιστημιακές Εκδόσεις Κρήτης.

• J. Hopcroft, R. Motwani, J. Ullman. Introduction to Automata Theory, Languages, and Computation (3rd edition). Addison-Wesley, 2000.

• Η. Κουτσουπιάς. Μαθηματικά της Πληροφορικής. ΕΚΠΑ, 2008.

• Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης. Διακριτά Μαθηματικά: Τα Μαθηματικά της Επιστήμης των Υπολογιστών. Gutenberg, 1994.

• Γ. Βουτσαδάκης, Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης. Διακριτά Μαθηματικά: Προβλήματα και Λύσεις. Gutenberg, 1994.

• DiscreteMath@MIT.

• DiscreteMath@Princeton.

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

• Π. Κατερίνης. Μάθημα Διακριτών Μαθηματικών. Οικονομικό Πανεπιστήμιο Αθηνών.

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

• Κάποιες συμπληρωματικές σημειώσεις στον ασυμπτωτικό συμβολισμό (Δ. Φωτάκης).

• Κάποιες σημειώσεις για τεχνικές επίλυσης αναδρομικών σχέσεων (Δ. Φωτάκης).

• Κάποιες σημειώσεις στις βασικές ιδιότητες των Γεννητριών Συναρτήσεων (Δ. Φωτάκης) και στις εφαρμογές τους.

• Κάποιες σημειώσεις στις βασικές έννοιες της συνδυαστικής (Δ. Φωτάκης) και μια χρήσιμη σύνοψη σε μορφή διαγράμματος (και η ίδια σύνοψη ενημερωμένη με τις αντίστοιχες Γεννήτριες Συναρτήσεις).

• Ένα πολύ χρήσιμο εργαλείο για εξάσκηση στο σχεδιασμό (και τη λειτουργία) DFAs και NFAs. Έχει δημιουργηθεί από τους τους φοιτητές της ΣΗΜΜΥ Μ. Ζαμπετάκη και Δ. Ζήνδρο.

• Σημειώσεις για την αποδεικτική τεχνική της Μαθηματικής Επαγωγής (Δ. Φωτάκης).

• Κάποιες σημειώσεις σχετικά με το συντακτικό και την σημασιολογία της Πρωτοβάθμιας Λογικής (Δ. Φωτάκης).

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

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

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

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

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

• Εκφώνηση της 1ης γραπτής εργασίας. Παράδοση εργασιών στο μάθημα της Δευτέρας 4/5.
• Εκφώνηση της 2ης γραπτής εργασίας. Παράδοση εργασιών στο μάθημα της Πέμπτης 4/6.
• Εκφώνηση της 3ης γραπτής εργασίας. Παράδοση εργασιών μέχρι την Τρίτη 23/6.

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

Παράδοση 9/3/2015

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

Παράδοση 16/3/2015

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

Παράδοση 23/3/2015

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

Παράδοση 26/3/2015

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

Παράδοση 30/3/2015

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

Παράδοση 2/4/2015

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

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

• Μη υπολογισιμότητα, το παράδοξο του Russell.
• Αποδεικτικές Διαδικασίες. Μαθηματική Επαγωγή.

Παράδοση 20/4/2015

• Μαθηματική Επαγωγή.
• Αρχή του Περιστερώνα.

Παράδοση 23/4/2015

• Αρχή του Περιστερώνα.
• Διμελείς Σχέσεις: Βασικοί ορισμοί και ιδιότητες.

Παράδοση 27/4/2015

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

Παράδοση 30/4/2015

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

Παράδοση 4/5/2015

• Σχέσεις Διάταξης.

Παράδοση 7/5/2015

• Τυπικές Γλώσσες. Γραμματικές.
• Ντετερμινιστικά πεπερασμένα αυτόματα.

Παράδοση 11/5/2015

• Ντετερμινιστικά πεπερασμένα αυτόματα. Μη ντετερμινιστικά πεπερασμένα αυτόματα.

Παράδοση 14/5/2015

• Ισοδυναμία ντετερμινιστικών και μη ντετερμινιστικών αυτομάτων.
• Αναπαράσταση κανονικών γλωσσών: κανονικές γραμματικές, πεπερασμένα αυτόματα, και κανονικές εκφράσεις.

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

• Πεπερασμένα αυτόματα και κανονικές εκφράσεις
• Λήμμα άντλησης για κανονικές γλώσσες.

Παράδοση 21/5/2015

• Γλώσσες χωρίς συμφραζόμενα.
• Λήμμα άντλησης για γλώσσες χωρίς συμφραζόμενα.

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

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

Παράδοση 25/5/2015

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

Παράδοση 28/5/2015

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

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

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

Παράδοση 8/6/2015

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

Παράδοση 11/6/2015

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

Παράδοση 15/6/2015

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

Παράδοση 18/6/2015

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

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

Φροντιστήριο 24/4/2015

• Σύνολα, Προτασιακή και Κατηγορηματική Λογική, Μαθηματική Επαγωγή.

Φροντιστήριο 8/5/2015

• Λύσεις 1ης σειράς γραπτών ασκήσεων.

Φροντιστήριο 5/6/2015

• Λύσεις 2ης σειράς γραπτών ασκήσεων. Παραδείγματα και ασκήσεις συνδυαστικής.