Παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων

Abstract

Τέσσερα ρεαλιστικά παραδείγματα παραδείγματα σύγχρονων εφαρμογών απλών μεθόδων των πιθανοτήτων σε πρακτικά προβλήματα της πληροφορικής: <br/><br/>1. Ανάλυση ενός "randomized" αλγορίθμου για το πρόβλημα επαλήθευσης ισότητας πολυωνύμων. Σύγκριση του κέρδους σε πολυπλοκότητα, σε συνάρτηση με την ακριβώς υπολογισμένη πιθανότητα σφάλματος.<br/><br/>2. Πιθανοτική ανάλυση ενος (κλασικού) αλγορίθμου ταιριάσματος σχηματομορφών (pattern matching). Απόδειξη του γεγονότος πως, παρότι η κλασική πολυπλοκότητα του είναι γραμμική στο μήκος n των δεδομένων, η πολυπλοκότητα του στα περισσότερα δεδομένα (δηλαδή με πιθανότητα κοντά στο 1) είναι λογαριθμική, της τάξης του log n.<br/><br/>3. Ανάλυση ενός randomized αλγορίθμου για το πρόβλημα εύρεσης cut sets σε γράφους.<br/><br/>4. Ανάπτυξη και ανάλυση του σημαντικού αλγορίθμου quicksort για το πρόβλημα ταξινόμησης. (α) Πιθανοκρατική ανάλυση: Υπολογισμός της πολυπλοκότητας του αλγορίθμου για τυχαία δεδομένα εισόδου. (β) Randomized quicksort: Υπολογισμός της πολυπλοκότητας μιας randomized μορφής του αλγορίθμου.