Тілдер мен автоматтар теориясы

Кйрсетілген ба“дарлама, тйбені тек ›ана оныЈ ±рпа›тары йЈделгеннен кейін “ана йЈдейді.Ба“дарламаны ›алай йзгерту керек,Щр тйбе, пара› болмайтын жа“дайда екі рет йЈделу Їшін: йз ±рпа›тарынан кейін ал сосын о“ан дейін. (Пара›тар б±рын“ыша бір рет йЈделеді.)

Б±л ба“дарламада“ы операциялар саны б±та› тйбесініЈ санына теЈ. (Бас›а ба“дарламаларда сия›ты, олар командаларды жіберу мен жЩне кей командаларды "йЈдеу"шектелмейді.)

Н±с›аулы›. Б±л ба“дарламаны орында“анда Щр ретте екінші Щрекет –тйбелерді йЈдеу,ал Щр тйбе кем дегенде екі рет йЈделеді.
Тапсырма 7

Б±та›ты айналу Щдісі келесі тапсырмаларды ›олдану Їшін пайдалынады: жиым берілген . –нан толы› оЈ сандардан т±рады жЩне санынан; білуіміз керек, саны жиым саныныЈ сомасы ретінде кйрсетілуі керек пе? (Шр санды тек ›ана бір рет пайдалану“а болады.)

Шешімі. бульдік ма“ыналардан -орынына тізбелікке жол береміз, б±л ма“ыналар сома санына кіре ме немесе жо› па? Б±л ±станым д±рыс егерде сома -тен аспаса.

Ескерту. Барлы› жиынты›ты толы› алып салыстыр“анда ( деЈгейінде ) кей жерде біз ±тамыз. жиымын азаю тЩртібінде алдын ала сараптау“а болады., жЩне де пен барлы› мЇшелердіЈ айырым сомасы алып тастал“ан мЇшелер сомасынан кйп болып келеді. СоЈ“ы ›абылдауды "тарма› жЩне шекара Щдісі"деп атайды. Біра›та толы› ›амтумен салыстыр“анда жа›сы нЩтиже жо›. Б±л есептін дЩстЇрлі аты- " рюкзаке туралы есеп" (жалпы жЇк кйтеруші рюкзагін тЇйінге байлау керек, салма›ты на›ты білгенде ). ЖЩне 7 тарауда ›араЈыз ( динамикалы› ба“дарлама туралы бйлім ) оныЈ шешілім алгоритмы, полиномиалды бойынша.

нйлінен, бірліктен жЩне екіліктен шы“атын тізбектілікті аны›таныз, жЩне де оныЈ ішінде цифрлар тобы екі рет ›айталанбау керек ( XX бйлігініЈ тЇрі жо›).

1. 
   љандай символ йЈдірмейтін деп аталады?
   
2. 
   љандай символ ›ол жетпейтін деп аталады?
   
3. 
   –ді –“а шахматты› та›тада n ферзиді ›ою тЩртібін аны›таныз жЩне олар бір-бірін со›пау керек.
   

Терминалданба“ан дЇкендік танушылар ж±мысыныЈ модельденуі реттіліктіЈ бастауыш жай-кЇйден соЈ“ы жай-кЇйге ауысуын іздеумен байланысты. Іздеу жеке-жеке ›адамдардан т±рады.

ЖЩне олардыЈ Щрбіреуі сЩтсіздікке жЩне бастап›ы жай-кЇйге Щкелуі мЇмкін. Б±ндай іздеу уа›ытты кйпалатынды›тан тЩжірибеде ›айтымсыз ж±мыс істейтін детерминалдан“ан танушыларды ›олданады. Б±л танушылар -тілдердіЈ шектеулі кластарын “ана ›олданыс›а жібереді, біра› олар ба“дарламалау тілдерініЈ барлы› синтаксистік жа›тарын кйрсетеді.

Танушыларды азаймалы жЩне йрмелі деп екі категория“а бйлуге болады.

Азаймалы танушылар ережелерді жо“арыдан тймен йЈдейді, я“ни жо“ары ережелерді тйменгілерден б±рын. Ал б±л уа›ытта кіріс анализаторлары тймендегі ережелерді жо“арыда“ылардан б±рын ›олданады. Детерминалдан“ан автоматтардыЈ мЇмкіндіктері мен олардыЈ т±р“ызылу тЩсілдерін кйрсету Їшін б±л бйлімде тЇріндегі грамматикалар тудыратын азаймалы танушылар ›арастырылады.  

  атауы Left сйзінен шы››ан, себебі анализатор кіріс шынжырын солдан – оЈ“а ›арай кйреді. ТЩжірибеде кйбінесе грамматика класы ›олданылады. Олар Їшін а“ымды позицияда орналас›ан детерминалдан“ан бір кіріс символды танушылар ж±мыс істейді. О›удыЈ бірінші ›адамы ретінде азаймалы танушылардыЈ грамматика кластары ішіндегі бір реттілікті ›араймыз.

Бйлінген ауыспалылар.

љ±рамында жою ережелері жо› мЩнмЩтінді-бос грамматика тймендегі келесі екі шартты орындаса “ана бйлінген немесе жай деп аталады: 

1. 
   Шр ереженіЈ оЈ жа“ы терминалмен басталса.
   
2. 
   Егер екі ереженіЈ сол жа“ы бірдей болса, онда б±л ережелердіЈ оЈ жа“ы тЇрлі терминалды› символдармен басталуы керек.
   

бйлек грамматика болып келеді, (1) и (2) жа“дайы орындалуда.

Бас›а жа›тан ал“анда, грамматика

бйлек грамматика болмайды , себебі (2) ережеде шарт б±зылады (1), ал ережесінде (3) жЩне (4) - шарт (2).

Бйлек грамматиканыЈ негізгі ›асиеті болып, олардыЈ Щр›айсысынан детерминалды тймен тЇсетін айырылымдарын ›±ру“а болады.

 

Мысалы

Ханой м±нараларында“ы есепте са›иналардыЈ ›оз“алу бірізділігін табу Їшін рекурсивті емес ба“дарламаны жазвЈвз.

Шешімі. Рекурсивті ба“дарламаны еске тЇсірейік, -ді ауыстырып ›оятын жо“ар“ы са›иналары с нен :
procedure move(i,m,n: integer);

| var s: integer;

begin

| if i = 1 then begin

| end else begin

| | s:=6-m-n; {s – Їшінші йзек: нймірлер сомасы 6 теЈ}

| | move (i-1, m, s);

| | writeln ('›адам жасау ', m, '->', n);

| | move (i-1, s, n);

| end;

end;

Б±л Їшін ›алтарыл“ан стек есептерін жасайы›.ОлардыЈ элементтері Їштіліктер болып келеді.Шр Їштілік тапсырыс ретінде интерпретациаланады "жо“ар“ы дисктерін -ші йзектен -ге ауыстырылсын" . Тапсырыстар олардыЈ орындалу талаптарына сЩйкес жасал“ан: еЈ жедел – стек биіктігі.Мынадай ба“дарлама аламыз:

begin

| стек›а Їштілікті ›ою

| {инвариант: стекта“ы тапсырыстарды орындау ›алды}

| while стек непуст do begin

| | жо“ар“ы элементті жою,оны

| | if j = 1 then begin ауыстыру

| | | writeln ('›адам жасау', p, '->', q);

| | end else begin

| | | s:=6-p-q;

| | | {s – Їшінші йзек: номерлер сомасы 6 теЈ}

| | | стек›а Їштерді ›ою , <1,p,q>,

| | end;

end;
(еЈ бірінші стекке Їш ›ойылады, оны соЈ“ы кезде орындау керек).

Стек Їштіліктері жеке стектері ретінде іске асады. (Сонымен ›оса, паскальдіЈ арнайы тЇрі бар, оны "жазылу" деп атайды).

Тапсырма 1

(А.К.Звонкин Анджея Лисовскиге хабарлады). Ханой м±наралары туралы есептерде рекурсивті емес алгоритмдер бар.

ОлардыЈ бірі: ›ондыру йзектері ( ауыстырулардан емес) барлы› йзектер кезек бойынша болу керек . Келесі ереже: кезекпен еЈ аз са›иналарды жЩне еЈ аз емес са›иналарды ауыстыру,сонымен еЈ азын шеЈбер бойнша.
Тапсырма 2

Рекурсия орнына стекті ›олдану. Толы› санныЈ онды› басылымныЈ рекурсивті ба“дарламасында тапсырмалар кейінге ›алдырыл“ан.

Екілік б±та› тйбелерініЈ барлы“ын жазатын рекурсивті емес ба“дарламаны жазыЈыз.

Не йзгереді, егерде б±та›тын екілік тйбелерін жазбаса›, біра›та оныЈ саныЈ есептесек?

6 мЇмкіндігі бар тЩртіптер Їшін кей жеЈілдіктер болуы мЇмкін, екі тЇрдегі стек элементтерінде керек емес са›талымдарды жасайды. Кейбіреулерін кйрсетейік.

Ескерту. Б±та›тын барлы› тйбелерін жазуда“ы бас›а ба“дарламасын б±та›ты айналу ба“дарламасы негізінде ›±ру“а болады (тиісті тарауда ›арастырыл“ан) Онда "тймен" командасы орындалады. Енді барлы› тйбелер тізімін тЇбірден а“ымда“ы тйбеге бару жолын са›тау керек Сонымен ›оса графта“ы алгоритмдар туралы тараудан ›араЈыз.
Тапсырма 6

1 – толы› сандар болсын. жиымын ›±растыру керек, ..., , ол Їшін сондай сандар болу керек.

Ескерту. сандар арасында теЈ болуы мЇмкін. Шр толы› сан ›анша рет кірсе, да кіру керек.

Шешімі. Санау“а онай, мен сандары жиымыныЈ бастап›ы жЩне соЈ“ы ма“ынасын білдіреді. Талаптар " жЩне бір сандарды талап етеді" кйре т±ра орындалады, егерде элементтерініЈ орынын ауыстыру процесімен шектелсек.

{ x жиымыныЈ k аз элементтері йз орындарында орналас›ан}

while k <> n do begin

| s := k + 1; t := k + 1;

| {x[s] - арасында еЈ азы... x[k+1] x[t] }

| while t<>n do begin

| | t := t + 1;

| | if x[t] < x[s] then begin

| | | s := t;

| | end;

| {x[s] – еЈ аз x[k+1]..x[n] }

| ... ауыстыру x[s] и x[k+1];

| k := k + 1;

end;
2 Инвариантты ›олданатын, с±рыптау есебіне бас›а шешім беру керек. {первые элементтін біріншісі реттелген: }

Ба›ылау с±ра›тары
1 Рекурсивті емес ба“дарламаны ›алай ›±ру керек?

2 Не йзгереді, егер де екілік б±та›тын тйбесін баспаса, ал тек ›ана оныЈ саныЈ санаса?

Бойер-Мура алгоритмы.

Б±л алгоритм жасау“а мЇмкін емес нЩрселерді істейді: ±›сас жа“дайда ол сйздердіЈ бір бйлік Щріптерін “ана о›иды. Б±л ›алай болуы мЇмкін? ите жеЈіл. Мысалы біз " " Їлгісін іздестірейік.

СйздіЈ тйртінші Щріпіне ›арайы›: егерде ол " Щріпі болса", бірінші Їш Щріпті о›у ›ажеттілігі жо›. (Негізінде " " Щрпі Їлгісінде жо›, сонды›тан ол бесінші Щріптен кейін “ана басталады).

Біз осы алгоритмніЈ еЈ оЈай вариантын кйрсетейік, біра›та ол барлы› жа“дайда ж±мыстыЈ шапшанды“ына кепілдік бере алмайды болсын - Їлгі, оны іздеу керек. символдыЈ Щр›айсысы Їшін, оныЈ сйзінде д±рыс кйтерілуін табайы› я“ни , теЈ бол“ан жа“дайда. Б±л мЩліметтер массивінде са›талады, егерде символы кездеспесе, онда бізге ›ою“а ыЈ“айлы болады (неге екеніЈ тйменде кйреміз).
Мысалы

массивін ›алай толтыру керек?

Шешімі
барлы› pos[s]›ойыЈыз б теЈ 0 бол“андай
for i:=1 to n do begin
pos[x[i]]:=i;
end;

Іздеу Їдерісінде біз ауысымын сйздегі Щріпті са›таймыз, ЇлгініЈ соЈ“ы Щрпі т±р“ан“а ›арсы. басында (Їлгі ±зынды“ы), ал сосын біртіндеп йседі.

last:=n;
{љал“ан барлы› Їлгі жа“дайлары тексерілген}

Б±л алгоритмніЈ Щр тЇрлі модификациясы болуы мЇмкін.

Мысалы, жолын жолына ауыстыру“а болады, онда – координаттары екінші оЈ жа“ында“ы шы“у Щріптері.

Осыны ба“дарламада ›алай ескеруге болады?

Шешімі. кестесін ›±р“анда

for i:=1 to n-1 do... жазыЈыз (ары ›арай б±рыЈ“ыша), ал негізгі ба“дарламада орнына жазыЈыз;

Келтірілген Бойер - Мура алгоритмніЈ жеЈіл тЇрі кей жа“дайда n Щрекетін кйбірек талап етеді. ( сандар ЩрекетініЈ тЩртібі), Кнута - Моррис – Пратта алгоритмінен кішкене “ана жеЈіліп ›алды›.

Тапсырма 1

Жа“дай мысалын келтіріЈіз, оныЈ ішіндегі Їлгі сйзге кірмейді, біра›та оны белгілеу Їшін, алгоритм Щрекетіндегі тЩртіпті талап етеді.

На›ты (жеЈілдетілмеген) Бойера - Мура алгоритмі кепілденеді, Щрекеттер саны аспайды. Ол Кнут-Моррис-Пратта алгоритмініЈ идеяларына жа›ын, идеялар пайдаланады. ОЈнан сол“а жЇргенде біз кірген сйзбен Їлгіні салыстырайы›. Кейбір бйлігі (ЇлгініЈ соЈы болып келген) теЈ келді, ал сосын айырмашылы“ын тапты›: Їлгіде алдында кіру сйзіндегідей емес болып келеді.Б±л кезде кіру сйзі туралы не айту“а болады? ОныЈ ішінде теЈ Їзінді табылды, ал оныЈ алдында Їлгідегі емес Щріп т±р. Б±л а›парат Їлгіні бірнеше рет оЈ“а ›арай жылжыту“а мЇмкіндік береді жЩне деоныЈ кіруіне еш кедергі болады. Б±л жылжытуларды ЇлгініЈ Щр соЈы Їшін алдан ала есептеп ал“ан жйн. ’алымдардыЈ айтуынша, б±нын барлы“ы (жылжудыЈ кестесін жЩне оныЈ ›олдануын есептеу) Щрекетіне ›ою“а болады.
Тапсырма 2

ДеЈгейге шы“ару мЩтінінде ›атар орналас›ан екі ж±лдызша мен белгіленген. Б±л белгіні '^' ауыстыру“а шешім ›абылданды (сонымен ' ' ауысады ' '). Осыны ›алай жай тЇрде жасау“а болады?

Бастап›ы мЩтін символдан кейін символды о›иды, алын“ан мЩтінді символдан кейін символды ›осып басу керек.

Шешімі. Шр уа›ыт сайын ба“дарлама екі жа“дайдыЈ бірінде болып келеді "негізгі" жЩне "ж±лдызшадан кейін"

Ескерту. БіздіЈ ба“дарлама заменяет '***' '^*' ауыстырады (біра›та '*^' емес). Есептеу жа“дайында біз кей детальдарды тал›ыла“ан жо›пыз - ба“дарлама "д±рыс Щрекет істеу керек". Атал“ан уа›ытта,ба“дарламаныЈ ›алай ж±мыс жасайтыныЈ тЇсіндірудіЈ еЈ тиімді жолы б±л оныЈ жа“дайы мен Щрекетін бейнелеп беру.

МЩтіннен барлы› сйдердіЈ ' ' тЇрін жоятын ба“дарламаны жазыЈыз.

Паскальда тЇсініктемелер бейнелі жа›шалармен келтірілген: begin { цикл басы} ; { ді 1арттырамыз}

Ба“дарламаны жазыЈыз, ол тЇсініктемелерді жойып, ал жойыл“анныЈ орнына аралы›ты ›ойсын ('1{бір}2' ауыссын, '12' емес, ал '1 2').

Шешімі. Ба“дарламаныЈ екі жа“дайы бар: "негізгі" жЩне "ішкі тЇсініктеме".

Жа“дайы. Кезекті жаЈа іс-Щрекет
жа“дайдыЈ ішкі символы
негізі { ішкі жа“ында жо›
негізі x <> '{' негізі x басу
ішінде } негізі аралы›ты басу
ішінде x <> '}' ішінде жо›
Ескерту. Б±л ба“дарлама салын“ан тЇсініктемелерді ›абылдамайды: жол {{тЇсініктемелер ішінде} тЇсініктемелер} ауысады тЇсініктемелер} (басында екі аралы› т±рады). СоЈ“ы автоматпен тЇсініктемені йЈдеу мЇмкін емес (жа›шалар саныЈ білу керек – ал натуралды сан соЈ“ы жады“а сыймайды).
Тапсырма 5

Паскаль ба“дарламасында тырна›ша“а алын“ан жолдар бар.

Егер де кескінді тырна›ша жол ішінде кездессе, онда ол тЇсініктеменіЈ басы немесе ая› жа“ы деген ма“ынаны білдіреді. љалай ба“дарламаны йзгертеміз, осыны ескеру Їшін?

Н±с›аулы›. Жа“дай Їш тЇрлі болады: негізгі, тЇсініктеме іші, жол іші.

Паскальді жЇзеге асыру Їшін та“ыда бір мЇмкіндік бар – б±л тЇрлердіЈ тЇсініктемесі ; (here i is increased by 1).

Сонымен ›оса жабыл“ан жа›ша, ашыл“ан жа›ша“а сЩйкес келе керек ({ ... *) р±›сат етілмейді). Осындай тЇсініктемені ›алай жоямыз?

Ба›ылау с±ра›тары
1. љ±рылымды› синтездіЈ ма›саты неде?

2. љ±рылымды› синтездіЈ негізгі кезеЈдерін атап шы›?

3. ЖадыныЈ ›андай элементтер тЇрін білесіндер?

14 -15 зертханалы› ж±мыс. LL(1)-грамматикасы Їшін рекурсивті тЇсі Щдісімен синтаксистік талдау.

Ма›саты: Студентерді ба“дарламаны кезеЈмен ›±ру“а Їйрету
3.1 љыс›аша теориялы› мЩліметтер

Терминалданба“ан дЇкендік танушылар ж±мысыныЈ модельденуі реттіліктіЈ бастауыш жай-кЇйден соЈ“ы жай-кЇйге ауысуын іздеумен байланысты. Іздеу жеке-жеке ›адамдардан т±рады.

ЖЩне олардыЈ Щрбіреуі сЩтсіздікке жЩне бастап›ы жай-кЇйге Щкелуі мЇмкін. Б±ндай іздеу уа›ытты кйпалатынды›тан тЩжірибеде ›айтымсыз ж±мыс істейтін детерминалдан“ан танушыларды ›олданады. Б±л танушылар -тілдердіЈ шектеулі кластарын “ана ›олданыс›а жібереді, біра› олар ба“дарламалау тілдерініЈ барлы› синтаксистік жа›тарын кйрсетеді.

Танушыларды азаймалы жЩне йрмелі деп екі категория“а бйлуге болады.

Азаймалы танушылар ережелерді жо“арыдан тймен йЈдейді, я“ни жо“ары ережелерді тйменгілерден б±рын. Ал б±л уа›ытта кіріс анализаторлары тймендегі ережелерді жо“арыда“ылардан б±рын ›олданады. Детерминалдан“ан автоматтардыЈ мЇмкіндіктері мен олардыЈ т±р“ызылу тЩсілдерін кйрсету Їшін б±л бйлімде тЇріндегі грамматикалар тудыратын азаймалы танушылар ›арастырылады.  

  атауы Left сйзінен шы››ан, себебі анализатор кіріс шынжырын солдан – оЈ“а ›арай кйреді. ТЩжірибеде кйбінесе грамматика класы ›олданылады. Олар Їшін а“ымды позицияда орналас›ан детерминалдан“ан бір кіріс символды танушылар ж±мыс істейді. О›удыЈ бірінші ›адамы ретінде азаймалы танушылардыЈ грамматика кластары ішіндегі бір реттілікті ›араймыз.

Бйлінген ауыспалылар.

љ±рамында жою ережелері жо› мЩнмЩтінді-бос грамматика тймендегі келесі екі шартты орындаса “ана бйлінген немесе жай деп аталады: 

1. 
   Шр ереженіЈ оЈ жа“ы терминалмен басталса.
   
2. 
   Егер екі ереженіЈ сол жа“ы бірдей болса, онда б±л ережелердіЈ оЈ жа“ы тЇрлі терминалды› символдармен басталуы керек.
   

бйлек грамматика болып келеді, (1) и (2) жа“дайы орындалуда.

Бас›а жа›тан ал“анда, грамматика

бйлек грамматика болмайды , себебі (2) ережеде шарт б±зылады (1), ал ережесінде (3) жЩне (4) - шарт (2).

Бйлек грамматиканыЈ негізгі ›асиеті болып, олардыЈ Щр›айсысынан детерминалды тймен тЇсетін айырылымдарын ›±ру“а болады.

 

Мысалы

Ханой м±нараларында“ы есепте са›иналардыЈ ›оз“алу бірізділігін табу Їшін рекурсивті емес ба“дарламаны жазвЈвз.

Шешімі. Рекурсивті ба“дарламаны еске тЇсірейік, -ді ауыстырып ›оятын жо“ар“ы са›иналары с нен :
procedure move(i,m,n: integer);

| var s: integer;

begin

| if i = 1 then begin

| end else begin

| | s:=6-m-n; {s – Їшінші йзек: нймірлер сомасы 6 теЈ}

| | move (i-1, m, s);

| | writeln ('›адам жасау ', m, '->', n);

| | move (i-1, s, n);

| end;

end;

Б±л Їшін ›алтарыл“ан стек есептерін жасайы›.ОлардыЈ элементтері Їштіліктер болып келеді.Шр Їштілік тапсырыс ретінде интерпретациаланады "жо“ар“ы дисктерін -ші йзектен -ге ауыстырылсын" . Тапсырыстар олардыЈ орындалу талаптарына сЩйкес жасал“ан: еЈ жедел – стек биіктігі.Мынадай ба“дарлама аламыз:

begin

| стек›а Їштілікті ›ою

| {инвариант: стекта“ы тапсырыстарды орындау ›алды}

| while стек непуст do begin

| | жо“ар“ы элементті жою,оны

| | if j = 1 then begin ауыстыру

| | | writeln ('›адам жасау', p, '->', q);

| | end else begin

| | | s:=6-p-q;

| | | {s – Їшінші йзек: номерлер сомасы 6 теЈ}

| | | стек›а Їштерді ›ою , <1,p,q>,

| | end;

end;
(еЈ бірінші стекке Їш ›ойылады, оны соЈ“ы кезде орындау керек).

Стек Їштіліктері жеке стектері ретінде іске асады. (Сонымен ›оса, паскальдіЈ арнайы тЇрі бар, оны "жазылу" деп атайды).

Тапсырма 1

(А.К.Звонкин Анджея Лисовскиге хабарлады). Ханой м±наралары туралы есептерде рекурсивті емес алгоритмдер бар.

ОлардыЈ бірі: ›ондыру йзектері ( ауыстырулардан емес) барлы› йзектер кезек бойынша болу керек . Келесі ереже: кезекпен еЈ аз са›иналарды жЩне еЈ аз емес са›иналарды ауыстыру,сонымен еЈ азын шеЈбер бойнша.
Тапсырма 2

Рекурсия орнына стекті ›олдану. Толы› санныЈ онды› басылымныЈ рекурсивті ба“дарламасында тапсырмалар кейінге ›алдырыл“ан.

Екілік б±та› тйбелерініЈ барлы“ын жазатын рекурсивті емес ба“дарламаны жазыЈыз.

Не йзгереді, егерде б±та›тын екілік тйбелерін жазбаса›, біра›та оныЈ саныЈ есептесек?

6 мЇмкіндігі бар тЩртіптер Їшін кей жеЈілдіктер болуы мЇмкін, екі тЇрдегі стек элементтерінде керек емес са›талымдарды жасайды. Кейбіреулерін кйрсетейік.

Ескерту. Б±та›тын барлы› тйбелерін жазуда“ы бас›а ба“дарламасын б±та›ты айналу ба“дарламасы негізінде ›±ру“а болады (тиісті тарауда ›арастырыл“ан) Онда "тймен" командасы орындалады. Енді барлы› тйбелер тізімін тЇбірден а“ымда“ы тйбеге бару жолын са›тау керек Сонымен ›оса графта“ы алгоритмдар туралы тараудан ›араЈыз.
Тапсырма 6

1 – толы› сандар болсын. жиымын ›±растыру керек, ..., , ол Їшін сондай сандар болу керек.

Ескерту. сандар арасында теЈ болуы мЇмкін. Шр толы› сан ›анша рет кірсе, да кіру керек.

Шешімі. Санау“а онай, мен сандары жиымыныЈ бастап›ы жЩне соЈ“ы ма“ынасын білдіреді. Талаптар " жЩне бір сандарды талап етеді" кйре т±ра орындалады, егерде элементтерініЈ орынын ауыстыру процесімен шектелсек.

{ x жиымыныЈ k аз элементтері йз орындарында орналас›ан}

while k <> n do begin

| s := k + 1; t := k + 1;

| {x[s] - арасында еЈ азы... x[k+1] x[t] }

| while t<>n do begin

| | t := t + 1;

| | if x[t] < x[s] then begin

| | | s := t;

| | end;

| {x[s] – еЈ аз x[k+1]..x[n] }

| ... ауыстыру x[s] и x[k+1];

| k := k + 1;

end;
2 Инвариантты ›олданатын, с±рыптау есебіне бас›а шешім беру керек. {первые элементтін біріншісі реттелген: }

Ба›ылау с±ра›тары
1 Рекурсивті емес ба“дарламаны ›алай ›±ру керек?

2 Не йзгереді, егер де екілік б±та›тын тйбесін баспаса, ал тек ›ана оныЈ саныЈ санаса?

1. 
   Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1990
   
2. 
   Грис Д. Наука программирования. М.:Мир. 1984
   
3. 
   Дейкстра Э. Дисциплина программирования. М.: Мир, 1978
   
4. 
   Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. – Новосибирск: НГУ, 1995.
   
5. 
   Лавров С. Программирование. Математические основы, средства, теории. Санкт-Петербург. БХВ-Петербург, 2001.
   
6. 
   Лисков Б., Дж.Гатэг. Использование абстракций и спецификаций при разработке программ.
   
7. 
   Льюс Ф. Д.Розенкранц. Р.Стирнз. Теоретические основы проектирования компиляторов. М.: Мир, 1984
   
8. 
   Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1986
   
9. 
   Языки и автоматы. Сб.переводов. М.:Мир, 1979.
   

1. 
   Агафонов В.Н. Синтаксический анализ языков программирования. Уч.пособие, Новосибирск, НГУ, 1981. 91с.
   
2. 
   Ахо А., Дж.Хопкрофт, Дж.Ульман. Построение и анализ вычислительных алгоритмов – М: Мир, 1979.
   
3. 
   Братчиков И.Л. Синтаксис языков программирования. М.: Наука, 1975. 232с.
   
4. 
   Гинзбург С. Математическая теория контексно-свободных языков. М.: Мир,, 1970. 326с.
   
5. 
   Гладкий А.В. Формальные грамматики и языки. М.: Наука, 1973. 368с.
   
6. 
   Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975. 544с.
   
7. 
   Кнут Д. Искусство программирования для ЭВМ. В 3 томах. –м.: Мир, 1976
   
8. 
   Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ – М:МЦНМО, 1999.