Διακριτά Μαθηματικά (2ΚΠ02 )
Διδάσκων : Βασίλειος Δρακόπουλος
ΕίδοςΥποχρεωτικό
Εξάμηνο2
ΠερίοδοςΕΕ
ECTS5
Ώρες Θεωρίας3
Ώρες Εργαστηρίου
Περιγραφή
Εισαγωγή εις την λογική και τις αποδείξεις· προτασιακός λογισμός, προτασιακές ισοδυναμίες, κατηγορήματα και ποσοδείκτες. Θεωρία συνόλων· πράξεις συνόλων, πεπερασμένα και άπειρα σύνολα. Σχέσεις και συναρτήσεις· ιδιότητες διμελών σχέσεων, σχέσεις ισοδυναμίας, δικτυωτά μερικής διατάξεως, αλυσίδες και αντιαλυσίδες. Καταμέτρηση· η αρχή του περιστερεώνα, διατάξεις και συνδυασμοί, γεννήτριες συναρτήσεις. Υπολογισιμότητα· γλώσσες και γραμματικές, μηχανές πεπερασμένων καταστάσεων, αναγνώριση γλωσσών. Γραφήματα· επίπεδα, βεβαρημένα και κατευθυνόμενα γραφήματα, ατραποί, διαδρομές και κυκλώματα, διαδρομές και κυκλώματα Euler, διαδρομές και κυκλώματα Hamilton, το πρόβλημα του πλανόδιου πωλητή. Δένδρα· εκτείνοντα και δυαδικά δένδρα, αλγόριθμοι δένδρων και γραφημάτων. Αλγόριθμοι· πολυπλοκότητα αλγορίθμων, ιδιότητες ακεραίων αριθμών, πρώτοι αριθμοί και μέγιστοι κοινοί διαιρέτες, μαθηματική επαγωγή και αναδρομή, διακριτές αριθμητικές συναρτήσεις.
Μαθησιακοί Στόχοι

Με την ολοκλήρωση της 2ΚΠ02, οι φοιτητές θα είναι σε θέση να εξηγούν και να εφαρμόζουν τις βασικές μεθόδους των διακριτών (ασυνεχών) μαθηματικών στην Επιστήμη των Υπολογιστών και την Πληροφορική. Θα είναι σε θέση να χρησιμοποιούν αυτές τις μεθόδους στα επακόλουθα μαθήματα στον σχεδιασμό και την ανάλυση αλγορίθμων, την θεωρία υπολογισιμότητας, την μηχανολογία λογισμικού και τα συστήματα υπολογιστών. Πιο συγκεκριμένα, οι φοιτητές θα είναι σε θέση

  • να συλλογούνται μαθηματικώς περί βασικών ειδών και δομών δεδομένων (όπως οι αριθμοί, τα σύνολα, τα γραφήματα και τα δένδρα) χρησιμοποιούντα σε αλγορίθμους και συστήματα υπολογιστών· να διακρίνουν αυστηρούς ορισμούς και συμπεράσματα από τα απλώς εύλογα· να συνθέτουν στοιχειώδεις αποδείξεις, ειδικώς αποδείξεις με επαγωγή.
  • να προτυπώνουν και να αναλύουν υπολογιστικές διεργασίες χρησιμοποιώντας αναλυτικές και συνδυαστικές μεθόδους.
  • να εφαρμόζουν τις αρχές των διακριτών πιθανοτήτων προς υπολογισμό πιθανοτήτων και αναμενομένων τιμών απλών τυχαίων διεργασιών.
  • να εργάζονται σε μικρές ομάδες προς επίτευξη όλων των ανωτέρω στόχων.
Συγγράμματα/Βιβλιογραφία
  • Susanna S. Epp, Διακριτά Μαθηματικά με εφαρμογές (Τρίτη Αμερικανική Έκδοση), 2η έκδ., Εκδ. Κλειδάριθμος, Αθήνα, 2010
  • S. Lipschutz και M. L. Lipson, Διακριτά Μαθηματικά, 2η έκδ., Εκδ. Τζιόλα, Θεσσαλονίκη, 2004
  • C. L. Liu, Στοιχεία Διακριτών Μαθηματικών, Πανεπιστημιακές Εκδόσεις Κρήτης, Ι.Τ.Ε., Ηράκλειο Κρήτης, 2006
  • K. H. Rosen, Διακριτά Μαθηματικά και Εφαρμογές τους, 7η έκδ., Εκδ. Τζιόλα, Θεσσαλονίκη, 2015
  • Δ. Αναπολιτάνος, Δ. Γαβαλάς, Α. Δέμης, Κ. Δημητρακόπουλος και Β. Καρασμάνης, Λογική: Θεωρία και πρακτική, Α’ έκδοση, Ο.Ε.Δ.Β., Αθήνα, 1999
  • Γ. Βουτσαδάκης, Λ. Κυρούσης, Χ. Μπούρας και Π. Σπυράκης, Διακριτά Μαθηματικά: Προβλήματα και λύσεις, Gutenberg, Αθήνα, 2003
Τρόπος Εξέτασης
Γραπτή εξέταση στο τέλος του ακαδημαϊκού εξαμήνου.
Υλικό
Διαφάνειες, Σύγγραμμα, Άρθρα