M153: Γραμμικός και μη Γραμμικός Προγραμματισμός

ΠΜΣ (Μ153) -- ΜΠΛΑ -- ΑΛΜΑ
Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Πανεπιστήμιο Αθηνών
Συνδιδασκαλία με το μάθημα Θεωρία Γραμμικού Προγραμματισμού των ΜΠΛΑ/ΑΛΜΑ
Χειμερινό Εξάμηνο 2016-2017

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







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

Ιστοσελίδα μαθήματος:

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

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

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

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

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

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



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

Εξετάσεις - Ασκήσεις - Βαθμολογία:

Θα έχουμε κάποια σύνολα ασκήσεων (με συντελεστή 15% το κάθε σετ), και ένα τελικό διαγώνισμα. Το τελικό διαγώνισμα θα μετρήσει (90 -Χ*15)% στον τελικό βαθμό, όπου Χ το πλήθος των ασκήσεων. Για το υπόλοιπο 10% του συνολικού βαθμού θα μετρήσει η παρουσία και η συμμετοχή στην τάξη.

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




Σημειώσεις

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

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

Διάλεξη 1: εισαγωγικοί ορισμοί
Διάλεξη 2: Θεώρημα Καραθεοδωρή, ακραία σημεία
Διάλεξη 3: Ακραία σημεία, κορυφές, βασικές λύσεις
Διάλεξη 4
Διάλεξη 5
Διάλεξη 6: ακραία σημεία και βελτιστοποίηση, απαλοιφή Fourier-Motzkin
Διάλεξη 7: προβολή πολυέδρων, Λήμμα Farkas
Διάλεξη 8: δυϊκότητα
Διάλεξη 9: δυϊκότητα (συνέχεια), Θεώρημα Minkowski-Weyl για κώνους.
Διάλεξη 10: Θεώρημα Minkowski-Weyl για πολύεδρα, lineality space.
Διάλεξη 11: αφινικό κάλυμα και διάσταση πολυέδρου
Διάλεξη 12: παραδείγματα ακέραιων πολυτόπων, όψεις και έδρες πολυέδρων
Διαλέξεις 13 και 14: όψεις και έδρες (συνέχεια)
Διάλεξη 15: ελαχιστικές αναπαραστάσεις πολυέδρων
Διάλεξη 16: ελαχιστικές όψεις
Διάλεξη 17
Διάλεξη 18
Διάλεξη 19
Διάλεξη 20
Διάλεξη 21


Ασκήσεις

Πρώτη άσκηση (δημοσίευση 19.10.2016, παράδοση 26.10.2016) (Προσθήκη: Wed Oct 19 17:52:20 EEST 2016).

Δεύτερη άσκηση (δημοσίευση Wed Oct 19 17:52:20 EEST 2016, παράδοση 16.11.2016)

Τρίτη άσκηση (δημοσίευση 13.12.2016, παράδοση 21.12.2016) | (Προσθήκη: Tue Dec 13 17:07:17 EET 2016)



http://www.di.uoa.gr/~sgk/teaching/grad/LP/index.html
Τελευταία ανανέωση: Tue Dec 12 16:43:16 EET 2017