Examples of the probabilistic analysis of algorithms

 
This item is provided by the institution :

Repository :
Kallipos Repository
see the original item page
in the repository's web site and access all digital files if the item*
share




2015 (EN)
Παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων (EL)
Examples of the probabilistic analysis of algorithms (EN)

Τουμπής, Σταύρος (EL)
Κοντογιάννης, Ιωάννης (EL)
Kontogiannis, Ioannis (EN)
Toumpis, Stavros (EN)

Τραμπούλης, Θεόφιλος (EL)
Γκιτζένης, Σάββας (EL)
Δελλαπόρτας, Πέτρος (EL)
Κάλλιπος (EL)
Kallipos (EN)
Gitzenis, Savvas (EN)
Trampoulis, Τheofilos (EN)
Dellaportas, Petros (EN)

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

learningMaterial
bookChapter

ΑΝΑΛΥΣΗ ΑΛΓΟΡΙΘΜΩΝ (EL)
ΜΕΤΡΟ ΠΙΘΑΝΟΤΗΤΑΣ (EL)
ΠΙΘΑΝΟΤΗΤΕΣ (EL)
ΠΥΚΝΟΤΗΤΑ ΠΙΘΑΝΟΤΗΤΑΣ (EL)
ΚΑΤΑΝΟΜΕΣ (EL)
ΣΤΑΤΙΣΤΙΚΗ (EL)
ΠΙΘΑΝΟΚΡΑΤΙΚΑ ΜΟΝΤΕΛΑ (EL)
Probability Measure (EN)
Probabilistic Models (EN)
Probability (EN)
Probability Density (EN)
Statistics (EN)
Analysis Of Algorithms (EN)
Distributions (EN)

Σύνδεσμος Ελληνικών Ακαδημαϊκων Βιβλιοθηκών (EL)
Hellenic Academic Libraries Link (EN)


Σύνδεσμος Ελληνικών Ακαδημαϊκών Βιβλιοθηκών (EL)
Hellenic Academic Libraries Link (EN)

2015



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)