Информатика пәнінен лекция тезистері

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 65 бет
Таңдаулыға:

14. ЛЕКЦИЯ ТЕЗИСТЕРІ

Алгоритмдеу негіздері. Алгоритмнің қасиеттері. Алгоритмді жазу тәсілдері.

Жоспары:

Алгоритм, программа ұғымдары.
Алгоритм қасиеттері. Алгоритм түрлері.
Алгоритмдердi график түрiнде жазу.
Алгоритмдердiң бiрыңғай түрлерi.

Лекция мақсаты:

Алгоритм, программа жөнінде алгоритмнің қасиеттері, алгоритмнің түрлеріне жалпы түсінік беру және алгоритмдердi график түрiнде жазу, алгоритмдердiң бiрыңғай түрлерін түсіндіру.

Лекция мәтіні:

Алгоритм, программа ұғымдары

ЭЕМ-ді пайдалану істерін қарастырмас бұрын оның жұмысымен тығыз байланысты алгоритм, программа ұғымдарын білуіміз қажет. Әрбiр ЭЕМ алдын ала берiлген алгоритммен, яғни жоспармен жұмыс iстейдi. Алгоритмдi заңдылық, реттелген амалдар жиыны, кезекпен орындалатын операциялар тiзiмi деп ұғынған жөн. Бұл ұғым қазіргі кезде кеңінен қолданылып жүр.

Алгоритм - берiлген есептiң шығару жолын реттелген амалдар тiзбегi түріне келтiру. Кез келген есептi қарапайым амалдарды тiзбектей орындау арқылы шығаруға болады. Алгоритмдi ЭЕМ-де орындау үшiн оны программа түрiнде жазып шығу керек.

Программа - алгоритмдi машинаға түсiнiктi нұсқаулар тiзiмi ретiнде жазу. Программа машинаға түсінікті командалардан тұрады. Осы командалар тізбегі орындалу барысында есептің нәтижесі шығады. Әрбір ЭЕМ алдын ала жазылған программамен істейді. Программа арнайы мәтiн арқылы ЭЕМ-ге тапсырманың реттi кезегiн хабарлайды. Процессор программаның құрамындағы командаларды кезекпен орындап отырады. Командалар тізбегін программа деп қарастыруға болады. Команда бір ғана қарапайым амалды орындау үшін бұйрық ретінде беріледі. Командалар: арифметикалық немесе логикалық амал; ақпаратты тасымалдау командасы; берілген сандарды салыстыру командасы, келесі командаларға көшу тәртібін орындау т. с. с.

Алгоритм - информатика пәнінің негізгі ұғымдарының бірі. Компьютерді қоғам өмірінің қай саласында болмасын пайдалана білу үшін алгоритм ұғымын меңгеру керек.

"Алгоритм" сѳзі мағынасы жағынан нұсқау, жарлык, рецепт, ереже, тәртіп, заң, жоба сѳздеріне синоним болып келеді. Алгоритм сѳзі Орта Азияның ортағасырлық ұлы ғалымы - Мұхамед ибн Мұса әл-Хорезмидің атымен байланысты шықкан. Ол өзінің "Арифметикалық трактат" деген еңбегінде арифметикалық амалдарды орындау тәртібін ұсынган. Сөйтіп арифметикалық амалдарды орындау ережесі, геометриялық фигураларды салу ережесі, сөздердің жазылуының грамматикалық ережесі т. е. сияқтылар алгоритм деп аталып кеткен.

A н ы қ т а м а. Алгоритм деп алдын - ала анықталган максатқа жету үшін, есептің шешімін табу үшін орындаушыға (адамға, компьютерге және т. б. ) берілген түсінікті нұсқаулардың тізбегін айтады.

ЭЕМ-нің жұмысы программалық принципке негізделген, яғни ол өзінің жадында сақталатын командалар тізбегін автоматты түрде орындау арқылы есеп шығарады.

Алгоритм мен программаға байланысты ЭЕМ-нiң мынадай жұмыс ерекшелiктерi болады:

Есептi шығару жолы алгоритм түрiнде өрнектелуi қажет;
Алгоритм программаға айналдырылуы тиiс;
Программа машина жадына енгiзiлiп, ретiмен орындалуы керек.

Сонымен, керектi нәтиженi алу жолында ақпаратқа қолданылатын әрекеттердiң орындалу ретiн анықтайтын нұсқау - алгоритм болып есептеледi.

Алгоритм қасиеттерi

Алгоритм ұғымының мәнiн ашатын негiзгi қасиеттерiнен немесе оған қойылатын талаптардан қысқаша мағлұматтар келтiрейiк. ЭЕМ-де орындалуға тиiс алгоритмдерге мынадай талаптар қойылады:

Анық әрi дәл өрнектелуi тиiс;
Алгоритм шектелген уақыттан соң нәтиже беруi тиiс, яғни алгоритм қадамдарының саны шексiз болмауы керек;
Бiр тектес есептерге жалпы бiр ғана алгоритм қолданылуы тиiс;
Модульдiк (бөлiк), яғни алгоритмдi кiшкене бөлiктерге бөлу мүмкiндiгi болуы қажет.

Алгоритмді кез келген басқа жазулардан мына мағыналык қасиеттері арқылы ажыратамыз. Олар алгоритмнің түсініктілігі, дискреттігі (жалғыздығы), анықтығы, нәтижелігі, жалпыға бірдейлігі. Берілген орындаушы үшін алгоритмнің т ү с і н і к т і л і г і деп, орындаушыньщ жарлықтарының жүйесіне, құрамына енетін іс - әрекеттерді орындау, тексеру туралы жазбалар мазмұнын айтады. Алгоритм ЭЕМ қабылдайтын және сол бойынша кажетті амалдарды орындай алатын нұсқаулар түрінде берілуі керек. Дискреттілігі- деп алгоритм жарлықтарының тізбектелген ретпен орындалуын айтады. Оның бір жарлығының орындалуының соңы мен келесі жарлықтың басына сілтеме дәл, нақты анықталады. Алгоритм, әрқайсысы ЭЕМ-ді белгілі бір қадам, әрекет жасататын нұсқаулардың тізбегінен тұрады. Әрбір жарлықты орындағанда алгоритмнің орындалуы аяқталды ма, не келесі қандай жарлық орындалады, сол туралы дәл мәлімет болуы шарт, яғни алгоритмде нұскаулардың орындалу реті анықталған болуы керек. Себебі, ЭЕМ үшін әрбір нұсқауды орындағаннан кейін келесі қай жарлықты орындау (не істеу керектігі) анык көрсетілуі қажет.

Алгоритм - шектеулі қадамдарды орындап болған соң нәтижеге алыл келеді. Нәтижеде, алгоритм орындалған соң есептің шешуінің аяқталуы, не қандай да бір себептерге байланысты есепті шешуді жалғастыру мүмкін еместігі туралы мәлімет болуы мүмкін. Алгоритмнің ж а л п ы л ы г ы деп оны бірдей типтегі (түрдегі) есептерді шешу үшін қолдануға болатындығьш айтады.

Алгоритмдердi ЭЕМ-де орындау үшiн оларды алдын-ала жазып алу керек, яғни ол белгiлi бiр заңдылықпен өрнектелуi тиiс. Жалпы алгоритмдi өрнектеу түрлерiне:

1) табиғи тіл арқылы жазу;

2) белгiлi бiр терминдер - псевдокодтар арқылы жазу;

3) графика жолымен жазу;

4) алгоритмдiк тiлдермен жазу жолдарын жатқызуға болады.

Алгоритмдердi графика жолымен жазу, кейiннен оны программаға айналдыру iстерi мемлекеттiк стандартпен бекiтiлiп ақпарат өңдеу жұмысында кеңiнен қолданылып келедi. Сонымен, алгоритм есептердi шығару жолын баяндау-өрнектеу үлгiсi, белгiлi бiр проблеманы шешу негiзiнде орындалатын әрекеттерге басшылық, ой еңбегiн үнемдеуге мүмкiндiк беретiн әдiс, есеп шешiмiн табуды автоматтандыруға қажеттi iс-әрекет, жаңа проблеманы шешу кезiнде қолданылатын тәсiлдер, күрделi процестердi өрнектеу және математикалық дәлдiкпен анық етiп жазу құралы бола алады.

Есептi ЭЕМ-де шығарудың негiзгi кезеңдерi

Есептi ЭЕМ-дi пайдаланып шығару алты кезеңнен тұрады:

Есептiң математикалық жобасын белгiлеу;
Есептiң шешу әдiсiн таңдап алу;
ЭЕМ-ң ерекшелiгiн ескерiп, есептi шешу үшiн алгоритм таңдау, құрастыру;
Программалау;
Программа жұмысын ЭЕМ-де тексеру, қалыптастыру;
Есептi ЭЕМ-де автоматты түрде орындау.

Алгоритмдердi график түрiнде жазу

Алгоритмдердi өрнектеудiң көп тараған түрi - оны график арқылы бейнелеу. Графикалық жолмен алгоритмдердi жазу үшiн мемлекеттiк стандарт белгiленген, онда кез келген амал белгiлi бiр геометриялық фигурамен өрнектеледi. Ол фигуралар немесе блоктар амалдар символы деп те аталады. Блоктар бағытталған сызықтармен байланысып, бiрiнен соң бiрi орналасады. Жиi қолданылатын амалдар, яғни мәлiметтердi ЭЕМ-ге енгiзу, формуламен есептеу, шарттардың орындалуын тексеру, нәтиженi қағазға басу символдары 1-суретте көрсетiлген. Осы суреттегi көрсетiлген блоктардан (символдардан) алгоритм схемалары құрастырылады. Алгоритмдер схемасымен ақпаратты өңдеудiң әрбiр сатысы немесе орындалатын операциялар ретi анықталады. Кейде алгоритмдер схемасын оның блок-схемасы деп те атайды.

Сонымен, керек болған жағдайда алгоритмге сәйкес блок-схема жасалады. Блок-схема - алгоритмнiң орындалуын ұйымдастыру үшiн қолданылатын амалдар тiзбегiнiң графиктiк кескiнi. Блок-схема келiсiлген геометриялық фигуралардың көмегiмен құрылады және бұл фигураларға келiсiмге байланысты өзiндiк мағыналар берiледi.

Іс-әрекеттiң аты

Блоктың пiшiнi

Оның атқаратын жұмысы

Іс-әрекеттiң аты: Процесс

Блоктың пiшiнi:

Оның атқаратын жұмысы: Математикалық өрнектердi есептеу

Іс-әрекеттiң аты: Таңдау

Блоктың пiшiнi: жоқ иә

Оның атқаратын жұмысы: Есеп шығару жолын таңдау

Іс-әрекеттiң аты: Модификация

Блоктың пiшiнi:

Оның атқаратын жұмысы: Цикл(қайталау) басы

Іс-әрекеттiң аты: Құжат

Блоктың пiшiнi:

Оның атқаратын жұмысы:

Нәтиженi шығару,

қағазға басып алу

Іс-әрекеттiң аты: Енгiзу, шығару

Блоктың пiшiнi:

Оның атқаратын жұмысы: Мәлiметтердi енгiзу(шығару)

Іс-әрекеттiң аты: Бастау, аяқтау

Блоктың пiшiнi:

Оның атқаратын жұмысы: Алгоритмдердi бастау, аяқтау

Іс-әрекеттiң аты: Қосалқы программа

Блоктың пiшiнi:

Оның атқаратын жұмысы: Қосалқы программаларға кiру және шығу

Іс-әрекеттiң аты: Түсiнiктеме

Блоктың пiшiнi:

Оның атқаратын жұмысы:

Схеманы, формулаларды

түсiндiру

1 - сурет. Алгоритмдердi бейнелеу блоктары

Алгоритмдердiң бiрыңғай түрлерi

Күрделi алгоритмдердi құру үшiн қарапайым бiрыңғайланған алгоритмдiк элементтердi қолданады. Олар сызықтық, тармақталу және цикл құрылымдарынан тұрады.

Сызықтық құрылымды алгоритм немесе қарапайым сызықтық алгоритм iс-әрекеттердiң орындалу ретiне қарай тiзбектеле орналасқан блоктардан тұрады. Амалдардың бұлай бiрiнен соң бiрi реттелiп орындалу тәртiбiн табиғи атқарылу дейдi. Мысалы: Z функциясының сандық мәнiн есептеу алгоритмiн құралық z=ax ² +b+cos(ax ² +b) -tg(ax ² +b) . 3 сурет сызықтық алгоритмнiң мысалы болып табылады.

Тармақталу алгоритмi . Тұрмыста кездесетiн алгоритмдер әр түрлi болып келедi. Олардың жиi кездесетiн түрiне алгоритмнiң белгiлi бiр шарттың орындалуына не орындалмауына байланысты тармақталып бiрнеше жолдарға бөлiнуi жатады. Тармақталу алгоритмiнiң құрылымы қарапайым болып келедi. Мұнда арифметикалық теңсiздiк түрiнде берiлген логикалық шарт тексерiледi. Егер ол орындалса, онда алгоритм бiр жолмен, ал орындалмаса 2-шi жолмен жүзеге асырылады, яғни есептi шығару жолы тармақталып 2-ге бөлiнiп кетедi. Тармақталу алгоритмдерiне шартты тексеру блогы мiндеттi түрде кiредi. Ол ромб түрiнде кескiнделiп, басқа блоктармен 1 кiру және 2 шығу сызықтары арқылы байланысады. Көбiнесе тармақталу алгоритмдерi екi түрде кездеседi, олар”таңдау” және “аттап өту ” мүмкiндiктерiн iске асыруға көмектеседi.

“Таңдау” жолымен тармақталуда берiлген шарт тексерiледi (2-сурет), егер ол шарт орындалса (орындалуы анық, ақиқат болса), онда 1-амал атқарылып, содан кейiн келесi 3-амалға көшемiз. Ал егер де шарт орындалмаса, яғни оның орындалу мүмкiндiгi жалған болса, онда 1-амал атқарылып, содан кейiн 3-амал атқарылады Сонымен, шарттың ақиқат немесе жалған болуына байланысты 1-амал немесе 2-амал орындалады.

“Аттап өту” (3-сурет) алгоритмiнде шарт орындалса, онда 1-амалды аттап өтiп, бiрден 2-амалды, содан кейiн 3-амалды орындаймыз. Ал шарт жалған болса, онда 1-шi амал мiндеттi түрде орындалып, одан кейiн 2 және 3-шi амалдар жүзеге асырылады.

2-сурет. 3-сурет

Тармақталу кезеңiнде шартты тексеру блогы орындалуы барысында, алгоритмнiң екi мүмкiндiгiнiң тек бiреуi ғана таңдап алынып жүзеге асырылады да, ал екiншi таңдап алынбаған тармақ бiрiктiру нүктесiне дейiн орындалмай қалады.

Циклдiк алгоритмдер . Көптеген есептердi шығару кезiнде бiр теңдеудi пайдаланып, ондағы айнымалының өзгеруiне байланысты оны бiрнеше рет қайталап есептеуге тура келедi. Осындай қайталап орындалатын есептеу процесiнiң белгiлi бiр бөлiктерiн цикл деп атайды. Осы бiрнеше рет қайталанатын бөлiгi бар алгоритмдер тобы циклдiк алгоритмдерге жатады. Цикл алгоритмдердi пайдалану оларды кейiннен программаларда цикл операторы түрiнде қысқартып жазу мүмкiндiгiн бередi. Циклдер қайталану санының алдын ала белгiлi және белгiсiз болуына байланысты 2 топқа бөлiнедi. қайталану сандары алдын ала белгiлi болып келетiн циклдер тобы арифметикалық цикл болып есептеледi, ал орындалу саны белгiсiз циклдер - қадамдық (итерациялық) цикл болып табылады. Цикл орындалуы алдында оның айнымалы аргументi-параметрi алғашқы мәнге ие болуы керек, сонан кейiн қайталану кезеңiнде цикл параметрi белгiлi бiр шамаға өзгере отырып, ол алдын-ала берiлген ең соңғы мәнге дейiн жетуi қажет.

Алгоритмнiң орындалу барысында цикл параметрi, мысалы, х өзiнiң ең алғашқы х ₀ мәнiнен ең соңғы х _k мәнiне дейiнгi тұрақты шамаға (dx) өзгерiп отырады. Осының нәтижесiнде х мынадай мәндердi қабылдайды:

х ₀ , x ₀ +dx, x ₀ +2dx, . . . , x ₀ +(n-1) dx, x _k

Қадамдық циклдер . Циклдi орындаудың алдында, оның қайталану саны белгiсiз болған жағдайда қадамдық циклдер пайдаланылады. Мұнда циклдi жазу үшiн тек қана “шартты тексеру” блогын қолдану қажет, ол циклдi аяқтау үшiн белгiлi бiр шартты тексередi. Қадамдық циклдердiң схемасын сызғанда модификаторды (алтыбұрышты) пайдалана алмаймыз, өйткенi алдын ала циклдiң неше рет қайталанатыны бiзге белгiсiз.

Бақылау сұрақтары:

Алгоритм деген не?
Алгоритмнің қандай қасиеттері бар, оларды қалай түсінесіз?
Алгоритмдердің берілуі. Алгоримнің орындаушысы?
Алгоритмді сипаттаудың қандай әдістерін білесіз?
Алғашқы, қорытынды мәліметтер деп нені айтамыз?

2 - лекция. Тақырыбы: Информация ѳлшемі. Алгоритм ұғымын нақтылау.

Тьюринг машинасы. Тьюрингтің тезисі және оның дәлелдеуі.

Марковтың нормалы алгоримдері. Нормалауды қағида және

оның дәлелдеуі.

Жоспары:

Тьюринг машинасының құрылымы, қызметі.
Тьюрингтің тезисі және оның дәлелдеуі.
Марковтың нормалы алгоримдері.
Нормалауды қағида және оның дәлелдеуі.
Марковтың тьюринг машинасы және нормалды алгоритмдерді композициялау.
Пост машинасы.

Лекция мақсаты:

Информация өлшемі, Тьюринг машинасының құрылымы, қызметі туралы, Мароковтың нормалы алгоритмдері, Пост машинасы туралы жалпы түсінік беру.

Лекция мәтіні:

Информация ѳлшемі. Алгоритм ұғымын нақтылау. Тьюринг машинасы

Информация шамасын өлшеудің үш тәсілі бар: көлемдік, энтропиялық , алгоритмдік.

Көлемдік өлшем - мәлімет құрайтын символдар саны.

Оны ѳлшеу информацияның жазылу түріне байланысты. Мысалы, 13 санын түрліше жазуға болады: "он ұш ", 13, XIII, 1101 ₂ (бұлардың соңғысы екілік санау жүйесінде жазылған) .

Информация теориясында информацияны ѳлшеу үшін энтропиялық тәсіл пайдаланылған (энтропия - ішке айналу) . Энтропия деп кездейсоқ (екі үштылық) болатын жағдайдың (орындалуы алдында нәтижесі белгілі емес тәжірибенің) анықталмағандық шамасын айтады. Ол мынадай модельден түрады:

- тәжірибе бойынша белгілі оқиғалардың орындалу шамасы анықталады;

- шамаларды дәл есептеу мүмкін болмағандықтан, олардың энтропиясын ықтималдықты пайдаланып есептейді.

Энтропияны информацияның жеткіліксіздік шамасы деп қарастыруға болады. Ол ықтималдықтар жиынтығының біршама математикалық байланыстылығы арқылы сипатталады.

1-мысал. Тиын ақшаны аспанға лақтырғаңда оның сандық бетімен не қарсы бетімен түсуінің энтропиясын анықтау керек.

Мұңдай жағдай тең ықтималдықты екі оқиғадан тұратыны белгілі, ықтималдық (P) 0. 5-ке тең. Информация теориясында берілген тең ықтималдықты n оқиғалар үшін әр оқиғаның энтропиялық шамасы (H) анықталатын формула:

H = * log ₂ n

Жоғарғы мысалда: n = 2, H = 0. 5 (log ₂ 2 = 1) .

Тандалған оқиғалар саны (n) 2-нің бүтін дәрежесіне тең болмаса да, тең ықтималдықты оқиғалар үшін осы формула пайдаланылады (әр оқиғаның орындалу ықтималдығы l/n-ге тең) . Егер оқиғалар тең ықтимаддықты болмаса, энтропия шамасы төмендегі формула бойынша есептеледі (формуланы 1948 жылы ғалым К. Шеннон ұсынған) :

Мұңдағы Р _к - к-жағдайдағы жүйенің ықтималдығы; H - жүйенің энтропиясы (информацияньщ жеткіліксіздік шамасы. Ол тәжірибеде информация санының мөлшері үшін де пайдаланылады) .

Егер барлық оқиғалар тең ықтимаддықты болса (Р _к = 1/ n), олардың энтропиясы:

2-мысал. Қапшықта 10 шар бар. Олардың 9-ы ақ, 1-і қара түсті. Қапшықтан алынған шардың түсін білдіретін информация шамасын (энтропияны) анықтау керек.

P ₁ = 0. 9; P ₂ = 0. 1

H = 0. 9 * log ₂ (1/ 0. 9) + 0. 1 * log ₂ (1/ 0. 1) 0. 469

Яғни бұл тәжірибенің энтропиясы бірдей ықтималдықты екі оқиғаның энтропиясынан кіші екенін көрсетеді.

Алгоритмдер теориясьшда мәліметтік информацияны алгоритмдік тәсілмен бағалау жүргізіледі. Алгоритм қасиеттері жоғарыда аталып кеткен болатын. Олар: үздіктілік, түсініктілік, қадамдардың қарапайымдылыгы, көпшілікке бірдейлігі және нәтижелілік. Ал, егер есептің шешімі болмаса, оны дәлелдеу және мәнсіздіктен құтылу үшін алгоритмнің қатаң түрде зандылық анықтамасы қажет. Мұндай ұғым өткен ғасырдың 30-жылдарының ортасында рекурсивті функциялар және дерексіз автоматтар (машиналар) негізінде енгізілді:

у = f (X ₁ , X ₂ , . . . , X _n ) сандық функциясының мәңдерін есептеудің алгоритмі болу үшін функция жарым-жартылай рекурсивті болу керек.

Жарым-жартылай рекурсивті функция ұғымы алгоритмдер теориясының негізгі ұғымдарының бірі:

- әр жарым-жартылай рекурсивті функцияньщ шешу алгоритмі бар;

- алгоритмдер бойынша шешілетін функциялар жарым-жартылай рекурсивті, керісінше жагдайда есеп алгоритм бойынша шешімсіз.

Есептің шешілуін оңайлату тәсілдерінің бірі - берілген есепті бастапқы берілгендер мен шешуі бірдей болатын оңайлатылған ішкі есепке ауыстыру (ол бәсендету стратегиясы делінеді), ал кезегімен оны да осы сияқты басқа ішкі есепке алмастыруға мүмкін болса, мұндай процесс рекурсия делінеді. Кейбір программалау тілдерінде ішкі программаның ѳзін-ѳзіне шақыратын құрылымын рекурсивтік құрылым деп атайды. Рекурсивтік әдіс нәтижелі болу үшін ол есептің шешуін дәл беруі тиіс. Рекурсияны пайдалану үшін алдымен берілген есеп пен қосымша есептің байланысын (кейде жиектік шартты да) анықтап алу керек. Әдетте қарапайымдау болатын жиектік шартты пайдаланып есепті шешу әдісі жоғары кѳтерілу стратегиясы делінеді. Мысалы, рекурсия бойынша n ! мәнін есептеу әдісі:

n! = (n-1) ! * n;

Мұндай әдіс рекурренттік деп те аталады (recurrent - қайталанушы) .

Алгоритмдер теориясында дәлелденгеніндей, алгоритмнің бір менді түсінілуі, ал оның қадамдары қарапайым және орыңдалатын болуы үшін осы талаптарды орындайтын машина болуы тиіс. МҰндай машиналардың бірі - абстрактілі (теория жүзіндегі) Тьюринг машинасы. Алгоритмнің қатаң зандылығымен жұмыс істейтін Тьюринг машинасының құрылымы 2. 1-суретте кѳрсетілген (а - енгізілген символдар, і = 1, 2, 3, . . . ) .

Машина құрамындағы таспа жеке ұяшықтардан тұрады (таспа шексіз болуы да мүмкін) . Әр ұяшыққа алфавитке сәйкес тек бір символ енгізіледі

( 1-суретте символ енгізілмеген ұяшық бос символ (<< >>) арқылы белгіленген) . Бастиек міндетті түрде бір ұяшықтың үстінде орналасулы тұрады. Ол символды оқи және енгізе алады, қажет болса, оны өшіреді. Бастиектің ерекшелігі - ол таспа бойынша еркін жылжи алатын етіп орналастырылган.

басқару құрылғысы

бастиек

. . .

<<>>

. . .

1-сурет. Тьюринг машинасының негізгі құрылымдық бөлімдері

Тьюринг машинасының қарапайым бір қадамдық өрекеті мынадай іс-әрекеттерден тұрады:

- бастиек бір тактілік уақытта өзі тұрған ұяшыққа енгізілген символды оқиды;

- оқылған символ және бастиектің ағымдық орны басқару құрылғысының жағдайын (жаңа күйге өтуін, жаңа жазылатын символды, бастиектің жылжуын және т. с. с. ) бір мәнді анықтайды;

- басқару құрылғысы машинаға берілген команданы орындайды және сақтайды;

- автоматтың соңғы қалып-күйге өтуіне байланысты, машина ѳз жұмысын тоқтатады не алгоритм дұрыс құрылмаған болса, еш уақытта тоқтамайды.

Жұмыс басында бастиек таспа ұяшығына бір машиналық сөз жазады да, келесі ұяшықтың үстіне орналастырылып қойылады, т. с. с.

Алгоритмдер теориясында құрылган алгоритмдер өзінің мүмкіндігі бойынша Тьюринг машинасына және алгоритм ұғымын делелдейтін басқа үлгілерге (модельдерге) баламалы екені делелденген. Алгоритмнің мұндай ұғымы арқылы шешілмейтін проблемаларды алгоритмдеу мүмкін емес екені де дәлелденді. Яғни есепті Тьюринг машинасы арқылы шешуге мүмкін болмаса, оның алгоритмі шешімсіз.

Машиналық тілдегі программа

Қарапайым операцияны орындау үшін компьютерге берілетін әр нұсқау машиналық команда деп, ал комаңдада көрсетілген амалға енетін сан не символ операнд не амал аргументі деп аталады.

Шын мәнінде есептеуіш машина жоғарғы есепті шешу үшін құрылған алгоритмге енгізілген командаларды оқи да, орындай да алмайды. Машинаның орындай алуы үшін оларды машина "түсіне" алатындай етіп, қайтадан жазып шығу керек. Осы шарт орындалған кезде командалар машина кодында не машиналық тілде жазылған делінеді. ЭЕМ-ге түсінікті командалар тізбегі арқылы жазылған алгоритм программа (өңдеу бағдарламасы) деп, программа құру процесі программалау (өңдеу бағдарламасын құру) деп, машина орындай алатын командалар жиыптыгы командалар жүйесі деп аталады.

Программаға программалау тілінің (жүйенің) кітапханасында сақтаулы арнайы функциялар (мысалы, sin, In) мен түрлі ішкі программалардың енгізілуі де мүмкін.

Программа дайындалып, машинаға еңізілген соң, ЭЕМ-нің жұмысы - оны автоматгы түрде орындау. Яғни ЭЕМ-нің іс-әрекеттері алдын ала құрылған программа бойынша ғана жүргізіледі. ЭЕМ жұмысының бұл ерекшелігін программалық басқару принцип деп атайды. Машиналық команда мынадай екі болімнен тұрады:

... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.