έχει ένα
σύνολο με 
στοιχεία. Αυτό τον αριθμό τον συμβολίζουμε με 
(διαβάζουμε « ανά »)
και τον υπολογίσαμε ακριβώς στην §2.2. Είδαμε επίσης πολλά παραδείγματα και ασκήσεις από την §2.2.
Δευτέρα 5-7, Πέμπτη 4-5 στο Αμφιθέατρο ΣΠ. Έναρξη μαθημάτων: 26/9/11.
Ώρες γραφείου: Τρίτη 10-12 και γενικά μπορείτε να με βρίσκετε τα πρωινά 10-12 στο γραφείο μου (Γ 111, στο προκατασκευασμένο κτήριο της Κνωσού).
Από τον οδηγό σπουδών:
Σκοπός του μαθήματος είναι η εισαγωγή στη συνδυαστική, τη θεωρία γραφημάτων, δένδρων και δικτύων.
Περιεχόμενα:
Δείτε επίσης την ιστοσελίδα του μαθήματος όπως το δίδαξα το 2010-11.
Θα γίνουν τρία υποχρεωτικά διαγωνίσματα κατά τη διάρκεια του εξαμήνου (συμπεριλαμβανομένου του «τελικού»).
Δίδεται η δυνατότητα σε όσους αδυνατούν να δώσουν τις υποχρεωτικές εξετάσεις μέσα στο εξάμηνο να ζητήσουν να βαθμολογηθούν μόνο από το τελικό διαγώνισμα. Αυτό είναι εφικτό όταν:
Κατά τη διάρκεια του εξαμήνου, και σε εθελοντική βάση, κάποιοι από σας θα αναλάβουν να γράφουν τις λύσεις για κάποιες από τις ασκήσεις που θα γίνονται στο μάθημα:
Μπορείτε να βλέπετε τις ασκήσεις προς λύση (και τις λύσεις τους) εδώ.
Η σελίδα αυτή θα ενημερώνεται τουλάχιστον μετά από κάθε μάθημα και σκοπό έχει να μεταδίδει μερικές βασικές χρήσιμες πληροφορίες για το περιεχόμενο του μαθήματος (π.χ. τι να προσέξετε, υποδείξεις για λύσεις των ασκήσεων, κ.ά.) καθώς και για διαδικαστικά θέματα.
Σπανίως θα βγαίνουν ανακοινώσεις που αφορούν το μάθημα σε χαρτί. Παρακαλώ να συμβουλεύεστε αυτή τη σελίδα τουλάχιστον 2-3 φορές την εβδομάδα.
Είδαμε τα βασικά για τη μέθοδο της επαγωγής και πολλά παραδείγματα. Διαβάστε την §1 (Κεφ. 1) και λύστε όσο μπορείτε περισσότερες ασκήσεις από κει.
Το πρώτο διαγώνισμα θα γίνει στα Αμφ. ΒΞ και ΣΠ, 7-9μμ, στις 31 Οκτωβρίου 2011. Εκείνη τη μέρα δε θα γίνει το μάθημα 5-7μμ.
Το δεύτερο διαγώνισμα θα γίνει στα Αμφ. ΒΞ και ΣΠ, 7-9μμ, στις 28 Νοεμβρίου 2011. Εκείνη τη μέρα δε θα γίνει το μάθημα 5-7μμ.
Είδαμε σήμερα μερικά παραδείγματα ακόμη (ασκήσεις από την §1) όπως και την §2 (ισχυρή επαγωγή).
Έχουν αναρτηθεί εδώ.
Σήμερα είδαμε διάφορα ακόμη παραδείγματα μαθηματικής επαγωγής. Είδαμε τη μέθοδο της «μπρος-πίσω» επαγωγής (§2.1) όπως και το ότι μπορεί κανείς να χρειαστεί να ενισχύσει την πρότασή του ώστε να μπορεί να την αποδείξει με επαγωγή (§2.3).
Από το Κεφ. 1 μπορείτε να παραλείψετε την §2.2 (πολλαπλή επαγωγή). Την παράγραφο §3 θα τη δούμε αργότερα όταν θα κάνουμε διμερή γραφήματα.
Λύστε επίσης και το Πρότυπο Διαγώνισμα στο τέλος του Κεφ. 1.
Αρχίσαμε να βλέπουμε τα βασικά στοιχεία της απαρίθμησης. Από το Κεφ. 2 είδαμε μέχρι την §2.1.
Θα είμαι στο γραφείο μου την Τρίτη μέχρι τις 11πμ μόνο λόγω συμμετοχής μου σε έκτακτη συνεδρίαση.
Σήμερα είδαμε διάφορα παραδείγματα ασκήσεων μέσα από τις σημειώσεις (κυρίως από την §2) και παραλλαγές αυτών.
Σήμερα είδαμε διάφορες περιπτώσεις μετρήματος όπου η σειρά του αποτελέσματος δεν έχει σημασία.
Ένα τυπικό παράδειγμα τέτοιου μετρήματος είναι το να μετρήσουμε πόσα υποσύνολα μεγέθους έχει ένα
σύνολο με στοιχεία. Αυτό τον αριθμό τον συμβολίζουμε με (διαβάζουμε « ανά »)
και τον υπολογίσαμε ακριβώς στην §2.2. Είδαμε επίσης πολλά παραδείγματα και ασκήσεις από την §2.2.
Είδαμε και σήμερα διάφορα παραδείγματα και ασκήσεις προς το τέλος του Κεφ. 2, το οποίο μπορούμε να θεωρήσουμε ότι κλείσαμε σήμερα. Πήραμε επίσης και μια πρόγευση του διωνυμικού θεωρήματος και της απόδειξής του καθώς και διαφόρων συνδυαστικών αποδείξεων για κάποιες ταυτότητες.
Σήμερα είδαμε το κεντρικό αποτέλεσμα της παραγράφου §3.1, ένα τύπο δηλ. που μας λέει
με πόσους τρόπους μπορούμε να επιλέξουμε αντικείμενα από διαφορετικά αντικείμενα,
όταν κάθε αντικείμενο μπορεί να επιλεγεί και παραπάνω από 1 φορά. Ο τύπος είναι
σε άθροισμα 
προσθετέων.
Λύσαμε διάφορες ασκήσεις από την §3.1.
Είδαμε σήμερα τους πολυωνυμικού συντελεστές (§3.2) που αποτελούν γενίκευση των διωνυμικών συντελεστών
. Επίσης αποδείξαμε (ξανά) το διωνυμικό θεώρημα (Θ. 3.4) και με επαγωγή ως προς .
Στην πορεία αποδείξαμε με συνδυαστικό επιχείρημα τον τύπο στον οποίο το λεγόμενο
τρίγωνο του Pascal
οφείλει την ύπαρξή του:
Το πρώτο διαγώνισμα θα γίνει τη Δευτέρα 31/10, 7-9μμ, στα Αμφ. ΒΞ και ΣΠ. Εκείνη τη μέρα δε θα γίνει το μάθημα 5-7μμ.
Το διαγώνισμα θα αποτελείται από ένα κομμάτι με ερωτήσεις πολλαπλών επιλογών και ένα κομμάτι με μερικά ερωτήματα τα οποία θα πρέπει να απαντήσετε αναλυτικά. Θα υπάρχει ένα ολιγόλεπτο διάλειμμα ανάμεσα στα δύο κομμάτια.
Μπορείτε να δείτε εδώ το αντίστοιχο περυσινό διαγώνισμα (μαζί με τις λύσεις) ώστε να πάρετε μια ιδέα τι να περιμένετε. Ο αριθμός των προβλημάτων δε θα είναι κατ' ανάγκη ο ίδιος με πέρυσι.
Σήμερα τελειώσαμε το υπόλοιπο του Κεφ. 3. Είδαμε κατ' αρχήν πώς μπορεί το διωνυμικό θεώρημα να εφαρμοστεί με διάφορους τρόπους ώστε να μας δώσει διάφορους υπολογισμούς αθροισμάτων με εύκολο τρόπο. Έπειτα είδαμε πώς διάφορες ταυτότητες μπορούν να αποδειχθούν με συνδυαστικό τρόπο, ερμηνεύοντας δηλ. τα δύο μέλη της ισότητας ως δύο διαφορετικούς τρόπους να μετρήσουμε την ίδια οικογένεια αντικειμένων.
Το μάθημα της Πέμπτης θα είναι αφιερωμένο στην απάντηση διαφόρων ερωτημάτων που έχετε, ενόψει και του διαγωνίσματος της Δευτέρας. Παρακαλώ ελάτε προετοιμασμένοι να κάνετε ερωτήσεις.
Σήμερα ασχοληθήκαμε αποκλειστικά με τη λύση διαφόρων ασκήσεων.
Σήμερα είχαμε το πρώτο διαγώνισμα. Μπορείτε εδώ να δείτε τα θέματα και τις λύσεις: Κομμάτι πολλαπλών επιλογών, Κομμάτι ολοκληρωμένων λύσεων.
Μπορείτε να δείτε τους βαθμούς του διαγωνίσματος (πολλαπλών επιλογών και συμβατικό διαγώνισμα) εδώ. Τα δύο μέρη συμμετέχουν εξίσου στο βαθμό του πρώτου διαγωνίσματος και το άριστα στο δεύτερο μέρος είναι το 30 (10 μονάδες για κάθε άσκηση). Οι βαθμοί του διαγωνίσματος πολλαπλών επιλογών, στο τέλος του εξαμήνου, θα μεγαλώσουν κατά τι λόγω της αρνητικής βαθμολογίας που υπάρχει για τις λάθος απαντήσεις. Με άλλα λόγια, η «βάση» για τα διαγωνίσματα πολλαπλών επιλογών δεν είναι το 5 αλλά ένας μικρότερος αριθμός. Το ποια θα είναι αυτή αποφασίζεται κάθε φορά στο τέλος του εξαμήνου.
Σήμερα είδαμε τις λύσεις για τις ασκήσεις του 1ου διαγωνίσματος.
Σήμερα κάναμε μια σύντομη εισαγωγή στην έννοια του απλού γραφήματος (καλύψαμε σχεδόν τις §4.1-4.3). Είδαμε αρκετά παραδείγματα και θεωρήματα.
Σήμερα είδαμε αρκετά παραδείγματα γραφημάτων που είναι ισόμορφα μεταξύ τους, όπως επίσης και παραδείγματα μη ισόμορφων γραφημάτων και το πώς μπορεί κανείς να αποδείξει ότι όντως δεν είναι ισόμορφα.
Παρακαλώ πολύ όσους έχουν αναλάβει ασκήσεις από τα Κεφ. 1 και 2 να μου έχουν φέρει τις λύσεις τους μέχρι και το τέλος αυτής της εβδομάδας, δηλ. μέχρι την Παρασκευή 18/11/11. Το όνομα όσων δε μου φέρουν τις λύσεις τους μέχρι τότε θα διαγραφεί από τις αντίστοιχες άλυτες ασκήσεις ώστε να μπορεί να τις αναλάβει όποιος άλλος θέλει.
Σήμερα καλύψαμε τις §4 και §5 του Κεφ. 4 από τις σημειώσεις.
Παρακαλώ αρχίστε από τώρα να μελετάτε εντατικά το υλικό αυτό και, κυρίως, να λύνετε τις ασκήσεις μια και απομένουν μόνο δύο συναντήσεις μέχρι το επόμενο διαγώνισμα που θα καλύψει περίπου το 2ο μισό του Κεφ. 3 και ολόκληρο το Κεφ. 4. (Εννοείται ότι και τα προηγούμενα θεωρούνται γνωστά, απλά το βάρος θα είναι σε αυτά που γράφω.)
Δεν έγινε μάθημα σήμερα λόγω αργίας.
Λόγω συμμετοχής μου σε κάποια επιτροπή του Πανεπιστημίου δε θα γίνουν οι ώρες γραφείου μου την Τρίτη 22/11/11.
Είδαμε διάφορες ισοδύναμες συνθήκες που χαρακτηρίζουν ένα γράφημα ως δέντρο.
Ορίσαμε τον πίνακα συνδεσμολογίας ενός απλού γραφήματος ή ενός γραφήματος με βάρη στις ακμές και δείξαμε ότι οι δυνάμεις του πίνακα συνδεσμολογίας ενός απλού γραφήματος έχουν μια πολύ συγκεκριμένη ερμηνεία σε σχέση με το πλήθος των μονοπατιών ορισμένου μήκους που συνδέουν δύο κορυφές.
Διατυπώσαμε τον αλγόριθμο Floyd-Warshall για την εύρεση αποστάσεων σε γραφήματα με βάρη στις ακμές και αποδείξαμε ότι όντως υπολογίζει αυτό που θέλουμε.
Σήμερα είδαμε τον αλγόριθμο του Kruskal για εύρεση ενός δέντρου που παράγει ένα γράφημα
με βάρη 
και το οποίο έχει το ελάχιστο συνολικό βάρος (άθροισμα των βαρών των ακμών του).
«Τρέξαμε» τον αλγόριθμο σε ένα παράδειγμα και τέλος αποδείξαμε την ορθότητά του, ότι δηλ. αυτό που
υπολογίζει είναι αυτό που ζητάμε.
Σήμερα τελειώσαμε το Κεφ. 4 των σημειώσεων.
Το δεύτερο διαγώνισμα θα γίνει τη Δευτέρα 28/11, 7-9μμ, στα Αμφ. ΒΞ και ΣΠ. Εκείνη τη μέρα δε θα γίνει το μάθημα 5-7μμ.
Το διαγώνισμα θα αποτελείται από ένα κομμάτι με ερωτήσεις πολλαπλών επιλογών και ένα κομμάτι με μερικά ερωτήματα τα οποία θα πρέπει να απαντήσετε αναλυτικά. Θα υπάρχει ένα ολιγόλεπτο διάλειμμα ανάμεσα στα δύο κομμάτια.
Έγινε σήμερα το δεύτερο διαγώνισμα του εξαμήνου.
Το δεύτερο μέρος του διαγωνίσματος (συμβατικό διαγώνισμα) είναι εδώ μαζί με τις λύσεις.
Σήμερα λύσαμε τις ασκήσεις πολλαπλών επιλογών του 2ου διαγωνίσματος.
Βρίσκονται εδώ.
Εισαγωγή στα διμερή γραφήματα.
Χαρακτηρισμοί διμερών γραφημάτων. Έχουμε καλύψει μέχρι και την §1 του Κεφ. 5.
Θα γίνει 17:00-20:00 στις 18 Ιανουαρίου 2012.
Μιλήσαμε για ταιριάσματα σε διμερή γραφήματα και αποδείξαμε το θεώρημα του Hall (θεώρημα του γάμου) που περιγράφει ακριβώς πότε υπάρχει ένα πλήρες ταίριασμα σε ένα διμερές γράφημα. Διαβάστε την απόδειξη του θεωρήματος από το Κεφ. 1, §3, στην ισοδύναμη μορφή που αφορά συστήματα ξένων αντιπροσώπων σε οικογένειες συνόλων.
Είδαμε διάφορες συνέπειες του θ. Hall, όπως το ότι κάθε κανονικό διμερές γράφημα έχει πλήρες ταίριασμα.
Λύσαμε την Άσκηση 5.14 (αν δεν υπάρχει στις σημειώσεις σας ξανακατεβάστε τις από την ιστοσελίδα γιατί προστέθηκε σχετικά πρόσφατα) και κάναμε και μια επίδειξη με μια τράπουλα εύρεσης της κατάλληλης επιλογής φύλλων με την ιδιότητα που λέει η άσκηση. Είδαμε ότι, παρότι είμαστε σίγουροι για την ύπαρξη αυτής της επιλογής, δεν είναι εύκολο να τη βρούμε. Θα δούμε την ερχόμενη εβδομάδα τρόπους για εύρεση μεγίστων ταιριασμάτων σε διμερή γραφήματα.
Είδαμε την έννοια του επαυξάνοντος μονοπατιού σε ένα διμερές γράφημα του οποίου έχουμε σταθεροποιήσει ένα ταίριασμα και αποδείξαμε ότι ένα ταίριασμα είναι μέγιστο αν και μόνο αν δεν έχει επαυξάνοντα μονοπάτια.
Έπειτα διατυπώσαμε το Θεώρημα König-Egervary και είδαμε μια εφαρμογή του. Δεν αποδείξαμε το θεώρημα αυτό.
Θα είναι ό,τι διδάχθηκε στο μάθημα ολόκληρο το εξάμηνο.
Αποδείξαμε το θεώρημα König-Egervary.
Το τρίτο διαγώνισμα μπορείτε να το δείτε εδώ σε μορφή PDF.
Οι τελικοί βαθμοί περιόδου Ιανουαρίου είναι εδώ σε μορφή PDF, και η αναλυτική βαθμολογία του εξαμήνου είναι εδώ σε μορφή xls.
Το διαγώνισμα Σεπτεμβρίου θα γίνει την Τετάρτη, 19/9/2012, ώρα 9:00, στις αίθουσες ΡΑ 101, ΡΑ 103 και ΡΑ 105.
Το διαγώνισμα δε θα είναι με ερωτήσεις πολλαπλών επιλογών αλλά με συμβατικά θέματα.
Το διαγώνισμα είναι εδώ σε μορφή PDF και τα αποτελέσματα εδώ σε μορφή PDF.