Adobe PDF (674.77 kB)
Title Details:
Το Πρόβλημα της Συνάντησης Δύο Κινητών Πρακτόρων
Authors: Markou, Evripidis
Kranakis, Evangelos
Pagourtzis, Aristeidis
Krizanc, Danny
Reviewer: Nikolopoulos, Stavros
Subject: MATHEMATICS AND COMPUTER SCIENCE > COMPUTER SCIENCE > ALGORITHMS AND COMPLEXITY
MATHEMATICS AND COMPUTER SCIENCE > COMPUTER SCIENCE
MATHEMATICS AND COMPUTER SCIENCE > COMPUTER SCIENCE > COMPUTATIONAL SCIENCE
MATHEMATICS AND COMPUTER SCIENCE > COMPUTER SCIENCE > ALGORITHMS AND COMPLEXITY
MATHEMATICS AND COMPUTER SCIENCE > COMPUTER SCIENCE
MATHEMATICS AND COMPUTER SCIENCE > MATHEMATICS > COMBINATORICS
Keywords:
Distributed Algorithms
Mobile Agents
Network Security
Computational Complexity
Approximation Algorithms
The Rendezvous Problem
The Black Hole Problem
Description:
Abstract:
Γίνεται εκτενής αναφορά στην επίλυση του προβλήματος της συνάντησης δύο κινητών πρακτόρων σε διαφορετικές τοπολογίες δικτύων, όπως δακτύλιους και τορικά (tori) δίκτυα. Αρνητικά αποτελέσματα (μοντέλα στα οποία το πρόβλημα της συνάντησης είναι μή-επιλύσιμο). Παρουσιάζονται και αναλύονται ντετερμινιστικοί αλγόριθμοι σε συγχρονισμένα και ασύγχρονα δίκτυα. Αποδείξεις ορθότητας των αλγορίθμων και ανάλυση πολυπλοκότητας. Αλγόριθμοι πρακτόρων που έχουν μοντελοποιηθεί με μηχανές Turing. Αλγόριθμοι για πεπερασμένα αυτόματα χωρίς μνήμη. Αλγόριθμοι για πράκτορες που μπορούν να αφήσουν μηνύματα πάνω στους κόμβους ή τις ακμές του δικτύου. Πιθανοτικοί αλγόριθμοι συνάντησης δύο πρακτόρων σε δακτύλιο. Random walk αλγόριθμοι. Trade-offs μεταξύ μνήμης και χρόνου. Ο Αλγόριθμος Coin Half Tour.
Type: Chapter
Creation Date: 2015
Item Details:
License: http://creativecommons.org/licenses/by-nc-nd/3.0/gr
Handle http://hdl.handle.net/11419/5773
Bibliographic Reference: Markou, E., Kranakis, E., Pagourtzis, A., & Krizanc, D. (2015). Το Πρόβλημα της Συνάντησης Δύο Κινητών Πρακτόρων [Chapter]. In Markou, E., Kranakis, E., Pagourtzis, A., & Krizanc, D. 2015. Αλγοριθμική θεωρία κατανεμημένων υπολογισμών [Undergraduate textbook]. Kallipos, Open Academic Editions. https://hdl.handle.net/11419/5773
Language: Greek
Is Part of: Αλγοριθμική θεωρία κατανεμημένων υπολογισμών
Publication Origin: Kallipos, Open Academic Editions