M119.CS Θεωρία Γραμμικού Προγραμματισμού

ΠΜΣ Πληροφορική (M119.CS) -- ΑΛΜΑ
Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Πανεπιστήμιο Αθηνών
Χειμερινό Εξάμηνο 2020-2021

Ώρες διδασκαλίας: Τρίτη 12:00-14:00, Τετάρτη 11:00-13:00, εξ αποστάσεως.
Διδάσκων: Σταύρος Κολλιόπουλος
Γραφείο: Β6, κτίριο Πληροφορικής
Email: id@host.uoa.gr όπου id sgk και host di
Ώρες επικοινωνίας: Με ραντεβού κατόπιν ηλ. επικοινωνίας.



ΕΝΑΡΞΗ ΜΑΘΗΜΑΤΩΝ: H πρώτη συνάντηση του μαθήματος θα πραγματοποιηθεί την Τρίτη 29/09. Θα χρησιμοποιηθεί η πλατφόρμα zoom. Όποιος ενδιαφέρεται αλλά δεν έχει γραφτεί ακόμα στη σελίδα του μαθήματος στο eclass, παρακαλείται να στείλει email στον διδάσκοντα με θέμα την ονομασία του μαθήματος και στο σώμα του μηνύματος να αναφέρει ονοματεπώνυμο, μεταπτυχιακό πρόγραμμα προέλευσης και προσωρινή ηλεκτρονική διεύθυνση επικοινωνίας.



Γενικές Πληροφορίες

Δημόσια Ιστοσελίδα μαθήματος: http://www.di.uoa.gr/~sgk/teaching/grad/LP/
Εδώ υπάρχουν γενικές πληροφορίες για το μάθημα και οι σημειώσεις. Υπάρχει και σελίδα στο eclass.uoa.gr στην οποία θα πρέπει όλοι οι ενδιαφερόμενοι να εγγραφούν. Για την εγγραφή είναι απαραίτητος λογαριασμός στο ΕΚΠΑ.

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

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

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

Μια ενδεικτική λίστα θεμάτων που θα μας απασχολήσουν. Συγγράμματα: Δεν θα ακολουθήσουμε αποκλειστικά ένα εγχειρίδιο. Ενδεικτικά αναφέρουμε τα παρακάτω πολύ καλά συγγράμματα:

Πολλές άλλες πηγές κάθε είδους είναι διαθέσιμες στο διαδίκτυο.



Διαδικαστικά

Εξετάσεις - Ασκήσεις - Βαθμολογία: Θα έχουμε κάποια σύνολα ασκήσεων και ένα τελικό διαγώνισμα. Το τελικό διαγώνισμα θα μετρήσει (100 -N*10)% στον τελικό βαθμό, όπου Ν >=3 το πλήθος των σετ ασκήσεων που θα δοθούν. Τα σετ δεν θα είναι απαραίτητα ισοδύναμα, o συνολικός βαθμός στις ασκήσεις θα υπολογιστεί ως (\sum_{i=1}^{N} d_i)/(\sum_{i=1}^{N} t_i), όπου d_i η επίδοση στο iστό σετ και t_i οι συνολικές μονάδες του iστού σετ.




Σημειώσεις

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

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

Διάλεξη 1: εισαγωγικοί ορισμοί (ανανέωση Wed Feb 10 16:56:29 EET 2021)
Διάλεξη 2: Θεώρημα Καραθεοδωρή, ακραία σημεία (ανανέωση Wed Feb 10 16:56:29 EET 2021)
Διάλεξη 3: ακραία σημεία, κορυφές, βασικές λύσεις (ανανέωση Wed Feb 3 17:26:45 EET 2021)
Διάλεξη 4: βασικές λύσεις πολυέδρων σε πρότυπη μορφή (ανανέωση Mon Dec 21 20:23:43 EET 2020)
Διάλεξη 5: εκφυλισμένες βασικές λύσεις, πολύεδρα χωρίς ακραία σημεία (ανανέωση Wed Feb 10 16:56:29 EET 2021)
Διάλεξη 6: ακραία σημεία και βελτιστοποίηση, απαλοιφή Fourier-Motzkin (ανανέωση Wed Oct 28 16:42:53 EET 2020)
Διάλεξη 7: προβολή πολυέδρων, Λήμμα Farkas (ανανέωση Fri Oct 30 17:18:15 EET 2020)
Διάλεξη 8: δυϊκότητα (ανανέωση Wed Feb 10 16:56:29 EET 2021)
Διάλεξη 9: δυϊκότητα (συνέχεια), Θεώρημα Minkowski-Weyl για κώνους (ανανέωση Wed Feb 10 16:56:29 EET 2021)
Διάλεξη 10: Θεώρημα Minkowski-Weyl για πολύεδρα, lineality space. (ανανέωση Thu Feb 11 14:27:05 EET 2021)
Διάλεξη 11: αφινικό κάλυμα και διάσταση πολυέδρου (ανανέωση Wed Dec 2 16:08:50 EET 2020)
Διάλεξη 12: παραδείγματα ακέραιων πολυτόπων, όψεις και έδρες πολυέδρων (ανανέωση Thu Dec 3 16:43:50 EET 2020)
Διαλέξεις 13 και 14: όψεις και έδρες (συνέχεια) (ανανέωση Wed Feb 10 16:56:29 EET 2021)
Διάλεξη 15: ελαχιστικές αναπαραστάσεις πολυέδρων(ανανέωση Wed Feb 10 16:56:29 EET 2021)
Διάλεξη 16: ελαχιστικές όψεις, αποσύνθεση πολυέδρων (ανανέωση Wed Feb 10 16:56:29 EET 2021)
Διάλεξη 17: το πολύτοπο των ταιριασμάτων (ανανέωση Wed Dec 2 16:08:50 EET 2020)
Διάλεξη 18: το πολύτοπο των ταιριασμάτων (συνέχεια) (ανανέωση Fri Dec 4 14:43:47 EET 2020)
Διάλεξη 19: θέματα Πολυπλοκότητας στον Ακέραιο Γραμμικό Προγραμματισμό (ανανέωση Wed Feb 10 16:56:29 EET 2021)
Διάλεξη 20: ακέραια πολύεδρα, Ολική Δυϊκή Ακεραιότητα (ανανέωση Wed Feb 10 16:56:29 EET 2021)
Διάλεξη 21: Ολική Δυϊκή Ακεραιότητα (συνέχεια) (ανανέωση Mon Dec 14 19:59:35 EET 2020)
Διάλεξη 22: υπολογισμοί σε πολύεδρα (ανανέωση Wed Feb 10 16:56:29 EET 2021)
Διάλεξη 23: πολικότητα, υπολογισμοί σε πολύεδρα (συνέχεια) (ανανέωση Wed Feb 10 16:56:29 EET 2021)


Ασκήσεις

Πρώτη άσκηση (δημοσίευση Mon Oct 12 12:44:26 EEST 2020, παράδοση 20.10.2020, ώρα 11:59 πμ )

Δεύτερη άσκηση (δημοσίευση Fri Oct 23 14:28:00 EEST 2020, παράδοση 03.11.2020, ώρα 11:59 πμ )

Τρίτη άσκηση (δημοσίευση Fri Nov 6 18:45:41 EET 2020, παράδοση 18.11.2020, ώρα 11:00 πμ )

Τέταρτη άσκηση (δημοσίευση Mon Nov 30 16:07:35 EET 2020, παράδοση 22.12.2020, ώρα 11:59 πμ )

Πέμπτη (προαιρετική) άσκηση (δημοσίευση Tue Dec 22 17:46:26 EET 2020, παράδοση 12.01.2021, ώρα 11:59 πμ )



http://www.di.uoa.gr/~sgk/teaching/grad/LP/index.html
Τελευταία ανανέωση: Thu Feb 11 14:27:05 EET 2021