ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ

Μαθησιακά Αποτελέσματα:

Μετά την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές θα είναι σε θέση:

• Να κατανοούν τις βασικές διακριτές δομές, τις ιδιότητες, τη σχέση τους με άλλα αντικείμενα και τις εφαρμογές τους σε προβλήματα του πραγματικού κόσμου.
• Να γνωρίζουν και να εφαρμόζουν ορθά τεχνικές για την απόδειξη λογικών επιχειρημάτων.
• Να μετατρέπουν απλές προτάσεις της φυσικής γλώσσας σε τύπους της προτασιακής λογικής και να κατανοούν την ανεπάρκεια της προτασιακής λογικής για τη διατύπωση πιο πολύπλοκων προτάσεων της φυσικής γλώσσας.
• Να χρησιμοποιούν βασικούς κανόνες μέτρησης (π.χ., γινόμενο, άθροισμα, διατάξεις, μεταθέσεις, επιλογές με/χωρίς επανάληψη, κ.λπ.) για εξαγωγή συνδυαστικών τύπων.
• Να κατανούν τις θεμελειώδεις έννοιες των πιθανοτήτων και να υπολογίζουν την (κανονική / υπό συνθήκη) πιθανότητα να συμβεί ένα γεγονός σε ένα διακριτό δειγματικό χώρο.
• Να αναγνωρίζουν σχέσεις ισοδυναμίας ή/και σχέσεις διάταξης, και να εντοπίζουν κλάσεις, ακρότατα και φράγματα.
• Να αναγνωρίζουν δομές γράφων και να εφαρμόζουν βασικούς αλγορίθμους (συνεκτικότητας, αναζήτησης κυκλωμάτων Euler και Hamilton, προσδιορισμού επικαλύπτοντος δέντρου κ.λπ.).
• Να αναγνωρίζουν και να αποδεικνύουν βασικές ιδιότητες γραφημάτων (π.χ., ισομορφισμοί, ίχνη και κυκλώματα Euler, επιπεδότητα, κ.λπ.).
• Να γνωρίζουν και να εφαρμόζουν διαφορετικές μεθόδους διαπέρασης για γραφήματα ή/και δένδρα (pre-order, in-order και post-order, BFS, DFS, κ.λπ).
• Να είναι σε θέση να μοντελοποιούν προβλήματα του πραγματικού κόσμου για επεξεργασία από Η/Υ, με τη χρήση κατάλληλης μορφής γραφημάτων και δένδρων, π.χ., για την αναπαράσταση μιας δικτυακής τοπολογίας, την οργάνωση ενός ιεραρχικού συστήματος αρχείων (π.χ. Linux), κ.λπ.
• Να κατανοούν τη δομή και τη χρήση των μηχανών πεπερασμένων καταστάσεων για επεξεργασία της πληροφορίας.
• Να αντιλαμβάνονται την έννοια της υπολογισιμότητας μιας τυπικής γλώσσας.
• Να κατανοούν τη συσχέτιση μεταξύ πεπερασμένων αυτομάτων και κανονικών γλωσσών.

Γενικές Ικανότητες:


Οι ικανότητες που πρέπει να αποκτήσει ο πτυχιούχος και στις οποίες αποσκοπεί το μάθημα είναι:

• Προαγωγή ελεύθερης, δημιουργικής και επαγωγικής σκέψης.
• Αναζήτηση, ανάλυση και σύνθεση δεδομένων, τεχνικών και πληροφοριών, με τη χρήση και των απαραίτητων τεχνικών.
• Ανάπτυξη και τεκμηρίωση επιχειρημάτων με αξιοποίηση δομημένης μαθηματικής σκέψης.
• Συνδυαστική ανάλυση μεθόδων για επίλυση προβλημάτων.
• Ανάπτυξη αλγοριθμικής σκέψης.
• Ικανότητα αφαίρεσης στη μοντελοποίηση προβλημάτων του πραγματικού κόσμου.

Περιεχόμενο Μαθήματος:

Ενότητα 1.
• Σύνολα και πράξεις.
• Στοιχεία προτασιακής και κατηγορηματικής λογικής.
• Αρχή εγκλεισμού-αποκλεισμού. Αρχές απόδειξης.
Ενότητα 2.
• Μεταθέσεις και συνδυασμοί.
• Στοιχεία διακριτής πιθανότητας.
Ενότητα 3.
• Σχέσεις και συναρτήσεις. Σχέσεις διάταξης.
• Σχέσεις ισοδυναμίας. Εφαρμογές.
Ενότητα 4.
• Γραφήματα. Ορισμοί, ιδιότητες και βασικά προβλήματα.
• Συνεκτικότητα και συγγενείς έννοιες.
• Βασικοί αλγόριθμοι γράφων και εφαρμογές
• Επίπεδα γραφήματα, τύπος του Euler, θεώρημα Kuratowski.
• Δέντρα. Ορισμοί, ιδιότητες, αλγόριθμοι και εφαρμογές.
Ενότητα 5. Υπολογισιμότητα Γλωσσών και Πεπερασμένα αυτόματα
• Τυπικές γλώσσες και υπολογισιμότητα.
• Αυτόματα Πεπερασμένων Καταστάσεων.
• Κανονικές γλώσσες, κανονικές εκφράσεις και Ντετερμινιστικά Πεπερασμένα Αυτόματα.