Μετά την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές θα είναι σε θέση:
Να κατανοούν τις βασικές διακριτές δομές, τις ιδιότητες, τη σχέση τους με άλλα αντικείμενα και τις εφαρμογές τους σε προβλήματα του πραγματικού κόσμου.
Να γνωρίζουν και να εφαρμόζουν ορθά τεχνικές για την απόδειξη λογικών επιχειρημάτων.
Να μετατρέπουν απλές προτάσεις της φυσικής γλώσσας σε τύπους της προτασιακής λογικής και να κατανοούν την ανεπάρκεια της προτασιακής λογικής για τη διατύπωση πιο πολύπλοκων προτάσεων της φυσικής γλώσσας.
Να χρησιμοποιούν βασικούς κανόνες μέτρησης (π.χ., γινόμενο, άθροισμα, διατάξεις, μεταθέσεις, επιλογές με/χωρίς επανάληψη, κ.λπ.) για εξαγωγή συνδυαστικών τύπων.
Να κατανούν τις θεμελειώδεις έννοιες των πιθανοτήτων και να υπολογίζουν την (κανονική / υπό συνθήκη) πιθανότητα να συμβεί ένα γεγονός σε ένα διακριτό δειγματικό χώρο.
Να αναγνωρίζουν σχέσεις ισοδυναμίας ή/και σχέσεις διάταξης, και να εντοπίζουν κλάσεις, ακρότατα και φράγματα.
Να αναγνωρίζουν δομές γράφων και να εφαρμόζουν βασικούς αλγορίθμους (συνεκτικότητας, αναζήτησης κυκλωμάτων Euler και Hamilton, προσδιορισμού επικαλύπτοντος δέντρου κ.λπ.).
Να αναγνωρίζουν και να αποδεικνύουν βασικές ιδιότητες γραφημάτων (π.χ., ισομορφισμοί, ίχνη και κυκλώματα Euler, επιπεδότητα, κ.λπ.).
Να γνωρίζουν και να εφαρμόζουν διαφορετικές μεθόδους διαπέρασης για γραφήματα ή/και δένδρα (pre-order, in-order και post-order, BFS, DFS, κ.λπ).
Να είναι σε θέση να μοντελοποιούν προβλήματα του πραγματικού κόσμου για επεξεργασία από Η/Υ, με τη χρήση κατάλληλης μορφής γραφημάτων και δένδρων, π.χ., για την αναπαράσταση μιας δικτυακής τοπολογίας, την οργάνωση ενός ιεραρχικού συστήματος αρχείων (π.χ. Linux), κ.λπ.
Να κατανοούν τη δομή και τη χρήση των μηχανών πεπερασμένων καταστάσεων για επεξεργασία της πληροφορίας.
Να αντιλαμβάνονται την έννοια της υπολογισιμότητας μιας τυπικής γλώσσας.
Να κατανοούν τη συσχέτιση μεταξύ πεπερασμένων αυτομάτων και κανονικών γλωσσών.
Γενικές Ικανότητες:
Οι ικανότητες που πρέπει να αποκτήσει ο πτυχιούχος και στις οποίες αποσκοπεί το μάθημα είναι:
Προαγωγή ελεύθερης, δημιουργικής και επαγωγικής σκέψης.
Αναζήτηση, ανάλυση και σύνθεση δεδομένων, τεχνικών και πληροφοριών, με τη χρήση και των απαραίτητων τεχνικών.
Ανάπτυξη και τεκμηρίωση επιχειρημάτων με αξιοποίηση δομημένης μαθηματικής σκέψης.
Συνδυαστική ανάλυση μεθόδων για επίλυση προβλημάτων.
Ανάπτυξη αλγοριθμικής σκέψης.
Ικανότητα αφαίρεσης στη μοντελοποίηση προβλημάτων του πραγματικού κόσμου.
Περιεχόμενο Μαθήματος:
Ενότητα 1.
• Σύνολα και πράξεις.
• Στοιχεία προτασιακής και κατηγορηματικής λογικής.
• Αρχή εγκλεισμού-αποκλεισμού. Αρχές απόδειξης.
Ενότητα 2.
• Μεταθέσεις και συνδυασμοί.
• Στοιχεία διακριτής πιθανότητας.
Ενότητα 3.
• Σχέσεις και συναρτήσεις. Σχέσεις διάταξης.
• Σχέσεις ισοδυναμίας. Εφαρμογές.
Ενότητα 4.
• Γραφήματα. Ορισμοί, ιδιότητες και βασικά προβλήματα.
• Συνεκτικότητα και συγγενείς έννοιες.
• Βασικοί αλγόριθμοι γράφων και εφαρμογές
• Επίπεδα γραφήματα, τύπος του Euler, θεώρημα Kuratowski.
• Δέντρα. Ορισμοί, ιδιότητες, αλγόριθμοι και εφαρμογές.
Ενότητα 5. Υπολογισιμότητα Γλωσσών και Πεπερασμένα αυτόματα
• Τυπικές γλώσσες και υπολογισιμότητα.
• Αυτόματα Πεπερασμένων Καταστάσεων.
• Κανονικές γλώσσες, κανονικές εκφράσεις και Ντετερμινιστικά Πεπερασμένα Αυτόματα.
