Adobe PDF (569.72 kB)
Title Details:
Examples of the probabilistic analysis of algorithms
Authors: Kontogiannis, Ioannis
Toumpis, Stavros
Reviewer: Dellaportas, Petros
Subject: MATHEMATICS AND COMPUTER SCIENCE > MATHEMATICS > PROBABILITY THEORY AND STOCHASTIC PROCESSES
MATHEMATICS AND COMPUTER SCIENCE > MATHEMATICS > STATISTICS
MATHEMATICS AND COMPUTER SCIENCE > COMPUTER SCIENCE > ALGORITHMS AND COMPLEXITY
MATHEMATICS AND COMPUTER SCIENCE > COMPUTER SCIENCE > DISCRETE STRUCTURES
Keywords:
Probability
Statistics
Analysis Of Algorithms
Probability Measure
Probability Density
Distributions
Probabilistic Models
Description:
Abstract:
Τέσσερα ρεαλιστικά παραδείγματα παραδείγματα σύγχρονων εφαρμογών απλών μεθόδων των πιθανοτήτων σε πρακτικά προβλήματα της πληροφορικής:

1. Ανάλυση ενός "randomized" αλγορίθμου για το πρόβλημα επαλήθευσης ισότητας πολυωνύμων. Σύγκριση του κέρδους σε πολυπλοκότητα, σε συνάρτηση με την ακριβώς υπολογισμένη πιθανότητα σφάλματος.

2. Πιθανοτική ανάλυση ενος (κλασικού) αλγορίθμου ταιριάσματος σχηματομορφών (pattern matching). Απόδειξη του γεγονότος πως, παρότι η κλασική πολυπλοκότητα του είναι γραμμική στο μήκος n των δεδομένων, η πολυπλοκότητα του στα περισσότερα δεδομένα (δηλαδή με πιθανότητα κοντά στο 1) είναι λογαριθμική, της τάξης του log n.

3. Ανάλυση ενός randomized αλγορίθμου για το πρόβλημα εύρεσης cut sets σε γράφους.

4. Ανάπτυξη και ανάλυση του σημαντικού αλγορίθμου quicksort για το πρόβλημα ταξινόμησης. (α) Πιθανοκρατική ανάλυση: Υπολογισμός της πολυπλοκότητας του αλγορίθμου για τυχαία δεδομένα εισόδου. (β) Randomized quicksort: Υπολογισμός της πολυπλοκότητας μιας randomized μορφής του αλγορίθμου.
Linguistic Editors: Trampoulis, Τheofilos
Technical Editors: Gitzenis, Savvas
Type: Chapter
Creation Date: 2015
Item Details:
License: http://creativecommons.org/licenses/by-nc-sa/3.0/gr
Handle http://hdl.handle.net/11419/2818
Bibliographic Citation: Kontogiannis, I., & Toumpis, S. (2015). Examples of the probabilistic analysis of algorithms [Chapter]. In Kontogiannis, I., & Toumpis, S. 2015. ELEMENTS OF PROBABILITY [Undergraduate textbook]. Kallipos, Open Academic Editions. chapter 8. http://hdl.handle.net/11419/2818
Language: Greek
Is Part of: ELEMENTS OF PROBABILITY
Publication Origin: Kallipos, Open Academic Editions