Эҳтимоллик тестлари
Download 174.02 Kb.
|
Эҳтимоллик тестлари
- Bu sahifa navigatsiya:
- Натижа 1 .
Эҳтимоллик тестлари Айтайлик , , n – тоқ ва . Берилган натурал соннинг туб эканлигини аниқлаш эҳтимоллик тести бўйича қуйидаги тартибда олиб борилади. Тасодифий , танланади ва унинг учун маълум бир шартларнинг бажаришлиги текширилади. Агар кўрсатилган шартлардан бирортаси бажарилмаса, у ҳолда n – мураккаб сон деб эълон қилинади. Агарда барча келтирилган шартлар бажарилса, у ҳолда бу ерда n –сони туб экан деган хулоса келиб чиқмайди. Бироқ “n –сони, маълум бир эҳтимоллик билан туб сон”- деб юритилади. Ана шундай тестлардан бири бўлган ва бугунги кунда амалда кенг фойдаланиб келинаётган Соловей – Штрассен тести ҳакида тўхталиб ўтамиз. Унинг учун эса қуйидаги тасдиқлар ўринли: Теорема 1. n – тоқ мураккаб сон. У ҳолда шартни : 1) ЭКУБ (a, n)=1; 2) қаноатлантирувчи бутун a – лар сони n/2 – дан ошмайди. Бу ерда - Якоби символи. Натижа 1. Агар n – туб бўлса, у ҳолда 1), 2) шартлар барча , -лар учун бажарилади. Агарда n – мураккаб бўлса, у ҳолда тасодифан олинган , - учун 1), 2) шартларнинг бажарилиш эҳтимоллиги ½ - дан ошмайди. Шунинг учун ҳам, k – та тасодифий , учун Теорема 1 – нинг 1), 2) шартларини бажарилишини текширамиз, агар барчасида ўринли бўлса, яъни n – мураккаб эмаслиги аниқланса, у ҳолда берилган n – сони - эҳтимоллик билан туб сон экан деб эьлон қилинади. Мисол 1. n=7 , туб ёки туб эмаслиги юқоридаги тест орқ али текширилсин Ечиш. , 1) ЭКУБ(2,7)=1; 2) ; демак, . энди ҳоли учун: ЭКУБ(3, 7)=1; , яъни бажарди. Энди учун: ЭКУБ(4,7)=1 яъни 2) шарт ҳам ўринли демоқчимиз. Энди учун: ЭКУБ(5,7)=1 . . яъни 2) шарт ҳам ўринли экан. Энди учун: ЭКУБ(6,7)=1. , яъни 2) шарт ҳам ўринли демоқчимиз. У ҳолда n=7 , k=6, - эҳтимоллик билан ёки яна ҳам аниқроқ қилиб айтсак, n=7 – сони туб деган хулосага келамиз. Download 174.02 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling