Ειδικά Θέματα: Άμεσοι Αλγόριθμοι (ΠΜΣ 556β)

Κουτσουπιάς Ηλίας

Περιγραφή
Εισαγωγή στη θεωρία των άμεσων αλγορίθμων για προβλήματα βελτιστοποίησης. Βασικές μέθοδοι σχεδίασης και ανάλυσης άμεσων αλγορίθμων στο πλαίσιο της ανάλυσης ανταγωνισμού (competitive analysis). Nτετερμινιστικοί και πιθανοτικοί άμεσοι αλγόριθμοι. Kάτω φράγματα για κάποια βασικά προβλήματα, όπως το πρόβλημα του εντοπισμού γέφυρας, το πρόβλημα της αντικατάστασης σελίδων, το πρόβλημα της διαχείρισης μιας λίστας, το πρόβλημα των διεκπεραιωτών, το πρόβλημα των μετρικών συστημάτων επεξεργασίας, καθώς και προβλήματα πρόβλεψης και εκμάθησης.