Συνδυαστική Βελτιστοποίηση και Σύγχρονες Οικονομικές Εφαρμογές

Περιεχόμενο μαθήματος

Η Συνδυαστική Βελτιστοποίηση (ΣΒ) μελετά αλγόριθμους εύρεσης της βέλτιστης λύσης μέσα από το σύνολο των δυνατών λύσεων ενός συνδυαστικού προβλήματος. Σταθμός στην θεωρία της ΣΒ ήταν η κατανόηση της επίλυσης των  γραμμικών/κυρτών προβλημάτων. Τα συνδυαστικά προβλήματα έχουν την δύναμη να εκφράσουν ποσοτικά τα σημαντικότερα ερωτήματα που αφορούν την πολυπλοκότητα των υπολογισμών σε έναν ηλεκτρονικό υπολογιστή. Έτσι, τα τελευταία 50 χρόνια η ΣΒ αποτέλεσε ισχυρό εργαλείο εξερεύνησης των δυνατότητων/περιορισμών των ηλεκτρονικών υπολογιστών. Ενώ η αρωγή της ΣΒ στην μακροχρόνια ωρίμανση/εξέλιξη των υπολογιστών ήταν καθοριστική, την τελευταία δεκαετία έχουμε να αντιμετωπίσουμε  σημαντικά μοντέρνα ερωτήματα που γενεσιουργός αιτία είναι η υπολογιστική ισχύς και η τεράστια ανάπτυξη του Διαδικτύου.  Αφορούν την ανεξάρτητη και λογική αλληλεπίδραση νέφους υπολογιστών μέσω Διαδικτύου, που διαπνέονται  από εγωιστική ή συνεργατική συμπεριφορά. Αυτά τα μοντέρνα προβλήματα αποτελούν διεπιστημονικό πεδίο έρευνας όπου, εκτός από την ΣΒ και την Θεωρία Υπολογιστών, σημαντικό ρόλο παίζουν η Θεωρία Παιγνίων και Οικονομική θεωρία. Η μελέτη μέσω ΣΒ των παίγνιων παικτών με πίνακες αμοιβών είναι σημαντική  λόγω της ικανότητας της μοντελοποίησης της εγωιστικής συμπεριφοράς ανεξάρτητων και λογικών οντοτήτων.  Επίσης, αντικείμενο μελέτης είναι οι εγωιστικές ροές χρηστών σε μεγάλα δίκτυα και ο υπολογισμός χαρακτηριστικών σημείων ισορροπίας. Είναι διαισθητικά & εμπειρικά προφανές ότι πολλές φορές ο εγωισμός των χρηστών μπορεί να οδηγήσει το Διαδίκτυο/Σύστημα  σε μη αποδοτική κατάσταση. Για αυτό το λόγο, σημαντικό πεδίο μελέτης είναι ο σχεδιασμός μηχανισμών, όπου δίνουν στους χρήστες την αίσθηση της ελεύθερης και εγωιστικής συμπεριφοράς,  αλλά  ο στόχος τους είναι να οδηγήσουν το Διαδίκτυο/Σύστημα σε βέλτιστη κατάσταση.

 

Επιδιωκόμενα μαθησιακά αποτελέσματα

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

 

Προαπαιτούμενα

Αλγόριθμοι, πολυπλοκότητα βασικές γνώσεις σχεδιασμού δικτύων .

 

Εγχειρίδια του μαθήματος

  1. http://tocs.ulb.tu-darmstadt.de/116091606.pdf
  2. http://homepages.cwi.nl/~lex/files/book.pdf
  3. http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf
  4. http://www.icsd.aegean.gr/kaporisa/index_files/Behavior.djvu
  5. http://theory.stanford.edu/~tim/papers/thesis.pdf

Συμπληρωματική βιβλιογραφία

  1. http://ocw.mit.edu/courses/mathematics/18-433-combinatorial-optimization-fall-2003/
  2. https://www.math.uwaterloo.ca/~cswamy/courses/co759/agt-material/mechdeslp-journ.pdf
  3. http://www-math.mit.edu/~goemans/18438S12/18438.html
  4. http://www.immorlica.com/combOpt/index.html
  5. https://www.youtube.com/channel/UCcH4Ga14Y4ELFKrEYM1vXCg?feature=watch
  6. http://www.cc.gatech.edu/~ninamf/LGO10/

 

Διδακτικές και μαθησιακές μέθοδοι

Ανάπτυξη και επεξήγηση θεωρητικών ενοτήτων, παρουσίαση ειδικών μελετών περίπτωσης και εφαρμογών, ανάλυση και αξιολόγηση αντιπροσωπευτικών προγραμμάτων matlab & maple, εκπόνηση ασκήσεων.

 

Μέθοδοι αξιολόγησης / βαθμολόγησης

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

 

Γλώσσα διδασκαλίας

Ελληνική ή/και Αγγλική

 

Τρόπος παράδοσης μαθήματος

Το μάθημα υλοποιείται με πρότυπες μορφές εκπαίδευσης ̟που συνδυάζουν: (α) μαθήματα και σεμινάρια, η παρακολούθηση των οποίων είναι υποχρεωτική, απαιτώντας προσδιορισμένη από τον κανονισμό σπουδών ελάχιστη φυσική παρουσία και (β) πρότυπες (ηλεκτρονικές) διαδικασίες εκπαίδευσης/μάθησης από απόσταση