سلام
همگی خسته نباشید
میشه حل این سوال رو بگید چطوری هست و اگه میشه رابطه بازگشتی هم بنویسید؟یک الگوریتم تصادفی A قرار است تعیین کند که آیا یک عدد ورودی x اول هست یا خیر. میدانیم که A در یک بار اجرا :
الف) اگر x اول باشد جواب بله می دهد.
ب) اگر x اول نباشد با احتمال ۳/۴ جواب خیر میدهد
برای آنکه تضمین کنیم که درحالت ب با احتمال حداقل [tex]1-\frac{1}{k}[/tex] جواب خیر بدهد. الگوریتم را چند بار اجرا کنیم؟ )گزینه صحیح گزینه سوم هستش)
۱)[tex]O(\sqrt{k})[/tex]
۲) [tex]O(1)[/tex]
۳)[tex]O(\log\: k)[/tex]
۴)[tex]k[/tex]
(۰۲ بهمن ۱۳۹۳ ۰۷:۳۷ ب.ظ)shayesteb نوشته شده توسط: سلامسلام
همگی خسته نباشید
یک الگوریتم تصادفی A قرار است تعیین کند که آیا یک عدد ورودی x اول هست یا خیر. میدانیم که A در یک بار اجرا :
الف) اگر x اول باشد جواب بله می دهد.
ب) اگر x اول نباشد با احتمال ۳/۴ جواب خیر میدهد
برای آنکه تضمین کنیم که درحالت ب با احتمال حداقل [tex]1-\frac{1}{k}[/tex] جواب خیر بدهد. الگوریتم را چند بار اجرا کنیم؟ )گزینه صحیح گزینه سوم هستش)
۱)[tex]O(\sqrt{k})[/tex]
۲) [tex]O(1)[/tex]
۳)[tex]O(\log\: k)[/tex]
۴)[tex]k[/tex]
البته سوال کمی بد بیان شده.ببینید در هر بار ران اگر عددمون اول نباشه به احتمال ۱/۴ خطا داریم.اگر هربار اجرای الگوریتم رو مستقل فرض کنیم اونوقت اگر دوبار خیر جواب بده احتمال خطاش میشه [tex]\frac{1}{4}\: ^2[/tex]
حالا اگر اگر n بار ران کنیم و جواب خیر بگیریم خطامون میشه [tex]\frac{1}{4}\: ^n[/tex]
در واقع شما میخواین معادله زیر رو حل کنید.
[tex]\frac{1}{4}\: ^n=\frac{1}{k}\: =>4^n=k\: =>n\: \log4=\log k=>n=C\: \log\: k=>n=O(\log(k))[/tex]
خیلی ممنون