Алгоритмнің қолданбалы теориясы пәнінен емтихан сұрақтары 25 сұрақ деңгей
Буль функцияларының толық жүйелері
жүктеу/скачать 0,9 Mb.
|
Алгоритм 001
- Бұл бет үшін навигация:
- Модульдік
- Объектіге
- Черч тезисі.
| Буль функцияларының толық жүйелері.
Кез келген логикалық функция өрнектелетін логикалық операциялардың жиынтықтары болады. Мұндай операциялар жиыны функционалды толық жүйелер немесе базис деп аталады. Функционапды толық жүйелерге немесе базистерге мысалдар. {, , }; {, }; {,}; {}; {}; {,,1}; {,}; {,,}; {, , }; т.б Бұлардың ішінде көбірек зерттелгені {, , }-базис; Бұлар буль формулалары деп аталады. Анықтама 1. Логикалық функциялар жиыны Р2-негізгі жиыны, ал операциялары-дизъюнкция, конъюнкция, терістеу болатын {Р2; , , } алгебрасы логикалық функциялардың бульдік алгебрасы деп аталады. Теорема 1. Кез келген логикалық функция буль формуласы түрінде кескінделеді яғни дизъюнкция, конъюнкция, терістеудің суперпозициясы. Бұдан буль формулаларының жүйесі {, , }; функциональды толық жүйе. Бұл кесте түрінде берілген кез келген функцияны буль алгебрасының формуласы түрінде кескіндеуге болатындығын көрсетеді. Теорема 2. Егер функционалды толық * жүйенің барлық функциялары -жүйенің формулалары арқылы өрнектелетін болса,онда -жүйе де функционалды толық жүйе болады. Есептеу функциясы ұғымы. Есептелетін функциялар теориясына сипаттама беріңіз. Есептелетін функциялар зерттеудің негізгі объектілері болып табылады есептеу теориясы. Есептелетін функциялар - интуитивті түсініктің формаланған аналогы алгоритмдер, егер функция функциясын орындай алатын алгоритм болса, функцияны есептеуге болады деген мағынада, яғни функция доменінің кірісі берілген жағдайда ол сәйкес нәтижені қайтара алады. Есептелетін функциялар есептеуді кез-келген нақты сілтеме жасамай-ақ талқылау үшін қолданылады есептеу моделі сияқты Тьюринг машиналары немесе машиналарды тіркеу. Алайда кез-келген анықтама есептеудің белгілі бір моделіне сілтеме жасауы керек, бірақ барлық анықталған анықтамалар функциялардың бірдей класын береді. Есептелетін функциялар жиынтығын тудыратын есептеудің жеке модельдері Тьюрингпен есептелетін функциялар және μ-рекурсивті функциялар. Есептелетін функцияны дәл анықтамас бұрын, математиктер көбінесе бейресми терминді қолданады тиімді есептелетін. Осы уақыттан бастап бұл термин есептелетін функциялармен анықталды. Осы функциялардың тиімді есептелуі олардың болуы мүмкін екенін білдірмейтінін ескеріңіз тиімді есептелген (яғни ақылға қонымды уақыт ішінде есептелген). Шындығында, кейбір тиімді есептелетін функциялар үшін оларды есептейтін кез-келген алгоритм алгоритмнің жұмыс істеу уақыты өсетін мағынасында өте тиімсіз болатындығын көрсетуге болады. экспоненциалды (немесе тіпті асықпай ) кіріс ұзындығымен. Өрістері мүмкін болатын есептеу және есептеу күрделілігі тиімді есептеуге болатын функцияларды зерттеу. Сәйкес Шіркеу-Тьюрингтік тезис, есептелетін функциялар - бұл шектеусіз уақыт пен сақтау кеңістігін ескере отырып, механикалық есептеу құрылғысы арқылы есептелетін функциялар. Эквивалентті түрде бұл тезисте функция алгоритмі болған жағдайда ғана есептелетіні айтылған. Осы мағынадағы алгоритм деп адамның уақыты шектеусіз және қалам мен қағаздың шексіз қоры жүретін қадамдардың бірізділігі деп түсінетіндігіне назар аударыңыз. The Блум аксиомалары рефератты анықтау үшін қолдануға болады есептеу күрделілігі теориясы есептелетін функциялар жиынтығында. Есептеу күрделілігі теориясында есептелетін функцияның күрделілігін анықтау мәселесі а деп аталады функция проблемасы. Тиімді есептеу. "Есептеу функциясы" және "функцияны есептеу алгоритмі бар"деген тұжырымдардың баламалылығын сипаттаңыз. Бағдарламалық жүйелерді жобалау әдістерін атаңыз және түсініктеме беріңіз. CASE технологиясы - бұл бағдарламалық пакеттолық автоматтандыру технологиялық процесскүрделі бағдарламалық құралдарды талдау, жобалау, әзірлеу және қызмет көрсету. Қазіргі заманғы CASE құралдары көптеген IC жобалау технологияларын қолдаудың кең ауқымын қамтиды: қарапайым талдау мен құжаттама құралдарынан бастап, бағдарламалық қамтамасыз етудің бүкіл өмірлік циклін қамтитын толық автоматтандырылған құралдарға дейін. АЖ әзірлеудің ең көп уақытты талап ететін кезеңдері талдау мен жобалау кезеңдері болып табылады, оның барысында CASE-құралдары техникалық шешімдердің жоғары сапасын және жобалық құжаттаманы дайындауды қамтамасыз етеді. Бұл жағдайда пәндік аймақты модельдеуге арналған графикалық құралдар маңызды рөл атқарады, бұл әзірлеушілерге қолданыстағы АЖ -ны визуалды түрде зерттеуге, оны мақсаттар мен қолданыстағы шектеулерге сәйкес қайта құруға мүмкіндік береді. Кіріктірілген CASE құралдарында келесілер бар тән ерекшеліктері: · АЖ әзірлеу процесін басқаруды қамтамасыз ету; · Жоба метадеректерін (репозиторий) арнайы ұйымдастырылған сақтауды пайдалану. Кіріктірілген CASE құралдары келесі компоненттерден тұрады: · АЖ -ді сипаттау мен құжаттау үшін қолданылатын графикалық талдау мен жобалау құралдары; · Бағдарламалау тілдері мен код генераторларын қамтитын қосымшаларды әзірлеу құралдары; · Әзірленіп жатқан жобаның нұсқаларын және оның жеке компоненттерін сақтауды, топтық өңдеу кезінде әр түрлі әзірлеушілерден ақпарат ағынын синхрондауды, метадеректердің толықтығы мен бірізділігін бақылауды қамтамасыз ететін репозиторий; · АЖ әзірлеу процесін басқару құралдары; · Құжаттама құралдары; · Тестілеу құралдары; Бағдарламалауға модульдік тәсілін сипаттаңыз. Модульдік бағдарламалау. Уақыт өте келе бағдарламаларға деген көзқарас өзгеріп, бұрынғыдай процедуралар құрудан гөрі мәліметтерді ұйымдастыру жағына көңіл бөліне бастады. Бұған басты себеп болған жайттардың бірі бағдарламалар көлемінің ұлғаюы болды. Бір-бірімен өзара байланысқан процедуралар мен солар арқылы өңделетін мәліметтер жиынын көбінесе модуль деп атайтын еді. Модульдік бағдарламалау ауқымды айнымалылардың белгілі бір тобын қолданатын ішкі бағдарламалар жиынын жеке копиляцияланатын модульдерге (ішкі бағдарламалар кітапханасы) бөліп қарастыру тәсілі болып табылады. Бұл технологияда модульдер арасындағы байланыс арнайы интерфейс арқылы жүзеге асырылады да, сол модульдердің өздерін пайдалануға (ішкі бағдарламалар командаларын және олардың «ішкі» айнымалыларын) тиым салынады. Бұл технологияны Pascal, С/C++, Ада, Modula тілдерінің соңғы нұсқалары сүйемелдейді. Объектіге бағытталған бағдарламалау Дәстүрлі процедураға бағытталған бағдарламалау тәсілдері күрделі бағдарламалардың талаптарын қанағаттандыра алмады. Сондықтан объектіге бағытталған бағдарламалау ұғымы пайда болды. Бағдарламалауға құрылымдық тәсілін сипаттаңыз. Өткен ғасырдың 60 жылдары – бағдарламалаудың «стихиялық» даму кезеңінде бағдарлама құрылымы, мәліметтер типтері сияқты ұғымдар болмады. Сол себепті бағдарламалар қайшылықтары көп, түсінуге қиын кодтардан тұратын еді. Ол кездегі бағдарламалау өзінше бір өнер тәрізді болып көрінетін. Бағдарламалаудағы сондай қиындықтан шығу үшін бағдарламалаудың құрылымдық парадигмасына көшу керек болды. Құрылымдық бағдарламалау есепті шағын құрылымдарға бөліп, олардың әрқайсысын жеке қарастыруды қажет етеді. Мұнда жобалау «жоғарыдан-төмен-ге» қарай жүргізілді де, жалпы құрылым идеясын жүзеге асырып, ішкі интерфейс бағдарламаларын орындауды талап етті. Бұған қоса, алгоритм конструкцияларына шектеулер қойылып, оларды формалды модель түрінде сипаттау ұсынылды және алгоритм құрудың арнайы тәсілі – қадамдық түрде орындау тәсілі қолданылды. Бұл топтағы кең таралған тілдер ретінде PL/1, ALGOL-68, Pascal, С тілдерін атауға болады. Бағдарламалық жабдықтамаларды ары қарай көлемінің өсуі, күрделілігінің артуы мәліметтерді құрылымдауды да дамытуды талап етті. Құрылымдық бағдарламалаудың 3 бөлігі (құраушысы) бар: 1. Модульдік бағдарламалау 2. Құрылымдық кодтау 3. Жоғарыдан төменге қарай жобалау. Бағдарламалау объектілі-бағытталған тәсілн сипаттаңыз. Объектіге бағытталған бағдарламалау Дәстүрлі процедураға бағытталған бағдарламалау тәсілдері күрделі бағдарламалардың талаптарын қанағаттандыра алмады. Сондықтан объектіге бағытталған бағдарламалау ұғымы пайда болды. Объектіге бағытталған бағдарламалау (ОБП) – бұл жаңа технология. Мұнда құрылымдық бағдарламалаудың ең тиімді жақтары алынып, олар жаңа идеялармен толықтырылады. Объектіге бағытталған тіл деп бағдарламалары өзара байланысқан объектілер тізімінен және солардың жұмысын сипаттаудан тұратын бағдарламалау тілін айтады. ОБП ерекшеліктері: бағдарламалық жабдықтамалардың күрделілік дәрежесін төмендету; бағдарламалық жабдықтамалардың сенімділігін жоғарылату; бағдарламалық жабдықтамалардың кейбір компоненттерін қайтадан қолдану мүмкіндігін қамтамасыз ету. ОБП негізгі ұғымдарының бірі – объект. Объект – мәліметтердің логикалық бірлігі ретінде бағдарламада құрастырылған жаңа типтегі айнымалы. Объектінің атқаратын басты міндеті – мәліметтерді және оларды өңдеуге арналған тәсілдердің (ережелердің) бірігуі. С++ тілінде мәліметтерді өңдеу тәсілдер, яғни функциялар арқылы атқарылады. Сондықтан С++ бағдарламалау тілінде объект мәліметтерден және соларға қолданылатын функциялардан тұрады. 77. Д. Гильберттің математикалық , Алгоритмнің «өзбетінше қолдануының» мәселесі атаңыз. 78. Черч тезисі. "Тоқтату" мәселесін сипаттаңыз. Черч тезисі. Алгоритмдік – есептелетін бөлшекті сандық функциялар класы барлық бөлшекті рекурсивті функциялар класымен беттеседі. Бөлшекті рекурсивті функция ұғымы есептелетін бөлшекті функция интуитивті ұғымының ғылымы эквиваленті бола алады. Рекурсивті функция ұғымы қатаң. Сондықтан кәдімгі математикалық техника есепті шешетін функция рекурсивті болуы мүмкін емес деп дәлелдейді. Интуитивті есептелетін функция ұғымы қатаң емес математикалық ұғым. Бірақ ол бөлшекті рекурсивті функция – қатаң математикалық ұғыммен байланысады. 79. Мәліметтер әдісі алгоритмдік шешімін дәлелдеу әдісі ретінде не мағына береді және салыстырмалы талдау жасаңыз. Әдетте, жаңа есептердің шешілмеуі белгілі алгоритмдік шешілмейтін есептерді осы есептерге дейін азайту арқылы дәлелденеді. Осылайша, егер жаңа тапсырма шешілсе, онда әдейі шешілмейтін мәселені шешуге болатындығы дәлелденді. Араластыру әдісін қолдана отырып, олар әдетте өзін-өзі қызықтырмайтын, бірақ жоғарыда сипатталған мәселе сияқты олардың шешілмейтіндігін тікелей дәлелдеу оңай болатын жасанды тапсырмаларға сілтеме жасайды 80. Тьюринг машинасында орындалатын командаларды атап, мысал келтіріңіз. Тьюринг машинасы екі бағытта да шексіз, ұяшықтарға бөлінген таспадан және бағдарламамен басқарылатын автоматтан (бас) тұрады. Тьюринг машиналарына арналған бағдарламалар кесте түрінде жазылады, мұнда бірінші баған мен жолда сыртқы алфавиттің әріптері және автоматтың мүмкін болатын ішкі күйлері (ішкі алфавит) болады. Кестенің мазмұны Тьюринг машинасына арналған командалар. Басшының ұяшықта оқитын әріпі (қазіргі уақытта оның үстінде орналасқан) және бастың ішкі күйі қандай пәрменді орындау керектігін анықтайды. Команда кестедегі сыртқы және ішкі алфавиттердің таңбаларының қиылысуымен анықталады. жүктеу/скачать 0,9 Mb. Достарыңызбен бөлісу:
|