Διακριτα Μαθηματικα (ΜΕΜ241) - Εαρινο Εξαμηνο 2018-19

Τμημα Μαθηματικων και Εφαρμοσμενων Μαθηματικων - Πανεπιστημιο Κρητης

Βασικες Πληροφοριες

Διδασκων:	Γιώργος Καπετανάκης (gnkapet@gmail.com)
Προγραμμα:	Τετάρτη 11.00-13.00 (Α201) και Παρασκευή 11.00-13.00 (Α201)
Βαθμολογηση:	Τελική εξέταση με θέματα ανάπτυξης

Βιβλιογραφια

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

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

Λόγω της μεγάλης προσέλευσης έγινε αλλαγή στην αίθουσα. Τα μαθήματα (και τις δύο μέρες) θα γίνονται ~~στην Ε204~~ στο Α201.
Εκτός από τις ασκήσεις που θα βρίσκετε στα φυλλάδια, ενθαρρύνεστε να ψάχνετε ασκήσεις και από άλλες πηγές, π.χ. στην βιβλιογραφία.
Έγινε νέα αλλαγή στην αίθουσα.
Το πρώτο φυλλάδιο είχε κάποια τυπογραφικά, αν το είχατε κατεβάσει, κατεβάστε την νέα έκδοσή του.
Θα φιλοξενηθεί στο τμήμα μας σεμινάριο σχετικά με το μαθηματικό λογισμικό SageMath από την Viviane Pons. Για πληροφορίες επικοινωνήστε με την Ελένη Τζανάκη.
Αλλαγή αίθουσας Τετάρτη 10/04: Το μάθημα της Τετάρτης 10/04/2019 θα γίνει στην αίθουσα Α212 λόγω της διεξαγωγής των φοιτητικών εκλογών.
Υπέπεσε στην αντίληψή μου ότι υπήρχε μια αναντιστοιχία στην αρίθμηση των κεφαλαίων ανάμεσα στην αγγλική (που έχω στην διάθεσή μου) και στην ελληνική έκδοση του [3]. Πλέον το ημερολόγιο είναι σωστό.
~~Λόγω του μεγάλου πλήθους των γραπτών,~~ Η ολοκλήρωση της αξιολόγησης (άρα και η ανακοίνωση των αποτελεσμάτων) ~~θα καθυστερήσει.~~ έγινε!
Μπορείτε να δείτε τα αποτελέσματα της εξέτασης του Ιουνίου. Αν πιστεύετε ότι έχει γίνει κάποιο λάθος ή απλά θέλετε να δείτε το γραπτό σας, μπορείτε να έρθετε στο γραφείο μου (Γ212) Τετάρτη 26/06 ή Παρασκευή 28/06 τις ώρες 11.00-13.00.
Για όποιον έχει κάποια απορία σχετικά με την εξεταστική του Σεπτεμβρίου, θα βρίσκομαι στο γραφείο μου στις 21/08 και 23/08 (13.00-15.00). Αν δεν μπορείτε αυτές τις ώρες επικοινωνήστε μαζί μου.
Μπορείτε να δείτε τα αποτελέσματα της εξέτασης του Σεπτεμβρίου. Αν πιστεύετε ότι έχει γίνει κάποιο λάθος ή απλά θέλετε να δείτε το γραπτό σας, μπορείτε να έρθετε στο γραφείο μου (Γ212) την Δευτέρα 16/09 τις ώρες 12.00-14.00.

Εξετασεις

Ιούνιος. [Θέματα, Αποτελέσματα]
Σεπτέμβριος. [Θέματα, Αποτελέσματα]

Φυλλαδια Ασκησεων

Ίσως σε κάποιους να φανεί χρήσιμο το βοήθημα με μερικές γνωστές γεννήτριες συναρτήσεις.

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

1^η εβδομάδα (04/02/19-08/02/19):: Ορίσαμε το δυναμοσύνολο ενός συνόλου και δείξαμε με επαγωγή ποιος είναι ο πληθάριθμος ενός δυναμοσυνόλου ενός πεπερασμένου συνόλου. Είδαμε την μαθηματική επαγωγή σε διάφορες μορφές της (απλή, ισχυρή, "μπρος-πίσω", πολλαπλή). Είδαμε σχετικά παραδείγματα. (Παράγραφοι 1.9.1 και 1.9.2 του [1])
2^η εβδομάδα (11/02/19-15/02/19):: Ορίσαμε τις έννοιες του συστήματος υποσυνόλων και του συστήματος ξένων αντιπροσώπων (ΣΞΑ) και αποδείξαμε το θεώρημα του Hall (θεώρημα του γάμου). Στη συνέχεια αποδείξαμε την αρχή του πολλαπλασιασμού και, ως εφαρμογές της, είδαμε το πλήθος των διαιρετών ενός ακεραίου και το πλήθος των συναρτήσεων από ένα σύνολο σε ένα άλλο. Ορίσαμε την έννοια της ημιανεξαρτησίας και υπολογίσαμε το πλήθος των διατεταγμένων επιλογών, των μεταθέσεων συνόλου και των συνδυασμών. Είδαμε διάφορα σχετικά παραδείγματα και ασκήσεις. (Παράγραφοι 1.9.3, 3.1 και 3.2 του [1])
3^η εβδομάδα (18/02/19-22/02/19):: Αποδείξαμε το τρίγωνο του Pascal και το Διωνυμικό Θεώρημα (αλγεβρικά). Είδαμε τις διαμερίσεις και τους συνδυασμούς με επανάθεση, καθώς και τους πολυωνυμικούς συντελεστές. Είδαμε πληθώρα σχετικών με την εως τώρα θεωρία ασκήσεων. (Παράγραφοι 4.1 και 4.2 του [1])
4^η εβδομάδα (25/02/19-01/03/19):: Αποδείξαμε συνδυαστικά το Διωνυμικό Θεώρημα και μερικές ακόμα ταυτότητες, ενώ είδαμε και εφαρμογές τους. Ακόμα, είδαμε την Αρχή του Εγκλεισμού-Αποκλεισμού και εφαρμογές της και έγινε μια εισαγωγή στις γεννήτριες συναρτήσεις. (Παράγραφοι 4.3 και 4.4 του [1] και Παράγραφοι 8.4, 8.5 και 8.6 του [3])
5^η εβδομάδα (04/03/19-08/03/19):: Είδαμε μερικές εφαρμογές και ασκήσεις των γεννητριών συναρτήσεων. Έγινε μια εισαγωγή στην Θεωρία Γραφημάτων: είδαμε τον ορισμό του απλού γραφήματος, των γειτονικών ακμών/κορυφών, της γειτονιάς, του βαθμού ακμών/κορυφών και του r-κανονικού γραφήματος. Τέλος είδαμε το Θεώρημα των Χειραψιών και μερικές εφαρμογές του. (Παράγραφος 5.1 του [1], Παράγραφοι 8.4 και 10.2 του [3] και Παράγραφος 11.1 του [4])
6^η εβδομάδα (11/03/19-15/03/19):: Είδαμε τις έννοιες του καλύμματος και του ανεξάρτητου υποσυνόλου κορυφών ενός γραφήματος, του υπογραφήματος και του επαγόμενου υπογραφήματος, καθώς και μερικά παραδείγματα ειδικών γραφημάτων (κενό, πλήρες πλήρες διμερές, κύκλος). Ορίσαμε το μονοπάτι και το μήκος του, την ισομορφία και τον ισομορφισμό γραφημάτων και δείξαμε ότι η ισομορφία γραφημάτων είναι σχέση ισοδυναμίας και είδαμε ιδιότητες που μένουν αναλλοίωτες μέσα από έναν ισομορφισμό γραφημάτων (πλήθος κορυφών/ακμών, βαθμός κορυφών, ύπαρξη μονοπατιών από κάθε κορυφή σε κάθε άλλη). Τέλος, είδαμε πληθώρα σχετικών ασκήσεων. (Παράγραφοι 5.1-5.3 του [1])
7^η εβδομάδα (18/03/19-22/03/19):: Είδαμε ασκήσεις σχετικές με την ισομορφία γραφημάτων, ορίσαμε το κύκλωμα και τον κύκλο. Ορίσαμε την έννοια της προσιτότητας κορυφών και δείξαμε ότι είναι σχέση ισοδυναμίας, ορίσαμε τις έννοιες της συνεκτικότητας, της συνεκτικής συνιστώσας και της απόστασης μεταξύ δύο κορυφών ενός γραφήματος και δείξαμε ότι πρόκειται για μετρική και ορίσαμε την διάμετρο ενός γραφήματος. Τέλος, είδαμε πληθώρα σχετικών με αυτές τις έννοιες ασκήσεις. (Παράγραφος 5.4 του [1])
8^η εβδομάδα (25/03/19-29/03/19):: Είδαμε ασκήσεις σχετικές με τον ισομορφισμό γραφημάτων, είδαμε τις έννοιες της γέφυρας, της άρθρωσης και είδαμε σχετικές ασκήσεις. Τέλος, ορίσαμε τα δέντρα, τα δάση, τα φύλλα του δέντρου και είδαμε ότι κάθε συνεκτικό γράφημα περιέχει ένα δέντρο που το παράγει και ότι κάθε δέντρο έχει τουλάχιστον δύο φύλλα. (Παράγραφος 10.4 του [3] και Παράγραφος 5.5 του [1])
9^η εβδομάδα (01/04/19-05/04/19):: Είδαμε ότι ένα συνεκτικό γράφημα με n κορυφές είναι δέντρο αν και μόνο αν έχει n-1 ακμές. Στη συνέχεια ορίσαμε τα κατευθυνόμενα γραφήματα, τα γραφήματα με βρόγχους, τα γραφήματα με πολλαπλές ακμές και τα γραφήματα με βάρη, ενώ είδαμε πώς επηρεάζονται οι έννοιες του μήκους μονοπατιού και της διαμέτρου στα τελευταία. Αναφερθήκαμε στο πρόβλημα του περιπλανώμενου πωλητή και, αφού ορίσαμε το ελάχιστο δέντρο που παράγει ένα συνεκτικό γράφημα με βάρη, αναλύσαμε τους αλγορίθμους Kruskal και Prim. (Παράγραφοι 5.5, 5.6 και 5.7 του [1] και Παράγραφος 11.5 του [3])
10^η εβδομάδα (08/04/19-12/04/19):: Είδαμε τον αλγόριθμο Floyd-Warshall και τον αλγόριθμο Dijkstra για την εύρεση των αποστάσεων μεταξύ κορυφών γραφήματος με βάρη. Επίσης, έγινε μια εισαγωγή στο διμερή γραφήματα και στον χαρακτηρισμό τους. (Παράγραφοι 5.8 και 6.1 του [1] και Παράγραφος 10.6 του [3])
11^η εβδομάδα (15/04/19-19/04/19):: Χαρακτηρίσαμε τα διμερή γραφήματα, τόσο με βάση τους κύκλους που περιέχουν, όσο και με βάση τον χρωματικό αριθμό, αφού πρώτα ορίσαμε τον τελευταίο. Μετά ορίσαμε τα ταιριάσματα και τα πλήρη ταιριάσματα και αναδιατυπώσαμε με γλώσσα γραφημάτων το Θεώρημα του Γάμου. Έπειτα ορίσαμε το μέγιστο ταίριασμα και είδαμε το Θεώρημα König-Egeváry. (Παράγραφοι 6.1, 6.2 και 6.3 του [1])
12^η εβδομάδα (06/05/19-10/05/19):: Ορίσαμε τα μονοπάτια και τους κύκλους Euler και Hamilton, ενώ χαρακτηρίσαμε πλήρως την ύπαρξη ή μη μονοπατιών και κύκλων Euler σε ένα γράφημα. Ακόμα είδαμε (χωρίς απόδειξη) τα θεωρήματα Dirac και Ore. Έπειτα υπενθυμίσαμε την έννοια του χρωματισμού και του χρωματικού αριθμού και είδαμε κάποια φράγματά του τελευταίου. Είδαμε σχετικές ασκήσεις. (Παράγραφοι 6.4 και 6.5 του [1] και Παράγραφος 10.5 του [3])
13^η εβδομάδα (13/05/19-17/05/19):: Είδαμε τον ορισμό του επίπεδου γραφήματος και αναφερθήκαμε στο θεώρημα των τεσσάρων χρωμάτων και την ιστορία του. Είδαμε μερικές σχετικές ασκήσεις και κάποιες από τις ασκήσεις των φυλλαδίων. (Παράγραφοι 10.7 και 10.8 του [3])