Μονάδα:
Κατεύθυνση / ειδίκευση Θεωρητική Πληροφορική (ΘΕΩ)Βιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2014-08-28
Συγγραφέας:
Λάμπρου Ιωάννης
Στοιχεία επιβλεπόντων καθηγητών:
Βασίλης Ζησιμόπουλος Καθηγητής ΕΚΠΑ (επιβλέπων)
Πρωτότυπος Τίτλος:
Robbing, surfing and rioting games on graphs
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Παιχνίδια κλεφτών, σέρφινγκ και αναταραχών σε γραφήματα
Περίληψη:
Εστιάζουμε σε 3 διαφορετικά συνδυαστικά παιχνίδια καταδίωξης-αποφυγής. Για το
διάσημο Αστυνόμοι & Κλέφτης (Cops & Robber), όπου αστυνόμοι-πιόνια προσπαθούν
να αιχμαλωτίσουν έναν κλέφτη-πιόνι σε ένα γράφημα, μελετώνται 2 παραλλαγές.
Αυτές είναι οι περιπτώσεις των κλασματικών αστυνόμων και του γρήγορου κλέφτη.
Πέρα από κάποια γενικά αποτελέσματα, μελετώνται κυρίως τα γραφήματα τύπου
πλέγματος. Για το παιχνίδι Επιτήρησης (Surveillance), που εισήχθη πρόσφατα με
σκοπό τη μοντελοποίηση της προανάκλησης (prefetching) στον Ιστό, δίνεται ένα
αποτέλεσμα δυσκολίας για γραφήματα με φραγμένο βαθμό. Σ'αυτό το παιχνίδι, ένας
παρατηρητής προσπαθεί να προβλέψει κάθε πιθανή διαδρομή ενός σέρφερ. Επιπλέον,
παρατίθεται μια γενικευμένη προσέγγιση Οφέλους-Ελλείμματος (Benefit-Deficit) ως
εναλλακτικό πεδίο έρευνας. Τέλος, μελετάται η Αιώνια Κυριαρχία (Eternal
Domination). Μια ομάδα φρουρών πρέπει να κυριαρχεί αιώνια πάνω σε ένα γράφημα
και έτσι να προστατεύει ενάντια επιθέσεων σε οποιονδήποτε κόμβο. Λαμβάνονται
υπόψη θέματα συνδυαστικής και πολυπλοκότητας.
Λέξεις-κλειδιά:
Αστυνόμοι & κλέφτης , Επιτήρηση, Αιώνια κυριαρχία, Παιχνίδια 2 παικτών, Παιχνίδια καταδίωξης-αποφυγής
Αρ. σελίδων ευρετηρίου:
11-12
Αρ. βιβλιογραφικών αναφορών:
52
Αρχείο:
Δεν επιτρέπεται η πρόσβαση στο αρχείο.
document.pdf
650 KB
Δεν επιτρέπεται η πρόσβαση στο αρχείο.
