Το Πρόβλημα της Συνάντησης Δύο Κινητών Πρακτόρων

Markou, Evripidis; Kranakis, Evangelos; Pagourtzis, Aristeidis; Krizanc, Danny; Μάρκου, Ευριπίδης; Κρανάκης, Ευάγγελος; Παγουρτζής, Αριστείδης; Krizanc, Danny

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