ΠΛΥ210 -- Διακριτά Μαθηματικά

Ακαδημαϊκό Έτος 2011 -- 2012

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

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

Διδάσκων:	Σπύρος Κοντογιάννης
Email -- URL -- Voice:	-- http://www.cs.uoi.gr/~kontog/ -- (26510) 08812
URL Μαθήματος:	http://www.cs.uoi.gr/~kontog/courses/DiscreteMath/
Ώρες Διαλέξεων:	Κάθε Τρίτη 17:00--20:00 και κάθε Πέμπτη 17:00--20:00
Χώρος Διαλέξεων:	Αίθουσα Ι5 (Ισόγειο Κτιρίου)
Ώρες Επικοινωνίας:	Your browser does not support inline frames or is currently configured not to display inline frames.

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

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

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

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

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

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

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

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

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

3/5/2012: Η διάλεξη της Πέμπτης 24 Μαΐου 2012 δε θα γίνει, λόγω απουσίας του διδάσκοντα στο εξωτερικό.
3/4/2012: Στις διαφάνειες της 3ης εβδομάδας έγινε μια μικρή διόρθωση (στη σελίδα 16, γραμμές 3,8,11 της απόδειξης, η τελευταία εμφάνιση του φ θα έπρεπε να είναι ΝΟΤ φ). Παρακαλούνται οι φοιτητές του μαθήματος να λάβουν υπόψη τη συγκεκριμένη διόρθωση, ή να ξανακατεβάσουν τις διαφάνειες της συγκεκριμένης εβδομάδας.
23/3/2012: Η πρώτη ενδιάμεση γραπτή εξέταση (1η πρόοδος) του μαθήματος θα διεξαχθεί την Πέμπτη 5 Απριλίου 2012, 17:00--19:00 στην αίθουσα Ι5. Η συμμετοχή στην πρόοδο είναι προαιρετική. Επιτρέπεται να έχετε μαζί σας ΕΝΑ ΧΕΙΡΟΓΡΑΦΟ φύλλο Α4, όπου θα αναγράφονται ευκρινώς τα στοιχεία σας.
23/3/2012: Έχουν ήδη αναρτηθεί οι διδακτικές σημειώσεις για την Κατηγορηματική Λογική Δείτε σχετικά το ημερολόγιο του μαθήματος.
16/3/2012: Έχουν ήδη αναρτηθεί οι διδακτικές σημειώσεις για την Προτασιακή Λογική και τις Τυπικές Αποδείξεις. Δείτε σχετικά το ημερολόγιο του μαθήματος.
6/3/2012: Τα στοιχεία πρόσβασης στον προστατευμένο χώρο της ιστοθεσίας έχουν αλλάξει και μπορείτε να τα πάρετε από το διδάσκοντα, πριν από κάποια διάλεξη του μαθήματος.

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

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

Διδακτική Εβδομάδα	Ημερομηνίες Διδασκαλίας	Ύλη Εβδομάδας	Συνοδευτικό Υλικό
Διδακτική Εβδομάδα	Ημερομηνίες Διδασκαλίας	Ύλη Εβδομάδας	Διαφάνειες password protected	Σημειώσεις & Αναθέσεις για το σπίτι password protected
1^η	1/3/2012	Εισαγωγή Μαθηματική Λογική -- Σημασιολογική Προσέγγιση	Διαφάνειες 1ης εβδομάδας: Εισαγωγή [για ανάγνωση][για εκτύπωση]
2^η	6-8/3/2012	Μαθηματική Λογική -- Νόμοι ΠΛ -- Εγκυρότητα Επιχειρημάτων	Διαφάνειες 2ης εβδομάδας: Προτασιακή Λογική [για ανάγνωση][για εκτύπωση]	Σημειώσεις Προτασιακή Λογική
3^η	13-15/3/2012	Μαθηματική Λογική -- Τυπικές Αποδείξεις -- Αποδεικτικές Τεχνικές	Διαφάνειες 3ης εβδομάδας [για ανάγνωση][για εκτύπωση]	Σημειώσεις Προτασιακή Λογική
4^η	20-22/3/2012	Κατηγορηματική Λογική -- Πρωτοβάθμιες Γλώσσες -- Ερμηνείες Γλωσσών -- Αποτίμηση τύπων και ορισμός της αλήθειας του Tarski -- Νόμοι της ΚΛ και μετακινήσεις ποσοδεικτών	Διαφάνειες 4ης εβδομάδας [για ανάγνωση][για εκτύπωση]	Σημειώσεις Κατηγορηματική Λογική
5^η	27-29/3/2012	Μαθηματική Επαγωγή & Άλλες Αποδεικτικές Τεχνικές	Διαφάνειες 5ης εβδομάδας [για ανάγνωση][για εκτύπωση]
6^η	3-5/4/2012	Σύνολα και Πράξεις Συνόλων Αρχή Εγκλεισμού Αποκλεισμού ΠΕΜΠΤΗ 5 ΑΠΡΙΛΙΟΥ: Διεξαγωγή 1ης ενδιάμεσης γραπτής εξέτασης -- Ώρα διεξαγωγής: 17:00 - 19:00 -- Χώρος διεξαγωγής: Αίθουσες Ι4 - Ι5 --Ύλη: Ό,τι έχει διδαχθεί μέχρι και την 5η εβδομάδα	Διαφάνειες 6ης εβδομάδας [για ανάγνωση][για εκτύπωση]
7^η	24-26/4/2012	Άλγεβρες Boole Το Παράδοξο του Russell και το Πρόβλημα του Τερματισμού	Διαφάνειες 7ης εβδομάδας [για ανάγνωση][για εκτύπωση]
8^η	3/5/2012	Σχέσεις και Συναρτήσεις Παράδοξο του Russell και το Πρόβλημα του Τερματισμού	Διαφάνειες 8ης +9ης εβδομάδας [για ανάγνωση][για εκτύπωση]
9^η	8-10/5/2012	Σχέσεις Ισοδυναμίας / Διάταξης Ακρότατα και Φράγματα Αριθμησιμότητα Συνόλων
10^η	15-17/5/2012	Συνδυαστική -- Άθροισμα, Γινόμενο, Εγκλεισμός - Αποκλεισμός -- Διατάξεις και Μεταθέσεις	Διαφάνειες 10ης εβδομάδας [για ανάγνωση][για εκτύπωση]
11^η	22-24/5/2012	Συνδυαστική -- Επιλογές Υποσυνόλων Αντικειμένων -- Επιλογές με / χωρίς επανάληψη	Διαφάνειες 11ης εβδομάδας [για ανάγνωση][για εκτύπωση]
12^η	29-31/5/2012	Συνδυαστική -- Διακριτή Πιθανότητα	Διαφάνειες 12ης εβδομάδας [για ανάγνωση][για εκτύπωση]
13^η	5-7/6/2012	Εισαγωγή στα Γραφήματα	Διαφάνειες 13ης εβδομάδας [για ανάγνωση][για εκτύπωση]
----		ΕΞΕΤΑΣΗ ΜΑΘΗΜΑΤΟΣ: -- Ώρα: 09:00 -- 12:00 -- Αίθουσα: Ι5 , Ι1-Ι2-Ι3-Ι4 (στο ισόγειο του κτιρίου) -- Κλειστές Σημειώσεις -- ΧΕΙΡΟΓΡΑΦΟ τυπολόγιο (τρία φύλλα Α4) με το ονοματεπώνυμό σας σε κάθε σελίδα, όπου συμπληρώνετε ό,τι επιθυμείτε.

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

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

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

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

Susanna S. Epp. Διακριτά Μαθηματικά με Εφαρμογές, Εκδόσεις Κλειδάριθμος, 2004.
Kenneth H. Rosen. Discrete Mathematics and its Applications (sixth edition). McGraw Hill, 2008.
Σημειώσεις/διαφάνειες του διδάσκοντος (θα δίνονται περιοδικά από το Ημερολόγιο του μαθήματος).

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

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 (διαθέσιμο και ηλεκτρονικά).
Kenneth H. Rosen. Discrete Mathematics and Its A pplications. McGraw-Hill, Sixth Edition.
Γ. Βουτσαδάκης, Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης. Διακριτά Μαθηματικά: προβλήματα και λύσεις. Gutenberg, 2000 (διατίθεται και ηλεκτρονικά).
Σελίδα του Μαθήματος από προηγούμενα έτη (διδάσκων: Χ. Νομικός).
Λ. Κυρούσης, Χ. Μπούρας, Π. Σπυράκης. Διακριτά Μαθηματικά: Τα Μαθηματικά της Επιστήμης των Υπολογιστών, 1992 (διατίθεται και ηλεκτρονικά).

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

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

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

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

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

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