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

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

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Κύριοι συγγραφείς: Kontogiannis, Ioannis, Toumpis, Stavros, Κοντογιάννης, Ιωάννης, Τουμπής, Σταύρος
Μορφή: 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