Παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων
Τέσσερα ρεαλιστικά παραδείγματα παραδείγματα σύγχρονων εφαρμογών απλών μεθόδων των πιθανοτήτων σε πρακτικά προβλήματα της πληροφορικής: <br/><br/>1. Ανάλυση ενός "randomized" αλγορίθμου για το πρόβλημα επαλήθευσης ισότητας πολυωνύμων. Σύγκριση του κέρδους σε πολυπλοκότητα, σε σ...
Κύριοι συγγραφείς: | , , , |
---|---|
Μορφή: | 7 |
Γλώσσα: | Greek |
Έκδοση: |
2016
|
Διαθέσιμο Online: | http://localhost:8080/jspui/handle/11419/2818 |
id |
kallipos-11419-2818 |
---|---|
record_format |
dspace |
spelling |
kallipos-11419-28182024-05-17T06:29:47Z Παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων Examples of the probabilistic analysis of algorithms Kontogiannis, Ioannis Toumpis, Stavros Κοντογιάννης, Ιωάννης Τουμπής, Σταύρος Τέσσερα ρεαλιστικά παραδείγματα παραδείγματα σύγχρονων εφαρμογών απλών μεθόδων των πιθανοτήτων σε πρακτικά προβλήματα της πληροφορικής: <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 μορφής του αλγορίθμου. 2016-02-08T20:42:53Z 2021-07-09T20:08:55Z 2016-02-08T20:42:53Z 2021-07-09T20:08:55Z 2016-02-08 7 http://localhost:8080/jspui/handle/11419/2818 el 1 application/pdf |
institution |
Kallipos |
collection |
DSpace |
language |
Greek |
description |
Τέσσερα ρεαλιστικά παραδείγματα παραδείγματα σύγχρονων εφαρμογών απλών μεθόδων των πιθανοτήτων σε πρακτικά προβλήματα της πληροφορικής: <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 μορφής του αλγορίθμου. |
format |
7 |
author |
Kontogiannis, Ioannis Toumpis, Stavros Κοντογιάννης, Ιωάννης Τουμπής, Σταύρος |
spellingShingle |
Kontogiannis, Ioannis Toumpis, Stavros Κοντογιάννης, Ιωάννης Τουμπής, Σταύρος Παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων |
author_facet |
Kontogiannis, Ioannis Toumpis, Stavros Κοντογιάννης, Ιωάννης Τουμπής, Σταύρος |
author_sort |
Kontogiannis, Ioannis |
title |
Παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων |
title_short |
Παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων |
title_full |
Παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων |
title_fullStr |
Παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων |
title_full_unstemmed |
Παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων |
title_sort |
παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων |
publishDate |
2016 |
url |
http://localhost:8080/jspui/handle/11419/2818 |
work_keys_str_mv |
AT kontogiannisioannis paradeigmatapithanokratikēsanalysēsalgorithmōn AT toumpisstavros paradeigmatapithanokratikēsanalysēsalgorithmōn AT kontogiannēsiōannēs paradeigmatapithanokratikēsanalysēsalgorithmōn AT toumpēsstauros paradeigmatapithanokratikēsanalysēsalgorithmōn AT kontogiannisioannis examplesoftheprobabilisticanalysisofalgorithms AT toumpisstavros examplesoftheprobabilisticanalysisofalgorithms AT kontogiannēsiōannēs examplesoftheprobabilisticanalysisofalgorithms AT toumpēsstauros examplesoftheprobabilisticanalysisofalgorithms |
_version_ |
1799946621895573504 |