Αλγοριθμική θεωρία κατανεμημένων υπολογισμών

Abstract

Το βιβλίο αυτό απευθύνεται σε προπτυχιακούς και μεταπτυχιακούς φοιτητές τμημάτων Πληροφορικής και Μαθηματικών που διδάσκονται θέματα σχετικά με τη σχεδίαση και ανάλυση αλγόριθμων. Μπορεί να χρησιμοποιηθεί τόσο από μη εξοικειωμένους με την περιοχή, όσο και από προχωρημένους επιστήμονες στους τομείς της Θεωρητικής Πληροφορικής και ειδικότερα στους τομείς της Σχεδίασης Αλγόριθμων, της Θεωρίας Υπολογισμού αλλά και της Τεχνητής Νοημοσύνης και της Ρομποτικής. Οι αναγνώστες μπορούν να βρουν στο παρόν βιβλίο το απαραίτητο υλικό για την κατανόηση των εννοιών που σχετίζονται με: - Κατανεμημένους αλγόριθμους. - Κινητούς πράκτορες. - Πολυπλοκότητα αγαθών στους κατανεμημένους υπολογισμούς. - Μοντέλα χρονισμού των κατανεμημένων μοντέλων. - Βασικά προβλήματα και κατανεμημένους αλγόριθμους. - Αναγωγές προβλημάτων, αποδείξεις ορθότητας και ανάλυση πολυπλοκότητας των αλγόριθμων. - Προσεγγισιμότητα με εγγύηση ποιότητας της λύσης για δύσκολα (NP-hard) προβλήματα. - Ζητήματα ασφάλειας δικτύων και πρακτόρων. Δίνεται ιδιαίτερη έμφαση στην παρουσίαση και κατανόηση των θεωρητικών μοντέλων με βάση τα οποία όχι μόνο μπορούν να σχεδιαστούν βέλτιστοι κατανεμημένοι αλγόριθμοι που επιλύουν ρεαλιστικά προβλήματα, αλλά και να αναδειχθούν μέσα απ’ αυτήν την αλγοριθμική θεωρία τα πλεονεκτήματα των κατανεμημένων μεθόδων σε σύγκριση με τους παράλληλους και τους σειριακούς αλγόριθμους. Το βιβλίο εστιάζει ιδιαίτερα στην επίλυση προβλημάτων με τη χρήση κινητών πρακτόρων. Γίνεται εκτενής αναφορά στις εφαρμογές που έχουν τα μοντέλα των προβλημάτων που παρουσιάζονται. Οι αλγόριθμοι παρουσιάζονται σε ψευδογλώσσα, ενώ οι αποδείξεις ορθότητας και πολυπλοκότητας των αλγόριθμων, καθώς και οι αποδείξεις αρνητικών αποτελεσμάτων, δίνονται με τυπικό τρόπο και έτσι ώστε να μπορούν να τις παρακολουθήσουν άνετα προπτυχιακοί φοιτητές. Στο τέλος των κεφαλαίων υπάρχουν σχόλια και βιβλιογραφικές αναφορές, καθώς και ασκήσεις που βοηθούν στην καλύτερη κατανόηση των μεθόδων σχεδίασης κατανεμημένων αλγόριθμων και στην ανάλυσή τους.

This book is intended for undergraduate and graduate students in computer science and mathematics who are studying topics related to algorithm design and analysis. It can be used by both those unfamiliar with the field and advanced scientists in the areas of Theoretical Computer Science, particularly in the fields of Algorithm Design, Computation Theory, Artificial Intelligence, and Robotics. Readers will find in this book the necessary material to understand concepts related to: - Distributed algorithms. - Mobile agents. - Complexity of goods in distributed computing. - Timing models for distributed models. - Basic problems and distributed algorithms. - Problem reductions, correctness proofs, and complexity analysis of algorithms. - Approximation with quality guarantees for difficult (NP-hard) problems. - Network and agent security issues. Particular emphasis is placed on the presentation and understanding of theoretical models based on which not only can optimal distributed algorithms be designed that solve realistic problems, but also highlight the advantages of distributed methods over parallel and serial algorithms. The book focuses particularly on problem solving using mobile agents. Extensive reference is made to the applications of the problem models presented. The algorithms are presented in pseudolanguage, while the proofs of correctness and complexity of the algorithms, as well as the proofs of negative results, are given in a standard manner so that undergraduate students can easily follow them. At the end of each chapter, there are comments and bibliographical references, as well as exercises that help to better understand the methods of designing distributed algorithms and their analysis.