Διακριτές Μέθοδοι για την επιστήμη των Υπολογιστών
εαρινό εξάμηνο 2014
Διακριτές Μέθοδοι για την επιστήμη των Υπολογιστών
Γενικά
Ώρες Μαθήματος
Δευτέρα και Πέμπτη 12:45-14:30 (Αίθουσα 1 Νέο Κτήριο ΣΗΜΜΥ)
Διδάσκοντες
- Φώτω Αφράτη, Καθηγήτρια ΣΗΜΜΥ()
- Στάθης Ζάχος, Καθηγητής ΣΗΜΜΥ()
- Δώρα Σούλιου, Ε.ΔΙ.Π. ΣΗΜΜΥ ()
Ώρες γραφείου
Κάθε Τετάρτη 13:30-15:30, στο Corelab (Παλαιό Κτήριο Ηλεκτρολόγων, 1ος όροφος, αίθ. 1.1.30).
Ανακοινώσεις
- [31/3/2015] Βαθμολογία εξέτασης Μαρτίου 2015 [pdf]
- [15/10/2014] Βαθμολογία επαναληπτκής εξέτασης 2014
[pdf]
Μπορείτε να δείτε τα γραπτά σας ή να ρωτήσετε σχετικά με την βαθμολογία σας την Δευτέρα 20 Oκτωβρίου 2014 και ώρα 17:00 στο Corelab (Πα - [23/09/2014] Βαθμολογία κανονικής εξέτασης 2014 [pdf]
- [30/08/2014]Σχέδιο λύσεων για την 3η γραπτή σειρ [pdf]
- [02/08/2014]Σχέδιο λύσεων για την 2η γραπτή σειρά ασκήσεων. [pdf]
- [25/07/2014] Η προθεσμία υποβολής της 6ης online άσκησης παρατείνεται ως τις 5 Αυγούστου 2014.
- [31/07/2014] Ανακοινώθηκε η τρίτη σειρά γραπτών ασκήσεων. [pdf] Παράδοση εργασιών Πέμπτη 28/08/2014 στη θυρίδα μου (Δ. Σούλιου) στο δεύτερο όροφο Παλαιό Κτήριο Ηλεκτρολόγων. Καλή Επιτυχία!
- [28/07/2014] Διόρθωση στη δεύτερη σειρά γραπτών ασκήσεων. Στο 5ο θέμα η τρίτη γλώσσα είναι n/=m και n+m άρτιος και όχι n/=m ή n+m άρτιος.
- [25/07/2014] Ανακοινώθηκε η 6η online άσκηση. Η προθεσμία υποβολής λήγει τo Σάββατο 2 Αυγούστου 2014. Καλή επιτυχία!
- [21/07/2014] Η παράδοση των εργασιών της δεύτερης σειράς γραπτών ασκήσεων έχει παραταθεί και θα γίνει πριν το μάθημα της Πέμπτης 31/7/2014.
- [21/07/2014] Ανακοινώθηκε η 5η online άσκηση. Η προθεσμία υποβολής λήγει την Δευτέρα 28 Ιουλίου 2014. Καλή επιτυχία!
- [14/07/2014] Βαθμολογία εξεταστικής Απριλίου 2014 [pdf]
- [14/07/2014] Ανακοινώθηκε η δεύτερη σειρά γραπτών ασκήσεων.
- [14/07/2014] Λόγω προβλήματος με το προβολικό μηχάνημα τα μαθήματα θα γίνονται στην αίθουσα 1 Νέο Κτήριο ΣΗΜΜΥ
- [2/06/2014] Ανακοινώθηκε η 4η online άσκηση. Η προθεσμία υποβολής λήγει την Δευτέρα 21 Ιουλίου 2014. Καλή επιτυχία!
- [15/05/2014] Η πρώτη σειρά γραπτών ασκήσεων με βοηθητική διευκρίνηση στην κατηγορηματική λογική. [pdf]. Παράδοση εργασιών στο μάθημα της Πέμπτης 5/6/2014.
- [2/06/2014] Ανακοινώθηκε η 3η online άσκηση. Η προθεσμία υποβολής λήγει την Κυριακή 15/6/2014. Καλή επιτυχία!
- [31/05/2014] Η παράδοση των εργασιών της πρώτης σειράς γραπτών ασκήσεων έχει παραταθεί και θα γίνει στο μάθημα της Πέμπτης 5/6/2014.
- [19/05/2014] Ανακοινώθηκε η 2η online άσκηση. Η προθεσμία υποβολής λήγει την Κυριακή 1/6/2014. Καλή επιτυχία!
- [15/05/2014] Ανακοινώθηκε η πρώτη σειρά γραπτών ασκήσεων [pdf]. Παράδοση εργασιών στο μάθημα της Πέμπτης 28/5/2014. Καλή Επιτυχία!
- [10/04/2014] Ανακοινώθηκε η 1η online άσκηση. Η προθεσμία υποβολής λήγει την Κυριακή 4/5/2014. Οδηγίες εγγραφής στο gradiance. [pdf]
- [7/04/2014] Η πρώτη συνάντηση θα γίνει την Πέμπτη 10 Απριλίου 2014 στις 12:45 στο αμφιθέατρο 5 του νέου κτιρίου ηλεκτρολόγων -->
Περιεχόμενα
- Σύνολα και πράξεις συνόλων.
- Αριθμήσιμα και μη αριθμήσιμα σύνολα, αρχή της διαγωνιοποίησης, μη υπολογισιμότητα, παράδοξο του Russell.
- Αποδεικτικές διαδικασίες, μαθηματική επαγωγή, αρχή του περιστερώνα.
- Στοιχεία προτασιακής και κατηγορηματικής λογικής.
- Σχέσεις και συναρτήσεις. Διμελείς σχέσεις, ιδιότητες διμελών σχέσεων, σχέσεις ισοδυναμίας, σχέσεις μερικής και ολικής διάταξης, κλειστότητες σχέσεων, συναρτήσεις, αρχή του περιστερώνα.
- Γλώσσες, γραμματικές, τύποι γραμματικών και γλωσσών, κανονικές γλώσσες, γλώσσες χωρίς συμφραζόμενα, πεπερασμένα αυτόματα ως μηχανές αναγνώρισης κανονικών γλωσσών, το Λήμμα 'Αντλησης για κανονικές γλώσσες.
- Αρχή εγκλεισμού-αποκλεισμού.
- Συνδυαστική απαρίθμηση. Κανόνες γινομένου και αθροίσματος, εφαρμογές αρχής εγκλεισμού-αποκλεισμού, μεταθέσεις και διατάξεις, συνδυασμοί, δυωνυμικοί συντελεστές, τρίγωνο του Pascal, διανομή διακεκριμένων και μη-διακεκριμένων αντικειμένων σε υποδοχές, κατασκευή μεταθέσεων και συνδυασμών, στοιχεία διακριτής πιθανότητας.
- Γεννήτριες Συναρτήσεις. Βασικές ιδιότητες, εφαρμογή στον υπολογισμό αθροισμάτων, εφαρμογή στην επίλυση συνδυαστικών προβλημάτων, εκθετικές Γεννήτριες Συναρτήσεις.
- Επίλυση γραμμικών αναδρομικών εξισώσεων με σταθερούς συντελεστές. Χαρακτηριστική εξίσωση, ομογενής λύση, ειδική λύση, επίλυση με τη μέθοδο των Γεννητριών Συναρτήσεων.
- Ασυμπτωτικός συμβολισμός και ασυμπτωτική εκτίμηση.
Ύλη
Βιβλιογραφία
Συμπληρωματικό Υλικό
Προτεινόμενες Ασκήσεις
Διαλέξεις Διαφάνειες
- Παράδοση 10/4/2014 Διαδικαστικά θέματα, εισαγωγή. [pdf] Οδηγίες εγγραφής στο gradiance. [pdf] Σύνολα και πράξεις συνόλων. [pdf]
- Παράδοση 28/4/2014 Αριθμήσιμα και μη αριθμήσιμα σύνολα. Αρχή της Διαγωνιοποίησης. [pdf]
- Παράδοση 5/5/2014 Μη υπολογισιμότητα. Τοπαράδοξο του Russell. Αποδεικτικές Διαδικασίες.
- Παράδοση 8/5/2014 Μαθηματική Επαγωγή. [pdf]
- Παράδοση 12/5/2014 Αρχή του Περιστερώνα [pdf]
- Παράδοση 15/5/2014 Αρχή του Περιστερώνα παραδείγματα. Αριθμοί Ramsey. [pdf].
- Παράδοση 19/5/2014 Προτασιακή Λογική. [pdf]
- Παράδοση 22/5/2014 Προτασιακός Λογισμός, Παραδείγματα. [pdf] Κατηγορηματική Λογική.
- Παράδοση 26/5/2014 Κατηγορηματική Λογική [pdf], Παραδείγματα [pdf].
- Παράδοση 29/5/2014 Κατηγορηματική Λογική [pdf], Παραδείγματα [pdf].
- Παράδοση 2/6/2014 Διμελείς Σχέσεις. Βασικοί Ορισμοί και Ιδιότητες. [pdf] Κλειστότητες. Μεταβατική Κλειστότητα.
- Παράδοση 5/6/2014 Κλειστότητες. Μεταβατική Κλειστότητα. [pdf] Σχεσιακό Μοντέλο Βάσεων Δεδομένων.
- Παράδοση 12/6/2014 Αλγόριθμος Warshall. Σχέσεις Ισοδυναμίας. [pdf]
- Παράδοση 3/7/2014 Σχέσεις Μερικής Διάταξης. [pdf]
- Παράδοση 7/7/2014 Τοπολογική Διάταξη, Παραδείγματα. [pdf] Τυπικές Γλώσσες. [pdf] Γραμματικές. [pdf]
- Παράδοση 10/7/2014 Ντετερμινιστικά πεπερασμένα αυτόματα. Μη ντετερμινιστικά πεπερασμένα αυτόματα.
- Παράδοση 14/7/2014 Μη ντετερμινιστικά πεπερασμένα αυτόματα. Ισοδυναμία ντετερμινιστικών και μη ντετερμινιστικών αυτομάτων. [pdf]
- Παράδοση 17/7/2014 Αναπαράσταση κανονικών γλωσσών: Κανονικές Γραμματικές, Πεπερασμένα Αυτόματα, Κανονικές Εκφράσεις, Λήμμα Άντλησης για κανονικές Γλώσσες. [pdf]
- Παράδοση 21/7/2014 Γλώσσες Χωρίς Συμφραζόμενα. Λήμμα Άντλησης για Γλώσσες Χωρίς Συμφραζόμενα. [pdf]
- Παράδοση 24/7/2014 Αρχή Εγκλεισμού-Αποκλεισμού. [pdf] Συνδυαστική Απαρίθμηση: Κανόνες Γινομένου και Αθροίσματος. [pdf]
- Παράδοση 28/7/2014 Συνδυαστική Απαρίθμηση: Διατάξεις και Συνδυασμοί.
- Παράδοση 31/7/2014 Συνδυαστική Απαρίθμηση: παραδείγματα και ασκήσεις.