| Κωδικός Μαθήματος | 23530 |
| Τίτλος | Αλγόριθμοι Άμεσης Απόκρισης |
| Τύπος | Προχωρημένα Θέματα Επιλογής |
| Ιστοσελίδα | |
| Περιγραφή | Αντικείμενο του μαθήματος είναι ο σχεδιασμός και η ανάλυση αλγορίθμων για προβλήματα όπου η είσοδος δεν είναι γνωστή εκ των προτέρων και εμφανίζεται σταδιακά. Ένας αλγόριθμος άμεσης απόκρισης παίρνει αποφάσεις χωρίς να έχει πρόσβαση σε όλα τα δεδομένα. Περιεχόμενα του μαθήματος: Το βασικό μοντέλο υπολογισμού. Η έννοια της ανταγωνιστικότητας (competitive ratio). Ορισμοί. Παραδείγματα προβλημάτων – Προβλήματα διαχείρισης μνήμης (paging). Ντετερμινιστικοί και πιθανοτικοί αλγόριθμοι. Κατηγορίες αντιπάλων. Ορισμοί και ιδιότητες. – Επισκόπηση τεχνικών ανάλυσης. Συναρτήσεις δυναμικού (potential functions). Διατύπωση της αρχής Minimax. – Εισαγωγή στο πρόβλημα k-Server. Ντετερμινιστικοί αλγόριθμοι. Άνω και κάτω φράγματα. – Προβλήματα εξισορρόπησης φορτίου σε παράλληλες μηχανές (load balancing). Διαφορετικά μοντέλα. Άπληστοι αλγόριθμοι. – Προβλήματα άμεσης χωροθέτησης (packing). – Έλεγχος αποδοχής κλήσεων (call admission control) σε δίκτυα. Αλγόριθμοι ομαδοποίησης και τυχαίας επιλογής. – Προβλήματα χρωματισμού γραφημάτων και μονοπατιών. Άνω και κάτω φράγματα σε διαφορετικές τοπολογίες. – Προβλήματα εξερεύνησης άγνωστης περιοχής. |
| Αρμοδιότητα Διδασκαλίας | Τομέας Εφαρμογών και Θεμελιώσεων της Επιστήμης των Υπολογιστών |
| Εξάμηνο | Εαρινό Εξάμηνο |
| Διδακτικές Μονάδες | |
| Ώρες Διδασκαλίας | 2 |
| Ώρες Φροντιστηρίου | 2 |
| Ώρες Εργαστηρίου | 1 |
| Καθηγητές | |
