Course: Διακριτά Μαθηματικά

Weekly outline

General

ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ (ΜΕΜ241) - ΧΕΙΜΕΡΙΝΟ ΕΞΑΜΗΝΟ 2020-21

ΤΜΗΜΑ ΜΑΘΗΜΑΤΙΚΩΝ ΚΑΙ ΕΦΑΡΜΟΣΜΕΝΩΝ ΜΑΘΗΜΑΤΙΚΩΝ - ΠΑΝΕΠΙΣΤΗΜΙΟ ΚΡΗΤΗΣ

Σημαντικό: Κάντε εγγραφή στο μάθημα, ώστε να λαμβάνετε άμεσα όλες τις ανακοινώσεις και να μπορείτε να συμμετέχετε στις συζητήσεις για το μάθημα και σε όποια άλλη δραστηριότητα προκύψει.

$Χάρτης με τις επτά γέφυρες της Καινιξβέργης$

ΒΑΣΙΚΕΣ ΠΛΗΡΟΦΟΡΙΕΣ

Διδάσκων:	Γιώργος Καπετανάκης (gnkapet@gmail.com)
Γραφείο:	Γ212
Ώρες γραφείου:	Δευτέρα 11.00-13.00 (Zoom link, ID: 727 6942 1258, passcode: 0Pteuy)
Διαλέξεις:	Κάθε εβδομάδα θα αναρτώνται στο ημερολόγιο μαγνητοσκοπημένες διαλέξεις
Βαθμολόγηση:	Τελικό διαγώνισμα (η ακριβής μορφή θα ανακοινωθεί αργότερα)

ΒΙΒΛΙΟΓΡΑΦΙΑ

Μ. Κολουντζάκης και Χ. Παπαχριστόδουλος. Διακριτά Μαθηματικά. Εκδόσεις Κάλλιπος, 2015.
C.L. Liu. Στοιχεία Διακριτών Μαθηματικών. Πανεπιστημιακές Εκδόσεις Κρήτης, 1999.
Kenneth H. Rosen. Διακριτά Μαθηματικά και εφαρμογές. Εκδόσεις Τζιόλα, 2014.
Susanna S. Epp. Διακριτά Μαθηματικά με εφαρμογές. Εκδόσεις Κλειδάριθμος, 2010.

Ανακοινώσεις Forum
Συζητήσεις για το μάθημα Forum
$Σετ ασκήσεων και λύσεις$ Σετ ασκήσεων και λύσεις
$set-01_ans.pdf$ set-01_ans.pdf
$set-01.pdf$ set-01.pdf
$set-02_ans.pdf$ set-02_ans.pdf
$set-02.pdf$ set-02.pdf
$set-03_ans.pdf$ set-03_ans.pdf
$set-03.pdf$ set-03.pdf
$set-04_ans.pdf$ set-04_ans.pdf
$set-04.pdf$ set-04.pdf
Βοηθητικό αρχείο: Μερικές γνωστές γεννήτριες συναρτήσεις File
Συνολικά αποτελέσματα Ιανουαρίου File
Συνολικά αποτελέσματα Σεπτεμβρίου File

28 September - 4 October
Κάναμε μια εισαγωγή στην μαθηματική επαγωγή και είδαμε την απλή, την ισχυρή, την φωλιασμένη, την "μπρος-πίσω" και την πολλαπλή επαγωγή.

(Παράγραφοι 1.9.1 και 1.9.2 του [1])
- 1η διάλεξη (βίντεο) URL
- 1η διάλεξη (διαφάνειες) File
- 2η διάλεξη (βίντεο) URL
  Υπάρχει ένα τυπογραφικό λάθος (ένα πρόσημο) στην 8η διαφάνεια. Το λάθος έχει διορθωθεί στο αρχείο των διαφανειών.
- 2η διάλεξη (διαφάνειες - διορθωμένες) File
5 October - 11 October
Είδαμε παραδείγματα ενίσχυσης πρότασης και το Θεώρημα του Γάμου. Έγινε εισαγωγή στην Συνδυαστική: αρχή του πολλαπλασιασμού, πλήθος συναρτήσεων από ένα σύνολο $A$ σε ένα σύνολο $B$, ημιανεξαρτησία, πλήθος διατεταγμένων επιλογών, μεταθέσεις συνόλου.

(Παράγραφοι 1.9.2, 1.9.3, 3.1 και 3.2.1 του [1])
- 3η διάλεξη (βίντεο) URL
  Υπάρχει τυπογραφικό στις διαφάνειες 2 και 4, δείτε το αρχείο pdf για να δείτε την διορθωμένη εκδοχή.
- 3η διάλεξη (διαφάνειες - διορθωμένες) File
- 4η διάλεξη (βίντεο) URL
- 4η διάλεξη (διαφάνειες) File
12 October - 18 October
Είδαμε τους συνδυασμούς $n$ ανά $k$ και σχετικά παραδείγματα. Επίσης, είδαμε τις διαμερίσεις και τους συνδυασμούς με επανάθεση, μαζί με μια πληθώρα από σχετικά παραδείγματα.

(Παράγραφοι 3.2.2 και 4.1 του [1])
- 5η διάλεξη (βίντεο) URL
  Υπάρχει ένα σημαντικό λάθος στο πρώτο ερώτημα του παραδείγματος στις διαφάνειες 9-11. Δείτε το αρχείο με τις διαφάνειες για να δείτε την σωστή απάντηση.
- 5η διάλεξη (διαφάνειες - διορθωμένο) File
- 6η διάλεξη (βίντεο) URL
  Υπάρχει ένα λάθος απροσεξίας στην 15η διαφάνεια (έχουμε 5 γυναίκες και 3 άνδρες και όχι αντίστροφα όπως φαίνεται στην αρχη). Επίσης, στην 10η διαφάνεια η απάντηση είναι $\binom{2n}{n}$. Δείτε τις διορθωμένες διαφάνειες.
- 6η διάλεξη (διαφάνειες - ξαναδιορθωμένο) File
19 October - 25 October
Είδαμε τους πολυωνυμικούς συντελεστές, το πολυωνυμικό θεώρημα (multinomial theorem) και μερικά παραδείγματα συνδυαστικών αποδείξεων ταυτοτήτων. Είδαμε την αρχή του εγκλεισμού-αποκλεισμού και το πλήθος των επί συναρτήσεων $[m] \to [n]$.

(Παράγραφοι 4.2, 4.3 και 4.4 του [1] και παράγραφοι 8.5 και 8.6 του [3] - Η απόδειξη του πολυωνυμικού θεωρήματος δεν εντοπίζεται στην προτεινόμενη βιβλιογραφία)
- 7η διάλεξη (βίντεο) URL
- 7η διάλεξη (διαφάνειες) File
- 8η διάλεξη (βίντεο) URL
  Υπάρχει ένα τυπογραφικό στην 5η διαφάνεια και ένα ακόμα στην 10η, τα οποία φαίνονται στο βίντεο. Τα λάθη έχουν διορθωθεί στις διαφάνειες.
- 8η διάλεξη (διαφάνειες - διορθωμένο) File
26 October - 1 November
Εισαγωγή στις γεννήτριες συναρτήσεις. Λύσαμε τις ασκήσεις του 1ου φυλλαδίου.

(Παράγραφος 8.4 του [3])
- 9η διάλεξη (βίντεο) URL
- 9η διάλεξη (διαφάνειες) File
- 10η διάλεξη (βίντεο) URL
  Στην διάλεξη αυτή λύνουμε όλες τις ασκήσεις. Επειδή το βίντεο είναι πολύ μεγάλο, μπορείτε να δείτε πρώτα τις λύσεις από το φυλλάδιο των λύσεων και να ανατρέχετε στο αντίστοιχο τμήμα του βίντεο αν χρειάζεστε επιπλέον επεξηγήσεις για κάποια άσκηση.
  
  Παρατήρηση: Όπως πολύ σωστά επισημάθηκε στο forum, υπάρχει ένα ζήτημα με την Άσκηση 9. Επειδή είναι παρόμοια με άσκηση που έχει λυθεί σε προηγούμενη διάλεξη, η λύση της δεν δόθηκε στην διάλεξη και η αρχική λύση στο φυλλάδιο των λύσεων ήταν ελλιπής. Δείτε τις λύσεις στο φυλλάδιο των λύσεων για την πλήρη απάντηση.
- 10η διάλεξη (διαφάνειες) File
2 November - 8 November
Έγινε μια εισαγωγή στην Θεωρία Γραφημάτων: είδαμε τον ορισμό του απλού γραφήματος, των γειτονικών ακμών/κορυφών, της γειτονιάς, του βαθμού ακμών/κορυφών και του $r$-κανονικού γραφήματος και το Θεώρημα των Χειραψιών με μερικές εφαρμογές του. Ακόμα είδαμε παραδείγματα ειδικών γραφημάτων, την έννοια του υπογραφήματος και του επαγόμενου υπογραφήματος και ορίσαμε την ισομορφία γραφημάτων, ενώ είδαμε μερικές ιδιότητες που μοιράζονται ισόμορφα γραφήματα. Κλείσαμε με παραδείγματα μοντελοποίησης απλών προβλημάτων με την βοήθεια γραφημάτων.

(Παράγραφοι 5.1, 5.2 και 5.3 του [1])
- 11η διάλεξη (βίντεο) URL
  Υπάρχουν τυπογραφικά στην 2η και την 7η διαφάνεια. Τα λάθη έχουν διορθωθεί στις διαφάνειες.
- 11η διάλεξη (διαφάνειες - διορθωμένες) File
- 12η διάλεξη (βίντεο) URL
  Υπάρχει μια παράλειψη στα σημεία 34:30-34:50, καθώς από την κορυφή (ΚΧΒ/ΚΧ), έχουμε ακμή προς την κορυφή (/ΚΚΧΧΒ), οπότε θα έχουμε τελικά επιπλέον δύο μονοπάτια που λύνουν το πρόβλημα.
- 12η διάλεξη (διαφάνειες) File
9 November - 15 November
Συνεχίσαμε με την ισομορφία γραφημάτων και ορίσαμε το μονοπάτι. Είδαμε ότι ένας ισομορφισμός γραφημάτων αντιστοιχεί μονοπάτια μήκους $n$ σε μονοπάτια μήκους $n$. Είδαμε πληθώρα παραδειγμάτων. Κυκλώματα, κύκλοι, προσιτότητα, η προσιτότητα ως σχέση ισοδυναμίας, συνεκτικότητα, συνεκτικές συνιστώσες, απόσταση κορυφών, η απόσταση ως μετρική, διάμετρος απλού γραφήματος.

(Παράγραφοι 5.3.2 και 5.4 του [1])
- 13η διάλεξη (βίντεο) URL
  Στο βίντεο, στις χρονικές στιγμές 00:45-01:20 αντί των $E\cap E=\emptyset$ και $E\cup E = \ldots$ θα έπρεπε να αναφέρεται $E\cap E^C=\emptyset$ και $E\cup E^C = \ldots$ αντίστοιχα.
- 13η διάλεξη (διαφάνειες) File
- 14η διάλεξη (βίντεο) URL
  Υπάρχει ένα τυπογραφικό στην 3η διαφάνεια. Το λάθος έχει διορθωθεί στο pdf αρχείο των διαφανειών.
- 14η διάλεξη (διαφάνειες) File
16 November - 22 November
Είδαμε τις λύσεις του 2ου φυλλαδίου. Ακόμα είδαμε μερικές προτάσεις σχετικές με την διάμετρο ενός απλού συνεκτικού γραφήματος και αρκετά παραδείγματα σχετικά με την διάμετρο και την ισομορφία γραφημάτων.

(Παράγραφος 5.4 του [1])
- 15η διάλεξη (βίντεο) URL
  Υπάρχουν κάποια μικρά λάθη στις λύσεις των ασκήσεων 2(iii) και 8(i). Δείτε το αρχείο pdf των διαφανειών ή το αρχείο των λύσεων για τις σωστές λύσεις.
- 15η διάλεξη (διαφάνειες - διορθωμένες) File
- 16η διάλεξη (βίντεο) URL
- 16η διάλεξη (διαφάνειες) File
23 November - 29 November
Είδαμε τις έννοιες της άρθρωσης και της γέφυρας, καθώς και εκείνες του δέντρου και του δάσους. Είδαμε ότι κάθε συνεκτικό γράφημα περιέχει ένα παράγων δέντρο και κάθε γράφημα έχει κάποιο παράγων δάσος. Αφού ορίσαμε τα φύλλα, είδαμε ότι ένα δέντρο $n\geq 2$ κορυφών έχει τουλάχιστον δύο φύλλα. Χαρακτηρίσαμε πλήρως ένα δέντρο. Στη συνέχεια είδαμε διάφορες γενικεύσεις του απλού γραφήματος (κατευθυνόμενα γραφήματα, βρόγχους, πολλαπλές ακμές, βάρη). Αναφερθήκαμε στο πρόβλημα του περιπλανώμενου πωλητή, ορίσαμε το ελάχιστο παράγων δέντρο και είδαμε τον αλγόριθμο του Kruskal.

(Παράγραφοι 5.5, 5.6 και 5.7 του [1] και παράγραφος 10.4 του [3])
- 17η διάλεξη (βίντεο) URL
  Υπάρχει ένα τυπογραφικό λάθος στην 8η διαφάνεια. Το λάθος έχει διορθωθεί στο pdf αρχείο με τις διαφάνειες.
- 17η διάλεξη (διαφάνειες - διορθωμένες) File
- 18η διάλεξη (βίντεο) URL
- 18η διάλεξη (διαφάνειες) File
30 November - 6 December
Είδαμε τους αλγόριθμους Floyd-Warshall και Dijkstra. Είδαμε και χαρακτηρίσαμε τα διμερή γραφήματα. Ορίσαμε τον χρωματικό αριθμό $\chi(G)$ του γραφήματος $G$, είδαμε κάποια άμεσα άνω και κάτω φράγματά του και είδαμε ότι το $G$ είναι διμερές αν και μόνο αν $\chi(G)\leq 2$.

(Παράγραφοι 5.8 και 6.1 του [1] και παράγραφοι 10.6 και 10.8 του [3])
- 19η διάλεξη (βίντεο) URL
- 19η διάλεξη (διαφάνειες) File
- 20η διάλεξη (βίντεο) URL
  Υπάρχει ένα μικρό τυπογραφικό στην 9η διαφάνεια. Δείτε το διορθωμένο pdf των διαφανειών παρακάτω.
- 20η διάλεξη (διαφάνειες - διορθωμένες) File
7 December - 13 December
Ορίσαμε τα ταιριάσματα και τα πλήρη ταιριάσματα και αναδιατυπώσαμε με γλώσσα γραφημάτων το Θεώρημα του Γάμου. Έπειτα ορίσαμε το μέγιστο ταίριασμα και το επαυξανον μονοπάτι και είδαμε ότι ένα ταίριασμα σε ένα διμερές γράφημα είναι μέγιστο αν και μόνο αν δεν έχει κάποιο επαυξάνον μονοπάτι. Στη συνέχεια είδαμε το θεώρημα König-Egeváry, ορίσαμε τους κύκλους και τα μονοπάτια Euler και Hamilton και είδαμε το θεώρημα του Euler σχετικά με την ύπαρξη ή όχι κύκλου και μονοπατιού Euler σε συνεκτικό γράφημα.

(Παράγραφοι 6.2, 6.3 και 6.4 του [1])
14 December - 20 December
Είδαμε μερικά παραδείγματα σχετικά με κύκλους/μονοπάτια Euler και Hamilton. Επίσης, είδαμε τα θεωρήματα Dirac και Ore. Στην συνέχεια, ορίσαμε την ομομορφία γραφημάτων, ορίσαμε τα επίπεδα γραφήματα και αναφέραμε το θεώρημα των τεσσάρων χρωμάτων και είδαμε σχετικά παραδείγματα. Στη συνέχεια, είδαμε τον τύπο του Euler και με την βοήθειά του δείξαμε ότι τα γραφήματα $K_5$ και $K_{3,3}$ δεν είναι επίπεδα. Κλείσαμε με το κριτήριο του Kuratowski.

(Παράγραφος 6.4 του [1] και παράγραφοι 10.7 και 10.8 του [3])
21 December - 27 December
Είδαμε τις λύσεις του 3ου και του 4ου φυλλαδίου.

Weekly outline

ΔΙΑΚΡΙΤΑ ΜΑΘΗΜΑΤΙΚΑ (ΜΕΜ241) - ΧΕΙΜΕΡΙΝΟ ΕΞΑΜΗΝΟ 2020-21

ΤΜΗΜΑ ΜΑΘΗΜΑΤΙΚΩΝ ΚΑΙ ΕΦΑΡΜΟΣΜΕΝΩΝ ΜΑΘΗΜΑΤΙΚΩΝ - ΠΑΝΕΠΙΣΤΗΜΙΟ ΚΡΗΤΗΣ

ΒΑΣΙΚΕΣ ΠΛΗΡΟΦΟΡΙΕΣ

ΒΙΒΛΙΟΓΡΑΦΙΑ

Stay in touch