«Информатиканың теориялық негіздері»
-ДӘРІС. Ықтималдықтар алгоритмдері
жүктеу/скачать 0.6 Mb.
|
| 15-ДӘРІС. Ықтималдықтар алгоритмдері.
Қарастырылатын сұрақтар: Сандық ықтималдық алгоритмдері. Монте Карло алгоритмі. Лас Вегас алгоритмдері. Шервуд алгоримтдері. Кездейсоқ оқиғалар “ықтималдық” ұғымын пайдаланумен түсіндіріліп баяндалуы мүмкін. Ықтималды теорясы үйлесімділігі жалғыз кездейсоқ оқиғалардың да, сондай – ақ өзара байланысқа немесе байланыссыз бірнеше оқиғаларды біріктіретін қиын тәжірибелердің ықтималдылығын табуға мүмкіндік береді. Алайда кездейсоқ оқиғаларды ықтималдық теориясында ғана баяндауға болады деуге болмайды. Оқиғаның кездейсоқтығы оның нәтижесінде толық сенімділік жоқтығын білдіреді, бұл өз кезегінде берілген оқиғамен байланысты бастапқы тәжірибеге белгісіздікті тудырады. Белгісіздік дәрежесі әртүрлі сипатуациялар үшін түрліше екені сөзсіз. Мысалы, егшер тәжірибе жоғары оқу орынының күндізгі бөлімінің 1- курсына кездейсоқ алынған студенттің жасын анықтаудан тұратын болса, онда үлкен сенімділікпен ол 30 – ға болып шығатынын айтуға болады. Күндізгі бөлім жағдайы бойынша онда 35 ке дейінгі жастағы тұлғалар оқи алатын болғанымен іштей тлдауға бірнеше жыл ішінде бітірген түлектер жиі оқиды. Егер еркімен алынған студенттің жасы 18-ден кіші бола ма екені тексерілсе, ұқсас тәжірибеде әлдеқайда азырақ нақылық болады. Практика үшін әртүрлі тәжірибелердің белгісіздігінің сандық бағасын жүгізу мүмкіндігі болғаны маңызды. Белгісіздіктің осындай сандық өлшемін клтіріп көрейік. Тәжірибе тең мүмкіндіігі бар бастауға n ие болғандағы қарапайым ситуациядан бастайық. Олардың әрқайсының белгісіздік өлшемі нәтиже (f(n)) санының функциясы болып табылады. Бұл функцияның кейбір қасиеттерін көрсетуге болады: n=1 болғанда тәжірибе нәтижесі кездейсоқ болмайтындықтан f(1)=0, сондықтан белгісіздік жоқ. Мүкін нәтижелер саны көбірек болған сайын, тәжірибе нәтижесін болжау соншалықты қиын болып кететіндіктен, f(n) n – нің өсуімен бірге өседі. Функцияның f(n) айқын түрін анықтау үшін теңмүмкіндікті нәтижелер санымен α және β екі тәуелсіз тәжірибені, сәйкесінше Πα, Πβ-ді қарастырымыз. Орында α және β тәжірибелерінің бір уақытта орындалуынан тұратын қиын тәжірибеге ие болсын делік: Олардың мүмкін нәтижелерінен саны nα, nβ-ға тең мүмкіндікті мұндай қиын тәжірибенің α және β нәтижесінің белгісіздігі оған α белгісіздігі қосылатындықтан α тәжірибесінің белгісіздігі көбірек болатыны анық; қиын тәжірибе белгісіздігінің мөлшері f(Πα, Πβ) тең. Екінші жағынан жеке α және β-ның белгісіздік өлшемі сәйкесінше f(Πα) және f(Πβ)-ны құрайды. Бірінші жағдайда біріккен оқиғалардың ортақ белгісіздігі көрінеді, екіншісінде әр оқиғаның жеке белгісіздігі көрсетіледі. Алайда α мен β тәуелсіздігінен қиын тәжірибеде олар бер – біріне ешқандай ықпал ете алмайды, соның ішінде α мен β-ның белгісіздігіне ықпал көрсете алмайды және керісіншеү. Сондықтан жиынтық белгісіздіктер өлшемі тәжірибелердің әрқайсысының белгісіздік өлшемі сомасына тең болуы тиіс: f(nα*nβ)=f(nα)+f(nβ) (2.1) Енді ол қасиеттер (1) мен (2) және үйлесімдік; (2.1) қанағаттандыру үшін функцияның f(n) айқын түрі қандай болуы мүмкін деген ойға қаламыз. Мұндай қасиет жиынтығын функция logn(n) қанағаттандыратынын көру оңай, оның үстіне ол функцияның барлық кластарының ішінде жалғыз екенін дәлелдеуге болады. Сөйтіп теңмүмкіндікті нәтижелері (n) бар тәжірибелердің белгісіздігі мөлшеріне logn(n) санын қабылдауға болады. Бұл жағдайда логарифм негізінің таңдалуында мән жоқ екенін айта кеткен жөн, өйткені лагорифмнің бір негізден екіншісіне түрленуінің белгілі формуласы күшіне. lognbn=lognba*lognan басқа негізге өтуі тұрақты, көбейткіштің lognba түрінің екі бөлігі үшін бірдей (2.1) енгізуден тұрады, бұл белгісіздік өлшемімасштабының өзгерісіне тең күште. Бұл осылай болғандықтан бізде логарифм негізінің біз үшін қолайлысын таңдап алуға мүмкіндік бар. Қолайлы негіз екеу, өйткені бұл жағадайда өлшем бірлік үшін айқын көрсетуге болатын және математикалық логика аппаратын осындай оқиғалардың анализі үшін қодануға болатын тек екі бірдей мүмкіндікті нәтижелерге бар тәжірибедегі белгісіздік қабылданады. Тәжірибернің екі мүмкін теңмүмкіндікті нәтижелерінде белгісіздік өлшем бірлігі бит2 деп аталады. Сөйтіп, біз n бірдей мүмкіндікті нәтижелері бар тәжірибе белгісіздігі өлшемін түсіндіретін функцияның айқын түрін анықтадық. f(n)=logn2 n (2.2) Бұл шама энтропия атауына ие болды. әрі қарай оны H деп белгілейтін боламыз. Қайтадан n бірдей мүмкіндікті нәтижелері бар тәжірибені қарасытырамыз. әрбір нәтиже кездейсоқ болғандықтан, олардың белгісіздіктері бірдей деу миға қонымды. Белгісіздік аддитивтік қасиеттен, сондай-ақ (2.2) сәйкес жалпы белгісіздік f(n)=logn2 n –ға тең, бір бастаумен енгізілген белгісіздік мынаны құрайды. , мұнда - кез келген жеке нәтиженің ықтималдығы. Осылайша, бірдей мүмкіндікті нәтижелердің әрқайсы енгізілген белгісіздік мынаған тең. H=-p *log2 p (2.3) Енді тәжірибелер нәтижелері бірдей мүмкіндікті емес болғандаға ситуацияға (2.3) формуласын жинақтап қорытамыз, мысалы, p(A1) және p(A2). Сонда : H1= -p(A1) және H2= -p(A2)*log2 p(A2) H=H1+H2= -p(A1)*log2 p(A1)*log2 p(A1) -p(A2)*log2 p(A2) Тәждірибеде α бірдей мүмкіндікті емес нәтижелер A1, A2, ... An болған жағадайға бұл формуланы жинақтай отырып, мынаны алмыз. H(α)= - (2.4) Айтылып кеткендей осындай түрде енгізілген шама тәжірибе α энтропиясы деп аталады. Дискретті кездейсоқ шамалардың (А.11) орташа мәніне арналған формуланы пайдалана отырып, мынаны жазуға болады. H( ) мұнда А(α) тәжірибедегі (α) мүмкін нәтижелерді білдіреді. Энтропия кездейсоқ оқиғалар көрінетін және оның барлық мүмкін нәтижелерінің орташа белгісіздігіне тең тәжірибе белгісіздігі мөлшер болып табылады. Практика үшін (2.4) формуласы әртүрлі тәжірибелермен салыстыруға мүмкіндік беретіндгімен маңызды. Мысал (2.1) Әрқайсында 12 шардан салынған екі жәшік бар. Біріншісінде 3-ақ шар, 3-қара және 6-қызыл, ал екіншісінде әр түстен 4-тен. Тәжірибелер әр жәшіктен бір шардан алып шығудан тұрады. Бұл тәжірибелердің нәтижелерінің белгісіздіктеріне қатысты не айтуға болады? (2.4) – ке сәйкес екі тәжірибенің де энтропиясын табамыз: бит, бит, Hβ >Hα, яғни β тәжірибесінде нәтиженің белгісіздігі жоғары, сондықтан, оны α нәтижесіне қарағанда азырақ сенімділікпен боложауға болады. Кездейсоқ нәтижелері бар тәжірибелерді белгілеу үшін грек әріптерін, ал тәжірибелердің жеке нәтижелернін белгілеу үшін латының бас әріптерін пайдаланатын боламыз. Бит атауы ағылшынның binari digit сөзінен шыққан, дәлме – дәл аудармада екілік разряд немесе екілік бірлік дегенді білдіреді. жүктеу/скачать 0.6 Mb. Достарыңызбен бөлісу:
|