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

CSE.UOI :: MYY302 -- Διακριτά Μαθηματικά 2

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

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

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

Διδάσκων: Σπύρος Κοντογιάννης
Email -- URL -- Voice: --  http://www.cse.uoi.gr/~kontog/  --  (26510) 08812
URL Μαθήματος: http://www.cse.uoi.gr/~kontog/courses/Discrete-Math-2/
Ώρες Διαλέξεων: Κάθε Τετάρτη 18:00--20:00 και κάθε Παρασκευή 09:00--12:00
Χώρος Διαλέξεων: Τεταρτη: ΑΜΦΙΘΕΑΤΡΟ, Παρασκευή: ΑΙΘΟΥΣΑ Ι5
Επικουρικό Έργο: Γιάννης Γεωργιάδης, γραφείο Γ1 στον τρίτο όροφο του κτιρίου της Πληροφορικής -- (igeorgiadis@cse.uoi.gr)
Ώρες Επικοινωνίας:

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

Περιγραφή

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

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

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

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

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

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

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

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

6. Εφαρμογές των ΔΜ στην Πληροφορική.
    ΠΗΓΕΣ: HUNTER, Chapter 3 -- ROSEN-8, Chapter 4.

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

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

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

 

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

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

 

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

Διδακτική  Εβδομάδα Ημερομηνίες Διδασκαλίας Ύλη Εβδομάδας Συνοδευτικό Υλικό
Περιοχη Περιορισμενης Προσβασης
ΔΙΑΦΑΝΕΙΕΣ
password protected
ΥΛΙΚΟ
(password protected
)
1η 2-4/10 Εισαγωγικά
Κατηγορηματική Λογική

-- Πρωτοβάθμιες Γλώσσες
--
Μοντελοποίηση Ιδιοτήτων μέσω Πρωτοβάθμιων  Γλωσσών
Εισαγωγικές Διαφάνειες
[ανάγνωση/εκτύπωση]
ROSEN-8 / CH1.4-1.5

HUNTER / CH1

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

Ενδεικτικές Ασκήσεις
Κατηγορηματικής Λογικής
[ανάγνωση/εκτύπωση]

2η 9-11/10 Κατηγορηματική Λογική
-- Αποτίμηση τύπων και ορισμός της αλήθειας του Tarski
-- Νόμοι της ΚΛ και μετακινήσεις ποσοδεικτών
Διαφάνειες
Κατηγορηματικής Λογικής
[ανάγνωση/εκτύπωση]
3η 16-18/10 Εισαγωγή στη Θεωρία Γραφημάτων
-- Βασικές Έννοιες
-- Βαθμοί & Λήμμα Χειραψίας
Διαφάνειες
Βασικές Έννοιες Γραφημάτων
[ανάγνωση/εκτύπωση]
ROSEN-8 / CH10

 

HUNTER / CH2

 

Σημειώσεις

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

4η 23/10 Εισαγωγή στη Θεωρία Γραφημάτων
--- Αναπαράσταση Γραφημάτων
 
Διαφάνειες
Αναπαράσταση-Μορφισμοί-Συνδεσιμότητα Γραφημάτων
[ανάγνωση/εκτύπωση]
5η 30/10-1/11 Εισαγωγή στη Θεωρία Γραφημάτων
-- Μορφισμοί
-- Συνδεσιμότητα
6η 6-8/11 Εισαγωγή στη Θεωρία Γραφημάτων
-- Κυκλώματα και Μονοκονδυλιές Euler
Διαφάνειες
Κυκλώματα/Μονοκονδυλίές Euler
[ανάγνωση/εκτύπωση]
7η 13-15/11 Εισαγωγή στη Θεωρία Γραφημάτων
-- Κύκλοι και Μονοπάτια Hamilton
-- Επιπεδότητα Γραφημάτων
Διαφάνειες
Κύκλοι/Μονοπάτια Hamilton
[ανάγνωση/εκτύπωση]

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

8η 20-22/11 ΠΡΟΟΔΟΣ: 20/11/2019, 18:00 - 20:00 @ ΑΜΦ-ΤΜΗΥΠ
Αναδρομικοί Συλλογισμοί
-- Αναδρομικές Σχέσεις & Αναδρομικά Ορισμένες Διακριτές Δομές
-- Επίλυση Αναδρομικών Σχέσεων με Χαρακτηριστικό Πολυώνυμο
Διαφάνειες
Σχέσεις Αναδρομής -- Επίλυση
Αναδρομικών Σχέσεων
[ανάγνωση/εκτύπωση]
ROSEN-8 / CH5.3-5.5, CH8.1-8.2-8.3
9η 27-29/11 Αναδρομικοί Συλλογισμοί
-- Αναδρομικοί Αλγόριθμοι και ανάλυσή του
ς

Γεννήτριες Συναρτήσεις
-- Βασικές έννοιες

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

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

 
10η 4-6/12 Γεννήτριες Συναρτήσεις
-- Αξιοποίηση Γεννητριών για Επίλυση Αναδρομικών Σχέσεων
-- Αξιοποίηση Γεννητριών στη Συνδυαστική
Διαφάνειες
Γεννήτριες και Συνδυαστική
[ανάγνωση/εκτύπωση]
Σημειώσεις
Χειρισμός Γεννητριών
[ανάγνωση/εκτύπωση]

ROSEN-8/CH8.4

11η 11-13/12 Εισαγωγή στη Θεωρία Αριθμών
-- Αριθμητική Υπολοίπου
-- Αλγόριθμοι για Στοιχειώδεις Πράξεις στην Αριθμητική Υπολοίπου
Διαφάνειες
Εισαγωγή στη Θεωρία Αριθμών
[ανάγνωση/εκτύπωση]
ROSEN-8 / CH4.1-4.5
12η 18-20/12 Εισαγωγή στη Θεωρία Αριθμών
-- Γραμμικά Συστήματα Ισοτιμιών
-- Πράξεις με Μεγάλους Αριθμούς
13η 8-10/1 Εφαρμογές ΔΜ στην Πληροφορική
-- Θεωρία Αριθμών και Κρυπτογραφία
-- Μοτίβα στο DNA
-- Ανάλυση Κοινωνικών Δικτύων
Διαφάνειες
Εφαρμογή Θεωρία Αριθμών στην Κρυπτογραφία
[ανάγνωση/εκτύπωση]
ROSEN-8 / CH4.6
---- 15/1/2020 ΕΞΕΤΑΣΗ ΜΑΘΗΜΑΤΟΣ:
-- Ώρα: 09:00-12:00
-- Αίθουσα: Ι5 & Αμφιθέατρο Πληροφορικής
-- Κλειστές Σημειώσεις
-- ΧΕΙΡΟΓΡΑΦΟ τυπολόγιο (τέσσερα φύλλα Α4), συρραμμένα και  με το ονοματεπώνυμό σας σε κάθε σελίδα, όπου συμπληρώνετε ό,τι επιθυμείτε.

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

 

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

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

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

  • [ROSEN-8] [Κωδικός Ευδόξου: 77106820] Kenneth Rosen : Διακριτά μαθηματικά και εφαρμογές τους (8η Έκδοση)
  • [HUNTER] [Κωδικός Ευδόξου: 86055409] David Hunter : Διακριτά μαθηματικά
  • [ΕΡΡ] [Κωδικός Ευδόξου: 13953] : SUSANNA S. EPP : ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ ΜΕ ΕΦΑΡΜΟΓΕΣ
  • [ΤΣΑΓΚΑΡΗΣ] [Κωδικός Ευδόξου: 45379] Παναγιώτης Τσαγκάρης : Θεωρία Αριθμών
  • [ΔΕΡΖΙΩΤΗΣ] [Κωδικός Ευδόξου: 22768507] ΔΗΜΗΤΡΗΣ ΔΕΡΙΖΙΩΤΗΣ : ΜΙΑ ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΑΡΙΘΜΩΝ
  • [GKP] [Κωδικός Ευδόξου: 12858904] RONALD L. GRAHAM, DONALD E. KNUTH, OREN PATASHNIK : ΣΥΝΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ -- ΜΙΑ ΘΕΜΕΛΙΩΣΗ ΓΙΑ ΤΗΝ ΕΠΙΣΤΗΜΗ ΤΩΝ ΥΠΟΛΟΓΙΣΤΩΝ

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

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

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

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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