Διακριτά Μαθηματικά (Μ 2411 ή Μ 251)

Μιχάλης Κολουντζάκης

Τμήμα Μαθηματικών, Πανεπιστήμιο Κρήτης, Λεωφόρος Κνωσού, 714 09 Ηράκλειο, E-mail: kolount AT gmail.com

Φθινόπωρο 2011-12


Περιεχόμενα

1 Ωράριο

Δευτέρα 5-7, Πέμπτη 4-5 στο Αμφιθέατρο ΣΠ. Έναρξη μαθημάτων: 26/9/11.

Ώρες γραφείου: Τρίτη 10-12 και γενικά μπορείτε να με βρίσκετε τα πρωινά 10-12 στο γραφείο μου (Γ 111, στο προκατασκευασμένο κτήριο της Κνωσού).

2 Περιγραφή του μαθήματος

Από τον οδηγό σπουδών:

Σκοπός του μαθήματος είναι η εισαγωγή στη συνδυαστική, τη θεωρία γραφημάτων, δένδρων και δικτύων.

Περιεχόμενα:
  1. Στοιχεία θεωρίας συνόλων, απεικονίσεις, επαγωγή, αλγόριθμοι, αναδρομικές σχέσεις.
  2. Bασικές αρχές συνδυαστικής, διατάξεις, συνδυασμοί, συνδυαστικές ταυτότητες, προβλήματα αντιστοίχισης.
  3. Γραφήματα, μονοπάτια, κυκλώματα – ιδιότητες και εφαρμογές.
  4. Eίδη δένδρου – ιδιότητες και εφαρμογές, μοντέλα δικτύων.
  5. Άλγεβρες Boole, προτασιακός λογισμός.

Δείτε επίσης την ιστοσελίδα του μαθήματος όπως το δίδαξα το 2010-11.

2.1 Βιβλίο

Θα χρησιμοποιήσουμε τις σημειώσεις που θα βρείτε εδώ σε PDF.

3 Βαθμολογικό Σύστημα - Εξετάσεις

Θα γίνουν τρία υποχρεωτικά διαγωνίσματα κατά τη διάρκεια του εξαμήνου (συμπεριλαμβανομένου του «τελικού»).

Δίδεται η δυνατότητα σε όσους αδυνατούν να δώσουν τις υποχρεωτικές εξετάσεις μέσα στο εξάμηνο να ζητήσουν να βαθμολογηθούν μόνο από το τελικό διαγώνισμα. Αυτό είναι εφικτό όταν:

  1. Συντρέχουν αντικειμενικοί λόγοι (π.χ. κάποιος υπηρετεί στο στρατό ή μένει μόνιμα αλλού και αδυνατεί να είναι εδώ).
  2. Πρέπει κάποιος που επιθυμεί να εξεταστεί μόνο σε τελικό διαγώνισμα να το δηλώσει γραπτώς (email αρκεί) σε μένα μέχρι την Παρασκευή 7 Οκτ, 2010, μαζί με τους λόγους που έχει.
Σε καμιά άλλη περίπτωση δε θα είναι δυνατή εναλλακτική εξέταση.

3.1 Συγγραφή λύσεων ασκήσεων

Κατά τη διάρκεια του εξαμήνου, και σε εθελοντική βάση, κάποιοι από σας θα αναλάβουν να γράφουν τις λύσεις για κάποιες από τις ασκήσεις που θα γίνονται στο μάθημα:

Μπορείτε να βλέπετε τις ασκήσεις προς λύση (και τις λύσεις τους) εδώ.

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

Η σελίδα αυτή θα ενημερώνεται τουλάχιστον μετά από κάθε μάθημα και σκοπό έχει να μεταδίδει μερικές βασικές χρήσιμες πληροφορίες για το περιεχόμενο του μαθήματος (π.χ. τι να προσέξετε, υποδείξεις για λύσεις των ασκήσεων, κ.ά.) καθώς και για διαδικαστικά θέματα.

Σπανίως θα βγαίνουν ανακοινώσεις που αφορούν το μάθημα σε χαρτί. Παρακαλώ να συμβουλεύεστε αυτή τη σελίδα τουλάχιστον 2-3 φορές την εβδομάδα.

4.1 Δε, 26/9/11: Η μέθοδος της επαγωγής

Είδαμε τα βασικά για τη μέθοδο της επαγωγής και πολλά παραδείγματα. Διαβάστε την §1 (Κεφ. 1) και λύστε όσο μπορείτε περισσότερες ασκήσεις από κει.

4.1.1 ΑΝΑΚΟΙΝΩΣΗ: Ημερομηνίες διαγωνισμάτων

Το πρώτο διαγώνισμα θα γίνει στα Αμφ. ΒΞ και ΣΠ, 7-9μμ, στις 31 Οκτωβρίου 2011. Εκείνη τη μέρα δε θα γίνει το μάθημα 5-7μμ.

Το δεύτερο διαγώνισμα θα γίνει στα Αμφ. ΒΞ και ΣΠ, 7-9μμ, στις 28 Νοεμβρίου 2011. Εκείνη τη μέρα δε θα γίνει το μάθημα 5-7μμ.

4.2 Πέ, 29/9/11: Παραδείγματα επαγωγής, ισχυρή επαγωγή

Είδαμε σήμερα μερικά παραδείγματα ακόμη (ασκήσεις από την §1) όπως και την §2 (ισχυρή επαγωγή).

4.2.1 ΑΝΑΚΟΙΝΩΣΗ: Οι πρώτες ασκήσεις προς λύση

Έχουν αναρτηθεί εδώ.

4.3 Δε, 3/10/11: Επαγωγή. Εισαγωγή στην απαρίθμηση.

Σήμερα είδαμε διάφορα ακόμη παραδείγματα μαθηματικής επαγωγής. Είδαμε τη μέθοδο της «μπρος-πίσω» επαγωγής (§2.1) όπως και το ότι μπορεί κανείς να χρειαστεί να ενισχύσει την πρότασή του ώστε να μπορεί να την αποδείξει με επαγωγή (§2.3).

Από το Κεφ. 1 μπορείτε να παραλείψετε την §2.2 (πολλαπλή επαγωγή). Την παράγραφο §3 θα τη δούμε αργότερα όταν θα κάνουμε διμερή γραφήματα.

Λύστε επίσης και το Πρότυπο Διαγώνισμα στο τέλος του Κεφ. 1.

Αρχίσαμε να βλέπουμε τα βασικά στοιχεία της απαρίθμησης. Από το Κεφ. 2 είδαμε μέχρι την §2.1.

4.3.1 ΑΝΑΚΟΙΝΩΣΗ: Ώρες γραφείου την Τρίτη 4/10/11

Θα είμαι στο γραφείο μου την Τρίτη μέχρι τις 11πμ μόνο λόγω συμμετοχής μου σε έκτακτη συνεδρίαση.

4.4 Πέ, 6/10/11: Απαρίθμηση.

Σήμερα είδαμε διάφορα παραδείγματα ασκήσεων μέσα από τις σημειώσεις (κυρίως από την §2) και παραλλαγές αυτών.

4.5 Δε, 10/10/11: Συνδυασμοί (όταν η σειρά δεν έχει σημασία)

Σήμερα είδαμε διάφορες περιπτώσεις μετρήματος όπου η σειρά του αποτελέσματος δεν έχει σημασία. Ένα τυπικό παράδειγμα τέτοιου μετρήματος είναι το να μετρήσουμε πόσα υποσύνολα μεγέθους $k$ έχει ένα σύνολο με $n$ στοιχεία. Αυτό τον αριθμό τον συμβολίζουμε με ${n \choose k}$ (διαβάζουμε «$n$ ανά $k$») και τον υπολογίσαμε ακριβώς στην §2.2. Είδαμε επίσης πολλά παραδείγματα και ασκήσεις από την §2.2.

4.6 Πέ, 13/10/11: Συνδυασμών συνέχεια

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

4.7 Δε, 17/10/11: Διαμερίσεις και συνδυασμοί με επανάθεση

Σήμερα είδαμε το κεντρικό αποτέλεσμα της παραγράφου §3.1, ένα τύπο δηλ. που μας λέει με πόσους τρόπους μπορούμε να επιλέξουμε $k$ αντικείμενα από $n$ διαφορετικά αντικείμενα, όταν κάθε αντικείμενο μπορεί να επιλεγεί και παραπάνω από 1 φορά. Ο τύπος είναι

\begin{displaymath}
{n+k-1 \choose k}.
\end{displaymath}

Για να το υπολογίσουμε αυτό λύσαμε πρώτα το πρόβλημα του με πόσους τρόπους μπορούμε να διαμερίσουμε τον ένα αριθμό $n$ σε άθροισμα $r$ προσθετέων.

Λύσαμε διάφορες ασκήσεις από την §3.1.

4.8 Πέ, 20/10/11: Πολυωνυμικοί συντελεστές. Διωνυμικό Θεώρημα.

Είδαμε σήμερα τους πολυωνυμικού συντελεστές (§3.2) που αποτελούν γενίκευση των διωνυμικών συντελεστών ${n \choose k}$. Επίσης αποδείξαμε (ξανά) το διωνυμικό θεώρημα (Θ. 3.4) και με επαγωγή ως προς $n$. Στην πορεία αποδείξαμε με συνδυαστικό επιχείρημα τον τύπο στον οποίο το λεγόμενο τρίγωνο του Pascal οφείλει την ύπαρξή του:

\begin{displaymath}
{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}.
\end{displaymath}

(Μπορείτε να δείτε την απόδειξη αυτού του τύπου στην §3.4.) Δεν προλάβαμε να λύσουμε πολλές από τις ασκήσεις της §3.3.

4.8.1 ΑΝΑΚΟΙΝΩΣΗ: Πρώτο διαγώνισμα

Το πρώτο διαγώνισμα θα γίνει τη Δευτέρα 31/10, 7-9μμ, στα Αμφ. ΒΞ και ΣΠ. Εκείνη τη μέρα δε θα γίνει το μάθημα 5-7μμ.

Το διαγώνισμα θα αποτελείται από ένα κομμάτι με ερωτήσεις πολλαπλών επιλογών και ένα κομμάτι με μερικά ερωτήματα τα οποία θα πρέπει να απαντήσετε αναλυτικά. Θα υπάρχει ένα ολιγόλεπτο διάλειμμα ανάμεσα στα δύο κομμάτια.

Μπορείτε να δείτε εδώ το αντίστοιχο περυσινό διαγώνισμα (μαζί με τις λύσεις) ώστε να πάρετε μια ιδέα τι να περιμένετε. Ο αριθμός των προβλημάτων δε θα είναι κατ' ανάγκη ο ίδιος με πέρυσι.

4.9 Δε, 24/10/11: Εφαρμογές διωνυμικού θεωρήματος. Συνδυαστικές αποδείξεις ταυτοτήτων.

Σήμερα τελειώσαμε το υπόλοιπο του Κεφ. 3. Είδαμε κατ' αρχήν πώς μπορεί το διωνυμικό θεώρημα να εφαρμοστεί με διάφορους τρόπους ώστε να μας δώσει διάφορους υπολογισμούς αθροισμάτων με εύκολο τρόπο. Έπειτα είδαμε πώς διάφορες ταυτότητες μπορούν να αποδειχθούν με συνδυαστικό τρόπο, ερμηνεύοντας δηλ. τα δύο μέλη της ισότητας ως δύο διαφορετικούς τρόπους να μετρήσουμε την ίδια οικογένεια αντικειμένων.

Το μάθημα της Πέμπτης θα είναι αφιερωμένο στην απάντηση διαφόρων ερωτημάτων που έχετε, ενόψει και του διαγωνίσματος της Δευτέρας. Παρακαλώ ελάτε προετοιμασμένοι να κάνετε ερωτήσεις.

4.10 Πε, 26/10/11: Επαναληπτικές ασκήσεις

Σήμερα ασχοληθήκαμε αποκλειστικά με τη λύση διαφόρων ασκήσεων.

4.11 Δε, 31/10/11: Πρώτο διαγώνισμα

Σήμερα είχαμε το πρώτο διαγώνισμα. Μπορείτε εδώ να δείτε τα θέματα και τις λύσεις: Κομμάτι πολλαπλών επιλογών, Κομμάτι ολοκληρωμένων λύσεων.

Μπορείτε να δείτε τους βαθμούς του διαγωνίσματος (πολλαπλών επιλογών και συμβατικό διαγώνισμα) εδώ. Τα δύο μέρη συμμετέχουν εξίσου στο βαθμό του πρώτου διαγωνίσματος και το άριστα στο δεύτερο μέρος είναι το 30 (10 μονάδες για κάθε άσκηση). Οι βαθμοί του διαγωνίσματος πολλαπλών επιλογών, στο τέλος του εξαμήνου, θα μεγαλώσουν κατά τι λόγω της αρνητικής βαθμολογίας που υπάρχει για τις λάθος απαντήσεις. Με άλλα λόγια, η «βάση» για τα διαγωνίσματα πολλαπλών επιλογών δεν είναι το 5 αλλά ένας μικρότερος αριθμός. Το ποια θα είναι αυτή αποφασίζεται κάθε φορά στο τέλος του εξαμήνου.

4.12 Πέ, 3/11/11: Λύση των ασκήσεων του 1ου διαγωνίσματος

Σήμερα είδαμε τις λύσεις για τις ασκήσεις του 1ου διαγωνίσματος.

4.13 Δε, 7/11/11: Η έννοια του γραφήματος

Σήμερα κάναμε μια σύντομη εισαγωγή στην έννοια του απλού γραφήματος (καλύψαμε σχεδόν τις §4.1-4.3). Είδαμε αρκετά παραδείγματα και θεωρήματα.

4.14 Πέ, 10/11/11: Ισομορφία γραφημάτων

Σήμερα είδαμε αρκετά παραδείγματα γραφημάτων που είναι ισόμορφα μεταξύ τους, όπως επίσης και παραδείγματα μη ισόμορφων γραφημάτων και το πώς μπορεί κανείς να αποδείξει ότι όντως δεν είναι ισόμορφα.

4.14.1 ΑΝΑΚΟΙΝΩΣΗ: Καθυστερήσεις στη λύση ασκήσεων που έχετε αναλάβει

Παρακαλώ πολύ όσους έχουν αναλάβει ασκήσεις από τα Κεφ. 1 και 2 να μου έχουν φέρει τις λύσεις τους μέχρι και το τέλος αυτής της εβδομάδας, δηλ. μέχρι την Παρασκευή 18/11/11. Το όνομα όσων δε μου φέρουν τις λύσεις τους μέχρι τότε θα διαγραφεί από τις αντίστοιχες άλυτες ασκήσεις ώστε να μπορεί να τις αναλάβει όποιος άλλος θέλει.

4.15 Δε, 14/11/11: Συνεκτικότητα, αποστάσεις σε γραφήματα, δέντρα

Σήμερα καλύψαμε τις §4 και §5 του Κεφ. 4 από τις σημειώσεις.

Παρακαλώ αρχίστε από τώρα να μελετάτε εντατικά το υλικό αυτό και, κυρίως, να λύνετε τις ασκήσεις μια και απομένουν μόνο δύο συναντήσεις μέχρι το επόμενο διαγώνισμα που θα καλύψει περίπου το 2ο μισό του Κεφ. 3 και ολόκληρο το Κεφ. 4. (Εννοείται ότι και τα προηγούμενα θεωρούνται γνωστά, απλά το βάρος θα είναι σε αυτά που γράφω.)

4.16 Πέ, 17/11/11: Αργία

Δεν έγινε μάθημα σήμερα λόγω αργίας.

4.16.1 ΑΝΑΚΟΙΝΩΣΗ: Όχι ώρες γραφείου την Τρίτη 22/11/11

Λόγω συμμετοχής μου σε κάποια επιτροπή του Πανεπιστημίου δε θα γίνουν οι ώρες γραφείου μου την Τρίτη 22/11/11.

4.17 Δε, 21/11/11: Δέντρα. Πίνακας συνδεσμολογίας.

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

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

Διατυπώσαμε τον αλγόριθμο Floyd-Warshall για την εύρεση αποστάσεων σε γραφήματα με βάρη στις ακμές και αποδείξαμε ότι όντως υπολογίζει αυτό που θέλουμε.

4.18 Πέ, 24/11/11: Ο αλγόριθμος του Kruskal

Σήμερα είδαμε τον αλγόριθμο του Kruskal για εύρεση ενός δέντρου που παράγει ένα γράφημα με βάρη $G$ και το οποίο έχει το ελάχιστο συνολικό βάρος (άθροισμα των βαρών των ακμών του). «Τρέξαμε» τον αλγόριθμο σε ένα παράδειγμα και τέλος αποδείξαμε την ορθότητά του, ότι δηλ. αυτό που υπολογίζει είναι αυτό που ζητάμε.

Σήμερα τελειώσαμε το Κεφ. 4 των σημειώσεων.

4.18.1 ΑΝΑΚΟΙΝΩΣΗ: Δεύτερο διαγώνισμα

Το δεύτερο διαγώνισμα θα γίνει τη Δευτέρα 28/11, 7-9μμ, στα Αμφ. ΒΞ και ΣΠ. Εκείνη τη μέρα δε θα γίνει το μάθημα 5-7μμ.

Το διαγώνισμα θα αποτελείται από ένα κομμάτι με ερωτήσεις πολλαπλών επιλογών και ένα κομμάτι με μερικά ερωτήματα τα οποία θα πρέπει να απαντήσετε αναλυτικά. Θα υπάρχει ένα ολιγόλεπτο διάλειμμα ανάμεσα στα δύο κομμάτια.

4.19 Δε, 28/11/11: Δεύτερο Διαγώνισμα

Έγινε σήμερα το δεύτερο διαγώνισμα του εξαμήνου.

Το δεύτερο μέρος του διαγωνίσματος (συμβατικό διαγώνισμα) είναι εδώ μαζί με τις λύσεις.

4.20 Πε, 1/12/11: Λύσεις ασκήσεων του 2ου διαγωνίσματος

Σήμερα λύσαμε τις ασκήσεις πολλαπλών επιλογών του 2ου διαγωνίσματος.

4.20.1 ΑΝΑΚΟΙΝΩΣΗ: Βαθμοί δεύτερου διαγωνίσματος

Βρίσκονται εδώ.

4.21 Δε, 5/12/11: Διμερή γραφήματα

Εισαγωγή στα διμερή γραφήματα.

4.22 Πέ, 8/12/11: Διμερή γραφήματα

Χαρακτηρισμοί διμερών γραφημάτων. Έχουμε καλύψει μέχρι και την §1 του Κεφ. 5.

4.22.1 ΑΝΑΚΟΙΝΩΣΗ: Τελικό Διαγώνισμα

Θα γίνει 17:00-20:00 στις 18 Ιανουαρίου 2012.

4.23 Δε, 12/12/11: Ταιριάσματα σε διμερή γραφήματα και το θεώρημα του Hall

Μιλήσαμε για ταιριάσματα σε διμερή γραφήματα και αποδείξαμε το θεώρημα του Hall (θεώρημα του γάμου) που περιγράφει ακριβώς πότε υπάρχει ένα πλήρες ταίριασμα σε ένα διμερές γράφημα. Διαβάστε την απόδειξη του θεωρήματος από το Κεφ. 1, §3, στην ισοδύναμη μορφή που αφορά συστήματα ξένων αντιπροσώπων σε οικογένειες συνόλων.

4.24 Πέ, 15/11/11: Παραλλαγές και εφαρμογές του θεωρήματος του Hall

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

Λύσαμε την Άσκηση 5.14 (αν δεν υπάρχει στις σημειώσεις σας ξανακατεβάστε τις από την ιστοσελίδα γιατί προστέθηκε σχετικά πρόσφατα) και κάναμε και μια επίδειξη με μια τράπουλα εύρεσης της κατάλληλης επιλογής φύλλων με την ιδιότητα που λέει η άσκηση. Είδαμε ότι, παρότι είμαστε σίγουροι για την ύπαρξη αυτής της επιλογής, δεν είναι εύκολο να τη βρούμε. Θα δούμε την ερχόμενη εβδομάδα τρόπους για εύρεση μεγίστων ταιριασμάτων σε διμερή γραφήματα.

4.25 Δε, 19/12/11: Μέγιστα ταιριάσματα, επαυξάνοντα μονοπάτια και το Θεώρημα König-Egervary

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

Έπειτα διατυπώσαμε το Θεώρημα König-Egervary και είδαμε μια εφαρμογή του. Δεν αποδείξαμε το θεώρημα αυτό.

4.25.1 ΑΝΑΚΟΙΝΩΣΗ: Ύλη τελικού διαγωνίσματος

Θα είναι ό,τι διδάχθηκε στο μάθημα ολόκληρο το εξάμηνο.

4.26 Πέ, 22/12/11: Το θεώρημα König-Egervary

Αποδείξαμε το θεώρημα König-Egervary.

4.27 Τε, 18/1/2012: Τρίτο Διαγώνισμα

Το τρίτο διαγώνισμα μπορείτε να το δείτε εδώ σε μορφή PDF.

Οι τελικοί βαθμοί περιόδου Ιανουαρίου είναι εδώ σε μορφή PDF, και η αναλυτική βαθμολογία του εξαμήνου είναι εδώ σε μορφή xls.

4.28 Πέ, 13/9/12: Διαγώνισμα Σεπτεμβρίου

Το διαγώνισμα Σεπτεμβρίου θα γίνει την Τετάρτη, 19/9/2012, ώρα 9:00, στις αίθουσες ΡΑ 101, ΡΑ 103 και ΡΑ 105.

Το διαγώνισμα δε θα είναι με ερωτήσεις πολλαπλών επιλογών αλλά με συμβατικά θέματα.

4.29 Κυ, 23/9/12: Αποτελέσματα Σεπτεμβρίου

Το διαγώνισμα είναι εδώ σε μορφή PDF και τα αποτελέσματα εδώ σε μορφή PDF.



Mihalis Kolountzakis 2012-09-23