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

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

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

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

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

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

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

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

Μονάδες ECTS: 6

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

Προσφερόμενο: ΝΑΙ

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

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

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

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

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

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

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

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

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