Τμημα Πληροφορικης Πανεπιστημιου Ιωαννινων

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

Ακαδημαϊκό Έτος 2016 -- 2017

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

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

Διδάσκων: Σπύρος Κοντογιάννης
Email -- URL -- Voice:   --  http://www.cse.uoi.gr/~kontog/  --  (26510) 08812
URL Μαθήματος: http://www.cse.uoi.gr/~kontog/courses/Discrete-Math-2/
Ώρες Διαλέξεων: Κάθε Τετάρτη 16:00--18:00 (προσοχή!) και κάθε Πέμπτη 13:00--16:00
Χώρος Διαλέξεων: ΑΜΦΙΘΕΑΤΡΟ
Ώρες Επικοινωνίας:

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

Περιγραφή

Ο κλάδος των Διακριτών Μαθηματικών αφορά τη μελέτη μαθηματικών δομών που από τη φύση τους είναι διακεκριμένες (διακριτές) παρά συνεχείς. Σε αντίθεση π.χ. με τους πραγματικούς αριθμούς, που ποικίλουν με "ομοιόμορφο" τρόπο μεταξύ τους, τα αντικείμενα που μελετώνται, όπως οι ακέραιοι αριθμοί, τα γραφήματα, οι προτάσεις της Μαθηματικής Λογικής, κ.λπ., έχουν διαφορετικές, καλά διαχωρισμένες τιμές. Τα διακεκριμένα αντικείμενα πολλές φορές μπορούν να απαριθμηθούν μέσω της αντιστοίχισής τους σε φυσικούς αριθμούς. Πιο αυστηρά, τα Διακριτά Μαθηματικά είναι ο κλάδος των Μαθηματικών που αφορά τη μελέτη πεπερασμένων συνόλων και αριθμήσιμα άπειρων  συνόλων (που έχουν δηλαδή την ίδια πληθικότητα με το σύνολο των φυσικών αριθμών, όπως π.χ. το σύνολο των ρητών αριθμών, αλλά όχι το σύνολο των πραγματικών αριθμών).

Η έρευνα στα Διακριτά Μαθηματικά έχει αυξηθεί σημαντικά από τα μισά του 20ού αιώνα, εν μέρει και λόγω της εμφάνισης των ηλεκτρονικών υπολογιστών, οι οποίοι από τη φύση τους εκτελούν διακεκριμένα βήματα (εντολές) και διαχειρίζονται πληροφορία που είναι αποθηκευμένη σε ψηφιακή μορφή. Έννοιες και συμβολισμοί των Διακριτών Μαθηματικών είναι ιδιαίτερα χρήσιμοι για τη μελέτη και αυστηρή περιγραφή αντικειμένων και προβλημάτων που συναντάμε σε διάφορους κλάδους της Πληροφορικής, όπως η Σχεδίαση και Ανάλυση Αλγορίθμων και Δομών Δεδομένων, οι Γλώσσες Προγραμματισμού, η Κρυπτογραφία, η Άνάπτυξη Λογισμικού, οι Βάσεις Δεδομένων, τα Δίκτυα, κ.λπ. Παρά το γεγονός ότι βασικό αντικείμενο είναι η μελέτη διακριτών δομών, αναλυτικές μέθοδοι των Μαθηματικών, όπως π.χ. οι γεννήτριες συναρτήσεις, χρησιμοποιούνται επίσης ως εργαλεία των Διακριτών Μαθηματικών.

Το μάθημα ΜΥΥ302: ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ-ΙΙ αποτελεί συνέχεια του μαθήματος   ΜΥΥ204: ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ-Ι. Οι ενότητες που θα καλυφθούν είναι οι εξής:

1. Μαθηματική Λογική: Σύνοψη Προτασιακής Λογικής. Πρωτοβάθμια Κατηγορηματική Λογική.
    ΠΗΓΕΣ: ROSEN-7, Chapter 1 -- EPP, Chapter 1 -- Κοντογιάννης, Σημειώσεις.

2. Αναδρομικές Σχέσεις και Αναδρομικά Ορισμένες Διακριτές Δομές.
    ΠΗΓΕΣ: ROSEN-7, Chapters 5,8 -- EPP, Chapter 8.

3. Γεννήτριες Συναρτήσεις: Βασικοί Ορισμοί. Τεχνικές Ανάλυσης. Επίλυση Αναδρομικών Σχέσεων. Μέτρηση Διακριτών Δομών με Γεννήτριες.
    ΠΗΓΕΣ: ROSEN-7, Chapter 8 -- GKP, Chapter 7 -- MN, Chapter 12.

4. Εισαγωγή στη Θεωρία Αριθμών.
    ΠΗΓΕΣ: ROSEN-7, Chapter 4 -- CLRS, Chapter 31 -- EPP, Chapter 3 -- GKP, Chapter 4.

5. Εισαγωγή στη Θεωρία Γραφημάτων: Βασικοί Ορισμοί. Υπογραφήματα. Ακολουθίες βαθμών. Μορφισμοί γραφημάτων. Συνδεσιμότητα. Γραφήματα Euler - Hamilton. Επιπεδότητα. Δένδρα.
    ΠΗΓΕΣ: ROSEN-7, Chapters 10,11 -- EPP, Chapter 11 -- Κοντογιάννης, Σημειώσεις.

6. Αυτόματα και Τυπικές Γλώσσες: Γλώσσες και γραμματικές. Πεπερασμένα αυτόματα με έξοδο. Πεπερασμένα αυτόματα δίχως έξοδο. Αναγνώριση γλωσσών.
    ΠΗΓΕΣ: ROSEN-7, Chapter 13 -- EPP, Chapter 12.

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

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

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

 

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

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

 

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

Διδακτική  Εβδομάδα Ημερομηνίες Διδασκαλίας Ύλη Εβδομάδας Συνοδευτικό Υλικό
Περιοχη Περιορισμενης Προσβασης
Διαφάνειες
password protected
Σημειώσεις
password protected
1η 28-29/9 Εισαγωγικά
Κατηγορηματική Λογική
-- Πρωτοβάθμιες Γλώσσες
-- Ερμηνείες Γλωσσών
Εισαγωγικές Διαφάνειες
[για εκτύπωση]

Διαφάνειες

Κατηγορηματικής Λογικής
[για ανάγνωση][για εκτύπωση]
Σημειώσεις
Κατηγορηματικής Λογικής
[ανάγνωση/εκτύπωση]

 

ROSEN-7, CH1

2η 5-6/10 Κατηγορηματική Λογική (συν.)
-- Αποτίμηση τύπων και ορισμός της αλήθειας του Tarski
-- Νόμοι της ΚΛ και μετακινήσεις ποσοδεικτών
3η 12-13/10 Αναδρομικές Σχέσεις & Αναδρομικά Ορισμένες Διακριτές Δομές Διαφάνειες
Σχέσεις Αναδρομής
[ανάγνωση/εκτύπωση]
ROSEN-7, CH.5
4η 19-20/10 Αναδρομικοί Αλγόριθμοι

Γεννήτριες Συναρτήσεις
-- Βασικές έννοιες
-- Αξιοποίηση Γεννητριών για Επίλυση Αναδρομικών Σχέσεων

Διαφάνειες
Ανάλυση Αναδρομικών Αλγορίθμων
[ανάγνωση/εκτύπωση]

Διαφάνειες
Εισαγωγή στις Γεννήτριες
[ανάγνωση/εκτύπωση]

ROSEN-7, CH.8

 

Σημειώσεις
Χειρισμός Γεννητριών
[ανάγνωση/εκτύπωση]

5η 26-27/10 Γεννήτριες Συναρτήσεις (συν.)
-- Αξιοποίηση Γεννητριών στη Συνδυαστική

Διαφάνειες
Γεννήτριες και Συνδυαστική
[για ανάγνωση][για εκτύπωση]

6η 2-3/11 Εισαγωγή στη Θεωρία Αριθμών
-- Αριθμητική Υπολοίπου
-- Αλγόριθμοι για Στοιχειώδεις Πράξεις στην Αριθμητική Υπολοίπου
Διαφάνειες
Εισαγωγή στη Θεωρία Αριθμών
[ανάγνωση/εκτύπωση]
 
7η 9-10/11 Εισαγωγή στη Θεωρία Αριθμών
-- Γραμμικά Συστήματα Ισοτιμιών
-- Πράξεις με Μεγάλους Αριθμούς
ΠΡΩΤΗ ΠΡΟΟΔΟΣ: Πέμπτη 10/11/2016,14:00-16:00
 
8η 16/11 Η ΔΙΑΛΕΞΗ ΤΗΣ ΣΥΓΚΕΚΡΙΜΕΝΗΣ ΕΒΔΟΜΑΔΑΣ ΑΝΑΒΑΛΛΟΝΤΑΙ, ΛΟΓΩ ΑΠΟΥΣΙΑΣ ΤΟΥ ΔΙΔΑΣΚΟΝΤΑ.  
9η 23-24/11 Εισαγωγή στη Θεωρία Αριθμών
-- Εφαρμογές στην Κρυπτογραφία
 
10η 30/11-1/12 Εισαγωγή στη Θεωρία Γραφημάτων
-- Βασικές Έννοιες
-- Βαθμοί & Λήμμα Χειραψίας
Διαφάνειες
Εισαγωγή στη Θεωρία Γραφημάτων
[ανάγνωση/εκτύπωση]
Σημειώσεις
Εισαγωγή στη Θεωρία Γραφημάτων
[ανάγνωση/εκτύπωση]
11η 7-8/12 Εισαγωγή στη Θεωρία Γραφημάτων
--- Αναπαράσταση Γραφημάτων
-- Μορφισμοί
-- Συνδεσιμότητα
Διαφάνειες
Αναπαράσταση-Μορφισμοί-Συνδεσιμότητα
[ανάγνωση/εκτύπωση]
12η 14-15/12 Εισαγωγή στη Θεωρία Γραφημάτων
-
- Κυκλώματα και Μονοκονδυλιές Euler
Διαφάνειες
Γραφήματα Euler
[ανάγνωση/εκτύπωση]
13η 21-22/12 Εισαγωγή στη Θεωρία Γραφημάτων
-- Κύκλοι και Μονοπάτια Hamilton
-- Επιπεδότητα Γραφημάτων
ΔΕΥΤΕΡΗ ΠΡΟΟΔΟΣ: Πέμπτη,
22/12/2016, 14:00-16:00. ΥΛΗ: Εισαγωγή στη Θεωρία Αριθμών (ROSEN: Κεφάλαιο 4) και Εισαγωγή στα Γραφήματα (ROSEN: ενότητες 10.1-10.5, ΣΗΜΕΙΩΣΕΙΣ: Κεφάλαια 1-2-3)
Διαφάνειες
Κύκλοι και Μονοπάτια Hamilton
[ανάγνωση/εκτύπωση]
14η 11-12/1 Εισαγωγή στη Θεωρία Γραφημάτων
-- Επιπεδότητα Γραφημάτων
Διαφάνειες
Επιπεδότητα Γραφημάτων
[ανάγνωση/εκτύπωση]
---- 23/1/2017 ΕΞΕΤΑΣΗ ΜΑΘΗΜΑΤΟΣ:
-- Ώρα: 09:00-12:00
-- Αίθουσα: Ι5 & Αμφιθέατρο Πληροφορικής
-- Κλειστές Σημειώσεις
-- ΧΕΙΡΟΓΡΑΦΟ τυπολόγιο (τρία φύλλα Α4) με το ονοματεπώνυμό σας σε κάθε σελίδα, όπου συμπληρώνετε ό,τι επιθυμείτε.

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

 

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

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

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

  • [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. Εισαγωγή στους Αλγορίθμους (δεύτερη έκδοση), Πανεπιστημιακές Εκδόσεις Κρήτης, 20ΧΧ.
     
  • Σημειώσεις/διαφάνειες του διδάσκοντος (θα δίνονται περιοδικά από το Ημερολόγιο του μαθήματος).

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

  • 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 (διατίθεται και ηλεκτρονικά).
     

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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