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

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

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



ΕΝΑΡΞΗ ΜΑΘΗΜΑΤΩΝ: H πρώτη συνάντηση του μαθήματος θα πραγματοποιηθεί την Τρίτη 04.10.2022.



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

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

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

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

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

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

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



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

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

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

Δεν θα ανατεθεί παρουσίαση, ούτε θα σταλεί βαθμός για όσους/ες δεν έρχονται τακτικά, κατά την κρίση του διδάσκοντα, στις παραδόσεις ή για όσους/ες δεν συγκεντρώσουν το 60% της συνολικής βαθμολογίας στις ασκήσεις.




Σημειώσεις

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

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

Διάλεξη 1: εισαγωγικοί ορισμοί (ανανέωση Wed Feb 10 16:56:29 EET 2021)
Διάλεξη 2: Θεώρημα Καραθεοδωρή, ακραία σημεία (ανανέωση Fri Dec 23 16:59:26 EET 2022)
Διάλεξη 3: ακραία σημεία, κορυφές, βασικές λύσεις (ανανέωση Fri Dec 23 16:59:26 EET 2022)
Διάλεξη 4: βασικές λύσεις πολυέδρων σε πρότυπη μορφή (ανανέωση Fri Dec 23 16:59:26 EET 2022)
Διάλεξη 5: εκφυλισμένες βασικές λύσεις, πολύεδρα χωρίς ακραία σημεία (ανανέωση Fri Dec 23 16:59:26 EET 2022)
Διάλεξη 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 για κώνους (ανανέωση Fri Jan 20 14:32:20 EET 2023)
Διάλεξη 10: Θεώρημα Minkowski-Weyl για πολύεδρα, lineality space. (ανανέωση Mon Dec 5 18:47:40 EET 2022)
Διάλεξη 11: αφινικό κάλυμμα και διάσταση πολυέδρου (ανανέωση Wed Dec 2 16:08:50 EET 2020)
Διάλεξη 12: παραδείγματα ακέραιων πολυτόπων, όψεις και έδρες πολυέδρων (ανανέωση Thu Dec 3 16:43:50 EET 2020)
Διαλέξεις 13 και 14: όψεις και έδρες (συνέχεια) (ανανέωση Thu Nov 10 17:29:24 EET 2022)
Διάλεξη 15: ελαχιστικές αναπαραστάσεις πολυέδρων(ανανέωση Wed Feb 10 16:56:29 EET 2021)
Διάλεξη 16: ελαχιστικές όψεις, αποσύνθεση πολυέδρων (ανανέωση Wed Nov 23 10:30:17 EET 2022)
Διάλεξη 17: το πολύτοπο των ταιριασμάτων (ανανέωση Wed Dec 2 16:08:50 EET 2020)
Διάλεξη 18: το πολύτοπο των ταιριασμάτων (συνέχεια) (ανανέωση Fri Dec 4 14:43:47 EET 2020)
Διάλεξη 19: θέματα Πολυπλοκότητας στον Ακέραιο Γραμμικό Προγραμματισμό (ανανέωση Mon Dec 5 18:47:40 EET 2022)
Διάλεξη 20: ακέραια πολύεδρα, Ολική Δυϊκή Ακεραιότητα (ανανέωση Tue Dec 6 18:25:21 EET 2022)
Διάλεξη 21: Ολική Δυϊκή Ακεραιότητα (συνέχεια) (ανανέωση Mon Dec 14 19:59:35 EET 2020)
Διάλεξη 22: υπολογισμοί σε πολύεδρα (ανανέωση Fri Dec 23 16:59:26 EET 2022)
Διάλεξη 23: πολικότητα, υπολογισμοί σε πολύεδρα (συνέχεια) (ανανέωση Thu Jan 19 16:21:03 EET 2023)
Φυλλάδιο 01: ο αλγόριθμος simplex (ανανέωση Mon Dec 5 18:47:40 EET 2022)


Ασκήσεις

Δεν υπάρχουν ανακοινωμένες ασκήσεις.


http://www.di.uoa.gr/~sgk/teaching/grad/LP/index.html
Τελευταία ανανέωση: Fri Jan 20 14:32:20 EET 2023