 |
Εθνικό Μετσόβιο Πολυτεχνείο Διακριτές Μέθοδοι για την Επιστήμη των Υπολογιστών http://www.softlab.ntua.gr/~fotakis/discrete_math |
Μάθημα Επιλογής Κορμού, 4ου Εξαμήνου, Κωδικός 3.4.07.4
|
Εξάμηνο: |
Εαρινό 2013 | ||||||||||||||||||||||||
|
|
Ανακοινώσεις, Γενικά, Περιεχόμενα, Παλαιότερα Έτη, Ύλη, Βιβλιογραφία, Συμπληρωματικό Υλικό, Προτεινόμενες Ασκήσεις, Γραπτές Εργασίες, Διαλέξεις - Διαφάνειες, Φροντιστηριακές Διαλέξεις
Διαλέξεις: 28/2 | 4/3 | 11/3 | 26/3 | 1/4 | 4/4 | 8/4 | 11/4 | 12/4 | 15/4 | 18/4 | 22/4 | 25/4 | 13/5 | 16/5 | 17/5 | 20/5 | 23/5 | 27/5 | 30/5 | 3/6 | 6/6 | 10/6 | 14/6
Φροντιστηριακές Διαλέξεις: 5/4 | 26/4 | 31/5
|
18/7/2013 |
Ανακοινώθηκε η βαθμολογία της εξέτασης του Ιουλίου (μαζί με τους βαθμούς από τις γραπτές εργασίες και τις online ασκήσεις, η βαθμολογία των εξετάσεων είναι με άριστα το 8, η βαθμολογία των online ασκήσεων είναι με άριστα το 2). Μπορείτε να δείτε τα γραπτά σας ή να ρωτήσετε σχετικά με την βαθμολογία σας την Πέμπτη 25/7, ώρα 17:00 - 18:00, στο γραφείο του Δ. Φωτάκη (γρ. 1.1.10, στο παλαιό κτήριο Ηλεκτρολόγων). |
|
3/7/2013 |
Ανακοινώθηκε σχέδιο λύσεων για την 3η γραπτή εργασία. Ελπίζουμε να σας βοηθήσει στην προετοιμασία για τις εξετάσεις. Καλή επιτυχία στις εξετάσεις! |
|
13/6/2013 |
Λόγω των απεργιακών κινητοποιήσεων, η τελευταία διάλεξη θα γίνει την Παρασκευή 14/6, ώρα 12:45 - 15:00, στο Αμφιθέατρο 3. |
|
10/6/2013 |
Ανακοινώθηκε η 6η online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 6η online άσκηση λήγει την Πέμπτη 4/7/2013. Επιπλέον, στην ενότητα Tutorials του Gradiance, έχουν ανακοινωθεί 9 sets (μη βαθμολογούμενων) ασκήσεων που καλύπτουν κάποια σημαντικά τμήματα της ύλης. Στόχος είναι να σας βοηθήσουν κατά την προετοιμασία για τις εξετάσεις. Οι ασκήσεις αυτές θα είναι διαθέσιμες μέχρι την Πέμπτη 4/7/2013, ημέρα εξέτασης του μαθήματος. Καλή Επιτυχία! |
|
4/6/2013 |
Ανακοινώθηκε η εκφώνηση της 3ης γραπτής εργασίας. Η προθεσμία για την παράδοσή της λήγει την Τρίτη 2/7. Καλή Επιτυχία! |
|
3/6/2013 |
Ανακοινώθηκε η βαθμολογία της 1ης γραπτής εργασίας. |
|
30/5/2013 |
Ανακοινώθηκε η 5η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 5η Online άσκηση λήγει την Δευτέρα 10/6/2013. Καλή Επιτυχία! |
|
16/5/2013 |
Ανακοινώθηκε η 4η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 4η Online άσκηση λήγει την Τρίτη 28/5/2013. Καλή Επιτυχία! |
|
13/5/2013 |
Ανακοινώθηκε η εκφώνηση της 2ης γραπτής εργασίας. Η προθεσμία για την παράδοσή της λήγει την Πέμπτη 30/5. Καλή Επιτυχία! |
|
25/4/2013 |
Ανακοινώθηκε η 3η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 3η Online άσκηση λήγει την Τετάρτη 15/5/2013. Καλή Επιτυχία! |
|
10/4/2013 |
Ανακοινώθηκε η εκφώνηση της 1ης γραπτής εργασίας. Η προθεσμία για την παράδοσή της λήγει την Πέμπτη 25/4. Καλή Επιτυχία! |
8/4/2013 |
Την Παρασκευή 12/4, ώρα 12:45 - 14:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 3, θα γίνει διάλεξη αναπλήρωσης. |
|
8/4/2013 |
Ανακοινώθηκε η 2η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής για την 2η Online άσκηση λήγει την Δευτέρα 22/4/2013. Σχετικά με τις Online ασκήσεις, υπενθυμίζεται ότι έγκυρη θεωρείται μόνο η τελευταία υποβολή, εφόσον έχει άριστη βαθμολογία. Καλή Επιτυχία! |
1/4/2013 |
Την Παρασκευή 5/4, ώρα 12:45 - 14:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 3, θα γίνει η πρώτη φροντιστηριακή διάλεξη. |
15/3/2013 |
Λόγω των κινητοποιήσεων, δίνεται παράταση στην 1η Online άσκηση μέχρι και την Πέμπτη 21/3/2013. Επίσης αναβάλλεται η φροντιστηριακή διάλεξη που ήταν προγραμματισμένη για την Τρίτη 19/3. |
|
28/2/2013 |
Ανακοίνωση 1ης Online Ασκησης. Για να υποβάλλετε Online Ασκήσεις επισκεφθείτε το http://www.gradiance.com/services/servlet/COTC και δημιουργείστε λογαριασμό μέσω της επιλογής "Create New Account". Ως "Unique User ID" να χρησιμοποιήσετε το dm13_ΑριθμόςΜητρώου (π.χ. dm13_03111001), ως "First Name" να δώσετε το Ονοματεπώνυμό σας (με λατινικούς χαρακτήρες, π.χ. Dimitris Fotakis), και ως "Last Name" να δώσετε τον Αριθμό Μητρώου σας (π.χ. 03111001, βλ. επίσης εδώ). Αφού συνδεθείτε στο σύστημα με αυτά τα στοιχεία, κάνετε "Sign in" στο μάθημα χρησιμοποιώντας το "Class token" που δώσαμε στο μάθημα. Επιλέγοντας το μάθημα DM 2013 μπορείτε να δείτε την 1η Online Ασκηση, που έχει ήδη ανακοινωθεί, και αποτελείται από 7 απλά ερωτήματα στις βασικές έννοιες της Θεωρίας Συνόλων. Η προθεσμία για την υποβολή της λήγει την Πέμπτη 14/3/2013. Υπενθυμίζεται ότι έγκυρη θεωρείται μόνο η τελευταία υποβολή, εφόσον αυτή έχει άριστη βαθμολογία. Καλή Επιτυχία! |
|
27/2/2013 |
Ο τελικός βαθμός του μαθήματος υπολογίζεται ως εξής:
|
|
27/2/2013 |
Έναρξη μαθημάτων. Οι διαλέξεις του μαθήματος θα γίνονται κάθε Δευτέρα, ώρα 12:45-14:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 5, και κάθε Πέμπτη, ώρα 12:45-14:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 5. Οι διαλέξεις αναπλήρωσης, που τυχόν θα χρειαστούν, και οι φροντιστηριακές διαλέξεις θα γίνονται την Παρασκευή, ώρα 12:45 - 14:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 3. |
Ώρες γραφείου διδασκόντων:
Σύνολα και πράξεις συνόλων.
Αριθμήσιμα και μη αριθμήσιμα σύνολα, αρχή της διαγωνιοποίησης, μη υπολογισιμότητα, παράδοξο του Russell.
Αποδεικτικές διαδικασίες, μαθηματική επαγωγή, αρχή του περιστερώνα.
Αρχή εγκλεισμού-αποκλεισμού.
Συνδυαστική απαρίθμηση. Κανόνες γινομένου και αθροίσματος, εφαρμογές αρχής εγκλεισμού-αποκλεισμού, μεταθέσεις και διατάξεις, συνδυασμοί, δυωνυμικοί συντελεστές, τρίγωνο του Pascal, διανομή διακεκριμένων και μη-διακεκριμένων αντικειμένων σε υποδοχές, κατασκευή μεταθέσεων και συνδυασμών, στοιχεία διακριτής πιθανότητας.
Γεννήτριες Συναρτήσεις. Βασικές ιδιότητες, εφαρμογή στον υπολογισμό αθροισμάτων, εφαρμογή στην επίλυση συνδυαστικών προβλημάτων, εκθετικές Γεννήτριες Συναρτήσεις.
Επίλυση γραμμικών αναδρομικών εξισώσεων με σταθερούς συντελεστές. Χαρακτηριστική εξίσωση, ομογενής λύση, ειδική λύση, επίλυση με τη μέθοδο των Γεννητριών Συναρτήσεων.
Ασυμπτωτικός συμβολισμός και ασυμπτωτική εκτίμηση.
Σχέσεις και συναρτήσεις. Διμελείς σχέσεις, ιδιότητες διμελών σχέσεων, σχέσεις ισοδυναμίας, σχέσεις μερικής και ολικής διάταξης, κλειστότητες σχέσεων, συναρτήσεις, αρχή του περιστερώνα.
Στοιχεία προτασιακής και κατηγορηματικής λογικής.
Γλώσσες, γραμματικές, τύποι γραμματικών και γλωσσών, κανονικές γλώσσες, γλώσσες χωρίς συμφραζόμενα, πεπερασμένα αυτόματα ως μηχανές αναγνώρισης κανονικών γλωσσών, το Λήμμα 'Αντλησης για κανονικές γλώσσες.
Ιστοσελίδα του μαθήματος για το ακαδ. έτος 2011-2012.
Ιστοσελίδα του μαθήματος για το ακαδ. έτος 2010-2011.
Ιστοσελίδα του μαθήματος για το ακαδ. έτος 2009-2010.
Ιστοσελίδα του μαθήματος για το ακαδ. έτος 2008-2009.
Ιστοσελίδα του μαθήματος για το ακαδ. έτος 2007-2008.
Για τις εξετάσεις, πρέπει να έχετε μελετήσει και κατανοήσει όλη την ύλη που παρουσιάσαμε στην τάξη (αν χάσατε κάποια μαθήματα, οι διαφάνειες θα σας βοηθήσουν). Ενδεικτικά αναφέρεται ότι η ύλη που καλύψαμε στο μάθημα περιλαμβάνει ότι αναφέρεται στα Κεφάλαια 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.
Μ. Κούτρας. Μάθημα (και βιβλίο) Συνδυαστικής. Πανεπιστήμιο Πειραιά.
Π. Κατερίνης. Μάθημα Διακριτών Μαθηματικών. Οικονομικό Πανεπιστήμιο Αθηνών.
Κάποιες συμπληρωματικές σημειώσεις στον ασυμπτωτικό συμβολισμό (Δ. Φωτάκης).
Κάποιες σημειώσεις για τεχνικές επίλυσης αναδρομικών σχέσεων (Δ. Φωτάκης).
Κάποιες σημειώσεις στις βασικές ιδιότητες των Γεννητριών Συναρτήσεων (Δ. Φωτάκης) και στις εφαρμογές τους.
Κάποιες σημειώσεις στις βασικές έννοιες της συνδυαστικής (Δ. Φωτάκης) και μια χρήσιμη σύνοψη σε μορφή διαγράμματος (και η ίδια σύνοψη ενημερωμένη με τις αντίστοιχες Γεννήτριες Συναρτήσεις).
Ένα πολύ χρήσιμο εργαλείο για εξάσκηση στο σχεδιασμό (και τη λειτουργία) DFAs και NFAs. Έχει δημιουργηθεί από τους τους φοιτητές της ΣΗΜΜΥ Μ. Ζαμπετάκη και Δ. Ζήνδρο.
Κάποιες σημειώσεις σχετικά με το συντακτικό και την σημασιολογία της Πρωτοβάθμιας Λογικής (Δ. Φωτάκης).
Σημειώσεις για την αποδεικτική τεχνική της Μαθηματικής Επαγωγής (Δ. Φωτάκης).
Σημειώσεις σχετικά με σύνολα και πράξεις συνόλων.
Μια χρήσιμη σύνοψη των περισσότερων βασικών εννοιών των Διακριτών Μαθηματικών (αναφέρεται και σε πολλές έννοιες που δεν θα συναντήσουμε στο μάθημα).
Τελευταία αλλαγή: 14/6/2013, 15:00
