Жүйелік программалау пәнінің алатын орны және оны зерттеудің заманауи тәсілдері
1.1 Жүйелік программалаудан виртуальді зертханалық жұмыстарды жасау мақсаты
Информатика бойынша элетивті курс
1.1. Элетивті курс туралы түсінік
1.2. Элективті курстығ маңызы мен формасы
1.3. Информатика бойынша элективті курста басқарудың әртүрлі түрлерін реализацияда қолданылатын басқару құралы
1.2.ТМ үшін программа құруға мысалдар
2. Марковтың қалыпты алгоритмдері
1.3 Есептің қойылуы және зертхана құру технологиясы
2 ЖҮЙЕЛІК ПРОГРАММАЛАУДАН ВИРТУАЛЬДІ
ЗЕРТХАНАЛЫҚ ЖҰМЫСТАРДЫ ЖОБАЛАУ
2.1 Жүйелік программалау пәнін сипаттау
2.2 Жүйелік программалау пәнінің зертханасының құрамы және
құрылымы
2.3 Зертхана жұмысының алгоритмдерін, әдістемелерін өңдеу
2.4 Компьютерлік жүйемен оқушының қатынас интерфейсін құру
Информатика бойынша элетивті курс
1.1. Элетивті курс туралы түсінік
1.2. Элективті курстығ маңызы мен формасы
1.3. Информатика бойынша элективті курста басқарудың әртүрлі түрлерін реализацияда қолданылатын басқару құралы
1.2.ТМ үшін программа құруға мысалдар
2. Марковтың қалыпты алгоритмдері
1.3 Есептің қойылуы және зертхана құру технологиясы
2 ЖҮЙЕЛІК ПРОГРАММАЛАУДАН ВИРТУАЛЬДІ
ЗЕРТХАНАЛЫҚ ЖҰМЫСТАРДЫ ЖОБАЛАУ
2.1 Жүйелік программалау пәнін сипаттау
2.2 Жүйелік программалау пәнінің зертханасының құрамы және
құрылымы
2.3 Зертхана жұмысының алгоритмдерін, әдістемелерін өңдеу
2.4 Компьютерлік жүйемен оқушының қатынас интерфейсін құру
Ақпараттық жүйелерді құру жұмысы пәндік облысқа талдау жүргізуден басталады. Нысанның жұмыс істеу барысын талдағанда жүйені қарастыру шекаралары еске алынып, болашақ ақпараттық жүйені қолданушылар анықталып, автоматтандырылатын кластар мен нысандар типтері қарастырылуы қажет.
Пәнді облысқа талдау жүргізу, ол - жобалау алдында сол пәндік облыстың зерттеу мәліметтерін жинау, қалыптастыру және талдау, сонымен бірге зерттеу объектісінің автоматтандырылатын есептер жиынтығын таңдау және нақтылау болып келеді.
Компьютерлік қызмет көрсететін менеджер клиенттердің тапсырысын қанағаттандыра алуы, тапсырыстар ағымын қарастыруы және қызмет көрсету сапасын мен өндірістік процестердің жылдамдығын арттыра алуы қажет. Компьютерлік қызмет көрсету бөлімінің менеджерлерінің негізгі функциялары:
- компьютерлерді сатуға келісім-шартты рәсімдеу;
- клиенттерден тапсырыстарды қабылдау;
- клиенттермен жұмыс (сатылымдарға талдау, клиенттер анықтамаларын жүргізу);
- есеп шот пен жинақтамаларды рәсімдеу ;
- сатылып алынатын өнімге немесе қызмет көрсетілген жұмысқа санақ жүргізу (шотты шығару);
- қызмет көрсетілген жұмыстарға есеп беру және т. б.
«Таразспецтехбаза» ЖШС-гі (жауапкершілігі шектеулі серіктестігі) шаруашылық қызмет көрсету арқылы серіктестік мүшелері мүддесі үшін пайда көру, сонымен бірге ішкі нарықтың талаптарын қанағаттандыру. Ұйымның қаржысы өнімді, жұмысты және қызметтерін нәтижелеуден түскен пайдадан құралады.
Осы аталған мақсаттарға жету үшін «Таразспецтехбаза» ЖШС-і мына жүмыстарды атқарады:
- құрастырушыларды сатып алу;
- клиенттердің тапсырысы бойынша компьютерлерді құрастыру;
- компьютерлерді жөндеу;
- компьютерлерді сату;
- кепілділік қызметін көрсету.
Потенциалды сатып алушылардың нарығын зерттеу және сатылуға ұсынылып отырған нысандардыңңң ұсыныстары негізінде қызметкер немесе арнайы маман каталогті өңдейді; үлкен фирмадағы сондай қызметті маркетинг бөлімі дейтін еді. Ал бұл ұйымда маркетинг қызметі экономикалық бөлімде атқарылады.
Пәнді облысқа талдау жүргізу, ол - жобалау алдында сол пәндік облыстың зерттеу мәліметтерін жинау, қалыптастыру және талдау, сонымен бірге зерттеу объектісінің автоматтандырылатын есептер жиынтығын таңдау және нақтылау болып келеді.
Компьютерлік қызмет көрсететін менеджер клиенттердің тапсырысын қанағаттандыра алуы, тапсырыстар ағымын қарастыруы және қызмет көрсету сапасын мен өндірістік процестердің жылдамдығын арттыра алуы қажет. Компьютерлік қызмет көрсету бөлімінің менеджерлерінің негізгі функциялары:
- компьютерлерді сатуға келісім-шартты рәсімдеу;
- клиенттерден тапсырыстарды қабылдау;
- клиенттермен жұмыс (сатылымдарға талдау, клиенттер анықтамаларын жүргізу);
- есеп шот пен жинақтамаларды рәсімдеу ;
- сатылып алынатын өнімге немесе қызмет көрсетілген жұмысқа санақ жүргізу (шотты шығару);
- қызмет көрсетілген жұмыстарға есеп беру және т. б.
«Таразспецтехбаза» ЖШС-гі (жауапкершілігі шектеулі серіктестігі) шаруашылық қызмет көрсету арқылы серіктестік мүшелері мүддесі үшін пайда көру, сонымен бірге ішкі нарықтың талаптарын қанағаттандыру. Ұйымның қаржысы өнімді, жұмысты және қызметтерін нәтижелеуден түскен пайдадан құралады.
Осы аталған мақсаттарға жету үшін «Таразспецтехбаза» ЖШС-і мына жүмыстарды атқарады:
- құрастырушыларды сатып алу;
- клиенттердің тапсырысы бойынша компьютерлерді құрастыру;
- компьютерлерді жөндеу;
- компьютерлерді сату;
- кепілділік қызметін көрсету.
Потенциалды сатып алушылардың нарығын зерттеу және сатылуға ұсынылып отырған нысандардыңңң ұсыныстары негізінде қызметкер немесе арнайы маман каталогті өңдейді; үлкен фирмадағы сондай қызметті маркетинг бөлімі дейтін еді. Ал бұл ұйымда маркетинг қызметі экономикалық бөлімде атқарылады.
Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 61 бет
Таңдаулыға:
Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 61 бет
Таңдаулыға:
1 Жүйелік программалау пәнінің алатын орны
және оны зерттеудің ЗАМАНАУИ ТӘСІЛДЕРІ
1.1 Жүйелік программалаудан виртуальді зертханалық жұмыстарды жасау
мақсаты
Информатика бойынша элетивті курс
1. Элетивті курс туралы түсінік
2. Элективті курстығ маңызы мен формасы
1.3. Информатика бойынша элективті курста басқарудың әртүрлі түрлерін
реализацияда қолданылатын басқару құралы
1.2.ТМ үшін программа құруға мысалдар
2. Марковтың қалыпты алгоритмдері
1.3 Есептің қойылуы және зертхана құру технологиясы
2 Жүйелік программалаудан виртуальді
зертханалық жұмыстарды жоБАЛАУ
2.1 Жүйелік программалау пәнін сипаттау
2.2 Жүйелік программалау пәнінің зертханасының құрамы және
құрылымы
2.3 Зертхана жұмысының алгоритмдерін, әдістемелерін өңдеу
2.4 Компьютерлік жүйемен оқушының қатынас интерфейсін құру
1 Жүйелік программалау пәнінің алатын орны
және оны зерттеудің ЗАМАНАУИ ТӘСІЛДЕРІ
1.1 Жүйелік программалаудан виртуальді зертханалық жұмыстарды жасау
мақсаты
Ақпараттық жүйелерді құру жұмысы пәндік облысқа талдау жүргізуден
басталады. Нысанның жұмыс істеу барысын талдағанда жүйені қарастыру
шекаралары еске алынып, болашақ ақпараттық жүйені қолданушылар анықталып,
автоматтандырылатын кластар мен нысандар типтері қарастырылуы қажет.
Пәнді облысқа талдау жүргізу, ол - жобалау алдында сол пәндік облыстың
зерттеу мәліметтерін жинау, қалыптастыру және талдау, сонымен бірге
зерттеу объектісінің автоматтандырылатын есептер жиынтығын таңдау және
нақтылау болып келеді.
Компьютерлік қызмет көрсететін менеджер клиенттердің тапсырысын
қанағаттандыра алуы, тапсырыстар ағымын қарастыруы және қызмет көрсету
сапасын мен өндірістік процестердің жылдамдығын арттыра алуы қажет.
Компьютерлік қызмет көрсету бөлімінің менеджерлерінің негізгі функциялары:
- компьютерлерді сатуға келісім-шартты рәсімдеу;
- клиенттерден тапсырыстарды қабылдау;
- клиенттермен жұмыс (сатылымдарға талдау, клиенттер анықтамаларын
жүргізу);
- есеп шот пен жинақтамаларды рәсімдеу ;
- сатылып алынатын өнімге немесе қызмет көрсетілген жұмысқа санақ жүргізу
(шотты шығару);
- қызмет көрсетілген жұмыстарға есеп беру және т. б.
Таразспецтехбаза ЖШС-гі (жауапкершілігі шектеулі серіктестігі)
шаруашылық қызмет көрсету арқылы серіктестік мүшелері мүддесі үшін пайда
көру, сонымен бірге ішкі нарықтың талаптарын қанағаттандыру. Ұйымның
қаржысы өнімді, жұмысты және қызметтерін нәтижелеуден түскен пайдадан
құралады.
Осы аталған мақсаттарға жету үшін Таразспецтехбаза ЖШС-і мына
жүмыстарды атқарады:
- құрастырушыларды сатып алу;
- клиенттердің тапсырысы бойынша компьютерлерді құрастыру;
- компьютерлерді жөндеу;
- компьютерлерді сату;
- кепілділік қызметін көрсету.
Потенциалды сатып алушылардың нарығын зерттеу және сатылуға ұсынылып
отырған нысандардыңңң ұсыныстары негізінде қызметкер немесе арнайы маман
каталогті өңдейді; үлкен фирмадағы сондай қызметті маркетинг бөлімі дейтін
еді. Ал бұл ұйымда маркетинг қызметі экономикалық бөлімде атқарылады.
Сондықтан клиенттің тапсырысы бойынша ақпараттық құралдарды және
конфигурацияларды таңдау бизнес-үрдісін автоматтандыру жұмысын нәтижелеу
варианты таңдалды.
XX ғасырдың соңында адамдардың индустриалды дәуірдің аяқталуымен және
ақпараттық дәуірге көшуімен сипатталады. Ақпаратты қолдана білу, оны өңдей
білу цивилизацияны дамыту болып табылады. Бұл курстық жұмыс элективті
курсты құруға арналған.
Элективті курс – оқу жоспарының жаңа элементі бағдарлы мазмұнын
толықтырады және оқушылардың әртүрлі қызығушылығын қанағаттандырады.
Элективті курс әртүрлі тақырыпқа, сонымен де жалпыбілімдік программаға да
қатысады. Біз информатиканың элективті курсы мен элетивті матиматикасын
ұсынамыз. Элективті курс бұл жаңа актуалды механизм және оқытудың
индивидуалды процесі. Жақсы жоспарланған элективті курстан, әрбір оқушы өз
қалауымен бір білім облысында білім алуына болады.
Элективті курс информатиканың оқушылар компаненті орындалады және
бірнеше функция атқарады: бағдарлы курстың мазмұнын толықтырады, бір
базалық курстың мазмұнын дамытады, әртүрлі дамытушылық қызығушылықтарды
қанағаттандырады.
Айта кететін жайт, элективті курсқа бірынғай мемлекеттік емтихан
өткізілмейді. Элективті курс информатиканың таға да бір маңызды функциясын
атқарады – жаңа оқулықтар материалдарын тексеруді. Факультативті курстың
өткізілуі оның аналогтық курстық функциясын жақсы орындағанын көрсетеді.
1. Информатика бойынша элетивті курс
1. Элетивті курс туралы түсінік
Элективті курс (таңдау бойынша курс) бағдарлы оқыту жүйесінің
маңызды рөлін атқарады. Факультативті курстан басқа, мектепке қатысты,
жоғарға сыныптарға арналған элективті курс.
Қазақстан Республикасында жақын арада жоғарғы мектептік білімде
бағдарлы оқыту енгізілді, құрамалық бөлік жалпы білімдік базаға байланысты
тереңдетілген (мамандандырылған және бағдарлы) және элективті курстар.
Әртүрлі курстарды орындағанда мұғалімдер жолында қиындықтар болуы мүмкін.
Олардың формальді білімнің , дарындылығы мен қолдана білуі іске асырылады.
Бақылаушының сұрағы актуальді, бақылау құрамалық бөлтік болып табылады,
оқытудың компанентті процесі, программалық материалды меңгерумен
байланысты, бекітуі мен қолданылуы, тиімді методтарды қолданылуымен, дер
кезінде орнатуға көмектеседі, сонан соң оқу процесінде аяқталмаған істі
жүргізеді, оқу материалдарының жетіспеушілігін қолға алады және ары қарай
жұмыс істеуіне көмектеседі.
Жалпы білімдік базалық курстың формасы мен мазмұны бойынша жай
сабақтар бойынша қойылады, қазіргі мектепте жүргізілген, сұраққа жауап
ретінде жабдық бақылауы мен түр таңдауы оларға еш қиындықсыз табуға болады6
8лкен баспа мекемелер, сонымен әртүрлі реализациялық сабақ түрлерінен
болады. Өкінішке орай, осындай жас мектептік дисциплинаға, информатика
сияқты, аса практикалық материалдар жоқ. Сондықтан да информатика
мұғалімдері осы сұрақты қызықтыратын, педагогикалық жұмысқа қатысты немесе
информатикаға жақын пәнге назар аудару керек.
Бағдарлы және элективті курстарға қатысты айтатын болсақ, олар соңғы
3-4 жылдың ішінде зерттелініп келе жатыр.Бақылауға және диагностикаға
байланысты нақты материал ала алынған жоқ.Авторлардың бір ғана затқа көңіл
аударуы мүмкін, ол соңғы сынақ проекті жобаға байланысты жүзеге асатын,
соның ішінде оқушылардың өздерінің элективті курс0а байланысты жаса5ан
жобалары немесе (конференциадағы баяндамалар) оқушылардың өздерінің
элективті курстарға байланысты материалдардан алған білім деңгейлерін
көрсететін баяндамалар. Курстық жұмыстың материалдары негізінен (элетрондық
және баспасөздік материлдарға негізделген) информатикаға байланысты
элективті курстарға
және компьютерлерге арналған дисциплина және оларды құруға арналған
тақырыбында курстарды өткізуге арналған.
Қазіргі кездегі ең жақсы мектептердің бір жоғарғы сыныптарға арналған
бағдарлы оқыту негізінен ол 3 бөлімнен тұрады:
- Базалық (негізгі)
- тереңдетілген (мамандандырылған)
- элективті (дамытушылық)
Егер де алғашқы екеуімен бәрі түсінікті, өйткені ол жоба кәдімгі
мектептерде де қолданылады, ал элективті курс олардан сәл өзгешелеу.
Біріншіден – оған байланысты нормативті құжаттар дайындалмаған. Екіншіден –
оған байланысты дайындалған жобалар тәжірибеден өтпеген және қана баяндама
ретінде қалған. Үшіншіден – элективті курсқа байланысты
базалардайындалмаған және ғылыми зерттеулерді күтуде. Төртіншіден –
элективті курсқа байланысты жасалған жалпы жоба жоқ.
Элективті курстың педагогикалық маңызын бағалай отырып, оның ғылымғы
деген қажеттілігін есте сақтау қажет.
2. Элективті курстығ маңызы мен формасы
Бірден айтып кететін жайт, элективті курс авторлық болып табылады
және ол оқу жоспарына арналған уақыттан аспайды, тәжірибе көрсеткендей ол
16 дан 134 сағатқа дейін болып келеді. Айтылған курстық жұмыста тек қана
мынадай элективті курс қарастырылған: оған уақыты 34 сағаттан аспайды,
өйткені мұндай ауқымды курстар мазмұнды және практикалық жүйелерге
бөлінген.
Элективті курстар жалпы білімдік курстар және кәсіптік курстардан
ерекшелінеді, формасы бойынша, мазмұны бойынша мектептегі білім берудегі
индивидуалды әдіс болып саналады. Олар тікелей білім берудегі мақсаттарға,
міндеттерге, өмірдегі жоспарларға байланысты. Элективті курстар – ол
таңдалынған білім берудегі жоғарғы сыныптардың білім беру жоспарына кіру
міндетті деп кездейсоқ айтылмаған. Сондықтан да элективті курстардың
өткізілу барысы 4 түрлі бақылау өткізу керек .
1. Кіріспе
2. өту барысы
3. аралық
4. соңғы
Ал бағдарлы және базалық курстарда бастапқы бақылаудан бас тартуға
болады. Бұл оның сатысын және оқу деңгейін анықтауға арналғандығына
байланысты. Төменгі деңгейі базалық курстың және бағдарлы курстың
білімгерлеріне таңдауға көмектеседі.
Бастапқы бақылаудың ең оңай түрі анкета және әңгіме. Кейінгісінен ең
үйлесімді, өйткені кеңес кезінде мұғалім оқушының білімін, айқын
мүмкіншілігін біле алады. Бірақ кеңес ұзақ уақаыт алып қояды, сондықтан да
кейбір кезде анкетамен толығымен ауыстырады. Бірақ анкеталық мұғалімге
қиыншылық тудыру мүмкін олар: сұрақтың толықтылығы мен мазмұны. Анкетадағы
сұрақтар тек қана ойдағыдай нәтиже бермей қоймай мұғалімді ойландырады,
қателестіреі, оның соңы білімнің сапасын төмендетеді. Оқушылардың жүйелік
өзіндік жұмысқа ынталануы, ұмтылуы, өзінше сынып және үй жұмысын жасауы,
берілеген жұмысқа жауапкершілік сезімі ағымдағы бақылауда үлкен мәні бар.
Элективтік курстарда ол әр сабақта жүзеген асады, және ақпарат алуға
бағытталған. Талдай отырып, мұғалім өзінің түзетулерін енгізеді. Мысалы
мазмұнының оқу әдісінің, өзгеруі. Ол тағыда мұғалімге оқушылардың білім
сатысын көрсетеді және оқушыларға қандай материал беруінің болжамдайды.
Жалпы түрде клгенде ағымдағы бақылау сұрақ жүйесі, бақылау, кеңес,
творчествалық тапсырмалар арқылы жүзеге асады.
Рубежкалық (шекаралық) бақылау тек қана көлемі 34 сағаттық элективті
курстарда ғана мүмкін, өйткені осы сияқты курстар бөлімнен тұрады және
рубежкалық бақылау бір- бірімен келісетін бөлімнін зерттеуінің аяқталуы.
Шекаралық бақылаудағы құралдардың арасында кіші жобалар, тесттер,
индивидуалдық тапсырмалар қолданылады.
Элективті курста қорытынды бақылау аяқтайды, мұғалім оқушының алған
білімін, дағдыларын, іскерлігін анықтайды. Информатикаға сәйкес элективті
курсты жобалық жұмыспен немесе белгілі тақырыптағы рефератпен аяқталады.
Бақылаудың құралын нақты таңдау біріншіден элективті курстың бағытымен
мақсатына, екіншіден мәтініне, үшіншіден дайындықтың сатысына және оқушының
интелектуалды дамуына байланысты. Информатикадан элективті курстың келесі
бағыттары бар: олар базалық жалпы білімді курстармен терең немесе кең білім
беру, ЖОО түсу үшін дайындық немесе ҰБТ-ны тапсыру, бастауыш
мамандандырылған дағдылар алу үшін курстың мәтіні ең қиын сұрақ, немесе
мәтіннің анықтамасы қатты бекітілмейді және элективті курсқа келушілердің
мүмкіндігін ескем алу керек.Бақылау құралының таңдауының қиындығы, элетивті
курс авторлық болып саналады, және оны өздері анықтайды, көбінесе бақылау
құралдарының қолданғанға берілетін кепілдер қиынға түседі.
Базалық жалпы білімді курстар барлық оқушыларға білімнің міндетті
инварианттық бөлімін көрсетеді және жалпы білімді дайындықтың аяқталуына
бағытталған. Бағдарлы курстар әр пәннің терең зерттеуін қамсыздандырады
және ең біріншіден мектеп бітірушілердің келесі кәсіптік біліміне
дайындайды. Элективті курстар әр оқушының қажеттілігімен, бейімділігімен
байланысты. Тек қана осы ғана индивидуалды жалпы білімді программаны құруға
мүмкіндік береді, өйткені көбінесе олар оқушының талдауымен,
қабілеттілігімен, кейінгі өмірдегі мақсатпен байланысты. Элективті курстар
базалық және бағдарлы шектеулі мүмкіншіліктерді компенсациялайды, жоғарғаы
сынып оқушыларының білімдік қажеттілігін қанағаттандырады. Элективті
курстың осы рөлі бағдарлы білім беру жүйесінде кең спектрді және оның кең
функция есептерін айқындайды. Бірнеше элективті курстардың типтарын
белгілеуге болады. Олардың кейбіреуі дарынды оқушыларға белгілі бір пәннен
жоғары сатыда білім бере алады. Басқа элективтер пән аралық байланыс және
қосымша оқулық пәндерді бағдарлы сатыда оқи алады. Элективті курстын
мысалы: Математикалық статистика экономикалық бағдарлы таңдаған
оқушыларға арналған, компьютерік графика индустриалды – технологиялық
профильге арналған немесе Өнер тарихы гуманитарлық бағдарға арналған.
Элективті курстың үшінші түрі оқушыға ҰБТ-ны жоғары деңгейде тапсыруға
мүмкіншілік береді. Тағы да бір айта кетсек ол оқушыға еңбек базарында
біліми нәтиже береді.
1.3. Информатика бойынша элективті курста басқарудың әртүрлі түрлерін
реализацияда қолданылатын басқару құралы
Көрсетілген кестеде, элективтік курстарға арналған бақылаудың түрлері
келтірілген.
Курстың бағыты – білімнің кеңейтуі.
Курстың аты – Компьютерлік графика Бейсикте.
Ұсынылатын бағдар: физика-математикалық, технологиялық.
Бақылау түрі
алдыңғы Ағымдағы шекаралық қорытынды
Кеңес, Бейсик құралыменШығармашылық мини Жобалар
оператолардың берілген жобалар және Үшөлшемділік
Бейсик суреттерді индивидуалдылық Бейсик
программасын құрудың тапсырмалар құралымен,
айқындауға тапсырмалары Бейсикте ертегі
(білуге) жазамыз
арналған тест
Курстың аты – Компьютерде мәтіндік информацияның өңдеуі.
Ұсынылатын бағдар – физика-математикалық, технологиялық, гуманитарлық.
Бақылау түрі
алдыңғы Ағымдағы шекаралық қорытынды
Анкеталық, MS Программалық MS Шығармашылық Индивидуалды
Excel Excel және тапсырмалар, тапсырмалар
функциясына жәнепрограммалық өзіндік шығаруға
жүйе жүйенің арналған
программалық тапсырмалары тапсырмалар
операторына
тесттер
Курстың аты – Компьютерде қызықты материалдың өңдеуі.
Ұсынылатын бағдар: физика-математикалық, технологиялық, гуманитарлық.
Бақылау түрі
алдыңғы Ағымдағы шекаралық қорытынды
Анкеталық Бақылау, мини Шығармашылық Мектептегі
шығармашылық тапсырмалар, дисциплинаның
тапсырмалар мини жобалар бір бөліміне
жобалық жұмысы
1. Тьюринг машинасы
Бөлімде Тьюринг машинасына арналған алгоритімдерді құру есептері
қарастырылады. Машинаға қысқаша сипаттама, соған сәйкес алгоритім құру
мысалдары және өзіндік жұмыстарға есептер беріледі.
1. Тьюринг машинасына сипаттама
Тьюринг машинасының құрлымы
Тьюринг машинасы (МТ) 2 бөліктен тұрады – лента және автомат (сол жағынан
қара):
q
автомат:
Лента ақпарат сақтауға арналған. Ол екі жағынан шексіз және
номірленбейтің, ат қойылмайтын торларға бөлінген. Әр торда бір символ
жазылуы немесе жазылмауы мүмкін. Тор ішін өзгертуге болады – оған басқа
символ жазуға немесе ондағы символды өшіруге болады.
Бос торларды бос символ деп атап және оны Λ (лямбда) белгісімен
белгілейміз.
Осыған байланысты суреттегі сол жақтағы лента оң жақтағы суретгідей. Бұл
кейбір тордағы символдарды өшіруді осы клеткаға Автомат – Тьюринг
машинасының активті бөлігі. Ол әр уақытта лентаның бір торына орналасып,
оның құрамын көреді: бұл көрінетін тор , ал оның ішіндегі символ көрінетін
символ деп аталады ; автомат көрші және басқа торларды көре алмайды.
Соңымен қатар автомат әр уақытта белгілі бір күйде болады, оны q әріпімен
белгілеп, q1, q2 нөмірлерімен нөмірлейміз. Автомат белгілі бір күйде болып
белгілі бір операция орындайды(мысалы, лентада оңға жылжып b және а
символдарын алмастырады), басқа күйде – басқа операция орындайды.
Автомат ағымдағы күйінде (q) көрінет символ жұбын (S) - конфигурация
деп атап, S, q белгісімен белгілейміз.
Автомат 3 элементар әрекеттерді орындайды:
1) көрінетін торға жаңа символ жазуды (автомат басқа торларды өзгерте
алмайды);
2) бір тор оңға немесе солға жылжиды (автомат бірнеше торлардан секіре
алмайды);
3) жаңа қалыпқа тұрады.
Автомат басқа әрекеттерді орындай алмайтындықтан, орындалатын
операциялардың барлығы осы 3 әрекеттерге сай келу қажет.
Тьюринг машина жұмысының такті
Тьюринг машинасы бір бірінен кейін орындалатын тактармен жұмыс
істейді.Әр такта тьюринг машина автоматты келесі үш әрекеттерді орындайды
және олар міндетті түрде көрсетілген ретімен орындалу керек:
1) S’ символын көрінетін торға жазады;
2) Бір тор солға жылжиды ( мағынысы – L, left), немесе бір тор оңға
жылжиды (мағынасы - R, right), немесе жылжымайды (мағынасы - N);
3) Белгілі бір q’ күйге келеді (бұрынғы қалпында да қала алады).
Формальды түрде бір такт үштік түрінде жазамыз:
S’,[L, R,N], q’
мұнда квадрат скобка ның орнына кез келген L, R, N әріпін жазуға мүмкіндік
береді. Мысалы, *,L,q8 такті көрінетін торға * символының жазылуын
білдіреді, бір тор солға жылжуды және q8 күйіне көшеді.
Тьюринг машинасына программа
Тьюринг машинасы өзінен өзі ешнарсе жасамайды. Оны жұмыс жасату үшін
оған программа жазу керек. Программа келесі кестедегідей жазылады:
Егер енгізілген сөз бос болса, онда автомат басқа бос торларды қарайды,
себебі олар бос.
Осы бастапқы әдәстерден кейін программаның орындалуы басталады.
Кестеден бірінші жолмен қиылысатын және (автомат q1 күйінде тұрады)
енгізілген сөздін бірінші символына сәйкес бағанға, (кестенің сол бағаны
болу шарт емес) осы ұяшыққа сәйкес тактті орындайтын ұяшық табылады.
Нәтижесінде автомат жаңа конфигурацияда орналасады. Енді осындай әрекеттер
жаңа конфигурацияға орындалады: кестеден қалыпқа сай және осы конфигурация
символына және осы ұяшықтын тактін орындайтын ұяшық табылады .
Программа орындалуы қашан аяқталады? Тоқтау такт ұғымын енгізейік. Ол
еншәрсені өзгертпейді: автомат көрінген торға бұрын болған символды жазады,
орны айыстырылмай бастапқы күйінде қалады, яғни S, q конфигурациясына
S,N,q такті. Тоқтау такті анықтап, тоқтап, өз жұмысын аяқтайды.
Толық алғанда Тьюринг машинасы жұмыс істеуінің 2 жолы бар:
1) Бірінші жолы – жақсы: бұл Тьюринг машинасының тоқтау сәті (тоқтау
сәтіне келгенде). Бұл жағдайда Тьюринг машинасы енгізілген сөзге
қолданулы деп атайды. Ал осы сәтте лентада алынған сөз шығу сөзі болып
саналады, яғни Тьюринг машина жұмыс нәтиже жауабы.
Тоқтау сәтіне келесі шарттар орындалу қажет:
- шығу сөзінің ішінде бос торлар болмау қажет (программа барысында
өнделетін сөз арасында бос торлар болу мүмкін, бірақ соңында олар
қалмау тиіс);
- Автомат шығу сөзінің бір символына тоқтау тиісті (қайсысына екені –
маңызды емес), ал сөз бос болса – кез келген лента торына.
2) Екінші жолы – жаман: ол Тьюринг машинасы ешқашан тоқтау тактісіне
түспей айнала береді (мысалы, автомат әр қадам сайын оңға жылжи береді
және тоқта алмайды, яғни лента шексіз). Бұл жағдайда: Тьюринг машинасы
енгізуле сөзіне қолданусыз деп аталады. Бұл жағдайда нәтиже болмайды.
Бір алгоритмнің Тьюринг машинасы (Тьюринг машина программасы) бір
енгізулі сөзіне қолданылатын (яғни тоқтайды) және басқаларға қолданусыз
(яғни айналады) болатының белгілейік. Яғни қолданулы қолданусыз болу тек
алгоритмнен ғана емес, сонымен қатар енгізулі сөзіне де байланысты.
Алгоритім қай енгізулі сөзінде тоқтау қажет? Жақсы сөздерге, яғни
жіберуге болатын мәндерде. Бірақ лентада кез келген, сонымен қатар есептін
мәні болмайтын енгізілген сөздер жазуға болады; мұндай сөздерде алгоритм
фиксирленген, тоқтай алады (кез келген нәтижеде), сонымен қатар айналу да
мүмкін.
Жазуды қысқартуға арналған келсім
Тьюринг машина программасын қысқартатын келсімдерді келтірейік
1) Егер тактте көрінетін символ өзгермесе немесе автомат жылжымаса немес
автомат күйі өзгермесе, сәйкес такт позициясы еш нәрсе жазылмайды.
Мысалы, a,q1 конфигурациясына келесі такт жазулары эквивалентті:
a,R,q3≡ ,R,q3 (Λ, R,q3!! тек бұларға емес )
b,N,q2≡ b, ,q2
a,L,q1≡ ,L,
a,N,q1≡ , , (бұл тоқтау
такті)
Ескерту. Тактар арасында үтір қалмауы тиіс, себебі шатасу болу мүмкін, егер
лента символарының арасынан L және R әріптері кездесе.
2) Егер бірнеше Тьюринг машина тактіден кейін тоқтау тиіс екенің көрсету
керек болса, онда үшінші такт позициясында ! белгісін жазу керек.
Мысалы, b,L,! такт келесі әрекеттердібілдіреді: b символының көрінетін
лента клеткасына жазылып, солға бұрылып, тоқтайды.
3) Егер, программа орындалу процесінде бірнеше конфигурация орындалмау
мүмкіндігі белгілі болса, онда мұны анық көрсету үшін сәйкес кесте
ұяшығына крестик саламыз. (Формальді түрде бұл крестик тоқтау такті
болып саналады).
Бұл келсімдер шартты емес, бірақ олар программа жазылуын қысқартып,
оны қабылдауды жетілдіреді.
1.2.ТМ үшін программа құруға мысалдар
ТМ-да кейбір типті программалау тәсілдерін көрсету үшін ТМ-нда программа
құруға арналған мысалдарды қарастырайық.
Есептің тұжырымдалуын қысқарту үшін келесідей екі келісімді енгіземіз:
- Р әрпі кіріс сөзін білдіреді;
- А әрпі кіріс сөзінің алфавитін білдіреді, яғни тек Р-дан ғана тұратын
символдар жиынтығы (айта кетін жайт, аралық және шығыс сөздерінде
басқа да символдар пайда болуы мүмкін).
1 Мысал (автоматты орналастыру, символдарды ауыстыру).
. Р-бос емес сөз болсын.Р-ондық сандардың реттелуі, яғни ондық
жүйедегі теріс емес бүтін сандардың жазылуы. Лентада Р санынан 1-ге үлкен
сандардың лентада жазылуын алу қажет.
Шешуі:
Бұл есепті шешу үшін келесі әрекеттерді орындау керек:
1.Автоматты соңғы цифрдың астына айдау.
2.Егер ол сан 0-ден 8-ге дейінгі сан болса, онда оны 1 санға жоғары етіп
алмастыру керек және тоқтау қажет, мысалы:
3.Егер 9 саны болса, онда оны 0 санымен алмастыру қажет және автоматты
алдыңғы санға жылжыту қажет. Одан кейін осы әдіспен соңғының алдындағы
санды 1-ге үлкейту керек, мысалы:
4.Ерекше жағдай: Р-да тек ондықтар (мысалы, 99). Онда автомат тоғыздықтарды
нольдермен алмастыра отырып солға қарай жылжиды және соңында бос клеткаға
тап болады. Бұл бос клеткаға 1 санын жазу керек және есептеуді тоқтату
қажет (жауабы 100 болады):
ТМ үшін арналған программа түріндегі бұл әрекеттер келесі түрде беріледі:
0 1 2 3 4
q1 A,R,q2 A,R,q3 A,R,q4 ,R, 1 символды талдау, оны
өшіру, тармақталуы
q2 ,R, ,R, ,R, a, ,! а –ның оң жақта жазылуы
q3 ,R, ,R, ,R, b, ,! b–ның оң жақта жазылуы
q4 ,R, ,R, ,R, c, ,! с–ның оң жақта жазылуы
Құрамында бір символдан артық символға ие кіріс сөздердегі программаның
әрекетін қарастырайық. Есеп үшін нашар болып табылатын бос сөзде
программа автоматты түрде тоқтап қалады, q1 күйінде болады және бос
клеткаларға түскен сайын ол шексіз оңға қарай орналасады.
Егер кіріс сөзінде дәл бір символ болса, онда автомат ол символды өшіреді,
бір клеткаға оңға жылжиды және оған берілген символды жазады:
q1 q4
!
Осылайша, бір сөзден тұратын символ жай ғана бір клеткаға оңға жылжиды. Бұл
мүмкін нәрсе. Лентаның клеткалары номерленбеген, сондықтан лентадағы сөздің
орны жазып алынбайды және сөзді оңға және солға орын ауыстыруын алмастыруға
болмайды. Осыған байланысты, кіріс сөзі міндетті түрде дәл сол жерде, яғни
кіріс сөзі болған жерде болуы қажет емес, нәтижесі ол орыннан солға немесе
оңға қарай болуы мүмкін.
Мысал 3 (символдарды салыстыру, сөзді өшіру)
. Р сөзінің бірінші және соңғы символдарды (бос емес) бірдей болса,
онда ол сөзді ауыстырмау керек, әйтпесе оны бос сөзге ауыстыру қажет.
Шешімі.
Бұл есепті шешу үшін келесі әрекеттерді орындау керек:
1. Кіріс сөзінің бірінші символын оны өшірмей тұрып, оны есте сақтау
керек.
2. Автоматты соңғы символдың астына орналастырып және ойдағы символмен
салыстыру керек.
3. Қарсы жағдайда барлық кіріс сөзін жойып жіберу қажет.
Символды қалай есте сақтау керектігін және автоматты соңғы символдың
астына айдауды алғашқы мысалдардан білеміз. Кіріс сөзінің өшірілуі оның
барлық символдарының А символына ауыстырылуымен жүзеге асырылады.
Осылайша, автомат сөз соңында болғандықтан, енді автоматты бірінші бос
клеткаға дейін оңнан солға қарай орналастыратын боламыз.
Бұл әрекеттер ТМ үшін келесідей программа түрінде бейнеленеді (есте
сақтайтын нәрсе, кестедегі х белгісі программаны орындау кезінде сәйкес
конфигурацияның пайда болуының мүмкін еместігін білдіреді):
a b c A
q1 , ,q2 , ,q4 , ,q6 , ,! 1 символды талдау, тармақталуы
q2 ,R, ,R, ,R, ,L,q3 Алғашқы а символы арқылы соңғы
символға бару
q3 , ,! , ,q8 , ,q8 X Соңғы символды а-мен салыстыру,
q8-ге тең емес(Р-ны өшіру)
q4 ,R, ,R, ,R, ,L,q5 Алғашқы b символына ұқсас
q5 , ,q8 , ,! , ,q8 X
q6 ,R, ,R, ,R, ,L,q7 Алғашқы с символына ұқсас
q7 , ,q8 , ,q8 , ,! X
q8 A,L, A,L, A,L, , ,! Оңнан-солға жылжу арқылы барлық
сөзді өшіру
Мысал 4 (сөздің ішінен символды өшіру)
. Р сөзінің ішінен оның екінші символын өшіру, егер ондай символ
болса.
Шешімі.
Бұл есептің шешімін табу оңай сияқты көрінеді: автоматты екінші символмен
клетканың астына жылжыту және одан кейін осы клетканы тазарту:
Бірақ та шығатын сөздің ішінде бос клеткалар болмауы керек. Сондықтан
екінші символды өшіргеннен кейін сөзді бірінші символды бір клеткаға оңға
жылжыту арқылы сығу қажет. Ол үшін автомат бірінші символға қайтып оралуы
керек, оны есіне сақтап және өшіріп, одан соң қайта оңға жылжу арқылы оны
екінші символ тұрған клеткаға жазу керек. Бірақ та оңға қарай екінші
символды өшіру үшін арналған бастапқы сапар және кейінгіні бірінші
символға қайтару артық әрекеттер болып табылады: бірінші символды бос
клеткаға ауыстыру әлде символы бар клеткаға ауыстырудың айырмашылығы
қандай? Сондықтан да бірден алғашқы символды есте сақтаймыз, оны өшіреміз
және екінші символдың орнына жазамыз:
ТМ үшін осылардың барлығы программа түрінде мынадай түрде болады:
a b A
q1 A,R,q2 A,R,q3 , ,! 1 символды талдау, тармақталуы
q2 , ,! a, ,! a, ,! Екінші символды а-мен
алмастыру
q3 b, ,! , ,! b, ,! Екінші символды b-мен
алмастыру
Мысал 5
.Р сөзінен бірінші а символының кірісін, егер ол болса, өшіру.
Шешімі.
Алдыңғы мысалда біз оңға позициясына тек бір символдың орнын ауыстырдық.
Бұл мысалда да біз цикл арқылы оңға қарай барлық бастапқы бірінші а
символына b және с символдарының орнын алмастырамыз:
2. Марковтың қалыпты алгоритмдері
Бұл бөлімде Марковтың қалыпты алгоритмдерін құру үшін есептер
қарастырылады. Мұнда алгоритмдердің қысқаша сипаттамасы берілген,
мысалдармен оларды құрудың негізгі тәсілдері түсіндіріледі және өз бетінше
шығаруға есептер берілген.
2.1 Марковтың қалыпты алгоритмдерінің қысқаша сипаттамасы
Қойылымдар. Марковтың қалыпты алгоритмдерінің (МҚА) қызықты
ерекшелігі - онда қойылым деп аталатын бір ғана элементарлы іс-әрекет
қолданылады.
Қойылымның формуласы деп α→β түріндегі жазба аталады (α-ны β-ға
ауыстыру деп оқылады), мұндағы α және β – кез келген сөздер (бос сөздер
болуы мүмкін). Сонымен қатар α – формуланың сол бөлігі, β – оң бөлігі деп
аталады.
Қойылымның өзі (әрекет сияқты) қойылым формуласымен беріледі және Р
сөзіне қолданылады. Операцияның мәні мынада: Р сөзінде осы формуланың сол
бөлігімен (яғни, α-мен) сәйкес келетін бөлігі іздестіріледі және ол
формуланың оң бөлігіне ауыстырылады (яғни β-ға). Сонымен қатар Р сөзінің
қалған бөліктері (α-дан оңға және солға қарай) өзгермейді. Алынған R сөзін
қойылым нәтижесі деп атайды. Шартты түрде оны былай белгілеуге болады:
Р х α у → R х β у
Қажетті толықтырулар:
1. Егер қойылым формуласының сол бөлігі Р сөзіне енсе, онда бұл
формуланы Р-ға қолдануға болады деп айтады. Ал егер α Р-ға кірмейтін
болса, онда формула Р-ға қолданылмайтын болып саналады және қойылым
орындалмайды.
2. Егер α-ның сол бөлігі Р-ға бірнеше рет енсе, онда анықтама бойынша
β-ның оң бөлігіне α-ның Р-дағы тек қана бірінші енуі ауыстырылады:
x α y α z
x β y α z
→ R
3. Егер қойылым формуласының оң бөлігі – бос сөз болса, онда α→
қойылымы Р-дан α бөлігін сызып тастауды білдіреді (қойылым формуласында бос
сөзді белгілеуге болмайды):
Р х α у → R
х у
4. Егер қойылым формуласының сол бөлігінде бос сөз көрсетілсе, онда
анықтама бойынша →β қойылымы β-ның Р сөзінің сол жағына жазылуын білдіреді:
x
β х
Р → R
Бұл ережеден өте маңызды ақиқат шығады: бос сол бөлігі бар формула
кез келген сөзге қолданылады. Сондай-ақ, бос оң және сол бөліктері бар
формула сөзді өзгертпейді.
МҚА-ның анықтамасы
Марковтың қалыпты алгоритмдері (МҚА) деп қойылымның бос емес соңғы
ықшамдалған формула топтамасы аталады:
(k≥1)
Бұл формулаларда екі түрлі бағдарша қолданылуы мүмкін: қарапайым бағдарша
(→) және құйрығы бар бағдарша (→). Қарапайым бағдаршасы бар формула
қарапайым формула, ал құйрықты бағдаршасы бар формула соңғы формула деп
аталады. Айырмашылығы төменде айтылады.
МҚА түрінде алгоритм жазу – бұл осындай формула топтамасын ұсыну
деген сөз.
МҚА-ны орындау ережелері
Алдымен Р бастапқы сөзі беріледі. Қай жерде жазылғаны - маңызды емес,
МҚА-да бұл сұрақ қайта айтылмайды.
МҚА жұмысы қадамдардың ретімен орындалуына келеді. МҚА-ға кіретін әр
қадамда қойылым формуласы жоғарыдан төмен қарай қарастырылады және Р сөзіне
қолданылатын формулалардың біріншісі таңдап алынады, яғни Р-ға сол бөлігі
кіретін ең жоғарғысы. Ары қарай қойылым табылған формулаға сәйкес
орындалады. Жаңа Р’ сөзі алынады.
Келесі қадамда Р’ сөзі бастапқы болып алынады және оған да сол
процедура қолданылады, яғни формулалар ең жоғарғысынан бастап қайтадан
жоғарыдан төмен қарай қарастырылады және Р’ сөзіне қолданылатын бірінші
формула іздестіріледі, одан кейін тиісті қойылым орындалады және жаңа Р”
сөзі алынады. Осылайша ары қарай жалғаса береді:
P → P’ → P’’ → ...
Ерекше көңіл бөлетін ақиқат - МҚА-да формуланың әрбір қадамы әрқашан
біріншісінен бастап қарастырылады.
Қажетті толықтырулар:
1. Егер кезекті қадамда қарапайым формула (α→β) қолданылған болса,
онда МҚА жұмысы жалғаса береді.
2. Егер кезекті қадамда соңғы формула (α→β) қолданылған болса, онда
оны қолданғаннан кейін МҚА-ның жұмысы тоқтайды. Осы сәтте пайда болған сөз
шығатын сөз деп аталады, яғни кіретін сөзге МҚА-ны қолдану нәтижесі.
Көріп отырғанымыздай, қойылымның қарапайым және соңғы формулаларының
айырмашылығы тек мына жағдайда ғана білінеді: қарапайым формуланы
қолданғаннан кейін МҚА-ның жұмысы жалғасады, ал соңғы формуладан кейін
тоқтайды.
3. Егер кезекті қадамда ағымдағы сөзге бірде-бір формула
қолданылмаса, онда бұл жағдайда МҚА жұмысы тоқтайды, ал шығатын сөз ретінде
ағымдағы сөз танылады.
Осылайша, МҚА екі себеп бойынша тоқтайды: 1) не соңғы формула
қоданылады; 2) не ешбір формула сәйкес келмейді. Бұл екеуі де МҚА жұмысының
жақсы аяқталуы болып саналады. Екі жағдайда да МҚА кіретін сөзге
қолданылады деп айтады.
Бірақ, МҚА ешқашан тоқтамауы да мүмкін. Бұл әрбір қадамда
қолданылатын формула бар және бұл формула қарапайым болған жағдайда іске
асады. Бұл кезде МҚА кіретін сөзге қолданылмайды деп айтады. Бұл жағдайда
ешқандай нәтиже жайлы сөз болмайды.
НАМ-ды құруға арналған мысалдар.
Типтік тәсілде демонстоацияланған НАМ-ды құруға арналған мысалдарды
қарастырайық.
Тьюринг машинасындағыдай формулалар мен есептерді қысқарту үшін
келесі ескерулерді қолданамыз:
- Р әрпімен кіріс сөзін тағайындаймыз;
- А әрпімен кіріс сөздің алфавитін, белгілейміз, яғни Р әрпіне де енетін
символды белгілейміз, (бірақ НАМ-ды іске асырғанда сөз ішінде басқа да
символдардың кездесуі мүмкін).
Сонымен қатар, формуланың оң жағынана бастап символдардың нөмірін
көрсетеді. Бұл нөмірлер формулаға кірмейді, бірақ НАМ-ның орындалуын
көрсеткенде формулаға сілтеме жасау үшін қажет.
Мысал1. (Символды қою және өшіру).
А={a,b,c,d}. P сөзіндегі бірінші bb қойылымын ddd – ға ауыстыру керек және
с символдарының кірістерінің бәрін өшіру керек.
Мысалға abbcabbca → adddabba
Шешімі
Алдымен мынаны ескерейік, Тьюринг машинасына қарағанда, НАМ-да символдарды
қою және өшіру оңай орындалады.
Сөзге жаңа символ қою – бұл кейбір сөздердің үлкен символдармен орын
ауыстыруы.
Мысалы, bb → ddd формуласының көмегімен 2 с имвол 3 сиимволға орын
ауыстырады. Қосымша символдар үшін алдын – ала орын ауыстырудың қажеті жоқ,
себебі НАМ-да сөздер автоматты түрде қозғалады.
Символдарды өшіру – бұл кейбір сөздердің кіші символдармен орын ауыстыруы.
Мысалы, с символын өшіру с→ формуласымен құрылады (с→ оң жағы бос болады).
Бұдан сөз ішінде ешқандай бос позиция пайда болмайды, сөздің сығылуы НАМ да
автоматты түрде орындалады.
Осы айтылғандардың есебінен, Мынадай НАМ есебін шешейік.
bb → ddd (1)
с→ (2)
Бірақ бұл олай емес. Бұл НАМ-ды abbcabbca кіріс сөзімен тексерейік.(әр
бағдарша бойында формуланың нөмірі көрсетілген, ал әрбір бағдаршаның сол
жағындағы сөздерде формула қабылдағандардың асты сызылған).
abbcabbca → adddcabbca → adddcadddca→ adddabbca → ...
Көріп тұрғанымыздай, bb кіріс сөзі ddd кірісімен орын ауыстырып,
өшірілген с символына көшірілмей, bb кірісіне орын ауыстыра бастайды. НАМ-
ның әрбәр жұмыс қадамында формулалар бірінші символдан бастап жоғарыдан
төмен қарай қарастырылады. Сондықтан, бірінші формуланы қолдану арқылы
басқа формулаға жолды жабамыз. Бұл дегеніміз, НАМ-да қойылымның
формулаларын шығару ретін білдіреді.
Осыны ескере отырып, (2) формуламыздың орындакрын ауыстырып қоямыз:
с→ (1)
bb→ ddd
Жаңа алгоритмді кіріс сөздер арқылы тексереміз:
abbcabbca → abbabbca → abbabba → adddabba →
Сонымен, НАМ алдымен с символдарының бәрін өшіріп алып bb бірінші
кірісін ddd кірісімен ауыстырыды. Бірақ НАМ осымен тоқтаған жоқ, ол басқа
bb кірістерін алмастыра бастады. Өйткені ең болмағанда бір формула
қолданса, НАМ өзінің жұмысын жалғастырады. Бізге бұның қажеті жоқ,
сондықтан біз bb кірісін ауыстырғаннан кейін ақ НАМ-ды тоқтатуымызға
болады.
Міне, сол үшін бізге қорытынды формула қажет. Осы арқылы біздің
алгоритмде жай формуланы қорытынды формуламен (bb→ ddd )ауыстыру керек.
с→ (1)
bb→ ddd
Енді біздің алгоритміміз дұрыс жұмыс істейді.
abbcabbca → abbabbca → abbabba → adddabba
Міне, сол үшін бізге қорытынды формула қажет. Осыдан біздің алгоритімде жай
формуланы (bb ddd), қорытынды формуламен (bb ddd) ауыстыру керек.
c (1)
bb ddd (2)
Енді біздің алгоритіміміз дұрыс жұмыс істейді: cbb c abbc a 1
abbabbca abbabba 2 adddabba
(2) қорытынды формуладан пайда болған сөз шығу сөзі болып табылады,
яғни НАМ-ның осы сөздегі нәтижесі.
Енді НАМ-ды bb кіріс сөзі кірмейтіндейетіп тексерейік
dcacb 1 dacb 1 dab
Соңғы (dab) сөзге еш формула енгізілмеген, сондықтан алгоритм
тоқтайды және бұл сөз шығу сөзі болып табылады.
Мысал 2 (символдарды қайта орнату)
A a,b сөзін (былай орналастырайық), а символдағы сөздің басында, b
символын соңында болатындай етіп орналастырайық.
Мысалы; babba aabbb
Шешімі.
Бұл мысалды шешу үшін күрделі НАМ қажет сияқты, бірақ олай емес,
осылармен НАМ – ның көмегі арқылы бір ғана формула шешіледі.
ba ab
Р сөзінің оң жағында в символы болған жағдайда а символы үнемі
тұрады, бұл формула b символдармен а символын сол жағына ауыстырады, b –
ның оң жағында істеуін тоқтатады, бұл дегеніміз а символының бәрі b
символының сол жағына орналасады деген сөз.
Babba abbba abbab ababb aabbb
Алгоритм соңғы сөзден тоқтады, формула бұл сөзге қажет емес.
Осы және алдыңғы мысалдарынан көретініміз, Тю,,,, машинасына
... ... . НАМ-да символдарды қайта орнату, қою және өшіру оңай орындалады.
Мысал 3 (алгоритм белгіні қолдану)
A a,b . бос емес Р сөзінен 1-ші символды керек. Бос сөзді
ауыстырамыз.
Шешімі
Сөздің бірінші смиволын өшіргеннен кейін, бірден тоқтау керек екені
белгілі. Сол үшін тапсырманы келесі НАМ орындайды.
а (1)
b (2)
Бірақ бұл дұрыс емес алгоритм, оған көз жеткізу үшін ввава сөзін
таңдаймыз:
bbaba 1 bbba
көріп тұрғанымыздай бұл НАМ сөздің бірінші символын өшірмей, сөздің
бірін а кіріс символын өшірді. Берілген алгоритм кіріс сөз а символынан
болалғанда ғана дұрыс жұмыс жатады. Бұл НАМ – да формуласы қайта орнату
көмектеспейді, керсінше, а -ға басталатын сөзде дұрыс жұмыс жасалады.
Мұндай жағдайда сөздің орнына қандай да бір белгі қою керек, мысалы*.
Осыдан кейінгі формуланың көмегімен мынадай тұрде
*E, I белгілеп, бірінші символ E, бос қойып тоқтатамыз.
Bbaba * bbaba I baba
(*)белгіні бірінші сөзге қою үшін не істейміз? Бұл – сол жолға бос
формуланың көмегімен іске асады.
Қорытындысына мынадай НАМ аламыз.
* (1)
*a I (2)
*b I (3)
Бұны сол кіріс сөзбен тереміз:
bbaba 1 * bbaba 1 ** bbaba 1 *** bbaba 1 ...
Бұл алгоритм үнемі сол жағына ... ... ... қосып отырады. Себебі
бос орнатылған формула сол жақ бөлігі үздіксіз қабылдап тұрады. Сондықтан,
(1) формула басқа формуланы ң жолын жауып өзі үнемі жұмыс атқарып отырад.
Осыдан маңызды бір анықтама пайда болады. Егер НАМ – да сол жақ бөлігі бос
формула ( ) бар болса, онда оның орны НАМ – ның тек соңғы жағында
орналасады.
Осыны еселеп алып, мынадай НАМ жазамыз:
*a I (1)
*b I ( 2)
* (3)
Берілген алгоритмді тексереміз:
bbaba 3 * bbaba 2 baba
Бәрі дұрыс болған жөн. Бірақ бұл олай емес, біздің алгоритм келісім
бойынша (3) формуладағы НАМ – да тоқтау керек еді. Бұл ... ... . себебі
неде? Себебі; біз (*) белгісін сөзді бірінші символды көрсету үшін содан
кейін (*) жұлдызнаманы да, символды да жою үшін арнайы белгіні қолдандық.
Бос сөзде бірде бір смивол жоқ, сол үшін (1)және (2) формула қолданылмай,
үнемі (3) формуланы пайдаланамыз. Бос сөзді ескеру үшін (1) және (2)
формуладан кейін тағы да бір формуланы қолданамыз. Ол формула жалғау
жұлдыздарды жойып, алгоритімді тоқтатады.
*a I (1)
*b I (2)
*I (3)
(4)
Енді біз дұрыс алгоритм құрастырдық.
Келесі тапсырмаға өту үшін, 3 мысалдағы жұлдызша тәсілін
қарастырамыз.
Өңделген Р сөзі бірінші рет а символына еніп:
Р ... а ... а ... а ...
Қандай да бір кіріс сөзін – кірісіне ауыстыру керек. Мұндай ауыстыру
а—в формуласының көлемінен іске асырылады. Бірақ, егер біз бұл формуланы Р
сөзін қолдансақ, онда бірінші а кіріс сөзі ауысады. Бұл кіріс сөзін
белгіліп қою керек (сол жағынан немесе сол жағына). Ол үшін * символын Р
сөзіне қолданамыз:
Р ... а ... * а ... а ...
бұдан былай мұндай белгіні аонайы белгі деп айтамыз. Оның қызметі а
кіріс сөзін белгілеп, оны ерекше етіп көрсетеміз. НАМ – да арнайы белгіні
қолдану тәсілі жиі – жиі қолданылады.
*-ны сөздің сол жағына қалай жазуға болады және арнайы белгіні тоқтату
арқылы қалай жоюға болатынын алдындағы мысалдардан білеміз. Ал * - ның
жылжуы мына формуламен *α→βγ* жүзеге асады. Мұнда α төрттік цифр, ал βγ – α
сәйкес пары болып табылады.
Сонымен, мынадай төрттік жүйеден екілік жүйеге ауысатын алгоритмді
аламыз:
*0→00* (1)
*1→01* (2)
*2→10 * (3)
*3→11 * (4)
* (5)
→ * (6)
Тексереміз:
0123→ *0123→00*123→0001*23→000110*3→00011 011*00011011
5 – мысал (Арнайы белгіні көшіру)
а символын Р сөзінің соңына жазу керек:
Мысалы: bbab→bbaba
Шешімі: Ең бірінші →а а символын Р сөзінің оң жағына емес сол жағына
жазады. А символын оң жағына жазу үшін ең алдымен сөздің соңын белгілеп
қою керек. Мұнда арнайы белгіні Р сөзінің соңына ауыстырамвыз. Содан кейін
а символын ауыстырамыз:
Р→ ... →Р*Ра
Бірақ арнайы белгіні сөз соңына қарай ауыстыруға болады. Бұл былай
бөлінеді: алдымен арнайы белгіні Р сөзінің сол жағына жазамыз, содан соң *
- ны орын ауыстыру арқылы сөздің келесі жағына шығарамыз:
bbab→*bbab→b*bab→bb*ab→bba*b→bbab*
ал мұндай ауыстыруды қалай жүзеге асыруға болады.
Қандай да бір ξ символының орын ауыстыруын байқау қиын емес. Бұл *ξ
символының ξ* орын ауыстыруы, мына формула бойынша жүзеге асады:
*ξ → ξ*
Айтылғандарды есепке ала отырып, келесі НАМ – ды аламыз:
*а→а*
*b→b*
* a
→ *
НАМ бос сөзге бірінші * - ны шығарады, содан кейін оны а символымен
ауыстырады да тоқтайды.
6 – мысал (Арнайы белгіні ауыстыру)
Р сөзідегі а символын аа – ға ауыстырады, егер осы сөзде а символы
болса.
Мысалы: bababb → babaabb
Шешімі: а символының қосарлануы мына формула бойынша жүзеге асады:
ааа. Бұл формула бірінші шыққан емес, соңғы шыққан а символына
қолданылуы үшін, айталық оң жағынан бастап санағанда соңғы а символынан
кейін арнайы белгі қойылады және а* аа формуласы қолданылады. Енді
соңғы шыққан а символының жанына * - ны қалай қоямыз. Соңғы шығу – соңынан
бастап санағандағы бірінші шығу болып табылады, сондықтан Р сөзінің сол
жағына * - ны жазып, орын ауыстыру арқылы сөздің келесі жағына өткіземіз,
содан кейін оңнан солға b символы арқылы жақын орналасқан а символына дейін
орындаймыз. Сонымен қатар кейде Р сөзінің а символы болмауы мүмкін. Егер *
сөз алдына шықса, оны жою керек немесе тоқтату керек.
Бұл ұсынысты келесі НАМ түрінде көрсетеміз:
*а→а* (1)
*b→b* (2)
b*→*b (3)
a*aa (4)
* (5)
→* (6)
(6) – шы формулада * Р сөзінің сол жағына жазылады, (1) және (2) формулада
* - ны Р сөзінің соңына қуады. ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
және оны зерттеудің ЗАМАНАУИ ТӘСІЛДЕРІ
1.1 Жүйелік программалаудан виртуальді зертханалық жұмыстарды жасау
мақсаты
Информатика бойынша элетивті курс
1. Элетивті курс туралы түсінік
2. Элективті курстығ маңызы мен формасы
1.3. Информатика бойынша элективті курста басқарудың әртүрлі түрлерін
реализацияда қолданылатын басқару құралы
1.2.ТМ үшін программа құруға мысалдар
2. Марковтың қалыпты алгоритмдері
1.3 Есептің қойылуы және зертхана құру технологиясы
2 Жүйелік программалаудан виртуальді
зертханалық жұмыстарды жоБАЛАУ
2.1 Жүйелік программалау пәнін сипаттау
2.2 Жүйелік программалау пәнінің зертханасының құрамы және
құрылымы
2.3 Зертхана жұмысының алгоритмдерін, әдістемелерін өңдеу
2.4 Компьютерлік жүйемен оқушының қатынас интерфейсін құру
1 Жүйелік программалау пәнінің алатын орны
және оны зерттеудің ЗАМАНАУИ ТӘСІЛДЕРІ
1.1 Жүйелік программалаудан виртуальді зертханалық жұмыстарды жасау
мақсаты
Ақпараттық жүйелерді құру жұмысы пәндік облысқа талдау жүргізуден
басталады. Нысанның жұмыс істеу барысын талдағанда жүйені қарастыру
шекаралары еске алынып, болашақ ақпараттық жүйені қолданушылар анықталып,
автоматтандырылатын кластар мен нысандар типтері қарастырылуы қажет.
Пәнді облысқа талдау жүргізу, ол - жобалау алдында сол пәндік облыстың
зерттеу мәліметтерін жинау, қалыптастыру және талдау, сонымен бірге
зерттеу объектісінің автоматтандырылатын есептер жиынтығын таңдау және
нақтылау болып келеді.
Компьютерлік қызмет көрсететін менеджер клиенттердің тапсырысын
қанағаттандыра алуы, тапсырыстар ағымын қарастыруы және қызмет көрсету
сапасын мен өндірістік процестердің жылдамдығын арттыра алуы қажет.
Компьютерлік қызмет көрсету бөлімінің менеджерлерінің негізгі функциялары:
- компьютерлерді сатуға келісім-шартты рәсімдеу;
- клиенттерден тапсырыстарды қабылдау;
- клиенттермен жұмыс (сатылымдарға талдау, клиенттер анықтамаларын
жүргізу);
- есеп шот пен жинақтамаларды рәсімдеу ;
- сатылып алынатын өнімге немесе қызмет көрсетілген жұмысқа санақ жүргізу
(шотты шығару);
- қызмет көрсетілген жұмыстарға есеп беру және т. б.
Таразспецтехбаза ЖШС-гі (жауапкершілігі шектеулі серіктестігі)
шаруашылық қызмет көрсету арқылы серіктестік мүшелері мүддесі үшін пайда
көру, сонымен бірге ішкі нарықтың талаптарын қанағаттандыру. Ұйымның
қаржысы өнімді, жұмысты және қызметтерін нәтижелеуден түскен пайдадан
құралады.
Осы аталған мақсаттарға жету үшін Таразспецтехбаза ЖШС-і мына
жүмыстарды атқарады:
- құрастырушыларды сатып алу;
- клиенттердің тапсырысы бойынша компьютерлерді құрастыру;
- компьютерлерді жөндеу;
- компьютерлерді сату;
- кепілділік қызметін көрсету.
Потенциалды сатып алушылардың нарығын зерттеу және сатылуға ұсынылып
отырған нысандардыңңң ұсыныстары негізінде қызметкер немесе арнайы маман
каталогті өңдейді; үлкен фирмадағы сондай қызметті маркетинг бөлімі дейтін
еді. Ал бұл ұйымда маркетинг қызметі экономикалық бөлімде атқарылады.
Сондықтан клиенттің тапсырысы бойынша ақпараттық құралдарды және
конфигурацияларды таңдау бизнес-үрдісін автоматтандыру жұмысын нәтижелеу
варианты таңдалды.
XX ғасырдың соңында адамдардың индустриалды дәуірдің аяқталуымен және
ақпараттық дәуірге көшуімен сипатталады. Ақпаратты қолдана білу, оны өңдей
білу цивилизацияны дамыту болып табылады. Бұл курстық жұмыс элективті
курсты құруға арналған.
Элективті курс – оқу жоспарының жаңа элементі бағдарлы мазмұнын
толықтырады және оқушылардың әртүрлі қызығушылығын қанағаттандырады.
Элективті курс әртүрлі тақырыпқа, сонымен де жалпыбілімдік программаға да
қатысады. Біз информатиканың элективті курсы мен элетивті матиматикасын
ұсынамыз. Элективті курс бұл жаңа актуалды механизм және оқытудың
индивидуалды процесі. Жақсы жоспарланған элективті курстан, әрбір оқушы өз
қалауымен бір білім облысында білім алуына болады.
Элективті курс информатиканың оқушылар компаненті орындалады және
бірнеше функция атқарады: бағдарлы курстың мазмұнын толықтырады, бір
базалық курстың мазмұнын дамытады, әртүрлі дамытушылық қызығушылықтарды
қанағаттандырады.
Айта кететін жайт, элективті курсқа бірынғай мемлекеттік емтихан
өткізілмейді. Элективті курс информатиканың таға да бір маңызды функциясын
атқарады – жаңа оқулықтар материалдарын тексеруді. Факультативті курстың
өткізілуі оның аналогтық курстық функциясын жақсы орындағанын көрсетеді.
1. Информатика бойынша элетивті курс
1. Элетивті курс туралы түсінік
Элективті курс (таңдау бойынша курс) бағдарлы оқыту жүйесінің
маңызды рөлін атқарады. Факультативті курстан басқа, мектепке қатысты,
жоғарға сыныптарға арналған элективті курс.
Қазақстан Республикасында жақын арада жоғарғы мектептік білімде
бағдарлы оқыту енгізілді, құрамалық бөлік жалпы білімдік базаға байланысты
тереңдетілген (мамандандырылған және бағдарлы) және элективті курстар.
Әртүрлі курстарды орындағанда мұғалімдер жолында қиындықтар болуы мүмкін.
Олардың формальді білімнің , дарындылығы мен қолдана білуі іске асырылады.
Бақылаушының сұрағы актуальді, бақылау құрамалық бөлтік болып табылады,
оқытудың компанентті процесі, программалық материалды меңгерумен
байланысты, бекітуі мен қолданылуы, тиімді методтарды қолданылуымен, дер
кезінде орнатуға көмектеседі, сонан соң оқу процесінде аяқталмаған істі
жүргізеді, оқу материалдарының жетіспеушілігін қолға алады және ары қарай
жұмыс істеуіне көмектеседі.
Жалпы білімдік базалық курстың формасы мен мазмұны бойынша жай
сабақтар бойынша қойылады, қазіргі мектепте жүргізілген, сұраққа жауап
ретінде жабдық бақылауы мен түр таңдауы оларға еш қиындықсыз табуға болады6
8лкен баспа мекемелер, сонымен әртүрлі реализациялық сабақ түрлерінен
болады. Өкінішке орай, осындай жас мектептік дисциплинаға, информатика
сияқты, аса практикалық материалдар жоқ. Сондықтан да информатика
мұғалімдері осы сұрақты қызықтыратын, педагогикалық жұмысқа қатысты немесе
информатикаға жақын пәнге назар аудару керек.
Бағдарлы және элективті курстарға қатысты айтатын болсақ, олар соңғы
3-4 жылдың ішінде зерттелініп келе жатыр.Бақылауға және диагностикаға
байланысты нақты материал ала алынған жоқ.Авторлардың бір ғана затқа көңіл
аударуы мүмкін, ол соңғы сынақ проекті жобаға байланысты жүзеге асатын,
соның ішінде оқушылардың өздерінің элективті курс0а байланысты жаса5ан
жобалары немесе (конференциадағы баяндамалар) оқушылардың өздерінің
элективті курстарға байланысты материалдардан алған білім деңгейлерін
көрсететін баяндамалар. Курстық жұмыстың материалдары негізінен (элетрондық
және баспасөздік материлдарға негізделген) информатикаға байланысты
элективті курстарға
және компьютерлерге арналған дисциплина және оларды құруға арналған
тақырыбында курстарды өткізуге арналған.
Қазіргі кездегі ең жақсы мектептердің бір жоғарғы сыныптарға арналған
бағдарлы оқыту негізінен ол 3 бөлімнен тұрады:
- Базалық (негізгі)
- тереңдетілген (мамандандырылған)
- элективті (дамытушылық)
Егер де алғашқы екеуімен бәрі түсінікті, өйткені ол жоба кәдімгі
мектептерде де қолданылады, ал элективті курс олардан сәл өзгешелеу.
Біріншіден – оған байланысты нормативті құжаттар дайындалмаған. Екіншіден –
оған байланысты дайындалған жобалар тәжірибеден өтпеген және қана баяндама
ретінде қалған. Үшіншіден – элективті курсқа байланысты
базалардайындалмаған және ғылыми зерттеулерді күтуде. Төртіншіден –
элективті курсқа байланысты жасалған жалпы жоба жоқ.
Элективті курстың педагогикалық маңызын бағалай отырып, оның ғылымғы
деген қажеттілігін есте сақтау қажет.
2. Элективті курстығ маңызы мен формасы
Бірден айтып кететін жайт, элективті курс авторлық болып табылады
және ол оқу жоспарына арналған уақыттан аспайды, тәжірибе көрсеткендей ол
16 дан 134 сағатқа дейін болып келеді. Айтылған курстық жұмыста тек қана
мынадай элективті курс қарастырылған: оған уақыты 34 сағаттан аспайды,
өйткені мұндай ауқымды курстар мазмұнды және практикалық жүйелерге
бөлінген.
Элективті курстар жалпы білімдік курстар және кәсіптік курстардан
ерекшелінеді, формасы бойынша, мазмұны бойынша мектептегі білім берудегі
индивидуалды әдіс болып саналады. Олар тікелей білім берудегі мақсаттарға,
міндеттерге, өмірдегі жоспарларға байланысты. Элективті курстар – ол
таңдалынған білім берудегі жоғарғы сыныптардың білім беру жоспарына кіру
міндетті деп кездейсоқ айтылмаған. Сондықтан да элективті курстардың
өткізілу барысы 4 түрлі бақылау өткізу керек .
1. Кіріспе
2. өту барысы
3. аралық
4. соңғы
Ал бағдарлы және базалық курстарда бастапқы бақылаудан бас тартуға
болады. Бұл оның сатысын және оқу деңгейін анықтауға арналғандығына
байланысты. Төменгі деңгейі базалық курстың және бағдарлы курстың
білімгерлеріне таңдауға көмектеседі.
Бастапқы бақылаудың ең оңай түрі анкета және әңгіме. Кейінгісінен ең
үйлесімді, өйткені кеңес кезінде мұғалім оқушының білімін, айқын
мүмкіншілігін біле алады. Бірақ кеңес ұзақ уақаыт алып қояды, сондықтан да
кейбір кезде анкетамен толығымен ауыстырады. Бірақ анкеталық мұғалімге
қиыншылық тудыру мүмкін олар: сұрақтың толықтылығы мен мазмұны. Анкетадағы
сұрақтар тек қана ойдағыдай нәтиже бермей қоймай мұғалімді ойландырады,
қателестіреі, оның соңы білімнің сапасын төмендетеді. Оқушылардың жүйелік
өзіндік жұмысқа ынталануы, ұмтылуы, өзінше сынып және үй жұмысын жасауы,
берілеген жұмысқа жауапкершілік сезімі ағымдағы бақылауда үлкен мәні бар.
Элективтік курстарда ол әр сабақта жүзеген асады, және ақпарат алуға
бағытталған. Талдай отырып, мұғалім өзінің түзетулерін енгізеді. Мысалы
мазмұнының оқу әдісінің, өзгеруі. Ол тағыда мұғалімге оқушылардың білім
сатысын көрсетеді және оқушыларға қандай материал беруінің болжамдайды.
Жалпы түрде клгенде ағымдағы бақылау сұрақ жүйесі, бақылау, кеңес,
творчествалық тапсырмалар арқылы жүзеге асады.
Рубежкалық (шекаралық) бақылау тек қана көлемі 34 сағаттық элективті
курстарда ғана мүмкін, өйткені осы сияқты курстар бөлімнен тұрады және
рубежкалық бақылау бір- бірімен келісетін бөлімнін зерттеуінің аяқталуы.
Шекаралық бақылаудағы құралдардың арасында кіші жобалар, тесттер,
индивидуалдық тапсырмалар қолданылады.
Элективті курста қорытынды бақылау аяқтайды, мұғалім оқушының алған
білімін, дағдыларын, іскерлігін анықтайды. Информатикаға сәйкес элективті
курсты жобалық жұмыспен немесе белгілі тақырыптағы рефератпен аяқталады.
Бақылаудың құралын нақты таңдау біріншіден элективті курстың бағытымен
мақсатына, екіншіден мәтініне, үшіншіден дайындықтың сатысына және оқушының
интелектуалды дамуына байланысты. Информатикадан элективті курстың келесі
бағыттары бар: олар базалық жалпы білімді курстармен терең немесе кең білім
беру, ЖОО түсу үшін дайындық немесе ҰБТ-ны тапсыру, бастауыш
мамандандырылған дағдылар алу үшін курстың мәтіні ең қиын сұрақ, немесе
мәтіннің анықтамасы қатты бекітілмейді және элективті курсқа келушілердің
мүмкіндігін ескем алу керек.Бақылау құралының таңдауының қиындығы, элетивті
курс авторлық болып саналады, және оны өздері анықтайды, көбінесе бақылау
құралдарының қолданғанға берілетін кепілдер қиынға түседі.
Базалық жалпы білімді курстар барлық оқушыларға білімнің міндетті
инварианттық бөлімін көрсетеді және жалпы білімді дайындықтың аяқталуына
бағытталған. Бағдарлы курстар әр пәннің терең зерттеуін қамсыздандырады
және ең біріншіден мектеп бітірушілердің келесі кәсіптік біліміне
дайындайды. Элективті курстар әр оқушының қажеттілігімен, бейімділігімен
байланысты. Тек қана осы ғана индивидуалды жалпы білімді программаны құруға
мүмкіндік береді, өйткені көбінесе олар оқушының талдауымен,
қабілеттілігімен, кейінгі өмірдегі мақсатпен байланысты. Элективті курстар
базалық және бағдарлы шектеулі мүмкіншіліктерді компенсациялайды, жоғарғаы
сынып оқушыларының білімдік қажеттілігін қанағаттандырады. Элективті
курстың осы рөлі бағдарлы білім беру жүйесінде кең спектрді және оның кең
функция есептерін айқындайды. Бірнеше элективті курстардың типтарын
белгілеуге болады. Олардың кейбіреуі дарынды оқушыларға белгілі бір пәннен
жоғары сатыда білім бере алады. Басқа элективтер пән аралық байланыс және
қосымша оқулық пәндерді бағдарлы сатыда оқи алады. Элективті курстын
мысалы: Математикалық статистика экономикалық бағдарлы таңдаған
оқушыларға арналған, компьютерік графика индустриалды – технологиялық
профильге арналған немесе Өнер тарихы гуманитарлық бағдарға арналған.
Элективті курстың үшінші түрі оқушыға ҰБТ-ны жоғары деңгейде тапсыруға
мүмкіншілік береді. Тағы да бір айта кетсек ол оқушыға еңбек базарында
біліми нәтиже береді.
1.3. Информатика бойынша элективті курста басқарудың әртүрлі түрлерін
реализацияда қолданылатын басқару құралы
Көрсетілген кестеде, элективтік курстарға арналған бақылаудың түрлері
келтірілген.
Курстың бағыты – білімнің кеңейтуі.
Курстың аты – Компьютерлік графика Бейсикте.
Ұсынылатын бағдар: физика-математикалық, технологиялық.
Бақылау түрі
алдыңғы Ағымдағы шекаралық қорытынды
Кеңес, Бейсик құралыменШығармашылық мини Жобалар
оператолардың берілген жобалар және Үшөлшемділік
Бейсик суреттерді индивидуалдылық Бейсик
программасын құрудың тапсырмалар құралымен,
айқындауға тапсырмалары Бейсикте ертегі
(білуге) жазамыз
арналған тест
Курстың аты – Компьютерде мәтіндік информацияның өңдеуі.
Ұсынылатын бағдар – физика-математикалық, технологиялық, гуманитарлық.
Бақылау түрі
алдыңғы Ағымдағы шекаралық қорытынды
Анкеталық, MS Программалық MS Шығармашылық Индивидуалды
Excel Excel және тапсырмалар, тапсырмалар
функциясына жәнепрограммалық өзіндік шығаруға
жүйе жүйенің арналған
программалық тапсырмалары тапсырмалар
операторына
тесттер
Курстың аты – Компьютерде қызықты материалдың өңдеуі.
Ұсынылатын бағдар: физика-математикалық, технологиялық, гуманитарлық.
Бақылау түрі
алдыңғы Ағымдағы шекаралық қорытынды
Анкеталық Бақылау, мини Шығармашылық Мектептегі
шығармашылық тапсырмалар, дисциплинаның
тапсырмалар мини жобалар бір бөліміне
жобалық жұмысы
1. Тьюринг машинасы
Бөлімде Тьюринг машинасына арналған алгоритімдерді құру есептері
қарастырылады. Машинаға қысқаша сипаттама, соған сәйкес алгоритім құру
мысалдары және өзіндік жұмыстарға есептер беріледі.
1. Тьюринг машинасына сипаттама
Тьюринг машинасының құрлымы
Тьюринг машинасы (МТ) 2 бөліктен тұрады – лента және автомат (сол жағынан
қара):
q
автомат:
Лента ақпарат сақтауға арналған. Ол екі жағынан шексіз және
номірленбейтің, ат қойылмайтын торларға бөлінген. Әр торда бір символ
жазылуы немесе жазылмауы мүмкін. Тор ішін өзгертуге болады – оған басқа
символ жазуға немесе ондағы символды өшіруге болады.
Бос торларды бос символ деп атап және оны Λ (лямбда) белгісімен
белгілейміз.
Осыған байланысты суреттегі сол жақтағы лента оң жақтағы суретгідей. Бұл
кейбір тордағы символдарды өшіруді осы клеткаға Автомат – Тьюринг
машинасының активті бөлігі. Ол әр уақытта лентаның бір торына орналасып,
оның құрамын көреді: бұл көрінетін тор , ал оның ішіндегі символ көрінетін
символ деп аталады ; автомат көрші және басқа торларды көре алмайды.
Соңымен қатар автомат әр уақытта белгілі бір күйде болады, оны q әріпімен
белгілеп, q1, q2 нөмірлерімен нөмірлейміз. Автомат белгілі бір күйде болып
белгілі бір операция орындайды(мысалы, лентада оңға жылжып b және а
символдарын алмастырады), басқа күйде – басқа операция орындайды.
Автомат ағымдағы күйінде (q) көрінет символ жұбын (S) - конфигурация
деп атап, S, q белгісімен белгілейміз.
Автомат 3 элементар әрекеттерді орындайды:
1) көрінетін торға жаңа символ жазуды (автомат басқа торларды өзгерте
алмайды);
2) бір тор оңға немесе солға жылжиды (автомат бірнеше торлардан секіре
алмайды);
3) жаңа қалыпқа тұрады.
Автомат басқа әрекеттерді орындай алмайтындықтан, орындалатын
операциялардың барлығы осы 3 әрекеттерге сай келу қажет.
Тьюринг машина жұмысының такті
Тьюринг машинасы бір бірінен кейін орындалатын тактармен жұмыс
істейді.Әр такта тьюринг машина автоматты келесі үш әрекеттерді орындайды
және олар міндетті түрде көрсетілген ретімен орындалу керек:
1) S’ символын көрінетін торға жазады;
2) Бір тор солға жылжиды ( мағынысы – L, left), немесе бір тор оңға
жылжиды (мағынасы - R, right), немесе жылжымайды (мағынасы - N);
3) Белгілі бір q’ күйге келеді (бұрынғы қалпында да қала алады).
Формальды түрде бір такт үштік түрінде жазамыз:
S’,[L, R,N], q’
мұнда квадрат скобка ның орнына кез келген L, R, N әріпін жазуға мүмкіндік
береді. Мысалы, *,L,q8 такті көрінетін торға * символының жазылуын
білдіреді, бір тор солға жылжуды және q8 күйіне көшеді.
Тьюринг машинасына программа
Тьюринг машинасы өзінен өзі ешнарсе жасамайды. Оны жұмыс жасату үшін
оған программа жазу керек. Программа келесі кестедегідей жазылады:
Егер енгізілген сөз бос болса, онда автомат басқа бос торларды қарайды,
себебі олар бос.
Осы бастапқы әдәстерден кейін программаның орындалуы басталады.
Кестеден бірінші жолмен қиылысатын және (автомат q1 күйінде тұрады)
енгізілген сөздін бірінші символына сәйкес бағанға, (кестенің сол бағаны
болу шарт емес) осы ұяшыққа сәйкес тактті орындайтын ұяшық табылады.
Нәтижесінде автомат жаңа конфигурацияда орналасады. Енді осындай әрекеттер
жаңа конфигурацияға орындалады: кестеден қалыпқа сай және осы конфигурация
символына және осы ұяшықтын тактін орындайтын ұяшық табылады .
Программа орындалуы қашан аяқталады? Тоқтау такт ұғымын енгізейік. Ол
еншәрсені өзгертпейді: автомат көрінген торға бұрын болған символды жазады,
орны айыстырылмай бастапқы күйінде қалады, яғни S, q конфигурациясына
S,N,q такті. Тоқтау такті анықтап, тоқтап, өз жұмысын аяқтайды.
Толық алғанда Тьюринг машинасы жұмыс істеуінің 2 жолы бар:
1) Бірінші жолы – жақсы: бұл Тьюринг машинасының тоқтау сәті (тоқтау
сәтіне келгенде). Бұл жағдайда Тьюринг машинасы енгізілген сөзге
қолданулы деп атайды. Ал осы сәтте лентада алынған сөз шығу сөзі болып
саналады, яғни Тьюринг машина жұмыс нәтиже жауабы.
Тоқтау сәтіне келесі шарттар орындалу қажет:
- шығу сөзінің ішінде бос торлар болмау қажет (программа барысында
өнделетін сөз арасында бос торлар болу мүмкін, бірақ соңында олар
қалмау тиіс);
- Автомат шығу сөзінің бір символына тоқтау тиісті (қайсысына екені –
маңызды емес), ал сөз бос болса – кез келген лента торына.
2) Екінші жолы – жаман: ол Тьюринг машинасы ешқашан тоқтау тактісіне
түспей айнала береді (мысалы, автомат әр қадам сайын оңға жылжи береді
және тоқта алмайды, яғни лента шексіз). Бұл жағдайда: Тьюринг машинасы
енгізуле сөзіне қолданусыз деп аталады. Бұл жағдайда нәтиже болмайды.
Бір алгоритмнің Тьюринг машинасы (Тьюринг машина программасы) бір
енгізулі сөзіне қолданылатын (яғни тоқтайды) және басқаларға қолданусыз
(яғни айналады) болатының белгілейік. Яғни қолданулы қолданусыз болу тек
алгоритмнен ғана емес, сонымен қатар енгізулі сөзіне де байланысты.
Алгоритім қай енгізулі сөзінде тоқтау қажет? Жақсы сөздерге, яғни
жіберуге болатын мәндерде. Бірақ лентада кез келген, сонымен қатар есептін
мәні болмайтын енгізілген сөздер жазуға болады; мұндай сөздерде алгоритм
фиксирленген, тоқтай алады (кез келген нәтижеде), сонымен қатар айналу да
мүмкін.
Жазуды қысқартуға арналған келсім
Тьюринг машина программасын қысқартатын келсімдерді келтірейік
1) Егер тактте көрінетін символ өзгермесе немесе автомат жылжымаса немес
автомат күйі өзгермесе, сәйкес такт позициясы еш нәрсе жазылмайды.
Мысалы, a,q1 конфигурациясына келесі такт жазулары эквивалентті:
a,R,q3≡ ,R,q3 (Λ, R,q3!! тек бұларға емес )
b,N,q2≡ b, ,q2
a,L,q1≡ ,L,
a,N,q1≡ , , (бұл тоқтау
такті)
Ескерту. Тактар арасында үтір қалмауы тиіс, себебі шатасу болу мүмкін, егер
лента символарының арасынан L және R әріптері кездесе.
2) Егер бірнеше Тьюринг машина тактіден кейін тоқтау тиіс екенің көрсету
керек болса, онда үшінші такт позициясында ! белгісін жазу керек.
Мысалы, b,L,! такт келесі әрекеттердібілдіреді: b символының көрінетін
лента клеткасына жазылып, солға бұрылып, тоқтайды.
3) Егер, программа орындалу процесінде бірнеше конфигурация орындалмау
мүмкіндігі белгілі болса, онда мұны анық көрсету үшін сәйкес кесте
ұяшығына крестик саламыз. (Формальді түрде бұл крестик тоқтау такті
болып саналады).
Бұл келсімдер шартты емес, бірақ олар программа жазылуын қысқартып,
оны қабылдауды жетілдіреді.
1.2.ТМ үшін программа құруға мысалдар
ТМ-да кейбір типті программалау тәсілдерін көрсету үшін ТМ-нда программа
құруға арналған мысалдарды қарастырайық.
Есептің тұжырымдалуын қысқарту үшін келесідей екі келісімді енгіземіз:
- Р әрпі кіріс сөзін білдіреді;
- А әрпі кіріс сөзінің алфавитін білдіреді, яғни тек Р-дан ғана тұратын
символдар жиынтығы (айта кетін жайт, аралық және шығыс сөздерінде
басқа да символдар пайда болуы мүмкін).
1 Мысал (автоматты орналастыру, символдарды ауыстыру).
. Р-бос емес сөз болсын.Р-ондық сандардың реттелуі, яғни ондық
жүйедегі теріс емес бүтін сандардың жазылуы. Лентада Р санынан 1-ге үлкен
сандардың лентада жазылуын алу қажет.
Шешуі:
Бұл есепті шешу үшін келесі әрекеттерді орындау керек:
1.Автоматты соңғы цифрдың астына айдау.
2.Егер ол сан 0-ден 8-ге дейінгі сан болса, онда оны 1 санға жоғары етіп
алмастыру керек және тоқтау қажет, мысалы:
3.Егер 9 саны болса, онда оны 0 санымен алмастыру қажет және автоматты
алдыңғы санға жылжыту қажет. Одан кейін осы әдіспен соңғының алдындағы
санды 1-ге үлкейту керек, мысалы:
4.Ерекше жағдай: Р-да тек ондықтар (мысалы, 99). Онда автомат тоғыздықтарды
нольдермен алмастыра отырып солға қарай жылжиды және соңында бос клеткаға
тап болады. Бұл бос клеткаға 1 санын жазу керек және есептеуді тоқтату
қажет (жауабы 100 болады):
ТМ үшін арналған программа түріндегі бұл әрекеттер келесі түрде беріледі:
0 1 2 3 4
q1 A,R,q2 A,R,q3 A,R,q4 ,R, 1 символды талдау, оны
өшіру, тармақталуы
q2 ,R, ,R, ,R, a, ,! а –ның оң жақта жазылуы
q3 ,R, ,R, ,R, b, ,! b–ның оң жақта жазылуы
q4 ,R, ,R, ,R, c, ,! с–ның оң жақта жазылуы
Құрамында бір символдан артық символға ие кіріс сөздердегі программаның
әрекетін қарастырайық. Есеп үшін нашар болып табылатын бос сөзде
программа автоматты түрде тоқтап қалады, q1 күйінде болады және бос
клеткаларға түскен сайын ол шексіз оңға қарай орналасады.
Егер кіріс сөзінде дәл бір символ болса, онда автомат ол символды өшіреді,
бір клеткаға оңға жылжиды және оған берілген символды жазады:
q1 q4
!
Осылайша, бір сөзден тұратын символ жай ғана бір клеткаға оңға жылжиды. Бұл
мүмкін нәрсе. Лентаның клеткалары номерленбеген, сондықтан лентадағы сөздің
орны жазып алынбайды және сөзді оңға және солға орын ауыстыруын алмастыруға
болмайды. Осыған байланысты, кіріс сөзі міндетті түрде дәл сол жерде, яғни
кіріс сөзі болған жерде болуы қажет емес, нәтижесі ол орыннан солға немесе
оңға қарай болуы мүмкін.
Мысал 3 (символдарды салыстыру, сөзді өшіру)
. Р сөзінің бірінші және соңғы символдарды (бос емес) бірдей болса,
онда ол сөзді ауыстырмау керек, әйтпесе оны бос сөзге ауыстыру қажет.
Шешімі.
Бұл есепті шешу үшін келесі әрекеттерді орындау керек:
1. Кіріс сөзінің бірінші символын оны өшірмей тұрып, оны есте сақтау
керек.
2. Автоматты соңғы символдың астына орналастырып және ойдағы символмен
салыстыру керек.
3. Қарсы жағдайда барлық кіріс сөзін жойып жіберу қажет.
Символды қалай есте сақтау керектігін және автоматты соңғы символдың
астына айдауды алғашқы мысалдардан білеміз. Кіріс сөзінің өшірілуі оның
барлық символдарының А символына ауыстырылуымен жүзеге асырылады.
Осылайша, автомат сөз соңында болғандықтан, енді автоматты бірінші бос
клеткаға дейін оңнан солға қарай орналастыратын боламыз.
Бұл әрекеттер ТМ үшін келесідей программа түрінде бейнеленеді (есте
сақтайтын нәрсе, кестедегі х белгісі программаны орындау кезінде сәйкес
конфигурацияның пайда болуының мүмкін еместігін білдіреді):
a b c A
q1 , ,q2 , ,q4 , ,q6 , ,! 1 символды талдау, тармақталуы
q2 ,R, ,R, ,R, ,L,q3 Алғашқы а символы арқылы соңғы
символға бару
q3 , ,! , ,q8 , ,q8 X Соңғы символды а-мен салыстыру,
q8-ге тең емес(Р-ны өшіру)
q4 ,R, ,R, ,R, ,L,q5 Алғашқы b символына ұқсас
q5 , ,q8 , ,! , ,q8 X
q6 ,R, ,R, ,R, ,L,q7 Алғашқы с символына ұқсас
q7 , ,q8 , ,q8 , ,! X
q8 A,L, A,L, A,L, , ,! Оңнан-солға жылжу арқылы барлық
сөзді өшіру
Мысал 4 (сөздің ішінен символды өшіру)
. Р сөзінің ішінен оның екінші символын өшіру, егер ондай символ
болса.
Шешімі.
Бұл есептің шешімін табу оңай сияқты көрінеді: автоматты екінші символмен
клетканың астына жылжыту және одан кейін осы клетканы тазарту:
Бірақ та шығатын сөздің ішінде бос клеткалар болмауы керек. Сондықтан
екінші символды өшіргеннен кейін сөзді бірінші символды бір клеткаға оңға
жылжыту арқылы сығу қажет. Ол үшін автомат бірінші символға қайтып оралуы
керек, оны есіне сақтап және өшіріп, одан соң қайта оңға жылжу арқылы оны
екінші символ тұрған клеткаға жазу керек. Бірақ та оңға қарай екінші
символды өшіру үшін арналған бастапқы сапар және кейінгіні бірінші
символға қайтару артық әрекеттер болып табылады: бірінші символды бос
клеткаға ауыстыру әлде символы бар клеткаға ауыстырудың айырмашылығы
қандай? Сондықтан да бірден алғашқы символды есте сақтаймыз, оны өшіреміз
және екінші символдың орнына жазамыз:
ТМ үшін осылардың барлығы программа түрінде мынадай түрде болады:
a b A
q1 A,R,q2 A,R,q3 , ,! 1 символды талдау, тармақталуы
q2 , ,! a, ,! a, ,! Екінші символды а-мен
алмастыру
q3 b, ,! , ,! b, ,! Екінші символды b-мен
алмастыру
Мысал 5
.Р сөзінен бірінші а символының кірісін, егер ол болса, өшіру.
Шешімі.
Алдыңғы мысалда біз оңға позициясына тек бір символдың орнын ауыстырдық.
Бұл мысалда да біз цикл арқылы оңға қарай барлық бастапқы бірінші а
символына b және с символдарының орнын алмастырамыз:
2. Марковтың қалыпты алгоритмдері
Бұл бөлімде Марковтың қалыпты алгоритмдерін құру үшін есептер
қарастырылады. Мұнда алгоритмдердің қысқаша сипаттамасы берілген,
мысалдармен оларды құрудың негізгі тәсілдері түсіндіріледі және өз бетінше
шығаруға есептер берілген.
2.1 Марковтың қалыпты алгоритмдерінің қысқаша сипаттамасы
Қойылымдар. Марковтың қалыпты алгоритмдерінің (МҚА) қызықты
ерекшелігі - онда қойылым деп аталатын бір ғана элементарлы іс-әрекет
қолданылады.
Қойылымның формуласы деп α→β түріндегі жазба аталады (α-ны β-ға
ауыстыру деп оқылады), мұндағы α және β – кез келген сөздер (бос сөздер
болуы мүмкін). Сонымен қатар α – формуланың сол бөлігі, β – оң бөлігі деп
аталады.
Қойылымның өзі (әрекет сияқты) қойылым формуласымен беріледі және Р
сөзіне қолданылады. Операцияның мәні мынада: Р сөзінде осы формуланың сол
бөлігімен (яғни, α-мен) сәйкес келетін бөлігі іздестіріледі және ол
формуланың оң бөлігіне ауыстырылады (яғни β-ға). Сонымен қатар Р сөзінің
қалған бөліктері (α-дан оңға және солға қарай) өзгермейді. Алынған R сөзін
қойылым нәтижесі деп атайды. Шартты түрде оны былай белгілеуге болады:
Р х α у → R х β у
Қажетті толықтырулар:
1. Егер қойылым формуласының сол бөлігі Р сөзіне енсе, онда бұл
формуланы Р-ға қолдануға болады деп айтады. Ал егер α Р-ға кірмейтін
болса, онда формула Р-ға қолданылмайтын болып саналады және қойылым
орындалмайды.
2. Егер α-ның сол бөлігі Р-ға бірнеше рет енсе, онда анықтама бойынша
β-ның оң бөлігіне α-ның Р-дағы тек қана бірінші енуі ауыстырылады:
x α y α z
x β y α z
→ R
3. Егер қойылым формуласының оң бөлігі – бос сөз болса, онда α→
қойылымы Р-дан α бөлігін сызып тастауды білдіреді (қойылым формуласында бос
сөзді белгілеуге болмайды):
Р х α у → R
х у
4. Егер қойылым формуласының сол бөлігінде бос сөз көрсетілсе, онда
анықтама бойынша →β қойылымы β-ның Р сөзінің сол жағына жазылуын білдіреді:
x
β х
Р → R
Бұл ережеден өте маңызды ақиқат шығады: бос сол бөлігі бар формула
кез келген сөзге қолданылады. Сондай-ақ, бос оң және сол бөліктері бар
формула сөзді өзгертпейді.
МҚА-ның анықтамасы
Марковтың қалыпты алгоритмдері (МҚА) деп қойылымның бос емес соңғы
ықшамдалған формула топтамасы аталады:
(k≥1)
Бұл формулаларда екі түрлі бағдарша қолданылуы мүмкін: қарапайым бағдарша
(→) және құйрығы бар бағдарша (→). Қарапайым бағдаршасы бар формула
қарапайым формула, ал құйрықты бағдаршасы бар формула соңғы формула деп
аталады. Айырмашылығы төменде айтылады.
МҚА түрінде алгоритм жазу – бұл осындай формула топтамасын ұсыну
деген сөз.
МҚА-ны орындау ережелері
Алдымен Р бастапқы сөзі беріледі. Қай жерде жазылғаны - маңызды емес,
МҚА-да бұл сұрақ қайта айтылмайды.
МҚА жұмысы қадамдардың ретімен орындалуына келеді. МҚА-ға кіретін әр
қадамда қойылым формуласы жоғарыдан төмен қарай қарастырылады және Р сөзіне
қолданылатын формулалардың біріншісі таңдап алынады, яғни Р-ға сол бөлігі
кіретін ең жоғарғысы. Ары қарай қойылым табылған формулаға сәйкес
орындалады. Жаңа Р’ сөзі алынады.
Келесі қадамда Р’ сөзі бастапқы болып алынады және оған да сол
процедура қолданылады, яғни формулалар ең жоғарғысынан бастап қайтадан
жоғарыдан төмен қарай қарастырылады және Р’ сөзіне қолданылатын бірінші
формула іздестіріледі, одан кейін тиісті қойылым орындалады және жаңа Р”
сөзі алынады. Осылайша ары қарай жалғаса береді:
P → P’ → P’’ → ...
Ерекше көңіл бөлетін ақиқат - МҚА-да формуланың әрбір қадамы әрқашан
біріншісінен бастап қарастырылады.
Қажетті толықтырулар:
1. Егер кезекті қадамда қарапайым формула (α→β) қолданылған болса,
онда МҚА жұмысы жалғаса береді.
2. Егер кезекті қадамда соңғы формула (α→β) қолданылған болса, онда
оны қолданғаннан кейін МҚА-ның жұмысы тоқтайды. Осы сәтте пайда болған сөз
шығатын сөз деп аталады, яғни кіретін сөзге МҚА-ны қолдану нәтижесі.
Көріп отырғанымыздай, қойылымның қарапайым және соңғы формулаларының
айырмашылығы тек мына жағдайда ғана білінеді: қарапайым формуланы
қолданғаннан кейін МҚА-ның жұмысы жалғасады, ал соңғы формуладан кейін
тоқтайды.
3. Егер кезекті қадамда ағымдағы сөзге бірде-бір формула
қолданылмаса, онда бұл жағдайда МҚА жұмысы тоқтайды, ал шығатын сөз ретінде
ағымдағы сөз танылады.
Осылайша, МҚА екі себеп бойынша тоқтайды: 1) не соңғы формула
қоданылады; 2) не ешбір формула сәйкес келмейді. Бұл екеуі де МҚА жұмысының
жақсы аяқталуы болып саналады. Екі жағдайда да МҚА кіретін сөзге
қолданылады деп айтады.
Бірақ, МҚА ешқашан тоқтамауы да мүмкін. Бұл әрбір қадамда
қолданылатын формула бар және бұл формула қарапайым болған жағдайда іске
асады. Бұл кезде МҚА кіретін сөзге қолданылмайды деп айтады. Бұл жағдайда
ешқандай нәтиже жайлы сөз болмайды.
НАМ-ды құруға арналған мысалдар.
Типтік тәсілде демонстоацияланған НАМ-ды құруға арналған мысалдарды
қарастырайық.
Тьюринг машинасындағыдай формулалар мен есептерді қысқарту үшін
келесі ескерулерді қолданамыз:
- Р әрпімен кіріс сөзін тағайындаймыз;
- А әрпімен кіріс сөздің алфавитін, белгілейміз, яғни Р әрпіне де енетін
символды белгілейміз, (бірақ НАМ-ды іске асырғанда сөз ішінде басқа да
символдардың кездесуі мүмкін).
Сонымен қатар, формуланың оң жағынана бастап символдардың нөмірін
көрсетеді. Бұл нөмірлер формулаға кірмейді, бірақ НАМ-ның орындалуын
көрсеткенде формулаға сілтеме жасау үшін қажет.
Мысал1. (Символды қою және өшіру).
А={a,b,c,d}. P сөзіндегі бірінші bb қойылымын ddd – ға ауыстыру керек және
с символдарының кірістерінің бәрін өшіру керек.
Мысалға abbcabbca → adddabba
Шешімі
Алдымен мынаны ескерейік, Тьюринг машинасына қарағанда, НАМ-да символдарды
қою және өшіру оңай орындалады.
Сөзге жаңа символ қою – бұл кейбір сөздердің үлкен символдармен орын
ауыстыруы.
Мысалы, bb → ddd формуласының көмегімен 2 с имвол 3 сиимволға орын
ауыстырады. Қосымша символдар үшін алдын – ала орын ауыстырудың қажеті жоқ,
себебі НАМ-да сөздер автоматты түрде қозғалады.
Символдарды өшіру – бұл кейбір сөздердің кіші символдармен орын ауыстыруы.
Мысалы, с символын өшіру с→ формуласымен құрылады (с→ оң жағы бос болады).
Бұдан сөз ішінде ешқандай бос позиция пайда болмайды, сөздің сығылуы НАМ да
автоматты түрде орындалады.
Осы айтылғандардың есебінен, Мынадай НАМ есебін шешейік.
bb → ddd (1)
с→ (2)
Бірақ бұл олай емес. Бұл НАМ-ды abbcabbca кіріс сөзімен тексерейік.(әр
бағдарша бойында формуланың нөмірі көрсетілген, ал әрбір бағдаршаның сол
жағындағы сөздерде формула қабылдағандардың асты сызылған).
abbcabbca → adddcabbca → adddcadddca→ adddabbca → ...
Көріп тұрғанымыздай, bb кіріс сөзі ddd кірісімен орын ауыстырып,
өшірілген с символына көшірілмей, bb кірісіне орын ауыстыра бастайды. НАМ-
ның әрбәр жұмыс қадамында формулалар бірінші символдан бастап жоғарыдан
төмен қарай қарастырылады. Сондықтан, бірінші формуланы қолдану арқылы
басқа формулаға жолды жабамыз. Бұл дегеніміз, НАМ-да қойылымның
формулаларын шығару ретін білдіреді.
Осыны ескере отырып, (2) формуламыздың орындакрын ауыстырып қоямыз:
с→ (1)
bb→ ddd
Жаңа алгоритмді кіріс сөздер арқылы тексереміз:
abbcabbca → abbabbca → abbabba → adddabba →
Сонымен, НАМ алдымен с символдарының бәрін өшіріп алып bb бірінші
кірісін ddd кірісімен ауыстырыды. Бірақ НАМ осымен тоқтаған жоқ, ол басқа
bb кірістерін алмастыра бастады. Өйткені ең болмағанда бір формула
қолданса, НАМ өзінің жұмысын жалғастырады. Бізге бұның қажеті жоқ,
сондықтан біз bb кірісін ауыстырғаннан кейін ақ НАМ-ды тоқтатуымызға
болады.
Міне, сол үшін бізге қорытынды формула қажет. Осы арқылы біздің
алгоритмде жай формуланы қорытынды формуламен (bb→ ddd )ауыстыру керек.
с→ (1)
bb→ ddd
Енді біздің алгоритміміз дұрыс жұмыс істейді.
abbcabbca → abbabbca → abbabba → adddabba
Міне, сол үшін бізге қорытынды формула қажет. Осыдан біздің алгоритімде жай
формуланы (bb ddd), қорытынды формуламен (bb ddd) ауыстыру керек.
c (1)
bb ddd (2)
Енді біздің алгоритіміміз дұрыс жұмыс істейді: cbb c abbc a 1
abbabbca abbabba 2 adddabba
(2) қорытынды формуладан пайда болған сөз шығу сөзі болып табылады,
яғни НАМ-ның осы сөздегі нәтижесі.
Енді НАМ-ды bb кіріс сөзі кірмейтіндейетіп тексерейік
dcacb 1 dacb 1 dab
Соңғы (dab) сөзге еш формула енгізілмеген, сондықтан алгоритм
тоқтайды және бұл сөз шығу сөзі болып табылады.
Мысал 2 (символдарды қайта орнату)
A a,b сөзін (былай орналастырайық), а символдағы сөздің басында, b
символын соңында болатындай етіп орналастырайық.
Мысалы; babba aabbb
Шешімі.
Бұл мысалды шешу үшін күрделі НАМ қажет сияқты, бірақ олай емес,
осылармен НАМ – ның көмегі арқылы бір ғана формула шешіледі.
ba ab
Р сөзінің оң жағында в символы болған жағдайда а символы үнемі
тұрады, бұл формула b символдармен а символын сол жағына ауыстырады, b –
ның оң жағында істеуін тоқтатады, бұл дегеніміз а символының бәрі b
символының сол жағына орналасады деген сөз.
Babba abbba abbab ababb aabbb
Алгоритм соңғы сөзден тоқтады, формула бұл сөзге қажет емес.
Осы және алдыңғы мысалдарынан көретініміз, Тю,,,, машинасына
... ... . НАМ-да символдарды қайта орнату, қою және өшіру оңай орындалады.
Мысал 3 (алгоритм белгіні қолдану)
A a,b . бос емес Р сөзінен 1-ші символды керек. Бос сөзді
ауыстырамыз.
Шешімі
Сөздің бірінші смиволын өшіргеннен кейін, бірден тоқтау керек екені
белгілі. Сол үшін тапсырманы келесі НАМ орындайды.
а (1)
b (2)
Бірақ бұл дұрыс емес алгоритм, оған көз жеткізу үшін ввава сөзін
таңдаймыз:
bbaba 1 bbba
көріп тұрғанымыздай бұл НАМ сөздің бірінші символын өшірмей, сөздің
бірін а кіріс символын өшірді. Берілген алгоритм кіріс сөз а символынан
болалғанда ғана дұрыс жұмыс жатады. Бұл НАМ – да формуласы қайта орнату
көмектеспейді, керсінше, а -ға басталатын сөзде дұрыс жұмыс жасалады.
Мұндай жағдайда сөздің орнына қандай да бір белгі қою керек, мысалы*.
Осыдан кейінгі формуланың көмегімен мынадай тұрде
*E, I белгілеп, бірінші символ E, бос қойып тоқтатамыз.
Bbaba * bbaba I baba
(*)белгіні бірінші сөзге қою үшін не істейміз? Бұл – сол жолға бос
формуланың көмегімен іске асады.
Қорытындысына мынадай НАМ аламыз.
* (1)
*a I (2)
*b I (3)
Бұны сол кіріс сөзбен тереміз:
bbaba 1 * bbaba 1 ** bbaba 1 *** bbaba 1 ...
Бұл алгоритм үнемі сол жағына ... ... ... қосып отырады. Себебі
бос орнатылған формула сол жақ бөлігі үздіксіз қабылдап тұрады. Сондықтан,
(1) формула басқа формуланы ң жолын жауып өзі үнемі жұмыс атқарып отырад.
Осыдан маңызды бір анықтама пайда болады. Егер НАМ – да сол жақ бөлігі бос
формула ( ) бар болса, онда оның орны НАМ – ның тек соңғы жағында
орналасады.
Осыны еселеп алып, мынадай НАМ жазамыз:
*a I (1)
*b I ( 2)
* (3)
Берілген алгоритмді тексереміз:
bbaba 3 * bbaba 2 baba
Бәрі дұрыс болған жөн. Бірақ бұл олай емес, біздің алгоритм келісім
бойынша (3) формуладағы НАМ – да тоқтау керек еді. Бұл ... ... . себебі
неде? Себебі; біз (*) белгісін сөзді бірінші символды көрсету үшін содан
кейін (*) жұлдызнаманы да, символды да жою үшін арнайы белгіні қолдандық.
Бос сөзде бірде бір смивол жоқ, сол үшін (1)және (2) формула қолданылмай,
үнемі (3) формуланы пайдаланамыз. Бос сөзді ескеру үшін (1) және (2)
формуладан кейін тағы да бір формуланы қолданамыз. Ол формула жалғау
жұлдыздарды жойып, алгоритімді тоқтатады.
*a I (1)
*b I (2)
*I (3)
(4)
Енді біз дұрыс алгоритм құрастырдық.
Келесі тапсырмаға өту үшін, 3 мысалдағы жұлдызша тәсілін
қарастырамыз.
Өңделген Р сөзі бірінші рет а символына еніп:
Р ... а ... а ... а ...
Қандай да бір кіріс сөзін – кірісіне ауыстыру керек. Мұндай ауыстыру
а—в формуласының көлемінен іске асырылады. Бірақ, егер біз бұл формуланы Р
сөзін қолдансақ, онда бірінші а кіріс сөзі ауысады. Бұл кіріс сөзін
белгіліп қою керек (сол жағынан немесе сол жағына). Ол үшін * символын Р
сөзіне қолданамыз:
Р ... а ... * а ... а ...
бұдан былай мұндай белгіні аонайы белгі деп айтамыз. Оның қызметі а
кіріс сөзін белгілеп, оны ерекше етіп көрсетеміз. НАМ – да арнайы белгіні
қолдану тәсілі жиі – жиі қолданылады.
*-ны сөздің сол жағына қалай жазуға болады және арнайы белгіні тоқтату
арқылы қалай жоюға болатынын алдындағы мысалдардан білеміз. Ал * - ның
жылжуы мына формуламен *α→βγ* жүзеге асады. Мұнда α төрттік цифр, ал βγ – α
сәйкес пары болып табылады.
Сонымен, мынадай төрттік жүйеден екілік жүйеге ауысатын алгоритмді
аламыз:
*0→00* (1)
*1→01* (2)
*2→10 * (3)
*3→11 * (4)
* (5)
→ * (6)
Тексереміз:
0123→ *0123→00*123→0001*23→000110*3→00011 011*00011011
5 – мысал (Арнайы белгіні көшіру)
а символын Р сөзінің соңына жазу керек:
Мысалы: bbab→bbaba
Шешімі: Ең бірінші →а а символын Р сөзінің оң жағына емес сол жағына
жазады. А символын оң жағына жазу үшін ең алдымен сөздің соңын белгілеп
қою керек. Мұнда арнайы белгіні Р сөзінің соңына ауыстырамвыз. Содан кейін
а символын ауыстырамыз:
Р→ ... →Р*Ра
Бірақ арнайы белгіні сөз соңына қарай ауыстыруға болады. Бұл былай
бөлінеді: алдымен арнайы белгіні Р сөзінің сол жағына жазамыз, содан соң *
- ны орын ауыстыру арқылы сөздің келесі жағына шығарамыз:
bbab→*bbab→b*bab→bb*ab→bba*b→bbab*
ал мұндай ауыстыруды қалай жүзеге асыруға болады.
Қандай да бір ξ символының орын ауыстыруын байқау қиын емес. Бұл *ξ
символының ξ* орын ауыстыруы, мына формула бойынша жүзеге асады:
*ξ → ξ*
Айтылғандарды есепке ала отырып, келесі НАМ – ды аламыз:
*а→а*
*b→b*
* a
→ *
НАМ бос сөзге бірінші * - ны шығарады, содан кейін оны а символымен
ауыстырады да тоқтайды.
6 – мысал (Арнайы белгіні ауыстыру)
Р сөзідегі а символын аа – ға ауыстырады, егер осы сөзде а символы
болса.
Мысалы: bababb → babaabb
Шешімі: а символының қосарлануы мына формула бойынша жүзеге асады:
ааа. Бұл формула бірінші шыққан емес, соңғы шыққан а символына
қолданылуы үшін, айталық оң жағынан бастап санағанда соңғы а символынан
кейін арнайы белгі қойылады және а* аа формуласы қолданылады. Енді
соңғы шыққан а символының жанына * - ны қалай қоямыз. Соңғы шығу – соңынан
бастап санағандағы бірінші шығу болып табылады, сондықтан Р сөзінің сол
жағына * - ны жазып, орын ауыстыру арқылы сөздің келесі жағына өткіземіз,
содан кейін оңнан солға b символы арқылы жақын орналасқан а символына дейін
орындаймыз. Сонымен қатар кейде Р сөзінің а символы болмауы мүмкін. Егер *
сөз алдына шықса, оны жою керек немесе тоқтату керек.
Бұл ұсынысты келесі НАМ түрінде көрсетеміз:
*а→а* (1)
*b→b* (2)
b*→*b (3)
a*aa (4)
* (5)
→* (6)
(6) – шы формулада * Р сөзінің сол жағына жазылады, (1) және (2) формулада
* - ны Р сөзінің соңына қуады. ... жалғасы
Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz