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

 
Το τεκμήριο παρέχεται από τον φορέα :

Αποθετήριο :
Αποθετήριο «Κάλλιπος»
δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο



Παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων (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



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.