Παρουσίαση/Προβολή

(ICSD225) -  Alexios Kaporis

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

Σύνδεσμος μαθήματος Zoom

 

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

 Combinatorial Optimization (CO) studies algorithms that compute the optimum solution amongst the feasible solutions of a combinatorial problem. A milestone of the theory was the understanding of the linear/convex problems. The combinatorial problems capture the intrinsic complexity of the most important problems for the computers. Due to this, in the last 50 years CO has played central role to explore the power and limitations of the computers. But, during this decade, due to the power of computers and the explosion of the Internet, modern problems have arisen. These concern the independent, rational interplay of a large number of computers in the Internet, which are motivated by greedy objectives, or coordinated play. These problems lie within an interdisciplinary area of research, such as CO, Computer Science, Game Theory and Economic Theory. An important subject is the study of bimatrix games, because these essentially capture the selfish behavior of atomic players. Also, important is the study of selfish network flows in large scale networks and the computation of their steady states. It is obvious that in many situations the selfish behavior  of the users can lead to a suboptimal state the Internet/System.  This manifests Mechanism Design as a key area to study.    

Ημερομηνία δημιουργίας

Τετάρτη 24 Σεπτεμβρίου 2014