Εδώ σε PDF.

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

Τετάρτη, 16 Σεπ, στις 13:00, στο Αμφ. Α.

Λόγω διακοπής ρεύματος αναβλήθηκε το προγραμματισμένο για σήμερα διαγώνισμα Σεπτεμβρίου.

Θα γίνει την ερχόμενη Τρίτη (15/9) ή Τετάρτη (16/9). Το πότε και που θα ανακοινωθεί τη Δευτέρα.

Advertisement

Είχαμε σήμερα το τρίτο και τελευταίο διαγώνισμα του εξαμήνου. Μπορείτε να δείτε τα αποτελέσματα εδώ.

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

Η τελική εξέταση του μαθήματος συμπίπτει με τις τελικές εξετάσεις των μαθημάτων «Πιθανότητες» (ΤΕΥ) και «Υγ. & Ασφ. Τροφίμων» (ΧΗΜ). Και στα δύο αυτά μαθήματα είναι γραμμένοι κάποιοι φοιτητές που παίρνουν και το μάθημα Διακριτά Μαθηματικά.

Οι φοιτητές αυτοί και μόνο αυτοί θα εξεταστούν χωριστά ως εξής:

Θα έρθουν στη Θ207 ακριβώς στις 12 το μεσημέρι και θα φύγουν ακριβώς στις 1 (δε θα μπορούν να φύγουν νωρίτερα). Αμέσως μετά θα αρχίσει η εξέταση του μαθήματος (στο Αμφ ΒΞ) για τους υπόλοιπους και περισσότερους φοιτητές. Οι φοιτητές που θα δώσουν το μάθημα νωρίτερα θα πρέπει αναγκαστικά να έχουν εγγραφεί σε ένα τουλάχιστον από τα προαναφερθέντα δύο μαθήματα και να πάνε να εξεταστούν σε αυτά μετά. Δεν επιτρέπεται σε άλλους να δώσουν το μάθημα 12-1.

Σημείωση: Για όσους φοιτητές χρειαστεί να μεταβούν στις Βούτες για την εξέταση του μαθήματος Χημείας έχει υπάρξει συνεννόηση με τον διδάσκοντα κ. Τσαγκατάκη ώστε να ξεκινήσουν την εξέτασή τους μισή ώρα αργότερα.

Λύσαμε μερικές ασκήσεις για κυκλώματα Euler και Hamilton καθώς και μερικές επαναληπτικές.

Θα υπάρξει κι άλλη συνάντηση στις 23/1/09, στη Θ207 από 12-2.

Σήμερα μιλήσαμε για μονοπάτια και κυκλώματα Euler και Hamilton. Διαβάστε το Κεφ 6 από τις σημειώσεις (ενημερωμένη έκδοση εδώ).

Καλή χρονιά.

Θα γίνει τα εξής έκτακτα μαθήματα:

Τρ, 13/1/09, 5-6 και Τε 14/1/09, 1-3 (Αμφ Α, όπως στη διάρκεια του εξαμήνου)

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

Σήμερα ασχοληθήκαμε με ιδιότητες των μεγίστων ταιριασμάτων σε διμερή γραφήματα. Σ’ ένα διμερές γράφημα δεν υπάρχει εν γένει πλήρες ταίριασμα (μιας πλευράς του) οπότε είναι λογικό να αναζητούμε όσο γίνεται μεγαλύτερα ταιριάσματα.

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

Έπειτα δείξαμε το θέωρημα Konig-Egervary που λέει ότι σ’ένα διμερές γράφημα το ένα μέγιστο ταίριασμα έχει τόσες ακμές όσες κορυφές έχει ένα ελάχιστο κάλυμμα κορυφών (ένα σύνολο κορυφών U λέγεται κάλυμμα αν κάθε ακμή του γραφήματος έχει τουλάχιστον ένα άκρο της στο U).

Τέλος επαναδιατυπώσαμε το Θ. Konig-Egervary στη γλώσσα πινάκων με στοιχεία 0 ή 1.

Σήμερα αποδείξαμε την εξής γενίκευση του θεωρήματος του Hall:

Αν είναι A_1, A_2, \ldots \subseteq X πεπερασμένα υποσύνολα του X που πληρούν τη συνθήκη του Hall:

Για κάθε πεπερασμένο σύνολο J \subseteq \{1,2,\ldots\} ισχύει

\displaystyle {\left|\bigcup_{j\in J} A_j\right| \ge |J|},

τότε υπάρχουν x_1 \in A_1, x_2 \in A_2, \ldots, τα x_j όλα διαφορετικά μεταξύ τους.

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

Χωρίς σχόλια …

ΠΡΑΚΤΙΚΑ 610ης/08.12.2008 ΕΚΤΑΚΤΗΣ ΣΥΝΕΔΡΙΑΣ ΤΟΥ
ΠΡΥΤΑΝΙΚΟΥ ΣΥΜΒΟΥΛΙΟΥ ΤΟΥ ΠΑΝΕΠΙΣΤΗΜΙΟΥ ΚΡΗΤΗΣ


Θέματα Ακαδημαϊκά

Θέμα  «Διακοπή της θεσμικής λειτουργίας του Πανεπιστημίου
Κρήτης για τις ημέρες 9 και 10 Δεκεμβρίου 2008»

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

Α π ο φ α σ ί ζ ε ι


Να διακόψει την θεσμική λειτουργία του Πανεπιστημίου Κρήτης για τις ημέρες 9 και 10 Δεκεμβρίου 2008, τιμώντας έτσι στο ελάχιστο, τον αδικοχαμένο μαθητή Αλέξη Γρηγορόπουλο. Παράλληλα, αναλαμβάνει πρωτοβουλίες για ειρηνικές παρεμβάσεις και συζητήσεις ούτως ώστε να κατανοήσουμε ότι η καταστολή της βίας δεν γίνεται με βία αλλά με εμπέδωση και εμβάθυνση της δημοκρατίας σε όλους τους θεσμούς. Το δικαίωμα της ειρηνικής αμφισβήτησης, της ελευθερίας γνώμης και της ελεύθερης διακίνησης των ιδεών, είναι η προϋπόθεση για μια ειρηνική
και ελεύθερη κοινωνία.

Ακριβές απόσπασμα
Ρέθυμνο, 08.12.2008
Η Γραμματέας
του Πρυτανικού Συμβουλίου
Φωτεινή Μαμαλάκη

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

Η ικανή και αναγκαία συνθήκη γι’ αυτό είναι η λεγόμενη συνθήκη του Hall. Δείξαμε το θεώρημα του Γάμου (παρ. 1.3) που, σε γλώσσα συνολοθεωρητική, λέει το εξής:

Αν είναι X ένα σύνολο και {{\mathcal F} = \{A_1, \dots, A_n\},\ A_j \subseteq X} ένα σύστημα n πεπερασμένων υποσυνόλων του X με την ιδιότητα

\displaystyle{\forall J \subseteq \{1,2,\ldots,n\} \ \ \left| \sum_{j \in J} A_j \right| \ge |J| } (λέγεται συνθήκη του Hall)

τότε υπάρχουν {x_1 \in A_1, \ldots, x_n \in A_n} που είναι όλα διαφορετικά μεταξύ τους. (Τα x_j λέγονται σύστημα ξένων αντιπροσώπων για τα A_j.)

Διαβάστε τις παραγράφους 1.3, 5.1 (την έχουμε κάνει σχεδόν πλήρως παλιότερα) και 5.3 (σχεδόν όλη).

Για να ακονίσετε το μυαλό σας προσπαθήσετε να αποδείξετε την εξής γενίκευση του θεωρήματος του Γάμου:

το n επιτρέπεται να είναι άπειρο και όλα τα άλλα παραμένουν τα ίδια (η συνθήκη του Hall, και το συμπέρασμα του θεωρήματος). Τα A_j εξακολουθούν να είναι πεπερασμένα σύνολα.

Εϊδαμε τον αλγόριθμο Floyd-Warshall ο οποίος υπολογίζει για ένα γράφημα με βάρη στις ακμές (τα οποία παριστάνουν, π.χ., το μήκος μιας ακμής) την απόσταση {d(u,v)} για κάθε δύο κορυφές {u, v \in V} (το σύνολο κορυφών).

Διαβάστε την παρ. 4.8.

Την Τετάρτη 3/12/08 θα κάνουμε μάθημα μόνο την πρώτη ώρα 1-2. Αυτό οφείλεται σε υποχρέωση μου να παρευρίσκομαι σε μια συνεδρίαση εκλεκτορικού σώματος ΔΕΠ στις 2.

Αναπληρώσεις μαθημάτων θα γίνουν κατά πάσα πιθανότητα μετά τις διακοπές των Χριστουγέννων.

Δοκιμάστε τις ικανότητές σας σε αυτό το διαγώνισμα. (Οι απαντήσεις εδώ αλλά μην τις κοιτάξετε πριν το λύσετε.)

Κατ’ αρχήν λύσαμε τις ασκήσεις του 2ου διαγωνίσματος.

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

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

Διαβάστε τις παραγράφους 4.6 και 4.7.

Είχαμε σήμερα το δεύτερό μας διαγώνισμα. Μπορείτε να δείτε τα αποτελέσματα εδώ σε μορφή PDF.

Από την Κοσμητεία της Σχολής:

ΠΡΟΣ

όλα τα μέλη της

Πανεπιστημιακής Κοινότητας

του προκατασκευασμένου κτιρίου

της λ. Κνωσού

Αγαπητά μέλη της Πανεπιστημιακής Κοινότητας,

Με λύπη μου σας ανακοινώνω ότι λόγω εκτάκτου ανάγκης, θα γίνει ΑΝΑΣΤΟΛΗ ΤΗΣ ΛΕΙΤΟΥΡΓΙΑΣ της Σχολής Θετικών και Τεχνολογικών Επιστημών στο ΠΡΟΚΑΤΑΣΚΕΥΑΣΜΕΝΟ ΚΤΙΡΙΟ της λ. Κνωσού, την ΤΡΙΤΗ 25 ΝΟΕΜΒΡΙΟΥ, λόγω επείγουσας ανάγκης για την επισκευή του δικτύου ύδρευσης.

Δεν θα υπάρχει νερό σε κανένα σημείο του προκατασκευασμένου κτιρίου (δηλαδή ούτε στο εστιατόριο, ούτε στο κυλικείο).

Ελπίζω ότι η βλάβη θα αποκατασταθεί εντός μίας ημέρας.

Κυλάφης Νικόλαος,

Κοσμήτωρ Σχολής Θετικών και

Τεχνολογικών Επιστημών

Λύσαμε τις υπόλοιπες ασκήσεις του 2ου φυλλαδίου και απάντησα σε διάφορες ερωτήσεις.

Είδαμε την έννοια του χρωματισμού κορυφών και του χρωματισμού ακμών ενός γραφήματος καθώς και τους αντίστοιχους χρωματικούς αριθμούς {\chi(G), \chi'(G)}.

Λύσαμε τις ασκήσεις 3-5 του 2ου φυλλαδίου ασκήσεων. Επίσης δείξαμε το θεώρημα του Koenig (1916), που λέει ότι για G διμερές γράφημα ισχύει \chi'(G) = \Delta(G) (ο χρωματικός αριθμός ακμών ισούται με το μέγιστο βαθμό).

Ορίσαμε και είδαμε τις ιδιότητες του πίνακα συνδεσμολογίας ενός απλού γραφήματος G, που είναι ένας {n \times n} πίνακας A με στοιχεία 0 ή 1 (n είναι το πλήθος των κορυφών του G) με {A_{ij} = 1} αν και μόνο αν η ακμή \{i,j\} υπάρχει στο γράφημα. Είδαμε κάποιες ιδιότητες των δυνάμεων A^k του πίνακα για {k\ge 1}.

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

Την Πέμπτη 20/11/08 στο Αμφ Α, 7-9 το βράδυ.

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

Σήμερα λύσαμε διάφορες ασκήσεις από τις παραγράφους \S4.4 και \S4.5.

Είδαμε τον ορισμό του δέντρου (συνεκτικό γράφημα χωρίς κύκλους). Έπειτα είδαμε ότι κάθε συνεκτικό γράφημα έχει ένα υπογράφημα που είναι δέντρο και περιέχει όλες τις κορυφές του αρχικού γραφήματος («δέντρο που παράγει το γράφημα», spanning tree). Τέλος δείξαμε ότι ένα δέντρο με n κορυφές έχει πάντα n-1 ακμές και ότι ένα συνεκτικό γράφημα με n κορυφές και n-1 ακμές είναι αναγκαστικά δέντρο. Καλύψαμε σχεδόν την \S 4.5.

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

Διαβάστε την \S 4.4 και λύστε τις ασκήσεις 4.19-4.24.

Λόγω απουσίας μου το μάθημα της Τετάρτης 12/11/2008 δε θα γίνει.

Υπενθυμίζεται επίσης ότι η 11/11/2008 είναι αργία για το Πανεπιστήμιο στο Ηράκλειο.

Συνεχίσαμε σήμερα την εισαγωγή μας στην έννοια του γραφήματος. Είδαμε μερικές κατηγορίες γραφημάτων (διμερή, πλήρη, κύκλους, πλήρη διμερή, κ.ά.) και λύσαμε μερικές ασκήσεις. Διαβάστε την παράγραφο \S4.3 και λύστε τις ασκήσεις που είναι εκεί.

Λύσαμε μερικές από τις ασκήσεις του προηγούμενου διαγωνίσματος.

Αρχίσαμε την εισαγωγή μας στη θεωρία των γραφημάτων. Διαβάστε τις \S 4.1 και 4.2 και λύστε όλες τις ασκήσεις που περιέχονται εκεί (τις πιο πολλές τις έχουμε ήδη λύσει στο μάθημα).

Θα ήθελα να διευκρινίσω ότι, όσον αφορά τους βαθμούς του διαγωνίσματος, οι οποίοι σας ανακοινώθηκαν στην κλίμακα 0-10, η βάση δε βρίσκεται στο 5, και αυτό επειδή υπάρχει και αρνητική βαθμολόγηση για τις λάθος απαντήσεις. Για παράδειγμα, εάν αυτό ήταν το μόνο διαγώνισμα από το οποίο θα σας έκρινα για να περάσετε ή όχι το μάθημα τότε θα πέρναγαν αυτοί που είχαν από 4 και πάνω (στην κλίμακα 0-10) και ίσως και κάτι λιγότερο.

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