Э. А. Абдыкеримова
жүктеу/скачать 1,31 Mb. Pdf көрінісі
|
Э.А.Абдыкеримова.ИНФОРМАТИКАНЫҢ ТЕОРИЯЛЫҚ НЕГІЗДЕРІ
|
8.5 Марковтың нормальды алгоритмдері Алгоритм ҧғымын формальдау ҥшін орыс математигі А.А.Марков ассоциативтік есептеулерді қолдануды ҧсынды. Мҧнда алгоритм ауыстырымдар жҥйесі тҥрінде беріледі, олар қандай символдарды ауыстыру керек екендігін және бҧл ауыстырулар қандай ретпен жҥретіндігін кӛрсетеді. Мҧндай тәсілді А.А.Марков 50–ші жылдары ҧсынды, ол нормальды алгоритм (Марков ӛзі алгоритм деп атаған) ҧғымын енгізді. 66 Ассоциативті есептеудің кейбір ҧғымдарын келтіреміз. А алфавиті (әр тҥрлі символдардың шектелген тобы) берілсін. Оны қҧрайтын символдарды әріптер деп атаймыз. Алфавиттің кез–келген шектелген тізбегін (сызықтық қатары), осы алфавиттегі сӛзі деп атаймыз. Сӛздегі символдар саны оның ҧзындығы деп аталады. Ҧзындығы нӛлге тең сӛз бос деп аталады. 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 сӛзімен ауыстырыла алады және керісінше. А алфавитіндегі алгоритм деп тиімді есептелетін функцияны айтамыз. Оның анықталу облысы ретінде А алфавитіндегі барлық сӛздер жиынтығындағы қандай да бір ішкі жиынды айтамыз. Және мәні ретінде А алфавитіндегі сӛздер болып табылады. жүктеу/скачать 1,31 Mb. Достарыңызбен бөлісу:
|