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

СЩйкес ережені ›олдан“анда, мынаны аламыз:

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

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

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

Шешімі. –нан кйп маршрутта цикл болады, сонды›тан миниумды ±зынды“ынан кем емес маршруттар арасынан іздеу керек.

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

уа›ытында ›аладан екінші ›ала“а барудыЈ жол тйлемініЈ еЈ тймен ба“асын табыЈыз ( деЈгейде).

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

ЕЈ тймен жол тйлемін табыЈыз барлы“ы Їшін уа›ыт ішінде ( –ді деЈгейде).

Барлы› ба“алар теріс емес екені бізге мЩлім. ЕЈ тймен жол тйлемін табыЈыз барлы› Їшін уа›ыт ішінде ( -ді деЈгейде).

Б±л матрицаны шы“ару Їшін матрица жай формула бойынша есептеледі, тек ›ана сома орнына минимум, ал ›осу орнына сома.

Сонымен матрицалардыЈ белгілі тЇрде шы“уы ассоциативті тЇрде болады.

Эквивалент жолыныЈ ›ыс›алы“ы туралы есепте "а›ырсыз деЈгей" матрица ба“асы , тізбектілігінде барлы› элементтер, кейбіреуінен баста“анда,›ыс›а жол ба“асыныЈ ізделетін матрица“а теЈ. (егер теріс циклдар болмаса).

љай элементтен бастап теЈсіздік кепілдігін беруге болады, Алдын“ы есепте?

Шдетте (модифицирлан“ан емес) матрицаларды кйбейту пайдалы бола алады, біра›та матрицалар бас›а болу керек. Барлы› рейстер болмасын (б±рын“ыша), ал кейбіреуі, теЈ ,егер рейс болса жЩне , егер рейс болмаса. матрицасын жасайы› (жай кЇйде) деЈгейіне жЩне оныЈ - шы элементіне ›арайы›.

Тапсырма 9

Дейкстр алгоритмы рейстері мен ›алаларын модифицирлеу Їшін операциялары керек екенін дЩлелдеу керек.

Н±с›аулы›. Шр ›адамда не істеу керек? Минималды ба“ада“ы белгіленбеген ›аланы аны›тау керек жЩне барлы› ›алалар Їшін маршруттары бар ба“аларды тЇзету керек. Егер де бізге ›ай ›ала“а ба“а минималды екеніЈ айтып отырса, онда ›ызметі жеткілікті болатын еді.
Тапсырма 10

С±рыптау алгоритмін ±сынайы›. Іс-Щрекет саны тЩртібінде болсын, аспау керек. Кейбір Їшін жЩне барлы› Їшін.

Біз бір шешімін кйрсетеміз.

Шешім. (›осылу ар›ылы с±рыптау).

саны- толы› оЈ сан. Разобьем массив массивін алайы›, ±зынды“ыныЈ кесіндісіне. ( бірінші, ал сосын жЩне т.б.) СоЈ“ы кесінді толы› болмайды, егер де – -“а бйлінбесе. массивін –реттелген деп атайы, егер де Щр кесінді жеке ал“анда реттелген болса. Шр массив 1- реттелген. Егер де массиві- реттелген болса жЩне , онда ол реттелген.

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

Біріктіру процедурасы при кесінділерді біріктірейік и реттелген кесіндіге ( массивтін бас›а бйліктеріне тиіспей).

Ендеше - реттелген массивті -реттелген массивке тЇрлендіру тймендегідей жЇзеге асады:

t:=0;
{t ›ыс›аша 2k немесе t = n, x[1]..x[t] болып келеді

немесе
b[s0+1]:=x[q0+1];

(C тілін жа›сы кйретіндер ›ыс›артуын ба“алайды немесе .)

Бірінші Щрекет (элементті бірінші кесіндіден алу) бір уа›ытта екі Щрекетті орында“анда шы“уы мЇмкін:

1. 
   бірінші кесінді ая›тал“ан жо› ( );
   
2. 
   екінші кесінді ая›талды () немесе ая›тал“ан жо›, біра›та оныЈ ішінде элемент аз болады (екінші кесіндіге ›ара“анда) и
   

Екінші Щрекет Їшін ±›сас. Сонымен мынаны аламыз

p0 := p; q0 := q; s0 := p;
while (p0 <> q) or (q0 <> r) do begin
| if (p0 < q) and ((q0 = r) or ((q0 < r) and
| | (x[p0+1] <= x[q0+1]))) then begin
| | b [s0+1] := x [p0+1];
| | p0 := p0+1;
| | s0 := s0+1;
| end else begin
| | {(q0 <| | (x[p0+1] > r) and ((p0 = q) or ((p0= x[q0+1])))}
| | b [s0+1] := x [q0+1];
| | q0 := q0 + 1;
| | s0 := s0 + 1;
| end;
end;
(Егерде екі кесінді ая›талма“ан болса онда таЈдалма“ан бірінші элементтері теЈ болып келеді, б±л жа“дайда екі Щрекетті де ›абылдаймыз; ба“дарламада біріншісі таЈдал“ан.)

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

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

1. 
   Алгоритм дегеніміз не?
   
2. 
   С±рыптау алгоритмі дегеніміз не?
   

Формалды› грамматика теориясында 4 тіл тЇрі сЩйкес келетін грамматиканыЈ 4 тЇрі ерекшеленеді. Б±л грамматикалар грамматика ережелеріне шектеу ›ою жолымен аны›талады.

Жалпы тЇр грамматикасы деп айтылатын 0 тЇріндегі грамматикалар тудыру ережелеріне еш›андай шектеу ›оймайды. Кез келген ережесі еркін шынжырынды› кймегімен ›±рылуы мЇмкін.

МЩнмЩтінді – ба“ыныЈ›ылы грамматика деп аталатын 1 тЇріндегі грамматикалар кез келген ережені ›олдану“а жол бермейді.

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

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

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

2 тЇріндегі грамматиканы мЩнмЩтінді – бос жЩне мЩнмЩтінсіз грамматика ( -грамматика немесе грамматика) деп атайды. б±ндай грамматикаларды шы“ару ережесі келесідей болады:

Б±л грамматика шынжыры немесе шынжырыныЈ айналы кйрінісініЈ Щрбіреуі екі бйлігінен т±ратын шынжырдан т±ратын тілді тудырады.

б±нда - б±л бос шынжырсыз жиыны. Б±л грамматика кймегімен мысал“а келесі шынжыр ›±ру“а болады:

3 тЇріндегі грамматика автоматты грамматика ( -грамматика) деп аталады. Б±ндай грамматикаларда шы“ару ережелері келесі тЇрде болады:

Б±л грамматикалар бір тілді тудырады.  

Тіл классификациясы тілді тудыратын грамматика тЇрлеріне сЩйкес ›±рылуы мЇмкін. Бір тіл екі тЇрлі грамматика болатын тЇрлі грамматикалармен берілуі мЇмкін. Сонды›тан тіл тЇрін тЇріндегі грамматика беруі мЇмкін грамматика тЇрімен аны›талады.
Тапсырма 1

Ферзи, бір - бірін со›пайды: б±та› орнын тексеру.

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

Тапсырма 2

ферзидерді шахматты› та›тасында ді - “а ›ой“анда“ы барлы› Щдістерін аны›таныз (олар бір –бірін со›па“ан жа“дайда)

Шешімі. Шр горизонтальнда бір ферзидан т±ру керек. –ны позиция дейміз - ( , Їшін ) ферзилердіЈ тйменгі горизонтында (ферзилар бір-бірін со“уы мЇмкін). Салайы› "б±та› орыны": оныЈ тЇбірі 0-орыны болады, Щр -орынан жо“ары ›арай кйтерілейік - орынына. Б±л орындары ферзилардыЈ -ші горизонталында орналасумен ерекшелінеді.

ОлардыЈ суретте орналасуы б±л ферзидіЈ ›осымша“а сЩйкес екеніЈ кйрсетеді: ферзи сол жа›та орналасса сол жа› орыны деп аталады.

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

Сонды›тан, осы жа“дайды кйргенде біз б±л ба“ытта“ы б±та›тыЈ ›±рылымын то›татамыз.

На›тыра›, -орыныЈ жетімді дейміз, егер жо“ары ферзиді жойса, ›ал“андары бір-бірін со“ады. БіздіЈ ба“дарлама р±›сат етілген орындарды “ана ›арастырады.

Есепті екі бйлікке бйлейік: (1) б±та›ты ерікті айналамыз жЩне (2) б±та›тарды р±›сат етілген орыннан іске асыру.

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

Ол берілген тапсырмаларды орындай біледі:

оЈ“а (кйрші оЈ жа›та“ы тйбеге кйшу)

тймен (бір деЈгейге тймен тЇсу)

жо“ары сол“а

оЈ“а

тймен
Шр команданы сЩйкесінше орындау Їшін "жо“ары бар", "сол жа›та бар", "тймен бар" (соЈ“ы тексеру барлы› жерде тиімді, тЇбірден бас›асы). КйЈіл бйліЈіз, "оЈ“а" командасы тек ›ана "ту“ан а“асына" “ана кйшуге мЇмкіндік береді.

БіздіЈ шахматты› есебін шы“ару Їшін команда ферзи орынында“ы басылым мен тексерісі сЩйкесінше йЈделеді.

Ба“дарламаны ары ›арай д±рыс ›олданудыЈ мынадай аны›тамасы беріледі. РоботтыЈ бір б±та›тын тйбесінде жа“дайын бекітсін.Сол жа“дайда б±та›тын барлы› пара›тары Їш категория“а бйлінеді: Робот Їстінде, Роботтан сол“а ›арай жЩне роботтан оЈ“а ›арай. (ТЇбірден пара››а Роботпен тйбе ар›ылы йтеді, сол“а ›арай б±рылу, о“ан жетпей оЈ“а ›арай б±рылу.) (ОЛ) ар›ылы жа“дайды белгілеймі"Роботтан сол“а ›арай барлы› пара›тар йЈделген ", а (ОЛН) ар›ылы - жа“дайы "барлы› пара›тар сол“а ›арай жЩне Робот Їстінде йЈделген".

Бізге мынадай процедура ›ажет:

| {берілген: (ОЛ), керек: (ОЛН)}

begin

| {инвариант: ОЛ}

| | жо“ары сол“а;

| end

| {ОЛ, Робот пара›та}

| {ОЛН}

берілген: Робот тЇбірде,пара›тары йЈделмеген

керек: Робот тЇбірде, пара›тары йЈделген
{ОЛ}

тірелгенге дейін жо“ары жЩне йЈдеу;

{инвариант: ОЛН}

while тймен бар do begin

| if оЈ жа›та бар then begin {ОЛН, оЈ жа›та бар }

| | оЈ“а;

| | {ОЛ}

| тірелгенге дейін жо“ары жЩне йЈдеу;

| end else begin

| | {ОЛН, оЈ жа›та емес тймен жа›та}

| | тймен;

| end;

{ОЛН, Робот тЇбірде=> барлы› пара›тар йЈделген}

(1) {ОЛ, жо“ары емес} (2) {ОЛ}

жо“ары сол“а йЈдеу

{ОЛН} {ОЛ}

(3) {оЈ жа›та бар, ОЛН} (4) {оЈ жа›та емес ОЛН}

оЈ“а ›арай тймен

{ОЛ} {ОЛН}
Тапсырма 3

Кйрсетілген ба“дарлама ж±мысты ая›тайтыныЈ дЩлелдеу керек (соЈ“ы б±та›тын ›айсысында болсын).

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

Шешімі. – кейбір тйбелер. Сол жа“дайда y тйбесі тйрт категорияныЈ біріне жатады. ТЇбірден у баратын жолды ›арастырайы›. Болуы мЇмкін:

1. 
   (а) –тен тЇбірге баратын жол ( тен тймен);
   
2. 
   (б) -ке баратын жолдан сол“а б±рылу ( -те сол“а ›арай);
   
3. 
   (в) ар›ылы йту( над -тен -“а);
   
4. 
   (г) жолдан оЈ“а -ке б±рылу ( -тен –“а ›арай);
   

(ОНЛ) барлы› тйбелер тймен жЩне сол“а орналас›ан;

(ОНЛН) барлы› тйбелер тймен, сол“а жЩне Їстінде орналас›ан.
Ба“дарлама осындай болады:
procedure тірелгенге дейін жЩне жо“ары;

| {берілген: (ОНЛ), керек: (ОНЛН)}

begin

| {инвариант: ОНЛ}

| |йЈдеу;

| | жо“ары сол“а;

| end

| йЈдеу;

end;
Негізгі алгоритм:

берілді: Робот тЇбірде , ештене йЈделген жо›

керек: Робот тЇбірде, барлы› тйбелер йЈделген

{ОНЛ}

тірелгенге дейін жо“ары жЩне йЈдеу;

while тйменде барdo begin

| if оЈ жа›та барthen begin {ОНЛН, оЈ жа›та бар}

| |оЈ“а;

| | тірелгенге дейін жо“ары жЩне йЈдеу;;

| end else begin

| | {ОЛН,оЈ жа›та емес, тйменнен}

| | тймен;

| end;

{ОНЛН, Робот тЇбірде => барлы› тйбелер йЈделген }