Э. А. Абдыкеримова информатиканың теориялық негіздері
Тьюринг және Пост машинасы кӛмегімен «алгоритм» ҧғымын анықтау
жүктеу/скачать 476,55 Kb.
|
Э.А.Абдыкеримова.ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ
- Бұл бет үшін навигация:
- Марковтың нормальды алгоритмдері
Тьюринг және Пост машинасы кӛмегімен «алгоритм» ҧғымын анықтау4-ші дәрісте Тьюринг және Пост машиналары цифрлы автоматтар мысалы ретінде қарастырылған. Бҧл машиналар толығымен детерминделген универсалды орындаушылар болып табылады. Олардың кӛмегімен алғашқы деректер енгізілгеннен кейін нәтижені «оқуғаң болады. Тьюринг және Пост машиналарында орындалатын есептеулерге шектеулер бар ма деген сҧраққа Пост былайша жауап берген: «егер кез–келген бойынша нәтижеге әкелетін жалпы әдіс болса ғана программа қҧруға берілген есептердің шешімі болады». Постың анықтамасы алгоритм ҧғымына және осы алгоритмді цифрлы автомат кӛмегімен шешуге болатындығына әкеледі. Марковтың нормальды алгоритмдеріАлгоритм ҧғымын формальдау ҥшін орыс математигі А.А.Марков ассоциативтік есептеулерді қолдануды ҧсынды. Мҧнда алгоритм ауыстырымдар жҥйесі тҥрінде беріледі, олар қандай символдарды ауыстыру керек екендігін және бҧл ауыстырулар қандай ретпен жҥретіндігін кӛрсетеді. Мҧндай тәсілді А.А.Марков 50–ші жылдары ҧсынды, ол нормальды алгоритм (Марков ӛзі алгоритм деп атаған) ҧғымын енгізді. Ассоциативті есептеудің кейбір ҧғымдарын келтіреміз. А алфавиті (әр тҥрлі символдардың шектелген тобы) берілсін. Оны қҧрайтын символдарды әріптер деп атаймыз. Алфавиттің кез–келген шектелген тізбегін (сызықтық қатары), осы алфавиттегі сӛзі деп атаймыз. Сӛздегі символдар саны оның ҧзындығы деп аталады. Ҧзындығы нӛлге тең сӛз бос деп аталады. S сӛзі q сӛзінің ішкі сӛзі деп аталады. Егер q-ді q=rst тҥрінде кӛрсетуге болса, мҧндағы r және t - сол алфавиттегі кез–келген сӛз. А алфавитінде N және M екі сӛзін қарастырамыз. Егер N M-нің бӛлігі болса, онда N M-ге кіреді деп аталады. Қандай да бір алфавитте N-M , S- T,...ауыстыруларының шектелген жҥйесі берілсін. Мҧндағы N,M,S,T...осы алфавиттегі сӛздер. N-M кез–келген ауыстыруын k сӛзіне былайша қолдануға болады. Егер K-ге N сӛзі бір немесе бірнеше рет кіретін болса, онда оның кез– келгені M сӛзімен ауыстырыла алады және керісінше. А алфавитіндегі алгоритм деп тиімді есептелетін функцияны айтамыз. Оның анықталу облысы ретінде А алфавитіндегі барлық сӛздер жиынтығындағы қандай да бір ішкі жиынды айтамыз. Және мәні ретінде А алфавитіндегі сӛздер болып табылады. жүктеу/скачать 476,55 Kb. Достарыңызбен бөлісу:
|