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

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

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

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

Διαλέξεις: 10/3 | 14/3 | 21/3 | 24/3 | 28/3 | 4/4 | 5/4 | 7/4 | 12/4 | 14/4 | 2/5 | 5/5 | 9/5 | 16/5 | 19/5 | 23/5 | 24/5 | 26/5 | 30/5 | 2/6 | 6/6 | 7/6 | 9/6 | 16/6 

Φροντιστηριακές Διαλέξεις: 3/5 | 17/5 | 31/5 | 14/6

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

Γενικά

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

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

Περιεχόμενα

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

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

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

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

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

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

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

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

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

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

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

Ύλη

Για τις εξετάσεις, πρέπει να έχετε μελετήσει και κατανοήσει όλη την ύλη που παρουσιάσαμε στην τάξη (αν χάσατε κάποια μαθήματα, οι διαφάνειες θα σας βοηθήσουν). Ενδεικτικά αναφέρεται ότι η ύλη που καλύψαμε στο μάθημα περιλαμβάνει ότι αναφέρεται στα Κεφάλαια 1, 2, 3 (με εξαίρεση τις ενότητες 3.7 και 3.8), 4, 7, 9, και 10 του βιβλίου του Liu, στα Κεφάλαια 1 (με εξαίρεση ένα μικρό μέρος της ενότητας 1.5), 2, 3.2, 4 (με εξαίρεση την ενότητα 4.5), 5, 7, 8, και 12 (με εξαίρεση τις ενότητες 12.2 και 12.5) του βιβλίου του Rosen (η αρίθμηση των ενοτήτων αναφέρεται στο πρωτότυπο, 6η έκδοση), και στα Κεφάλαια 1 (με εξαίρεση τις ενότητες 1.4 και 1.5), 2 (με εξαίρεση την ενότητα 2.4), 4 (με εξαίρεση την ενότητα 4.5), 5, 6 (με εξαίρεση τις ενότητες 6.8 και 6.9), 7, 8, 10 (με εξαίρεση την ενότητα 10.4), και 12 του βιβλίου της Epp. Υπάρχουν αρκετά πράγματα που είπαμε στο μάθημα και δεν αναλύονται επαρκώς στα βιβλία (αυτό συχνότερα συμβαίνει με το βιβλίο του Liu).

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

• Φ. Αφράτη, Γ. Παπαγεωργίου. Στοιχεία Διακριτών Μαθηματικών. Έκδοση Ε.Μ.Π., 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.

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

• Χ. Νομικός. Μάθημα Διακριτών Μαθηματικών. Πανεπιστήμιο Ιωαννίνων.

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

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

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

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

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

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

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

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

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

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

Προτεινόμενες Ασκήσεις - Θέματα Εξετάσεων

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

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

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

Ευχαριστίες

• Ευχαριστούμε τους φοιτητές της ΣΗΜΜΥ Μ. Ζαμπετάκη, Δ. Ζήνδρο, Φ. Ηλιόπουλο, και Ν. Κορασίδη για την πολύτιμη βοήθειά τους στην οργάνωση των φροντιστηρίων του μαθήματος.

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

Παράδοση 10/3/2011

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

Παράδοση 14/3/2011

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

Παράδοση 21/3/2011

• Μη υπολογισιμότητα, το παράδοξο του Russel.
• Στοιχεία Προτασιακής Λογικής.

Παράδοση 24/3/2011

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

Παράδοση 28/3/2011

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

Παράδοση 4/4/2011

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

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

• Στοιχεία Κατηγορηματικής Λογικής. Αποδεικτικές Διαδικασίες. Μαθηματική Επαγωγή.

Παράδοση 7/4/2011

• Μαθηματική Επαγωγή.

Παράδοση 12/4/2011

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

Παράδοση 14/4/2011

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

Παράδοση 2/5/2011

• Σχέσεις Μερικής Διάταξης.

Παράδοση 5/5/2011

• Τοπολογική Διάταξη. Αρχή του Περιστερώνα.

Παράδοση 9/5/2011

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

Παράδοση 16/5/2011

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

Παράδοση 19/5/2011

• Μη ντετερμινιστικά πεπερασμένα αυτόματα. Ισοδυναμία ντετερμινιστικών και μη ντετερμινιστικών αυτομάτων.

Παράδοση 23/5/2011

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

Παράδοση 24/5/2011

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

Παράδοση 26/5/2011

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

Παράδοση 30/5/2011

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

Παράδοση 2/6/2011

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

Παράδοση 6/6/2011

• Συνδυαστική απαρίθμηση: ασκήσεις. Ιδιότητες δυωνυμικών συντελεστών. Δημιουργία μεταθέσεων και συνδυασμών.

Παράδοση 7/6/2011

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

Παράδοση 9/6/2011

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

Παράδοση 16/6/2011

• Αναδρομικές Σχέσεις.

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

Φροντιστήριο 3/5/2011

• Σύνολα, προτασιακή λογική.

Φροντιστήριο 17/5/2011

• Συζήτηση των ασκήσεων της 1ης γραπτής εργασίας.

Φροντιστήριο 31/5/2011

• Γλώσσες - Αυτόματα - Γραμματικές.
• Αρχή του Περιστερώνα.

Φροντιστήριο 14/6/2011

• Συζήτηση των ασκήσεων της 2ης γραπτής εργασίας.