Περιγραφή θέματος

  • Γενικά

    • Διακριτά Μαθηματικά Ι

      Διδάσκων: Σπύρος Κοντογιάννης

    • Περιεχόμενο μαθήματος: Εισαγωγή στη μαθηματική λογική (Προτασιακή λογική, σημασιολογική προσέγγιση. Προτασιακός λογισμός και τυπικές αποδείξεις, συντακτική προσέγγιση). Αποδεικτικές τεχνικές (Αντιθετοαναστροφή, απαγωγή σε άτοπο, μαθηματική επαγωγή). Σύνολα, σχέσεις, συναρτήσεις (Πράξεις και ιδιότητες πράξεων συνόλων, εγκλεισμός-αποκλεισμός, συναρτήσεις 1-1, επί, σχέσεις ισοδυναμίας, σχέσεις διάταξης, ακρότατα και φράγματα, ασυμπτωτική συμπεριφορά συναρτήσεων). Αριθμησιμότητα (Πεπαρασμένα / άπειρα σύνολα, αρχή περιστερώνα, παράδοξο του Russell, διαγωνοποίηση του Cantor). Συνδυαστική: Κανόνες αθροίσματος/γινομένου, διατάξεις και μεταθέσεις, σφαιρίδια σε κουτιά, επιλογές μη διατεταγμένων συλλογών με/δίχως επανάληψη). Διακριτή πιθανότητα (Διακριτός δειγματικός χώρος,γεγονός, υπό συνθήκη πιθανότητα, κανόνας του Bayes, αναμενόμενη τιμή μεταβλητής).

      Μαθησιακοί στόχοι: Το μάθημα αποσκοπεί:

      1. Στην κατανόηση των δυνατοτήτων μοντελοποίησης που παρέχει η μαθηματική λογική στην πληροφορική.
      2. Στην εξοικείωση με τη χρήση βασικών τεχνικών για την απόδειξη της ορθότητας λογικών επιχειρημάτων.
      3. Στην εξοικείωση με τη βασική ορολογία, τις πράξεις, και τις ιδιότητες συνόλων, σχέσεων και συναρτήσεων.
      4. Στην εξοικείωση με θεμελιώδεις κανόνες μέτρησης διακριτών δομών, τη μοντελοποίηση προβλημάτων μέτρησης με χρήση αυτών των κανόνων.
      5. Στην εξοικείωση με τον υπολογισμό μάζας πιθανότητας γεγονότων / αναμενόμενης τιμής τυχαίων μεταβλητών, διάκριση μεταξύ εξαρτώμενων και ανεξάρτητων γεγονότων σε διακριτό δειγματικό χώρο.

      Λέξεις κλειδιά: Προτασιακή λογική, σημασιολογική προσέγγιση, προτασιακός λογισμός, αποδεικτικές τεχνικές, αντιθετοαναστροφή, απαγωγή σε άτοπο, μαθηματική επαγωγή, σύνολα, εγκλεισμός-αποκλεισμός, σχέσεις ισοδυναμίας, σχέσεις διάταξης, ακρότατα, φράγματα, αριθμησιμότητα, αρχή περιστερώνα, παράδοξο του Russell, διαγωνοποίηση του Cantor, συνδυαστική, κανόνας του Bayes.

  • 1. Μαθηματική λογική και αποδεικτικές τεχνικές

    • Περιγραφή θεματικής ενότητας: Εισαγωγικά, Προτασιακή Λογική, Εκφράσεις, Τύποι, Δενδροδιαγράμματα, Αποτιμήσεις, Πίνακες Αλήθειας, Ικανοποιησιμότητα, Ταυτολογίες, Αντιφάσεις, Ταυτολογική Συνεπαγωγή & Ισοδυναμία, Νόμοι της Προτασιακής Λογικής, Κανονική Διαζευκτική Μορφή, Πληρότητα Συνόλων Συνδέσμων, Αποδεικτικές Τεχνικές, Συντακτική Προσέγγιση, Αξιωματικά Συστήματα, Τυπικές αποδείξεις, Μεταθεωρήματα Απαγωγής, Αντιθετοαναστροφής, Απαγωγής σε Άτοπο, Εγκυρότητα-Πληρότητα, Συμπάγεια, Μαθηματική Επαγωγή.

      Λέξεις κλειδιά: Προτασιακή Λογική, δενδροδιαγράμματα, πίνακες Αλήθειας, ταυτολογίες, πληρότητα συνόλων συνδέσμων, συντακτική προσέγγιση προτασιακής λογικής, αξιωματικά συστήματα, μεταθεωρήματα απαγωγής, αντιθετοαναστροφής, απαγωγή σε άτοπο, μαθηματική επαγωγή.

  • 2. Θεωρία συνόλων

    • Περιγραφή θεματικής ενότητας: Εισαγωγή Στη Θεωρία Συνόλων, Σύνολα, Υποσύνολα, Πράξεις Συνόλων, Ταυτότητες Πράξεων σε Σύνολα, Ιδιότητες Πληθαρίθμων, Αρχή Εγκλεισμού-Αποκλεισμού, Άλγεβρες Boole, Παράδοξα Θεωρίας Συνόλων, Παράδοξο του Russell, Αδυναμία Ελέγχου Τερματισμού Προγραμμάτων, Πληθικότητα Συνόλων, Άπειρα και Πεπερασμένα Σύνολα, Αριθμησιμότητα / Μη Αριθμησιμότητα Συνόλων.

      Λέξεις κλειδιά: Θεωρία συνόλων, σύνολα, υποσύνολα, πληθάριθμοι, αρχή εγκλεισμού-αποκλεισμού, άλγεβρα Boole, παράδοξο του Russell, πληθικότητα συνόλων, αριθμησιμότητα συνόλων.

  • 3. Σχέσεις και συναρτήσεις

    • Περιγραφή θεματικής ενότητας: Σχέσεις & Συνάρτήσεις, Ιδιότητες Σχέσεων, Σχέσεις Ισοδυναμίας και Διατάξεις, Πράξεις Σχέσεων, Αρχή Περιστερώνα, Ακρότατα και Φράγματα.

      Λέξεις κλειδιά: Σχέσεις, συνάρτήσεις, σχέσεις ισοδυναμίας, διατάξεις, αρχή Περιστερώνα, ακρότατα, φράγματα.

  • 4. Συνδυαστική

    • Περιγραφή θεματικής ενότητας: Συνδυαστική, Κανόνες Αθροίσματος & Γινομένου, Μεταθέσεις και Διατάξεις, Διατάξεις Ομάδων Αντικειμένων, Ρίψη Σφαιριδίων σε Υποδοχές, Επιλογές με/χωρίς Επανάληψη, Διωνυμικοί Συντελεστές & Τύπος του Pascal, Διωνυμικό Θεώρημα.

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

  • 5. Διακριτή πιθανότητα

    • Περιγραφή θεματικής ενότητας: Διακριτή Πιθανότητα, Διακριτή Συνάρτηση Πιθανότητας, Δείγματα και Γεγονότα, Αναμενόμενη Τιμή Πειράματος με Αριθμητικές Τιμές, Παράδοξο των Γενεθλίων, Μέθοδος Monte Carlo, Πιθανοτική Μέθοδος, Δεσμευμένη Πιθανότητα, Θεώρημα του Bayes.

      Λέξεις κλειδιά: Διακριτή πιθανότητα, διακριτή συνάρτηση πιθανότητας, δείγματα, αναμενόμενη τιμή πειράματος, παράδοξο των γενεθλίων, μέθοδος Monte Carlo, δεσμευμένη πιθανότητα, θεώρημα του Bayes.

  • Προτεινόμενα συγγράμματα

    • Kenneth H. Rosen. Διακριτά Μαθηματικά και Εφαρμογές τους (7η έκδοση). Εκδόσεις Τζιόλα, 2015.
       
    • Susanna S. Epp. Διακριτά Μαθηματικά με Εφαρμογές. Εκδόσεις Κλειδάριθμος, 2004.

    • Επιπλέον συνιστώμενη βιβλιογραφία

      • C. L. Liu.  Στοιχεία Διακριτών Μαθηματικών, Πανεπιστημιακές Εκδόσεις Κρήτης, 2003.
         
      • C. L. Liu : Introduction to  Combinatorial Mathematics. McGraw-Hill.
         
      • L. Lovasz, K. Vesztergombi. Discrete Mathematics. Lecture Notes, Yale University, Spring 1999 (διαθέσιμο και ηλεκτρονικά).
         
      • Γ. Βουτσαδάκης, Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης. Διακριτά Μαθηματικά: προβλήματα και λύσεις. Gutenberg, 2000 (διατίθεται και ηλεκτρονικά).
         
      • Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης. Διακριτά Μαθηματικά: Τα Μαθηματικά της Επιστήμης των Υπολογιστών, 1992 (διατίθεται και ηλεκτρονικά).