Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18200
Τίτλος: Αναζήτηση εξόδου σε κύκλο υπό την παρουσία faulty robot
Συγγραφείς: Αναγνωστόπουλος, Θεόδωρος
Παγουρτζής Αριστείδης
Λέξεις κλειδιά: Faulty
Byzantine
crash
ασύρματη επικοινωνία
έξοδος κύκλου
αναζήτηση
Ημερομηνία έκδοσης: 11-Νοε-2021
Περίληψη: Η αναζήτηση αποτελεί κύριο μέρος της καθημερινότητας των ανθρώπων. Για αυτό το λόγο προβλήματα αναζήτησης αποτελούν σημαντική ερευνητική περιοχή της επιστήμης των υπολογιστών. Στην παρούσα διπλωματική εργασία θα ασχοληθούμε με τη μελέτη ενός τέτοιου προβλήματος. Συγκεκριμένα προτείνουμε λύσεις για το το πρόβλημα αναζήτησης εξόδου, η οποία βρίσκεται στην περιφέρεια ενός κύκλου. Την αναζήτηση την πραγματοποιούν σημειακά ρομπότ. Αυτά έχουν ως αρχική θέση το κέντρο του κύκλου και κινούνται με ταχύτητα ίση με ένα. Επικοινωνούν μεταξύ τους ασύρματα και το μήνυμα που στέλνει το κάθε ρομπότ περιέχει την ταυτότητα του ρομπότ, η οποία δεν μπορεί να αλλαχθεί με κανένα τρόπο. Μελετάμε την περίπτωση που έχουμε n ρομπότ από τα οποία τα f είναι faulty. Το πρόβλημα θεωρούμε ότι έχει λυθεί όταν ένα non-faulty ρομπότ έχει βρει την έξοδο και τα υπόλοιπα non-faulty ξέρουν με σιγουριά την θέση της εξόδου. Τα faulty χωρίζονται σε δύο κατηγορίες, στα crash και στα Byzantine. Τα crash είναι ελαττωματικά και μπορεί να σταματήσουν να λειτουργούν οποιαδήποτε στιγμή. Τα Byzantine έχουν ως στόχο να αποπροσανατολίσουν τα υπόλοιπα ρομπότ και μεταφέρουν ψευδείς πληροφορίες για την θέση της εξόδου. Συγκεκριμένα θα μελετηθεί η περίπτωση όπου διαθέτουμε δύο Byzantine. Η κύρια συνεισφορά της εργασίας είναι η ανάπτυξη ενός αλγορίθμου που πετυχαίνει χρόνο 1+8π/n για την περίπτωση (n,2,2) και 1+2π(f-1)/n + 2sin(4π/n) για την περίπτωση (n,f,2). Πρώτα παρουσιάζουμε μια αναλυτική περιγραφή του αλγορίθμου και αποδεικνύουμε την ορθότητα και τα άνω φράγματα στον χρόνο εκτέλεσης. Στη συνέχεια παρουσιάζονται διάφορα παραδείγματα που δείχνουν την δυσκολία στην ύπαρξη αλγορίθμου που επιλύει το ίδιο πρόβλημα σε λιγότερο χρόνο. Στο τέλος γίνεται μία εισαγωγή στην επίλυση της περίπτωσης (n,f,f), που βρίσκεται υπό ολοκλήρωση αυτή την περίοδο. Ο χρόνος που έχουμε καταλήξει είναι 1+2f2π/n για f≤6, 1+2+(f+2)2π/n για f≤16 και 1+2+(f+3)2π/n για τις υπόλοιπες περιπτώσεις.
URI: http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/18200
Εμφανίζεται στις συλλογές:Διπλωματικές Εργασίες - Theses

Αρχεία σε αυτό το τεκμήριο:
Αρχείο Περιγραφή ΜέγεθοςΜορφότυπος 
Αναζήτηση εξόδου σε κύκλο υπό την παρουσία faulty robot.pdf1.05 MBAdobe PDFΕμφάνιση/Άνοιγμα


Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.