forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 21 Σεπ 2017, 12:42

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 3 δημοσιεύσεις ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Άσκηση σε Αλγορίθμους
ΔημοσίευσηΔημοσιεύτηκε: 08 Φεβ 2012, 17:55 
Χωρίς σύνδεση
Regular Forumer

Εγγραφή: 12 Μαρ 2006, 23:50
Δημοσ.: 442
Τοποθεσια: Άγιος Στέφανος
Έστω ότι έχουμε ένα πιθανοτικό αλγόριθμο A για ένα πρόβλημα απόφασης (δηλαδή απαντά ναι ή όχι) που για κάθε είσοδο δίνει τη σωστή απάντηση με πιθανότητα τουλάχιστον q. Για να βελτιώσουμε την πιθανότητα q, τρέχουμε τον αλγόριθμο 3 φορές και επιστρέφουμε την απάντηση που πλειοψηφεί. Ποια η πιθανότητα να είναι σωστή η απάντηση? Είναι πράγματι μεγαλύτερη αυτή η πιθανότητα από το q?

_________________
Maths are so beautiful as a statue....


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Άσκηση σε Αλγορίθμους
ΔημοσίευσηΔημοσιεύτηκε: 09 Φεβ 2012, 21:26 
Χωρίς σύνδεση

Εγγραφή: 02 Δεκ 2009, 15:45
Δημοσ.: 24
Αν δεν κάνω λάθος :

Θες την πιθανότητα να έχεις τη σωστή απάντηση τουλάχιστον 2 φορες, δηλαδή είτε 2 είτε 3.
Για 3 φορές η πιθανότητα είναι q^3
Για 2 φορές η πιθανότητα είναι q^2(1-q) για κάποια συγκεκριμένη θέση της λανθασμένης απάντησης. Κι επειδή έχεις 3 τέτοιες περιπτώσεις (η λανθασμένη μπορεί να είναι είτε η 1η, είτε η 2η, είτε η 3η) τελικά έχεις 3*q^2*(1-q)

Συνολικά q^3+3q^2(1-q)=-2q^3+3q^2

-- Είναι αυτό μεγαλύτερο από q ; Θες να λύσεις την -2q^3+3q^2>q
-2q^3+3q^2-q>0
-2q^2+3q-1>0 (διαιρούμε με q>0)
Τελίκα έχεις 1/2 < q < 1

ΥΓ: Περισσότερο άσκηση πιθανοτήτων μου κάνει :P


Κορυφή
 Προφίλ  
 
 Θέμα δημοσίευσης: Re: Άσκηση σε Αλγορίθμους
ΔημοσίευσηΔημοσιεύτηκε: 13 Φεβ 2012, 21:41 
Χωρίς σύνδεση
Regular Forumer

Εγγραφή: 12 Μαρ 2006, 23:50
Δημοσ.: 442
Τοποθεσια: Άγιος Στέφανος
Ναι έχεις δίκιο! Είναι στις παρυφές των αλγορίθμων και πολύ βαθιά στις Πιθανότητες!!

Στέλιος

_________________
Maths are so beautiful as a statue....


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 3 δημοσιεύσεις ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση : Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group