Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής

Πολυτεχνική Σχολή - Πανεπιστήμιο Ιωαννίνων

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

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

Κωδικός μαθήματος: ΜΥΥ302

Εβδομαδιαίες ώρες διδασκαλίας: 4,1,0

Εξάμηνο σπουδών: 3ο

Διδακτικές Μονάδες: 5

Μονάδες ECTS: 6

Ιστοσελίδα Μαθήματος: https://www.cs.uoi.gr/~cnomikos/courses/dm-ii/dm-ii-main.htm

Προσφερόμενο: Ακαδημαϊκό έτος 2023-2024

Προαπαιτούμενα:

Περιεχόμενο:

Πρωτοβάθμια κατηγορηματική λογική: Σημασιολογία της κατηγορηματικής λογικής. Χειρισμός ποσοδεικτών. Έλεγχος εγκυρότητας τύπων μέσω αλήθειας του Tarski.

Αναδρομικές σχέσεις και αναδρομικά ορισμένες διακριτές δομές: Διακριτές αριθμητικές συναρτήσεις (ακολουθίες). Εισαγωγή στα Αθροίσματα. Μέθοδοι Υπολογισμού Αθροισμάτων. Αναδρομές. Ομογενείς / μη ομογενείς γραμμικές αναδρομικές εξισώσεις. Μέθοδος της χαρακτηριστικής εξίσωσης. Αλγόριθμοι «Διαίρει & Βασίλευε» και αναδρομικές σχέσεις. Ανάλυση πολυπλοκότητας με χρήση του Κύριου Θεωρήματος (Master Theorem).

Γεννήτριες συναρτήσεις: Συνήθεις και εκθετικές γεννήτριες ακολουθιών. Γενικευμένο διωνυμικό θεώρημα. Χρήση γεννητριών ως εργαλεία μέτρησης και για επίλυση αναδρομικών σχέσεων. Απόδειξη ταυτοτήτων μέσω γεννητριών.

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

Θεωρία γραφημάτων: Βαθμός, υπογράφημα, Λήμμα Χειραψίας, είδη γραφημάτων, μορφισμοί. Αναπαράσταση γραφημάτων. Σύνολα κοπής και διαχωριστές, συνδεσιμότητα ως προς ακμές ή/και κορυφές, τεμάχια γραφημάτων, θεώρημα του Menger. Δένδρα, χαρακτηρισμοί & ιδιότητες, απαρίθμηση, ειδικές κατηγορίες (Μ-δικά δένδρα), διατάξεις. Κατά Πλάτος/Βάθος Διάσχιση γραφήματος, συνδετικά δένδρα ελάχιστου κόστους. Μήκη και αποστάσεις σε γραφήματα, μονοπάτια ελάχιστου μήκους, ανίχνευση κύκλων αρνητικού μήκους. Κυκλώματα και ίχνη Euler. Κύκλοι και μονοπάτια Hamilton. Επιπεδότητα, τύπος του Euler, θεώρημα Kuratowski.

Πεπερασμένα αυτόματα: Αναγνώριση γλώσσας από αυτόματο, απλοποίηση αυτομάτου, αιτιοκρατικά / μη αιτιοκρατικά πεπερασμένα αυτόματα και η ισοδυναμία τους.

Παρατηρήσεις:

Παλιά Ιστοσελίδα Μαθήματος – http://www.cse.uoi.gr/~kontog/courses/Discrete-Math-2/