Είσοδος

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

Γενικά στοιχεία

 

 
Περιγραφή

Το μάθημα αφορά στην συστηματική μελέτη των σημαντικότερων εννοιών των Διακριτών Μαθηματικών και των εφαρμογών τους στην Επιστήμη των Υπολογιστών.

Ύλη

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

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

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

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

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

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

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

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

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

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

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

  • Μ. 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.

Διδάσκοντες

  • Φώτω Αφράτη, Καθηγήτρια ΣΗΜΜΥ, ΕΜΠ

  • Δημήτρης Φωτάκης, Λέκτορας ΣΗΜΜΥ, ΕΜΠ

Βοηθοί

  • Δώρα Σούλιου, ΕΕΔΙΠ ΣΗΜΜΥ, ΕΜΠ

Ιστοσελίδα

  • Η ιστοσελίδα του μαθήματος: http://www.softlab.ntua.gr/~fotakis/discrete_math. Εκεί θα βρείτε περισσότερες πληροφορίες για το μάθημα, τις διαφάνειες των διαλέξεων, και συμπληρωματικό υλικό.

 

 



Συγχρηματοδότηση
από την Ε.Ε.