 |
Εθνικό Μετσόβιο Πολυτεχνείο Διακριτές Μέθοδοι για την Επιστήμη των Υπολογιστών http://users.softlab.ece.ntua.gr/~nidal/discretehttp://www.softlab.ntua.gr/~fotakis/discrete_math_2008_2009 |
Μάθημα Επιλογής Κορμού, 4ου Εξαμήνου, Κωδικός 3.4.07.4
| Εξάμηνο: | Εαρινό 2009 | ||||||||||||||||
|
|
Ανακοινώσεις, Γενικά, Περιεχόμενα, Ύλη, Βιβλιογραφία, Συμπληρωματικό Υλικό, Γραπτές Ασκήσεις, Διαλέξεις - Διαφάνειες
Διαλέξεις: 23/3 | 26/3 | 30/3 | 2/4 | 6/4 | 9/4 | 27/4 | 30/4 | 4/5 | 7/5 | 11/5 | 14/5 | 18/5 | 21/5 | 25/5 | 28/5 | 1/6 | 4/6 | 11/6 | 15/6 | 18/6 | 22/6 | 25/6 | 29/6
|
22/9/2009 |
Ανακοινώθηκε η βαθμολογία της εξέτασης του Σεπτεμβρίου (η βαθμολογία των εξετάσεων είναι με άριστα το 8, η βαθμολογία των online ασκήσεων είναι με άριστα το 2). Μπορείτε να δείτε τα γραπτά σας ή να ρωτήσετε σχετικά με την βαθμολογία σας την Πέμπτη 24/9,ώρα 17:00 - 19:00, στο γραφείο του κ. Φωτάκη (γρ. 1.1.10, στο παλαιό κτήριο Ηλεκτρολόγων). |
|
21/7/2009 |
Ανακοινώθηκε η βαθμολογία της εξέτασης του Ιουλίου (συνολικά μαζί με τους βαθμούς από τις γραπτές και τις online ασκήσεις, η βαθμολογία των εξετάσεων είναι με άριστα το 8, η βαθμολογία των online ασκήσεων είναι με άριστα το 2). Μπορείτε να δείτε τα γραπτά σας ή να ρωτήσετε σχετικά με την βαθμολογία σας την Τετάρτη 22/7, ώρα 13:00 - 16:00, στο γραφείο της κας Αφράτη (γρ. 1.1.14, στο παλαιό κτήριο Ηλεκτρολόγων). |
|
26/6/2009 |
Στο Gradiance (http://www.gradiance.com/services/servlet/COTC), στην ενότητα Tutorials, έχουν ανακοινωθεί 9 sets (μη βαθμολογούμενων) ασκήσεων που καλύπτουν κάποια σημαντικά τμήματα της ύλης. Στόχος είναι να σας βοηθήσουν κατά την προετοιμασία σας για τις εξετάσεις. Οι ασκήσεις θα είναι διαθέσιμες μέχρι την 20/7/2009, ημέρα της εξέτασης του μαθήματος. Καλή Επιτυχία! |
|
15/6/2009 |
Ανακοινώθηκε η 5η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής λήγει την Κυριακή 21/6/2009. Καλή Επιτυχία! |
|
12/6/2009 |
Ανακοινώθηκε η 2η γραπτή εργασία (με προθεσμία υποβολής τη Δευτέρα 29/6, πριν την έναρξη του τελευταίου μαθήματος, είτε στο αμφιθέατρο είτε στη θυρίδα μου). Στο τελευταίο μάθημα θα συζητήσουμε τις λύσεις των ασκήσεων. Επίσης ανακοινώθηκαν κάποιες σημειώσεις για τις ιδιότητες και τις εφαρμογές των γεννητριών συναρτήσεων. |
|
3/6/2009 |
Ανακοινώθηκε η 4η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής λήγει την Παρασκευή 12/6/2009. Καλή Επιτυχία! Επίσης ανακοινώθηκε η βαθμολογία και ενδεικτικές λύσεις για την 1η γραπτή εργασία. |
|
26/5/2009 |
Ανακοινώθηκε η 3η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής λήγει την Δευτέρα 1/6/2009. Υπενθυμίζεται ότι έγκυρη θεωρείται μόνο η τελευταία υποβολή, εφόσον έχει άριστη βαθμολογία. Καλή Επιτυχία! |
|
15/5/2009 |
Ανακοινώθηκε η 2η Online άσκηση στο http://www.gradiance.com/services/servlet/COTC. Η προθεσμία υποβολής λήγει την Κυριακή 24/5/2009. Υπενθυμίζεται ότι έγκυρη θεωρείται μόνο η τελευταία υποβολή, εφόσον έχει άριστη βαθμολογία. Επίσης φροντίστε ώστε τα στοιχεία σας να συμφωνούν με το format που ανακοινώθηκε αρχικά. Το σημαντικότερο είναι ως "First Name" να υπάρχει το Ονοματεπώνυμό σας (καλύτερα με λατινικούς χαρακτήρες) και ως "Last Name" ο Αριθμός Μητρώου σας. Καλή Επιτυχία! |
|
15/5/2009 |
Διανομή σημειώσεων. Οι σημειώσεις της κας Αφράτη θα μοιράζονται στο γραφείο της (1.1.14) τη Δευτέρα 18/5, ώρα 14:30-16:00, και την Πέμπτη 21/5, ώρα 14:30-16:00. |
|
27/4/2009 |
Ανακοίνωση 1ης Online Aσκησης. Για να υποβάλλετε Online Ασκήσεις επισκεφθείτε το http://www.gradiance.com/services/servlet/COTC και δημιουργείστε λογαριασμό μέσω της επιλογής "Create new account". Ως "First Name" να δώσετε το Ονοματεπώνυμό σας (ας είναι με λατινικούς χαρακτήρες), ως "Last Name" να δώσετε τον Αριθμό Μητρώου σας, και ως "User id" να χρησιμοποιήσετε το dm09_Αριθμός_Μητρώου (π.χ. dm09_00001041). Αφού συνδεθείτε στο σύστημα με αυτά τα στοιχεία, κάνετε "Sign in" στο μάθημα χρησιμοποιώντας το "Class token" που δώσαμε στο μάθημα. Επιλέγοντας το μάθημα DM μπορείτε να δείτε την 1η Online Aσκηση, που έχει ήδη ανακοινωθεί, και αποτελείται από 5 απλές ασκήσεις. Η προθεσμία για την υποβολή της λήγει την Πέμπτη 7/5/2009. Υπενθυμίζεται ότι έγκυρη θεωρείται μόνο η τελευταία υποβολή, εφόσον έχει άριστη βαθμολογία. Καλή Επιτυχία! |
|
26/3/2009 |
Ο τελικός βαθμός του μαθήματος υπολογίζεται ως εξής:
|
|
23/3/2009 |
Τα μαθήματα άρχισαν σήμερα. Οι διαλέξεις του μαθήματος θα γίνονται κάθε Δευτέρα, ώρα 12:45-14:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 2 και Αίθουσα 01, και κάθε Πέμπτη, ώρα 12:45-14:30, στο Νέο Κτήριο Ηλεκτρολόγων, Αμφιθέατρο 5 και Αίθουσα 01. |
Ώρες γραφείου διδασκόντων:
Στοιχεία προτασιακής και κατηγορηματικής λογικής.
Σύνολα και πράξεις συνόλων.
Αριθμήσιμα και μη αριθμήσιμα σύνολα, αρχή της διαγωνιοποίησης, μη υπολογισιμότητα, παράδοξο του Russel.
Αποδεικτικές διαδικασίες, μαθηματική επαγωγή.
Αρχή εγκλεισμού-αποκλεισμού.
Σχέσεις και συναρτήσεις. Διμελείς σχέσεις, ιδιότητες διμελών σχέσεων, σχέσεις ισοδυναμίας, σχέσεις μερικής και ολικής διάταξης, κλειστότητες σχέσεων, συναρτήσεις, αρχή του περιστερώνα.
Γλώσσες, γραμματικές, τύποι γραμματικών και γλωσσών, κανονικές γλώσσες, γλώσσες χωρίς συμφραζόμενα, πεπερασμένα αυτόματα ως μηχανές αναγνώρισης κανονικών γλωσσών, το Λήμμα Αντλησης για κανονικές γλώσσες.
Συνδυαστική απαρίθμηση. Κανόνες γινομένου και αθροίσματος, εφαρμογές αρχής εγκλεισμού-αποκλεισμού, μεταθέσεις και διατάξεις, συνδυασμοί, δυωνυμικοί συντελεστές, τρίγωνο του Pascal, διανομή διακεκριμένων και μη-διακεκριμένων αντικειμένων σε υποδοχές, κατασκευή μεταθέσεων και συνδυασμών, στοιχεία διακριτής πιθανότητας.
Ασυμπτωτικός συμβολισμός και ασυμπτωτική εκτίμηση.
Ακολουθίες, πράξεις μεταξύ ακολουθιών.
Γεννήτριες Συναρτήσεις. Βασικές ιδιότητες, εφαρμογή στον υπολογισμό αθροισμάτων, εφαρμογή στην επίλυση συνδυαστικών προβλημάτων, εκθετικές Γεννήτριες Συναρτήσεις.
Επίλυση γραμμικών αναδρομικών εξισώσεων με σταθερούς συντελεστές. Χαρακτηριστική εξίσωση, ομογενής λύση, ειδική λύση, επίλυση με τη μέθοδο των Γεννητριών Συναρτήσεων.
Για τις εξετάσεις, πρέπει να έχετε μελετήσει και κατανοήσει όλη την ύλη που θα παρουσιάσουμε στην τάξη (αν χάσατε κάποια μαθήματα, οι διαφάνειες θα σας βοηθήσουν). Ενδεικτικά αναφέρεται ότι η ύλη που θα καλύψουμε στο μάθημα αντιστοιχεί στα Κεφάλαια 1, 2, 3 (με εξαίρεση τις ενότητες 3.7 και 3.8), 4, 7, 9, και 10 από το βιβλίο του Liu, και στα Κεφάλαια 1 (με εξαίρεση τις ενότητες 1.4 και 1.5), 2, 3.2, 4 (με εξαίρεση την ενότητα 4.5), 5, 7, 8, και 12 (με εξαίρεση τις ενότητες 12.2 και 12.5) από το βιβλίο του Rosen (η αρίθμηση των ενοτήτων αναφέρεται στο πρωτότυπο, 6η έκδοση). Υπάρχουν αρκετά πράγματα που θα πούμε στο μάθημα και δεν αναλύονται επαρκώς στα βιβλία (σε ένα από τα δύο ή και στα δύο, συχνότερα συμβαίνει αυτό με το βιβλίο του 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.
Η. Κουτσουπιάς. Μαθηματικά της Πληροφορικής. ΕΚΠΑ, 2008.
Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης. Διακριτά Μαθηματικά: Τα Μαθηματικά της Επιστήμης των Υπολογιστών. Gutenberg, 1994.
Γ. Βουτσαδάκης, Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης. Διακριτά Μαθηματικά: Προβλήματα και Λύσεις. Gutenberg, 1994.
Μ. Κούτρας. Μάθημα (και βιβλίο) Συνδυαστικής. Πανεπιστήμιο Πειραιά.
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.
Χρήσιμο υλικό, ασκήσεις, και σημειώσεις μπορείτε να βρείτε στην ιστοσελίδα του μαθήματος.
Σημειώσεις για την αποδεικτική τεχνική της Μαθηματικής Επαγωγής (Δ. Φωτάκης). Οι σημειώσεις δεν εντάσσονται στην εξεταστέα ύλη, αλλά η αποδεικτική τεχνική της Μαθηματικής Επαγωγής εντάσσεται.
Κάποιες σημειώσεις στις βασικές έννοιες της συνδυαστικής (Δ. Φωτάκης) και μια χρήσιμη σύνοψη σε μορφή διαγράμματος.
Κάποιες σημειώσεις στις βασικές ιδιότητες των Γεννητριών Συναρτήσεων (Δ. Φωτάκης) και στις εφαρμογές τους.
Κάποιες σημειώσεις για τεχνικές επίλυσης αναδρομικών σχέσεων (Δ. Φωτάκης).
Κάποιες συμπληρωματικές σημειώσεις στον ασυμπτωτικό συμβολισμό (Δ. Φωτάκης).
Μια χρήσιμη σύνοψη των περισσότερων βασικών εννοιών των Διακριτών Μαθηματικών (αναφέρεται και σε πολλές έννοιες που δεν παρουσιάσαμε στο μάθημα).
Συζήτηση των ερωτημάτων της 1ης ΓΕ.
Συνδυαστική Απαρίθμηση: Παραδείγματα. Βασικές Ιδιότητες Δυωνυμικών Συντελεστών. Δημιουργία Μεταθέσεων και Συνδυασμών.
Γεννήτριες Συναρτήσεις: Ορισμός και Βασικές Ιδιότητες.
Γεννήτριες Συναρτήσεις: Βασικές Ιδιότητες. Εφαρμογή στον υπολογισμό αθροισμάτων και στην απαρίθμηση συνδυασμών.
Γεννήτριες Συναρτήσεις: Εφαρμογή στην απαρίθμηση συνδυασμών. Εκθετικές γεννήτριες συναρτήσεις και απαρίθμηση διατάξεων.
Επίλυση Γραμμικών Αναδρομικών Σχέσεων με Σταθερούς Συντελεστές.
Αλγόριθμοι Διαίρει-και-Βασίλευε. Επίλυση Αναδρομικών Σχέσεων που προκύπτουν κατά την ανάλυσή τους.
Σύντομη αναδρομή στην ύλη. Συζήτηση ερωτημάτων 2ης γραπτής εργασίας.
Τελευταία αλλαγή: 29/6/09 18:00
