1. 1Жиын ұғымы. Шекті және шексіз жиындар. Жиындарды анықтау тәсілдері.Ішкі жиындар. Берілген жиынның барлық жиынтығы. К- элемент жиындарының саны туралы n- элемент жиынтығы
жүктеу/скачать 336,61 Kb.
|
1. 1Жиын ??ымы. Шекті ж?не шексіз жиындар. Жиындарды аны?тау т?с
| Автомат ұғымы
Автоматтар теориясы негізінен цифрлық есептеу техникасы мен басқару жүйелеріне сұраныстардың, сонымен қатар алгоритмдер теориясы мен математикалық логикаға деген ішкі сұраныстың әсерінен пайда болды. Автоматтардың қазіргі теориясы шартты түрде үш үлкен бөлімге бөлінеді: автоматтардың абстрактілі алгебралық теориясы; автоматтардың құрылымдық теориясы; Ықтималдық автоматтар теориясы және өздігінен ұйымдастырылатын жүйелер. Өз кезегінде, автоматтардың абстрактілі-алгебралық теориясында мыналарды бөліп көрсетуге болады: ақырлы автоматтар теориясы; Шексіз автоматтар теориясы. Автоматтардың құрылымдық теориясы кодтау теориясымен, коммутациялық функциялардың жалпы теориясымен, комбинациялық схемалар теориясымен, ақпарат теориясымен, дискретті құрылғылардың сенімділік теориясымен және т.б. тығыз байланысты. «Автомат теориясы» пәнінің мақсаты: ақырлы автоматтар теориясына және комбинациялық және тізбекті құрылғыларды талдау мен синтездеуге байланысты аспектілері, ақпаратты өңдеу жүйелерінде қолданылатын микробағдарлама автоматтары, сонымен қатар шексіз автоматтар теориясы, мысалы, автоматтар мен автоматтар модельдерін тану негізінде білімді қалыптастыру Петри торлары. Автомат – кіріс символдарының тізбегін шығыс таңбалар тізбегіне түрлендіретін абстрактілі машина. Автоматтар үлкен кластарға бөлінеді: детерминизм бойынша – детерминирленген және детерминирленген емес, күйлер санының шектеулілігі бойынша – шекті және шексіз. Детерминирленген автомат – кіріс таңбаларының жинағы мен ішкі күйі кез келген операция цикліндегі келесі жұмыс цикліндегі шығыс таңбаларының жиынын және детерминирленген автоматтың ішкі күйін біркелкі анықтайтын автомат. Детерминирленген емес автомат – кіріс таңбаларының жиыны және жұмыстың кейбір циклдеріндегі ішкі күйі келесі жұмыс циклінде шығыс таңбалар жиынының балама таңдауын және детерминирленген емес автоматтың ішкі күйін анықтайтын автомат. Стохастикалық автомат (құрылысы ауыспалы автомат) – жалпы жағдайда ауысу және шығару функцияларының орнына дискретті типті ықтималдық үлестірімдері бар автомат. Ауысулар үшін Hij ықтималдықтары берілген, олар i санымен күйдің j санымен күйге ауысу ықтималдығын сипаттайды, ал шығыс үшін Qij ықтималдықтары j санымен шығудың көрінісін сипаттайды, егер автоматтың ағымдағы күйінде i саны болса. . Стохастикалық автомат көбінесе өзі жұмыс істейтін ортаға бейімделу процесін сипаттау үшін қолданылады. Стохастикалық автоматтың әрекеттерінің сәтті немесе сәтсіздігіне байланысты Hij және Qij қайта есептеледі, бұл қоршаған орта стационарлық болса, стохастикалық автоматтың бейімделуіне әкеледі. Ықтималды автомат - автоматтың параметрлері кездейсоқ болатын және автоматтың құрылымы оның жұмыс істеу нәтижелеріне қарамастан өзгеріссіз қалатын стохастикалық автоматтың ерекше жағдайы. Енді автоматты күйлер санының шектілігі тұрғысынан қарастырайық. Ақырлы автомат – жұмысы екі функциямен анықталатын автомат: y(t+1) = F1(x(t), y(t)), z(t) = F2(x(t),y(t) ). Бірінші функция t дискретті уақыт периодтарындағы автомат күйлерінің өзгеруін анықтайды және өтпелі функция деп аталады; екіншісі - автоматтың шығыс сигналдары және шығыс функциясы деп аталады; x, y және z - бекітілген ұзындықтағы екілік векторлардың жиындары, яғни. ақырлы жиындар. А.Қ.-ның математикалық моделі. автоматтық грамматика қызметін атқара алады, оның көмегімен автомат тілі жасалады. Шексіз автомат — ішкі күйлерінің жиыны есептелетін автомат (мысалы, Пост машинасы және Тьюринг машинасы). Тьюринг машинасы – бұл бір бағытта шексіз, ұяшықтарға бөлінген таспадан және таспа бойымен қозғала алатын басқару басынан тұратын дерексіз машина. Енгізу алфавитінің таңбалары, соның ішінде нөлдік таңба, әрбір ұяшыққа бір-бірден таспаға орналастырылуы мүмкін. Басқару басы ішкі күйлердің шектеулі санының бірінде болуы мүмкін, олардың біреуі ерекше. Бұл Тьюринг машинасын өшіруге сәйкес келеді. Жұмыстың әрбір қадамы басқару басының жұбы (басқару басы орналасқан таспаның ұяшығындағы байқалатын белгі; - бастың ішкі күйі) үштік (ұяшықтың жаңа мазмұны -) генерациялауынан тұрады. бастың жаңа ішкі күйі - бастың бір ұяшықты солға немесе оңға жылжытуы немесе бастың қалпын сақтау). Тьюринг машинасының жұмысы басқару басы жұмыстың соңғы күйіне өткенде аяқталады. Таспаның бастапқы толтырылуы және басқару басының бастапқы жағдайы оның бастапқы күйімен бірге сырттан орнатылады. Тьюринг машинасының әр қадамдағы әрекеттері сыртқы алфавиттің таңбаларының санына және бастың ішкі күйлерінің санына сәйкес келетін соңғы кестемен анықталады. Тьюринг машинасы әмбебап есептеу процесінің үлгісі болып табылады, өйткені кез келген белгілі бір Тьюринг машинасының жұмысын еліктейтін әмбебап Тьюринг машинасын жасауға болады. Осы тұрғыдан алғанда әмбебап Тьюринг машинасын дәстүрлі архитектура бойынша құрастырылған компьютердің математикалық моделі ретінде қарастыруға болады. Тьюринг машинасы дискретті математикада белгілі алгоритм тұжырымдамасының ықтимал нақтылауларының бірі болып табылады. Тьюринг машинасының жұмысы нәтижесінде пайда болған тілдер рекурсивті санаулы деп аталады. Пошта машинасы екі бағытта да шексіз, ұяшықтарға бөлінген таспадан және басқару басынан тұратын дерексіз машина. Таспаның ұяшықтары бос болуы немесе арнайы таңбамен белгіленуі мүмкін. Басқару басы тор бойымен қозғалады. Жұмыстың бір циклі үшін Post машинасы негізгі алты команданың бірін орындайды: басқару басын бір ұяшықты солға жылжыту, сол сияқты бір ұяшықты оңға жылжыту, бос ұяшыққа таңбалау таңбасын енгізу, шартты өту және тоқтату. Натурал сандармен қайта нөмірленген осындай командалар тізбегінен Пошта машинасының жұмыс істеу бағдарламалары құрылады. Пошта машинасының жұмысын бастамас бұрын, таспаның қажетті ұяшықтарын таңбалау белгілерімен толтырып, басқару басын белгілі бір ұяшыққа қарсы қою керек. жүктеу/скачать 336,61 Kb. Достарыңызбен бөлісу:
|