Μαθηματικά ΙΙI

Γενικά

• Κωδικός Μαθήματος: 1302
• Εξάμηνο: 3ο
• Τύπος Μαθήματος: Γενικής Υποδομής (ΓΥ)
• Είδος Μαθήματος: Υποχρεωτικό (ΥΠ)
• Γνωστική Περιοχή: Γενικών Γνώσεων και Δεξιοτήτων (ΓΓΔ)
• Διδασκαλία Θεωρίας: 4 ώρες/εβδομάδα
• Πιστωτικές μονάδες ECTS: 6
• Ηλεκτρονική σελίδα μαθήματος: https://exams-iee.the.ihu.gr/course/view.php?id=32
• Γλώσσα διδασκαλίας και Εξετάσεων: Ελληνικά
• Συντονιστής: Αντωνίου Ευστάθιος
• Διδάσκοντες: Ασδρέ Κατερίνα

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

Σκοπός το μαθήματος είναι να εξοικειώσει τους φοιτητές του τμήματος με τις θεμελιώδεις έννοιες των Διακριτών Μαθηματικών, όπως η βασική τυπική λογική, οι τεχνικές απαρίθμησης, η θεωρία γραφημάτων και οι εφαρμογές τους στην επιστήμη των υπολογιστών. Ειδικότερα, με την επιτυχή ολοκλήρωση του μαθήματος ο φοιτητής/τρια θα είναι σε θέση να:

• Γνωρίζει τις βασικές έννοιες της απλοϊκής θεωρίας συνόλων και να εφαρμόζει πράξεις με αυτά. Κατανοεί την έννοια του πληθαρίθμου ενός συνόλου και να διακρίνει και περιγράφει αριθμήσιμα και μη αριθμήσιμα, πεπερασμένα και άπειρα, σύνολα. Εφαρμόζει την (γενικευμένη) αρχή του Περιστερώνα για την επίλυση πρακτικών προβλημάτων. Γνωρίζει την έννοια της διμελούς σχέσης και μπορεί να αναγνωρίζει σχέσεις διατάξεων ή ισοδυναμίας. Εφαρμόζει τα τις παραπάνω έννοιες σε πραγματικά προβλήματα.
• Κατανοεί το συντακτικό της γλώσσας της προτασιακής λογικής και είναι σε θέση να συνθέσει προτασιακούς τύπους που κωδικοποιούν δηλώσεις της φυσικής γλώσσας. Εξάγει λογικά συμπεράσματα χρησιμοποιώντας σημασιολογικά εργαλεία της προτασιακής λογικής. Διακρίνει προτασιακούς τύπους που είναι ταυτολογίες ή αντιφάσεις.
• Γνωρίζει την αποδεικτική μεθοδολογία της μαθηματικής επαγωγής και μπορεί να την αξιοποιήσει για να αποδείξει την ορθότητα ισχυρισμών που εξαρτώνται από ένα φυσικό αριθμό.
• Γνωρίζει τις βασικές αρχές και τα μοντέλα της συνδυαστικής ανάλυσης και μπορεί να υπολογίσει το πλήθος των ενδεχομένων σε μια μεγάλη γκάμα συνδυαστικών προβλημάτων, διακρίνοντας το συνδυαστικό μοντέλο που πρέπει να χρησιμοποιηθεί κατά περίπτωση. Επιπλέον, είναι σε θέση να συνθέσει τα γνωστά συνδυαστικά μοντέλα για την επίλυση περισσότερο σύνθετων προβλημάτων.
• Κατανοεί την σχέση μεταξύ ακολουθιών και γεννητριών συναρτήσεων και μπορεί να διακρίνει τα δύο είδη γεννητριών συναρτήσεων. Είναι σε θέση να συνθέτει κατάλληλες γεννήτριες συναρτήσεις για την επίλυση συγκεκριμένων συνδυαστικών προβλημάτων και να υπολογίζει τους ζητούμενους συντελεστές. Αναγνωρίζει τη μορφή μιας αναδρομικής σχέσης και στην περίπτωση που αυτό είναι δυνατό μπορεί να υπολογίσει τη λύση της με τη βοήθεια γεννητριών συναρτήσεων.
• Γνωρίζει την ορολογία και τις βασικές έννοιες της θεωρίας γραφημάτων και ειδικότερα των δέντρων, ενώ μπορεί να εκτιμήσει και να αναγνωρίσει το ρόλο των γραφημάτων ως μοντέλο για μια μεγάλη ποικιλία προβλημάτων της πληροφορικής. Διακρίνει την παρουσία ή μη συγκεκριμένων χαρακτηριστικών σε δεδομένα γραφήματα, όπως οι κύκλοι Euler ή Hamilton και η δυνατότητα διχοτόμησης. Εφαρμόζει αλγορίθμους (Dijkstra, BFS, DFS, Prim, Kruskal) και κατανοεί την εφαρμογή τους σε πρακτικά προβλήματα. Γνωρίζει την έννοια του δέντρου, του δέντρο με ρίζα και του δυαδικού δέντρου και είναι σε θέση να εφαρμόσει αλγορίθμους προ-, ενδο- και μετα-διατεταγένης διάσχισης στα δυσδικά δέντρα.

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

• Εργασία σε διεπιστημονικό περιβάλλον
• Παράγωγή νέων ερευνητικών ιδεών
• Προαγωγή της ελεύθερης, δημιουργικής και επαγωγικής σκέψης

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

Στοιχεία Θεωρίας Συνόλων: Εισαγωγή, Ορισμός συνόλου, Πράξεις στα σύνολα, Δυναμοσύνολα, Αριθμήσιμα – Μη αριθμήσιμα σύνολα, Πληθάριθμοι, Αρχή του Περιστερώνα

Σχέσεις και συναρτήσεις: Σχέσεις Ισοδυναμίας, Σχέσεις Μερικής Διάταξης.

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

Μαθηματική επαγωγή: Βασική και Ισχυρή μορφή της Μαθηματικής Επαγωγής.

Συνδυαστική Ανάλυση: Κανόνες Γινομένου – Αθροίσματος, Διατάξεις, Συνδυασμοί, Μοντέλα Τοποθέτησης σφαιριδίων σε υποδοχές.

Γεννήτριες συναρτήσεις: Συνήθεις γεννήτριες συναρτήσεων, Ιδιότητες, Εκθετικές γεννήτριες συναρτήσεων, εφαρμογές στην επίλυση συνδυαστικών προβλημάτων.

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

Στοιχεία Θεωρίας γραφημάτων: Ορισμοί, Μη κατευθυνόμενο και κατευθυνόμενο γράφημα, Βαθμός κορυφής, Δρόμοι, Συνεκτικά γραφήματα, Υπογραφήματα, Ειδικά γραφήματα, Ισομορφικά γραφήματα, κύκλοι Euler και Hamilton, Γραφήματα και πίνακες, Ελάχιστη Διαδρομή και αλγόριθμος του Dijkstra, Δένδρα, Δένδρα με βάρος, Ελάχιστο Συνδετικό Δένδρο, Δένδρα με Ρίζα, Δυαδικά δένδρα.

Διδακτικές και Μαθησιακές Μέθοδοι - Αξιολόγηση

Τρόπος Παράδοσης

• Πρόσωπο με πρόσωπο θεωρητική διδασκαλία

Χρήση Τεχνολογιών Πληροφορίας και Επικοινωνιών

• Διάθεση διδακτικών σημειώσεων του μαθήματος σε ηλεκτρονική μορφή.
• Υποστήριξη της μαθησιακής διαδικασίας μέσω της ηλεκτρονικής πλατφόρμας Moodle.

Οργάνωση Διδασκαλίας

Αξιολόγηση φοιτητών

Η γραπτή τελική εξέταση του μαθήματος που περιλαμβάνει 7-8 κύρια ερωτήματα ανάπτυξης, που εμπλέκουν τα παρακάτω ζητούμενα:

Προτασιακή Λογική
Διμελείς σχέσεις και ιδιότητες
Αρχή του Περιστερώνα
Μαθηματική Επαγωγή
Στοιχειώδης Συνδυαστική
Αναδρομικές Σχέσεις
Γεννήτριες Συναρτήσεις
Γραφήματα και Δέντρα

Το ως άνω σχήμα αξιολόγησης στο θεωρητικό και στο εργαστηριακό μέρος του μαθήματος γνωστοποιείται στους ενδιαφερόμενους φοιτητές

(α) μέσω της ιστοσελίδας του τμήματος,
(β) μέσω των σελίδων του μαθήματος στην ηλεκτρονική πλατφόρμα Moodle, και
(γ) με ανακοινώσεις στη διάρκεια των πρώτων διαλέξεων και συναντήσεων στο εργαστήριο κατά την έναρξη του κάθε ενός ακαδημαϊκού εξαμήνου.

Συνιστώμενη Βιβλιογραφία

Συγγράμματα μέσω του συστήματος "Εύδοξος"

1. EPP, SUSANNA S., Διακριτά Μαθηματικά με Εφαρμογές, 3η έκδοση, Εκδόσεις Κλειδάριθμος, 2010, ISBN 978-960-461-325-0, [Κωδ. Ευδόξου 13953].
2. Κατωπόδης Κωνσταντίνος Σπ., Εισαγωγή στα διακριτά μαθηματικά, Εκδότης: Ζήτη Πελαγία & Σια Ι.Κ.Ε., 1η έκδ., 2015, ISBN: 978-960-456-446-0, [Κωδ. Ευδόξου 50658666].

Συμπληρωματική ελληνόγλωσση βιβλιογραφία

1. LIU C., Στοιχεία Διακριτών Μαθηματικών, Πανεπιστημιακές Εκδόσεις Κρήτης, 2009, ISBN 978-960-524-072-1
2. ROSEN K., Διακριτά μαθηματικά και εφαρμογές τους, 7η έκδοση, Εκδόσεις Τζιόλα & Υιοι Α.Ε., 2014, ISBN: 978-960-418-394-4.
3. Κυρούσης Λ.Μ., Μπούρας Χ.Ι., Σπυράκης Π.Γ., Διακριτά μαθηματικά. Τα μαθηματικά της επιστήμης των υπολογιστών, Gutenberg, 1994, ISBN 978-960-01-0661-4.
4. Αγγελής Ε.Σ.,Μπλέρης Γ.Λ., Διακριτά μαθηματικά, Εκδόσεις Τζιόλα, 2003, ISBN 960-418-009-6.

Συμπληρωματική ξενόγλωσση βιβλιογραφία

1. EPP, SUSANNA S.: Discrete Mathematics with Applications, Wadsworth, 1990, ISBN 0495391328
2. GRAHAM, R., KNUTH, D., PATASHNIK, O.: Concrete Mathematics, Addison Wesley, 1994.
3. ROSEN K.H., Discrete mathematics and its applications. New York: McGraw-Hill, 2012.
4. GRIMALDI, R.: Discrete and Combinatorial Mathematics. An Applied Introduction, Addison Wesley, 1994.
5. HALL, M., Jr.: Combinatorial Theory, John Wiley & Sons, 1986.
6. HARARY, F.: Graph Theory, John Wiley & Sons, 1986.
7. LIPSCHUTZ, S.: Set Theory, McGraw Hill, 1964.
8. LIU, C.: Introduction to Combinatorial Mathematics, McGraw Hill, 1968.
9. LIU, C.: Elements of Discrete Mathematics, McGraw Hill, 1986.
10. REINGOLD, M., NIERERGELT, J., DEO, N.: Combinatorial Algorithms Theory and Practice, Prentice Hall, 1977.
11. ROSS, K. A., WRIGTH, C. R. B. : Discrete Mathematics, Prentice Hall, 1992.
12. TOMESCU, I. And MELTER, R.: Problems in Combinatorial and Graph Theory, John Wiley & Sons, 1985.
13. WITALA, S, A.: Discrete Mathematics. A Unified Approach, McGraw Hill, 1987.