Алгоритмнің қолданбалы теориясы пәнінен емтихан сұрақтары 25 сұрақ деңгей
жүктеу/скачать 0,9 Mb.
|
Алгоритм 001
- Бұл бет үшін навигация:
- Чёрч — Тьюринг тезисі
| i =0, j - ұяшықта сақтаулы бос белгі бос емес белгіге (алфавиттегі j белгісіне) ауыстырылғанын білдіреді, яғни белгі қою орындалады;
i j - бір белгіні екіншісімен ауыстыруды білдіреді. Осылайша, Тьюринг машинасында ақпараттарды өңдеудің ең қарапайым командалары жүзеге асырылады. Бұл өңдеудің командалар жүйесі тура сол сияқты қарапайым лентаның орын ауыстыруының командалар жүйесімен толықтырылады: бір ұяшық солға, бір ұяшық оңға және орнында қалу, яғни шолынулы ұяшықтың адресі команданы орындау нәтижесінде немесе 1-ге ауысады, немесе өзгеріссіз қалады. Бірақ, шыныда лента жылжығанмен, әдетте головканың секцияға қатысты жылжуы қарастырылады – сондықтан лентаның оңға жылжуы командасы R («Right») арқылы, ал солға жылжу командасы L («Left») арқылы, жылжудың болмауы - S («Stop») арқылы бейнеленеді. Ары қарай головканың жылжуы туралы айтамыз да, R, L және S командаларын оның қозғалысы деп білеміз. Бұл командалардың қарапайымдылығы қандай-да бір ұяшықтың мазмұнына барғымыз келсе, ол жеке бір ұяшыққа жылжу командасының тізбегі арқылы ізделінетінін білдіреді. Әрине бұл өңдеу процесін біршама ұзартады, оның есесіне ұяшықтарды нөмірлеу және адрес бойынша өту командасынан арылуымызға көмектеседі Тьюринг машинасына арналған бағдарлама жасаңыз, мысалдар келтіріңіз. Функциялар туралы ұғымға анықтама беріңіз, мысал келтіріңіз. Функция ұғымы негізгі математикалық ұғымдардың бірі. Бұл ұғым екі жиынның элементтері арасындағы тәуелділікті (байланысты) орнатумен байланысты. Функция ұғымы негізгі математикалық ұғымдардың бірі. Бұл ұғым екі жиынның элементтері арасындағы тәуелділікті (байланысты) орнатумен байланысты. Екі бос емес Х және У жиындары берілсін. Әрбір элементіне тек бір ғана элементін сәйкес қоятын сәйкестігі функция деп аталып, , немесе арқылы белгіленеді. Сонымен қатар, функциясы Х жиынын У жиынына бейнелейді деп те атайды. Мысалы, а мен б жағдайындағы және сәйкестіктері функция болып табылса, в, г жағдайында функция емес. в-жағдайында барлық элементіне элементі сәйкес келмейді, ал г-жағдайында бірмәнділік шарты орындалмайды. Х жиынын функциясының анықталу облысы деп аталып, арқылы белгіленеді. Ал барлық элементтерінің жиыны функциясының мәндер жиыны деп аталып, арқылы белгіленеді. Предикаттар мен кванторлардың анықтамасын айтып беріңіз. Предикаттар алгебрасы пікірлер алгебрасының бөлігі болып жалпы математикалық пікірлерді өрнектеу және формал теорияларды құру құралы. Модельдер теориясы предикаттар алгебрасын қолданудың маңызды облыстарының бірі. Анықтама 1. М жиын және бұл жиында берілген ,..., предикаттар модель деп аталады. Оны біз үлкен латын әріпімен белгілейміз: М - моделдің негізгі жиыны, ал– ,..., негізгі пердикаттар деп айтылады. Предикаттардың барлығы =<Р1(к),...,Рп(к)> жиынды модельдің сигнатурасы деп атайды. Мұндағы К1,...,Кп натурал сандарды модельдің арлары деп айтады. =<К1,...,Кп> жиынды модельдің типі деп аталады. Бос жиын -ды 0-арлық предикатттың моделі деп атайды. Мысалдар. 1. N – натурал сандар жиыны, Е, S, П – N жиында анықталған теңдік, қосу және көбейту предикаттары. Жиі қолданылатын кванторлар: -кез келген; - табылады; :(/)- мынадай, қасиетін сипаттау үшін; - бұдан шығатын салдар; - тепе-теңдік кванторы, тек сол жағдайда; - қатаң енгізу кванторы. Черч тезисі ұғымын түсіндіріңіз. 1930-жылдардың ортасында Алонзо Чёрч пен Алан Тьюринг айтқан бұл тұжырым —есептелу теориясы, информатика, теориялық кибернетика және т.б. ғылым салалары үшін іргелі тұжырым. Алан Тьюринг мынандай жорамал айтты (оны Чёрч — Тьюринг тезисідейді):«Кез келген алгоритм осы сөздің интуициялық мағынасында эквивалентті Тьюринг машинасымен көрсетіле алады».Жалпы түрде бұл Чёрч-Тьюрингтіңтезисі былай дейді: «Кез келген интуициялық есептелетін функция жартылай есептелетін функция, яғни қандай да бір Тьюринг машинасымен есептеліне алады».Чёрч-Тьюрингтің физикалық тезисі:«Физикалық құрылғымен есептеліне алатын кез келген функция Тьюринг машинасымен де есептеліне алады».Тьюринг машинасы Пост машинасын Марковтың нормальды алгоритмдері және компьютердегі кез – келген программаны (кірістік деректерді қандай да бір алгоритм бойынша шығыстық деректерге түрлендіретін) имитация жасай алады. Өз кезегінде түрлі абстрактілі орындаушылар Тьюринг машинасын имитациялай алады. Мұндай орындаушыларды Тьюринг бойынша толық деп атайды. Тьюринг машинасын имитациялайтын программалар бар (компьютерлерге арналған), бірақ оның имитациясы толық емес, өйткені Тьюринг машинасының лентасы екі жағынан да шексіз, ал компьютер жады шектеулі.Тьюринг машинасының моделі өзін кеңейтуге мүмкіндік береді. Ленталардың кез – келген саны бар және көпөлшемді ленталардан тұратын Тьюринг машиналарын қарастыруға болады. Олардың барлығы Тьюринг машинасы бойынша толық болады және кәдімгі Тьюринг машинасымен модельденеді. Функционалдық схемалардың құрылу жолдарын сипаттаңыз. Хэмминг коды ұғымын түсіндіріңіз. Кодын Хемминга. Сандық Ақпаратты Кодтау кез келген автоматтандырылған жүйесінің жұмыс істеуі жеткілікті алынған деректер тазалығы ақпаратты қабылдау, қателерді табу және олардың түзету проблемасына тап. нысанға тағайындалған неғұрлым ауыр міндеттер ақпаратты өңдеу, бағдарламалық қамтамасыз ету жаман элементтерін неғұрлым күрделі және сезімтал анықтау жүйесі мен ақпараттық қателер ағымы оның жұмысы болып табылады. Қателер үшін ақпарат ағынын сынау және тіпті оларды түзету үшін бір параметр сандық ақпаратты кодтау болып табылады. түрлі деректермен жұмыс істеу кезінде пайдаланылатын көптеген кодекстер мен әдістері бар. деп аталатын Хемминга коды кезінде туындайтын ақаулықтарды жою неғұрлым күрделі және күрделі жолдарын құру үшін нүктесі болды классикалық мысал болып табылады, деректерді беру қателіктер.код тарихы ортасында 1940 жылы басталады. Сол уақытта, Ричард Хемминга атақты Bell Labs жұмыс істейтін, Есеп машина Bell Model V игерді. Содан кейін ол электромеханикалық принципін пайдаланатын озық тетігі болды. Релелік бірлік пайдаланылатын машиналар жобалау. Оларды пайдалану жылдамдығы айтарлықтай пайда бермейді. бір революция жүзеге асыру үшін бірнеше секунд қажет. Деректерді енгізу перфокарт құралдарын өтті, және қателер оқу процесінде сирек емес еді. Жылы аптасына анықтау және дұрыс қателер арнайы кодтарды пайдаланылады табылған. Машина оператор өз кезегінде, бұл шамдардың жарқыл хабардар қатесін түзеткен және есептеу процесін-іске қайта. Бірақ демалыс процесіне әр түрлі ережелерге сәйкес өтті. Комбинаторика ұғымының анықтамасын айтып беріңіз. Комбинаторика – берілген ережелерге сәйкес кейбір негізгі жиынтықтан элементтерді таңдау және орналастыру есептерін зерттейтін математиканың бөлімі. Комбинаториканың формулалары мен принциптері ықтималдықтар теориясында кездейсоқ оқиғалардың ықтималдығын есептеу және сәйкесінше кездейсоқ шамалардың таралу заңдарын алу үшін қолданылады. Қосу және көбейту ережелерінің қолданылу аймақтары қандай? Комбинаторикалық формулалар қандай есептерге бағытталады? Негізгі комбинаторикалық ұғымдарға түсініктеме беріңіз: орналастырулар, алмастырулар, терулер. Математикалық индукция ұғымына түсінік беріңіз. Графтар және терминология ұғымын түсіндіріңіз? Сыбайлас және инциденттік матрицаларын құру жолдары келтіріңіз және мысал келтіріңіз. G-графының сыбайлас матрицасы деп төмендегідей анықталған n ретті AG={Aij} матрицаны айтамыз. Графтардың көпірлері, блоктары және ілесім нүктелер дегеніміз не? Эйлер және Гамильтон циклдері не үшін қолданылады? жүктеу/скачать 0,9 Mb. Достарыңызбен бөлісу:
|