«Информатиканың теориялық негіздері»
жүктеу/скачать 0.6 Mb.
|
- Бұл бет үшін навигация:
- Зертханалық жұмыс №5 (3 сағат) Тақырып: Алгоритмдерді көрсетуді формальдандыру.
| Бақылау сұрақтары
Неге математикада алгоритм ұғымын формальдандыру қажет болды? Алгоритм ұғымын жетілдірудің қандай қырлары бар? Қандай функциялар есептелінетін функциялар деп аталады? Қандай функциялар бөлікті рекурсиялы функциялар деп аталады? рекурсивті функциялар теориясында қандай қарапайым функциялар мен амалдар жиынтығы қолданылады? Черч тезисінің формулировкасы қандай? Посттың абстрактілі машинасының құрылғылары қандай? Тъюрингтің абстрактілі машинасының құрылымы қандай? Тьюринг машинасы қалай сипатталады? Тьюринг машинасының схемаларына мысал келтір. Тьюринг машинасының композициясы деген не? Тьюринг теоремасының мазмұны неден тұрады? Дедекциялық шынжырға мысал келтір. Марковтың қалыпты алгоритмдері қалай анықталады? Әмбебап алгоритмнің есебі неден тұрады? Зертханалық жұмыс №5 (3 сағат) Тақырып: Алгоритмдерді көрсетуді формальдандыру. Формальді тілдер Алгоритмдерді көрсету тәсілдері Құрылымдық теорема Формальды тілдер грамматикасын қарастыруды алгоритмнің қатаң сипаттамасын құру қажеттілігінен келетін болсақ, шын мәнісінде олардың қолданылу облысы әлдеқайда кеңірек. Формальды грамматика негізінде программалау тілдері және оларға трансляторлар құрылады. Жасанды интеллект есептерін шығару кезінде олар машиналық аударуға, сол сияқты эксперттік жүйелердегі өолданушылардың жауаптарына синтаксикалық дұрыс сөйлемдерді генерациялау үшін қолданылады. Формальды грамматикалар оқу және басқа да программаларда қолданылады. Формалды тілдерді сипаттау тәсілдері Объект-тілді сипаттау үшін метатіл қолданылуы қажет. Бірақ метатіл оъект-тілдің құрылымын бірмәнді анықтау үшін формальді тілдің бірқатар қасиеттеріне ие болуы керек, Бұдан, метатіл алдымен өзі сипатталуы қажет, бұл үшін ден сол сияқты тіл қажет -* әрине, мұндай процесстің ешқашан бітпейтіндігі туралы ой қалыптасуы мүмкін. Бірақ кез-келген метатілді сипаттау үшін табиғи тілді қолдануға болатыны дәлелденген. Осылайша формальді тілді құру үшін табиғи тілдің құралдарымен метатілді сипаттау қажет, содан кейін метатіл арқылы формальді тілді сипаттау қажет. Метатілдерді сипаттаудың екі нұсқасын қарастырайық. Ең кең тараған метатілдердің бірі - Бекус-Наур нотациялары. Бекуса-Наура формасында сөйлем құру үшін әмбебап метасимволар қолданылады: { <, >, ::=, | }. Алғашқы екі метасимволды «бұрыштық жақшалар» деп атайды – олар терминді емес сөздерді қоршауға қажет. «::=» символы «анықтама бойынша бар» деп оқылады; «»"символы – «немесе». Бекус-Наура формасында жазылған сөйлемдерде бұрыштық жақшаларда тұрған терминалды емес символ объект-тілдің құрылымы анықтайтын роль атқарады. Бекус-Наур формулаларында әмбебап метасимволдардан айрықша объект-тілдің алфавитінен терминалды символдар қолданыла алады. Формальді тілдің терминалды символдары ешнәрсемен шектелмейді. Формальді тілдердің сипатталуы формулалар тізбегінен тұрады, олардың әрқайсысының сол жағында объект-тілдің қандай-да бір құрылымын бейнелейтін бір метасимвол болады. Мұндай формуланың оң жағы немесе орбъект-тілдің метасимволдар және терминалды символдар тізімінен (бұл жерде ешқандай бөлгіштер қойылмайды), немесе «|» символымен бөлінген тізімдер жинағынан тұрады. Оң және сол бөліктері «::=» таңбасымен бір формулаға бірігеді. Егер кез-келген теминальді емес символды теминалды символдар тізбегі ретінде көрсетуге болатын болса, онда объект-тілді толығымен Бекус-Наур формасында анықталған деп есептеуге болады. Мысал ретінде көптеген программалау тілдерінде қолданылатын «идентификатор» ұғымын анықтауды қарастыруға болады.табиғи тілде анықтама төмендегідей айтылады: «Идентификатор – бұл әріптен басталатын әріптер мен цифрларлың кез-келген тізбегі». Бекус-Наур формасында оло төмендегідей көрінетін болады:
Осы ұғымның анықтамасында рекурсивтілік бар екені көрінеді, себебі «идентификатор» ұғымы өзі арқылы анықталып тұр. Бір әріптен тұратын идентификатор қарапайым болып табылады. Бекус-Наур нотацияларының жетістігі олардың әріптік түрде көрсетілуі; Келесі формальді тілді сипаттау тәсілі бдан да көрнекті деп есептеуге болады: оны PASCAL программалау тілін құрастырушы Никлаус Вирт ұсынған – және «синтаксикалық диаграммалар» деген атауға ие болған. Синтаксикалық диаграмма – бұл объект-тілдің қандай-да бір терминалды емес символын сипаттау схемасы (графикалық көрсетілуі). Схема үнемі бір кіріс және бір шығысқа ие. Схема элементтері ретінде объект-тілдің дөңгелекке алынған теминалды символдары немесе тіктөртбұрышқа алынған объект-тілдің теминалды емес символдары қызмет атқара алады. Элементтер анықталатын терминалды емес символдағы объектілердің ілесу ретін көрсететін бағытталған сызықтармен өзара біріктіріледі. Келесі бейнелеулер қабылданған: Синтаксикалық диаграммалардың құрылымы программалау тілдерінің құрылымдарына ұқсас, бұл диаграммаларды әртүрлі тілдердің трансляторларын жазуға кең қолданылуына мүмкіндік берді. Синтаксикалық диаграммалардың көмегімен сипатталған тіл – PASCAL тілі болған. Диаграмманы оқу стрелка бағытына сәйкес; тармақталу нүктесінде кез-келген маршрут таңдалоынуы мүмкін. Метатіл ретінде табиғи орыс тілі қолданылуы мүмкін; программалау тілдері ағылшын тілі негізінде құрылады. Терминальды символдар формальды тілдердің құрылымына сөзбе-сөз жазылады. Синтаксикалық диаграммаларды құрудың бірнеше мысалын қарастырайық: Қажетті жетілдіретін диаграммалар: Ағылшын тілінде осы диаграммаға сәйкес идентификаторлар құру мысалдары: q, a123, identificator, e2e4. PASCAL тілінің жалпы түрін көрсететін диаграмма: Шартты және циклды жазбалар мысалы: Осындай және ұқсас диаграммаларға сәйкес тілдің мүмкін синтаксикалық құрылымдары құрылады. Сонымен, Бекус-Наур нотациялары және синтаксикалық диаграммалар – бұл формальді тілдер құрылатын метатілдер құрылымын сипаттаудың ұқсас екі тәсілі. Формальды грамматика құрылып болғаннан, және бұдан тіл туындаса, ол қолданбалы есептерді шешуге қолданыла алады – коммуникация, ақпаратты сақтау және өңдеу. Соңғы есептер класы тілдер көмегімен ақпаратты өңдеу тізбегін сипаттауды жасаудың қажеттігіне әкеледі, яғни алгоритмдерге және оларды өңдеуді жүргізетін адам немесе техникалық құрылғы түсініп, орындауға мүмкін формада көрсету. жүктеу/скачать 0.6 Mb. Достарыңызбен бөлісу:
| ||||