DSpace

Πληροφορίες Τίτλου
Τίτλος: Παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων
Συγγραφείς:Κοντογιάννης, Ιωάννης
Τουμπής, Σταύρος
Κριτικός Αναγνώστης: Δελλαπόρτας, Πέτρος
Σχολές/Τμήματα: ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ, ΟΙΚΟΝΟΜΙΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΘΗΝΩΝ
Θέμα: 
Λέξεις-κλειδιά: 
ΠΙΘΑΝΟΤΗΤΕΣ
ΣΤΑΤΙΣΤΙΚΗ
ΑΝΑΛΥΣΗ ΑΛΓΟΡΙΘΜΩΝ
ΜΕΤΡΟ ΠΙΘΑΝΟΤΗΤΑΣ
ΠΥΚΝΟΤΗΤΑ ΠΙΘΑΝΟΤΗΤΑΣ
ΠΙΘΑΝΟΚΡΑΤΙΚΑ ΜΟΝΤΕΛΑ
ΚΑΤΑΝΟΜΕΣ
Περιγραφή
Περίληψη: 
Τέσσερα ρεαλιστικά παραδείγματα παραδείγματα σύγχρονων εφαρμογών απλών μεθόδων των πιθανοτήτων σε πρακτικά προβλήματα της πληροφορικής:

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

2. Πιθανοτική ανάλυση ενος (κλασικού) αλγορίθμου ταιριάσματος σχηματομορφών (pattern matching). Απόδειξη του γεγονότος πως, παρότι η κλασική πολυπλοκότητα του είναι γραμμική στο μήκος n των δεδομένων, η πολυπλοκότητα του στα περισσότερα δεδομένα (δηλαδή με πιθανότητα κοντά στο 1) είναι λογαριθμική, της τάξης του log n.

3. Ανάλυση ενός randomized αλγορίθμου για το πρόβλημα εύρεσης cut sets σε γράφους.

4. Ανάπτυξη και ανάλυση του σημαντικού αλγορίθμου quicksort για το πρόβλημα ταξινόμησης. (α) Πιθανοκρατική ανάλυση: Υπολογισμός της πολυπλοκότητας του αλγορίθμου για τυχαία δεδομένα εισόδου. (β) Randomized quicksort: Υπολογισμός της πολυπλοκότητας μιας randomized μορφής του αλγορίθμου.
Ημερομηνία Δημιουργίας: 2015
Πληροφορίες Τεκμηρίου
Είδος Τεκμηρίου: Κεφάλαιο Συγγράμματος
URI: http://hdl.handle.net/11419/2818
Βιβλιογραφική Αναφορά:Κοντογιάννης, Ι., Τουμπής, Σ. 2015. Παραδείγματα πιθανοκρατικής ανάλυσης αλγορίθμων. [Κεφάλαιο Συγγράμματος]. Στο Κοντογιάννης, Ι., Τουμπής, Σ. 2015. Στοιχεία πιθανοτήτων. [ηλεκτρ. βιβλ.] Αθήνα:Σύνδεσμος Ελληνικών Ακαδημαϊκών Βιβλιοθηκών. κεφ 8. Διαθέσιμο στο: http://hdl.handle.net/11419/2818
Γλώσσα: Ελληνικά
Αποτελεί μέρος του: Στοιχεία πιθανοτήτων
Άδεια Χρήσης: Αναφορά - Μη Εμπορική Χρήση - Παρόμοια Διανομή
Σχετικά Μαθήματα: 
1. ΠΙΘΑΝΟΤΗΤΕΣ [ΟΙΚΟΝΟΜΙΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΘΗΝΩΝ, ΣΧΟΛΗ ΕΠΙΣΤΗΜΩΝ ΚΑΙ ΤΕΧΝΟΛΟΓΙΑΣ ΤΗΣ ΠΛΗΡΟΦΟΡΙΑΣ, ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ]
2. ΕΦΑΡΜΟΣΜΕΝΕΣ ΠΙΘΑΝΟΤΗΤΕΣ ΚΑΙ ΣΤΑΤΙΣΤΙΚΗ [ΟΙΚΟΝΟΜΙΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΘΗΝΩΝ, ΣΧΟΛΗ ΕΠΙΣΤΗΜΩΝ ΚΑΙ ΤΕΧΝΟΛΟΓΙΑΣ ΤΗΣ ΠΛΗΡΟΦΟΡΙΑΣ, ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ]
3. ΕΦΑΡΜΟΣΜΕΝΕΣ ΠΙΘΑΝΟΤΗΤΕΣ ΚΑΙ ΠΡΟΣΟΜΟΙΩΣΗ [ΟΙΚΟΝΟΜΙΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΘΗΝΩΝ, ΣΧΟΛΗ ΕΠΙΣΤΗΜΩΝ ΚΑΙ ΤΕΧΝΟΛΟΓΙΑΣ ΤΗΣ ΠΛΗΡΟΦΟΡΙΑΣ, ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ]
4. ΠΙΘΑΝΟΤΗΤΕΣ ΙΙ [ΕΘΝΙΚΟ & ΚΑΠΟΔΙΣΤΡΙΑΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΘΗΝΩΝ, ΣΧΟΛΗ ΘΕΤΙΚΩΝ ΕΠΙΣΤΗΜΩΝ, ΤΜΗΜΑ ΜΑΘΗΜΑΤΙΚΩΝ]
5. ΠΙΘΑΝΟΤΗΤΕΣ Ι [ΕΘΝΙΚΟ & ΚΑΠΟΔΙΣΤΡΙΑΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΘΗΝΩΝ, ΣΧΟΛΗ ΘΕΤΙΚΩΝ ΕΠΙΣΤΗΜΩΝ, ΤΜΗΜΑ ΜΑΘΗΜΑΤΙΚΩΝ]
6. ΠΙΘΑΝΟΤΗΤΕΣ ΚΑΙ ΣΤΟΙΧΕΙΑ ΣΤΑΤΙΣΤΙΚΗΣ [ΕΘΝΙΚΟ & ΚΑΠΟΔΙΣΤΡΙΑΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΘΗΝΩΝ, ΣΧΟΛΗ ΘΕΤΙΚΩΝ ΕΠΙΣΤΗΜΩΝ, ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ ΚΑΙ ΤΗΛΕΠΙΚΟΙΝΩΝΙΩΝ]
7. ΠΙΘΑΝΟΤΗΤΕΣ ΚΑΙ ΣΤΑΤΙΣΤΙΚΗ [ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΩΣ, ΣΧΟΛΗ ΤΕΧΝΟΛΟΓΙΩΝ ΠΛΗΡΟΦΟΡΙΚΗΣ ΚΑΙ ΕΠΙΚΟΙΝΩΝΙΩΝ, ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ]
8. ΠΙΘΑΝΟΤΗΤΕΣ [ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΕΙΡΑΙΩΣ, ΣΧΟΛΗ ΤΕΧΝΟΛΟΓΙΩΝ ΠΛΗΡΟΦΟΡΙΚΗΣ ΚΑΙ ΕΠΙΚΟΙΝΩΝΙΩΝ, ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ]
9. ΕΙΣΑΓΩΓΗ ΣΤΙΣ ΠΙΘΑΝΟΤΗΤΕΣ [ΟΙΚΟΝΟΜΙΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΘΗΝΩΝ, ΣΧΟΛΗ ΕΠΙΣΤΗΜΩΝ ΚΑΙ ΤΕΧΝΟΛΟΓΙΑΣ ΤΗΣ ΠΛΗΡΟΦΟΡΙΑΣ, ΤΜΗΜΑ ΣΤΑΤΙΣΤΙΚΗΣ]
Γλωσσική Επιμέλεια: Τραμπούλης, Θεόφιλος
Τεχνική Επεξεργασία: Γκιτζένης, Σάββας
Τύπος έκδοσης: Εκδόσεις Κάλλιπος
Εμφανίζεται στις συλλογές:Επιστήμες Μηχανικών και Πληροφορική

Αρχεία σε αυτό το τεκμήριο:

Μορφότυπο Μέγεθος Περιγραφή
Adobe PDF569,72 kB-KατεβάστεΔείτε

Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα

Όροι χρήσης HEAL-Link © 2015

HEAL-Link NTUA GRNET European Union EDULLL ESPA