CSE.UOI / ΜΥΥ204 : Διακριτά Μαθηματικά Ι

Ακαδημαϊκό Έτος 2018 -- 2019

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

Γενικές Πληροφορίες

Διδάσκων:	Σπύρος Κοντογιάννης, γραφείο Γ3 στον τρίτο όροφο του κτιρίου Πληροφορικής
Email -- URL -- Voice:	-- http://www.cse.uoi.gr/~kontog/ -- (26510) 08812
URL Μαθήματος:	http://www.cse.uoi.gr/~kontog/courses/Discrete-Math-1/
Ώρες Διαλέξεων:	Κάθε Τετάρτη (17:00--20:00) και κάθε Παρασκευή (09:00--12:00)
Χώρος Διαλέξεων:	ΑΜΦΙΘΕΑΤΡΟ ΜΗΥΠ (κάθε Τετάρτη και Παρασκευή)
Επικουρικό Έργο:	Ιωάννης Γεωργιάδης, γραφείο Γ16 στον τρίτο όροφο του κτιρίου της Πληροφορικής -- (igeorgiadis@cse.uoi.gr)
Ώρες Επικοινωνίας:	Your browser does not support inline frames or is currently configured not to display inline frames.

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

Τα Διακριτά Μαθηματικά Ι αφορούν τη μελέτη διεργασιών που απαρτίζονται από ΞΕΧΩΡΙΣΤΑ (διακεκριμένα, ή διακριτά) βήματα. Θα εξετάσουμε βασικές τεχνικές που χρησιμοποιούμε για τη μελέτη και απαρίθμηση συλλογών από διακριτές οντότητες (πχ, το σύνολο των ακεραίων, το σύνολο των τοποθετήσεων αντικειμένων σε υποδοχές, το σύνολο των αποτελεσμάτων της ρίψης δυο όμοιων ζαριών,...). Στην Επιστήμη των Υπολογιστών τα διακριτά αντικείμενα αναπαριστώνται πολύ πιο εύκολα, και συνήθως οι αλγόριθμοι που κατασκευάζουμε αφορούν τη διαχείριση διακριτών οντοτήτων (δομών δεδομένων, ακεραίων αριθμών, αριθμών πεπερασμένης ακρίβειας, κ.λπ). Για το λόγο αυτό το μάθημα των Διακριτών Μαθηματικών αποτελεί τη βάση για όλα σχεδόν τα μαθήματα θεωρητικής κατεύθυνσης του Τμήματος, με εφαρμογές που αρχίζουν από την Σχεδίαση και Ανάλυση Αλγορίθμων, μέχρι τις Βάσεις Δεδομένων, τα Γραφικά, την Κρυπτογραφία, κ.λπ.

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

Αξιολόγηση του Μαθήματος

Θα υπάρξει ΜΙΑ γραπτή πρόοδος, η οποία θα είναι ατομική, και θα διεξάγεται σε προγραμματισμένες ημερομηνίες, στις αίθουσες όπου δίνονται και οι διαλέξεις του μαθήματος. Η πρόοδος είναι προαιρετική, και ο μέσος βαθμός τους θα προσμετράται ως 20% μπόνους στον τελικό βαθμό του μαθήματος, με την προϋπόθεση ότι ο βαθμός τελικής γραπτής εξέτασης είναι ΤΟΥΛΑΧΙΣΤΟΝ 3,5. Δηλαδή, αν
- ΒΓΕ = βαθμός γραπτής εξέτασης
- ΒΠ = βαθμός ενδιάμεσης προόδου
- η συνάρτηση δ επιστρέφει 1 αν επαληθεύεται η συνθήκη που δέχεται ως όρισμα, διαφορετικά επιστρέφει 0,
τότε ο τελικός βαθμός του μαθήματος υπολογίζεται ως εξής:

ΤΕΛΙΚΟΣ ΒΑΘΜΟΣ = ΒΓΕ + 0.2 * ΒΠ * δ(ΒΓΕ >= 3.5)

Σε περίπτωση αποτυχίας στην τελική εξέταση, ο ΙΔΙΟΣ κανόνας θα ισχύσει και για την επαναληπτική εξέταση του Σεπτεμβρίου. Οι βαθμοί της προόδου ΔΕ ΜΕΤΑΦΕΡΟΝΤΑΙ για το επόμενο έτος, σε περίπτωση αποτυχίας.

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

Ανακοινώσεις

11/07/2019: Στον ΚΡΟΝΟ είναι ήδη αναρτημένη η βαθμολογία της εξέτασης Ιουνίου 2019. Στο Χρήσιμο Υλικό του μαθήματος έχουν επίσης αναρτηθεί οι ενδεικτικές λύσεις της εξέτασης (στο ίδιο αρχείο και για τις δυο ομάδες). Οι φοιτητές που επιθυμούν να δούνε το γραπτό τους, μπορούν να προσέλθουν στο γραφείο του διδάσκοντα την Παρασκευή 12/07/2019, ή διαφορετικά από τον Σεπτέμβριο.
11/05/2019: Στο Ημερολόγιο του Μαθήματος αναρτήθηκαν οι διαφάνειες της Συνδυαστικής, καθώς επίσης και μια μικρή συλλογή από λυμένες ασκήσεις, τις οποίες μπορείτε να χρησιμοποιήσετε για δική σας εξάσκηση (δοκιμάστε να τις λύσετε μόνοι σας, κι ανατρέξτε στις απαντήσεις μόνο όταν θα έχετε προσπαθήσει αρκετά αλλά δε θα τα έχετε καταφέρει).
09/04/2019: Η ύλη της προγραμματισμένης ενδιάμεσης προόδου για το μάθημα (την Τετάρτη 17 Απριλίου 2019) περιγράφεται σε αυτό το αρχείο. Περιλαμβάνει όλες τις διαφάνειες και σημειώσεις του μαθήματος, μέχρι και την 8η διδακτική εβδομάδα, και τις αντίστοιχες ενότητες από το διδακτικό σύγγραμμα που έχετε επιλέξει. Για τον ROSEN, δείτε και τις ενότητες που περιλαμβάνονται στην ύλη (περίπου 340 σελίδες συνολικά). Με κίτρινο χρώμα υπογραμμίζονται οι ενότητες που περιλαμβάνονται στην ύλη της προόδου. Με πράσινο χρώμα υπογραμμίζονται οι επιπλέον ενότητες που περιλαμβάνονται στην τελική εξέταση του μαθήματος (πέραν αυτών της προόδου).
27/03/2019: Οι δυο διαλέξεις της Τετάρτης 15/5/2019 και της Παρασκευή 17/5/2019 αναβάλλονται, λόγω προγραμματισμένης απουσίας του διδάσκοντα. Η αναπλήρωση των συγκεκριμένων ωρών διδασκαλίας έχει ήδη προβλεφθεί από τις αρχές του εξαμήνου να γίνει με την επέκταση των διαλέξεων της Παρασκευής κατά μια ώρα (09:00-12:00, αρχής γενομένης από την Παρασκευή 15/03/2019).
14/03/2019: Η διάλεξη του μαθήματος την Παρασκευή 22/03/2019 αναβάλλεται, λόγω προγραμματισμένης επαγγελματικής υποχρέωσης του διδάσκοντα.
13/03/2019: Οι διαλέξεις της Παρασκευής από δίωρες γίνονται πλέον τρίωρες (09:00-12:00). Η συγκεκριμένη αλλαγή θα ξεκινήσει από την Παρασκευή 15/03/2019 και θα ισχύει για το υπόλοιπο του εξαμήνου.
27/02/2019: Στο Χρήσιμο Υλικό του μαθήματος μπορείτε να βρείτε μια καινούρια ενότητα όπου θα αναρτώνται οι ενδεικτικές λύσεις των φροντιστηριακών ασκήσεων που παρουσιάζονται στο μάθημα από τον μεταπτυχιακό φοιτητή Γεωργιάδη Ιωάννη ο οποίος επικουρεί το μάθημα.
15/02/2019: Η προαιρετική ενδιάμεση προόδος του μαθήματος έχει ήδη οριστεί για την Τετάρτη 10/04/2019 και ώρα 17:00-19:00 (στο Αμφιθέατρο και στις αίθουσες Ι1-5 του Κτιρίου της Πληροφορικής).
14/02/2019: Όλες οι διαλέξεις του μαθήματος στο εξής θα γίνονται στο Αμφιθέατρο της Πληροφορικής.
13/02/2019: Οι διαλέξεις του μαθήματος ξεκινούν κανονικά από σήμερα, Τετάρτη 13/2/2019, στην αίθουσα Ι5 του Κτιρίου Πληροφορικής.

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

Ημερολόγιο Μαθήματος

Διδακτική Εβδομάδα	Ημερομηνίες Διδασκαλίας	Ύλη Εβδομάδας	Συνοδευτικό Υλικό
Διδακτική Εβδομάδα	Ημερομηνίες Διδασκαλίας	Ύλη Εβδομάδας	Διαφάνειες password protected	Σημειώσεις & Αναθέσεις για το σπίτι password protected
1^η	13-15/02	Εισαγωγικά Προτασιακή Λογική -- Εκφράσεις, Τύποι, Δενδροδιαγράμματα, Αποτιμήσεις, Πίνακες Αλήθειας -- Ικανοποιησιμότητα, Ταυτολογίες, Αντιφάσεις, Ταυτολογική Συνεπαγωγή & Ισοδυναμία	Εισαγωγικά [εκτύπωση \| ανάγνωση]
2^η	20-22/02	Προτασιακή Λογική -- Νόμοι της Προτασιακής Λογικής -- Κανονική Διαζευκτική Μορφή -- Πληρότητα Συνόλων Συνδέσμων	Διαφάνειες Προτασιακής Λογικής [εκτύπωση \| ανάγνωση]	Σημειώσεις Προτασιακής Λογικής [προβολή] Συλλογή ασκήσεων για εξάσκηση στην Προτασιακή Λογική [προβολή]
3^η	27-28/02	Αποδεικτικές Τεχνικές -- Συντακτική Προσέγγιση ΠΛ: Αξιωματικά Συστήματα, Τυπικές αποδείξεις -- Μεταθεωρήματα Απαγωγής, Αντιθετοαναστροφής, Απαγωγής σε Άτοπο -- Εγκυρότητα-Πληρότητα, Συμπάγεια.	Διαφάνειες Αποδεικτικών Τεχνικών [εκτύπωση \| ανάγνωση]
4^η	06/03	Ασθενής Μαθηματική Επαγωγή -- Ασθενής Μαθηματική Επαγωγή -- Παραδείγματα Χρήσης για Απόδειξη Αριθμητικών Ιδιοτήτων -- Παραδείγματα Χρήσης για Απόδειξη Γεωμετρικών Ιδιοτήτων -- Παραδείγματα Χρήσης για Ανάλυση Αλγορίθμων Ισχυρή Μαθηματική Επαγωγή -- Η Σημασία της Ισχυρής Επαγωγικής Υπόθεσης -- Παραδείγματα Χρήσης	Διαφάνειες Μαθηματικής Επαγωγής [εκτύπωση \| ανάγνωση]
5^η	13-15/03	Εισαγωγή Στη Θεωρία Συνόλων -- Σύνολα, Υποσύνολα -- Πράξεις Συνόλων -- Ταυτότητες Πράξεων σε Σύνολα -- Ιδιότητες Πληθαρίθμων -- Αρχή Εγκλεισμού-Αποκλεισμού	Διαφάνειες Θεωρίας Συνόλων [εκτύπωση \| ανάγνωση]
6^η	20/03	Παράδοξα Θεωρίας Συνόλων -- Παράδοξο του Russell -- Αδυναμία Ελέγχου Τερματισμού Προγραμμάτων	Διαφάνειες Άλγεβρες Boole Παράδοξα Θεωρίας Συνόλων [εκτύπωση \| ανάγνωση]
7^η	27-29/03	Σχέσεις & Συνάρτήσεις -- Ιδιότητες Σχέσεων -- Σχέσεις Ισοδυναμίας και Διατάξεις -- Πράξεις Σχέσεων -- Αρχή Περιστερώνα -- Ακρότατα και Φράγματα	Διαφάνειες Σχέσεις & Συναρτήσεις [εκτύπωση \| ανάγνωση]
8^η	03-05/04	Πληθικότητα Συνόλων -- Άπειρα και Πεπερασμένα Σύνολα -- Αριθμησιμότητα / Μη Αριθμησιμότητα Συνόλων	Διαφάνειες Αριθμησιμότητα Συνόλων [εκτύπωση \| ανάγνωση]
9^η	12/04	Συνδυαστική -- Κανόνες Αθροίσματος & Γινομένου -- Μεταθέσεις και Διατάξεις -- Διατάξεις Ομάδων Αντικειμένων
10^η	17-19/04	[17/04/2019, 17:00-19:00] ΔΙΕΞΑΓΩΓΗ ΕΝΔΙΑΜΕΣΗΣ ΠΡΟΟΔΟΥ ΠΡΟΟΔΟΥ (Ι5, ΑΜΦ-ΗΥ, ΑΜΦ-ΧΗΜ)Συνδυαστική -- Ρίψη Σφαιριδίων σε Υποδοχές -- Επιλογές με/χωρίς Επανάληψη	Διαφάνειες Συνδυαστικής [εκτύπωση \| ανάγνωση]	Επαναληπτικές Ασκήσεις Συνδυαστικής [προβολή]
11^η	08-10/5	Συνδυαστική -- Επιλογές με/χωρίς Επανάληψη -- Διωνυμικοί Συντελεστές & Τύπος του Pascal -- Διωνυμικό Θεώρημα
12^η	15-17/05	ΑΝΑΒΟΛΗ ΔΙΑΛΕΞΕΩΝ ΛΟΓΩ ΠΡΟΓΡΑΜΜΑΤΙΣΜΕΝΗΣ ΑΠΟΥΣΙΑΣ ΤΟΥ ΔΙΔΑΣΚΟΝΤΑ. Η ΑΝΑΠΛΗΡΩΣΗ ΤΩΝ ΔΙΑΛΕΞΕΩΝ ΕΧΕΙ ΗΔΗ ΠΡΟΒΛΕΦΘΕΙ (ΜΙΑ ΕΠΙΠΛΕΟΝ ΩΡΑ ΔΙΔΑΣΚΑΛΙΑΣ ΚΑΘΕ ΠΑΡΑΣΚΕΥΗ) ΚΑΙ ΥΛΟΠΟΙΕΙΤΑΙ ΑΠΟ ΤΙΣ 15/03/2019 ΜΕΧΡΙ ΤΟ ΤΕΛΟΣ ΤΟΥ ΕΞΑΜΗΝΟΥ.
13^η	22-24/05	Διακριτή Πιθανότητα -- Διακριτή Συνάρτηση Πιθανότητας -- Δείγματα και Γεγονότα -- Αναμενόμενη Τιμή Πειράματος με Αριθμητικές Τιμές -- Παράδοξο των Γενεθλίων	Διαφάνειες Διακριτής Πιθανότητας [εκτύπωση \| ανάγνωση]
14^η	29-31/05	Διακριτή Πιθανότητα -- Μέθοδος Monte Carlo -- Πιθανοτική Μέθοδος -- Δεσμευμένη Πιθανότητα -- Θεώρημα του Bayes	Διαφάνειες Διακριτής Πιθανότητας [εκτύπωση \| ανάγνωση]
----		ΕΞΕΤΑΣΗ ΜΑΘΗΜΑΤΟΣ: -- Ώρα: -- Αίθουσα: Ι5, ΑΜΦ-ΜΗΥΠ, ΑΜΦ-ΧΗΜ -- Κανονισμός εξέτασης: Οι διδακτικές σημειώσεις και τα βιβλία θα είναι κλειστά. Απαγορεύεται η χρήση όλων των ηλεκτρονικών συσκευών (π.χ., κινητά), για οποιονδήποτε λόγο. Οποιασδήποτε μορφής χρήση τους επιφέρει μηδενισμό του γραπτού. Επιτρέπεται μόνο η χρήση αριθμομηχανής, εφόσον αυτό κρίνεται απαραίτητο. Θα διατεθεί από τον διδάσκοντα τυπολόγιο, κατά την έναρξη της εξέτασης, μαζί με τα θέματα.

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

Χρήσιμο Υλικό

Βιβλιογραφία Μαθήματος

Τα βασικά εγχειρίδια του μαθήματος είναι:

[ROSEN] Kenneth H. Rosen. Διακριτά Μαθηματικά και Εφαρμογές τους (έβδομη έκδοση), Εκδόσεις Τζιόλα , 2014.
[EPP] Susanna S. Epp. Διακριτά Μαθηματικά με Εφαρμογές, Εκδόσεις Κλειδάριθμος, 2004.
[GKP] Ronald Graham, Donald Knuth, Oren Patashnik. Συνκριτά Μαθηματικά (δεύτερη έκδοση), Εκδόσεις Κλειδάριθμος, 2011.
[CLRS] Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Εισαγωγή στους Αλγορίθμους (δεύτερη έκδοση), Πανεπιστημιακές Εκδόσεις Κρήτης, 2012.
Σημειώσεις/διαφάνειες του διδάσκοντος (θα δίνονται περιοδικά από το Ημερολόγιο του μαθήματος).

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

C. L. Liu. Στοιχεία Διακριτών Μαθηματικών, Πανεπιστημιακές Εκδόσεις Κρήτης, 2003.
C. L. Liu : Introduction to Combinatorial Mathematics. McGraw-Hill.
L. Lovasz, K. Vesztergombi. Discrete Mathematics. Lecture Notes, Yale University, Spring 1999 (διαθέσιμο και ηλεκτρονικά).
Γ. Βουτσαδάκης, Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης. Διακριτά Μαθηματικά: προβλήματα και λύσεις. Gutenberg, 2000 (διατίθεται και ηλεκτρονικά).

Ενδεικτικές λύσεις ασκήσεων φροντιστηρίου (προετοιμασία και παρουσίαση: Ιωάννης Γεωργιάδης):

27/2/2019: Ασκήσεις Προτασιακής Λογικής.

Ενδεικτικές Λύσεις Αναθέσεων Εργασιών για το Σπίτι (για αναφορά πιθανών λαθών παρακαλείστε να επικοινωνήσετε με τον διδάσκοντα):

2008: 1η ανάθεση -- 2η ανάθεση -- 3η ανάθεση -- 4η ανάθεση.
2009: 1η ανάθεση -- 2η ανάθεση -- 3η ανάθεση.
2010: 1η ανάθεση -- 2η ανάθεση -- 3η ανάθεση.

Ενδεικτικές Λύσεις Προόδων / Εξετάσεων (για αναφορά πιθανών λαθών παρακαλείστε να επικοινωνήσετε με τον διδάσκοντα):

2011: 1η πρόοδος (ομάδα Α -- ομάδα Β) | 2η πρόοδος (ομάδα Α -- ομάδα Β) | 3η πρόοδος (ομάδα Α -- ομάδα Β) | 4η πρόοδος (ομάδα Α -- ομάδα Β) | Εξέταση Ιουνίου 2011 (ομάδα Α -- ομάδα Β) | Εξέταση Σεπτεμβρίου 2011 (ομάδα Α -- ομάδα Β)
2012: 1η πρόοδος (ομάδα Α -- ομάδα Β) | 2η πρόοδος (ομάδα Α -- ομάδα Β) | Εξέταση Ιουνίου 2012 (ομάδα Α -- ομάδα Β) | Εξέταση Σεπτεμβρίου 2012 (ομάδα Α -- ομάδα Β)
2013: 1η πρόοδος (ομάδα Α -- ομάδα Β) | 2η πρόοδος (ομάδα Α -- ομάδα Β) | Εξέταση Ιουνίου 2012 (ομάδα Α -- ομάδα Β) | Εξέταση Σεπτεμβρίου 2012 (ομάδα Α -- ομάδα Β)
2015: 1η πρόοδος (ομάδα Α -- ομάδα Β) | 2η πρόοδος (ομάδα Α -- ομάδα Β) | Εξέταση Ιουνίου 2015 (ομάδα Α -- ομάδα Β) | Εξέταση Σεπτεμβρίου 2015 (ομάδα Α -- ομάδα Β)
2018: Ενδιάμεση πρόοδος (ομάδα Α+Β) | Εξέταση Ιουνίου 2018 (ομάδα Α+Β) | Εξέταση Σεπτεμβρίου 2018 (ομάδα Α+Β)
2019: Εξέταση Ιουνίου 2018 (ομάδα Α+Β) | Εξέταση Σεπτεμβρίου 2018 (ομάδα Α+Β)

[Γενικές Πληροφορίες][Περιγραφή][Ανακοινώσεις][Ημερολόγιο][Χρήσιμο Υλικό]

Δημιουργία και συντήρηση σελίδας μαθήματος: Σπύρος Κοντογιάννης. Ημερομηνία τελευταίας αλλαγής: 12/07/2019.