«Алгоритм жЩне оныЈ кЇрделілігі» пшнін ољыту-шдістемелік кешен

Черч тезисі

Бйлшекті рекурсивті функция ±“ымы есептелетін бйлшекті функция интуитивті ±“ымыныЈ “ылымы эквиваленті бола алады.

Рекурсивті функция ±“ымы ›атаЈ. Сонды›тан кЩдімгі математикалы› техника есепті шешетін функция рекурсивті болуы мЇмкін емес деп дЩлелдейді.

Интуитивті есептелетін функция ±“ымы ›атаЈ емес математикалы› ±“ым. Біра› ол бйлшекті рекурсивті функция – ›атаЈ математикалы› ±“ыммен байланысады.

1. 
   Есептелетін функция деген не?
   
2. 
   Рекурсияны ›алай тЇсінесіз?
   
3. 
   Черч тезисініЈ ма“ынасы?
   

°сынылатын Щдебиеттер

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

1. 
   есептеу процесі ±“ымы
   
2. 
   алгоритм кЇрделілігі
   
3. 
   алгоритмніЈ уа›ытша кЇрделілігі
   
4. 
   алгоритмніЈ теориялы› кЇрделілігі
   

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

t- уа›ыт орындаушы – машинадан тЩуелді болса, алгоритмніЈ кЇрделілігі k-элементарлы Щрекеттер тізбегініЈ санынан тЩуелді.

А алгоритмі бар болсын. О“ан деректерді йЈдеу кйлемін кйрсететін а параметрі табылсын. Оны (а) – есептіЈ йлшемі дейді. Т ар›ылы алгоритмніЈ орындалу уа›ытын белгілесе, / -ар›ылы Щлдебір n-нан тЩуелді функцияны белгілейік.

Аны›тама. T(n) алгоритмініЈ йсу реті f(n) бар, немесе бас›аша, алгоритмніЈ теориялы› кЇрделілігі O^*(f(n)) бар болады, егер c₁, c₂>0 т±ра›тылары жЩне барлы› n<=n₀ Їшін

c₁ f(n)2f(n) шарты орындалатындай n₀ саны табылса. М±нда“ы f(n) функциясы еЈ болма“анда n<=n₀ Їшін теріс емес болуы керек. Егер T(n) Їшін T(n)<=cf(n) шарты орындалса, онда алгоритмніЈ теориялы› кЇрделілігі O(n) болады. (n-нен Їлкен «0» деп о›ылады.).

Шама дегеніміз есепті шы“ару барысында ›олданылатын белгілеулер. Олар 3 топ›а бйлінеді:

1. 
   аргументтер – енетін шамалар
   
2. 
   аралы› шамалар
   
3. 
   нЩтижелер – шы“атын шамалар
   

Берілген информацияны ал“аш›ы информация дейді.

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

АлгоритмніЈ орындалу процесінде алынатын йЈделген информацияларды са›тау“а арнал“ан шамаларды шы“атын шамалар деп атайды.

Енетін шамалар“а да, шы“атын шамалар“а дажатпайтын алгоритмді орындау процесінде аралы› мЩндерді са›тау“а арнал“ан шамаларда аралы› шамалар дейді.

Шамалар 2 бйліктен т±рады:

1. 
   шаманыЈ аты – белгіленуі йзгермейді
   
2. 
   шаманыЈ мЩні – йзгеріп отырады
   

Шамалар программасында“ы ›ызметіне ›арай:

1. 
   т±ра›ты шамалар
   
2. 
   айнымалы шамалар
   

Алгоритмді орындау процесінде мЩндері йзгеріп отыратын шамаларды айнымалы шамалар дейді.

Шамалар алгоритмде ›ызметіне ›арай бірнеше болып бйлінеді:

1. 
   натурал
   
2. 
   бЇтін
   
3. 
   на›ты
   
4. 
   литерлік
   

изін тексеру с±ра›тары

1. 
   Есептеу процесі деген не?
   
2. 
   алгоритм кЇрделілігін ›алай тЇсінесіз?
   
3. 
   алгоритмніЈ уа›ытша кЇрделілігі ›ай кезде бай›алады?
   
4. 
   алгоритмніЈ теориялы› кЇрделілігі деген не?
   

°сынылатын Щдебиеттер

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

1. 
   алгоритмніЈ итерациялы› ±“ымы
   
2. 
   реттелмеген массивте біртіндеп іздеу алгоритмі
   
3. 
   реттелген массивте бинарлы іздеу алгоритмі
   
4. 
   с±рыптау – деректерді йЈдеудіЈ жаЈа процесі.
   
5. 
   “кйпіршіту” Щдісімен с±рыптау
   
6. 
   “сызы›ты” с±рыптау
   
7. 
   “бинарлы” с±рыптау
   

Математикада тізбектер элементтері Щр тЇрлі индекспен берілетін бір “ана Щріппен белгіленеді. немесе i= 1, n м±ндай тізбектерді са›тау Їшін таблица ›±ру тиімді. Сонды›тан оларды таблицалы› шама деп атайды. Алгоритмдік тілде таблицалы› шама былай сипатталады:

Мысалы:

Таблицалы› шаманыЈ индексі біреу немесе кйп болуы мЇмкін. Бір индекесті таблицалы› шамалар векторлар, 2- йлшемді немесе индексті таблицалы› шамалар матрицалар деп аталады. Кейде тйртб±рышты таблицалы› шамалар дейді.

i = 1

Щзір i<=n

ц. б.

S = S + x[i]

ц. с.

Алгоритмдік тілде бір индексті таблицалы› шамаларды бір йлшемді массив немесе векторлар деп атайды.

Егер таблицалы› шама 2 индексті болса, онда екі йлшемді массив немесе матрица деп атайды.

Матрица бірнеше жол жЩне бірнеше ба“аннан т±ратын реттелген а›парат жиыны. ОныЈ элементтері сан, символ, йрнек болуы мЇмкін. МатрицаныЈ бірінші индексі, оныЈ жол санын, екінші идексі ба“ан санын аны›тайды. Ба“ан жЩне жол индексініЈ ›иылысуы матрицаныЈ элементініЈ адресін береді. Матрица индексі тік жа›ша“а алынады (A[2, 4]).

Екі йлшемді массивті енгізу ерекшеліктері.

1. Массив элементтерін жол бойымен енгізу.

...

j:=1 ден M – “а дейін

b[і ,j] – ді енгіз

...

...

j:=1 ден М – “а дейін

ц. б.

і=1 ден N – “а дейін

b[i,j] – ді енгізу

ц. с.

ц. с.

і = 1 ден N – “а дейін

ц. б.

j= 1 ден N – “а дейін

а[i,j] –ді енгізу;

b[i,j] – ді енгізу;

ц.с.

S:=0;

ц.б.

ц.с.

5. Екі массив элементтерін ›осу

i=1ден N-“а дейін

ц.б.

ц.с.

i=1 ден N-“а дейін

ц.б.

j=1 ден N- “а дейін

С[i,j]:=a[i,j]+b[i,j]

ц.с.

ц.с.
6. i-жол элементтерін ›осу

j:=1 ден N-“а дейін

ц.б.

S:=S+b[i,j]

i=1 ден N-“а дейін

ц.б

S:=0

S:=S+b [i,j]

D[i]=S

8. Матрица элементтерін транспонирлеу жолды ба“анмен, ба“анды жолмен ауыстыру.

ц.б

ц.б

ц.с

егер квадрат матрица болса:

а_12-ні р-“а аламыз, а₂₁-ді а₁₂-ніЈ орнына ›оямыз, а₂₁-ніЈ орнына р-дан ›оямыз, т.с.с., сонда:

i:=1 ден N-1 ге дейін

ц.б.

ц.б.

a[I,j]=a[j,i];

a[j,i]=p;

ц.с.

ц.б

j:=1 ден М-“а дейін

ц.б.

S:=S+a [i,j] + b[j]

C[i]:=S

A(NXK) ; B(KXM)

a = b=

ц.б

ц.б

L=1 ден k-“а дейін

Ц. б

S:= S+a[i, l] *b[l,j]

С[i,j]=S

ц.с

ц.с

S=0+

i=1 j=1 l=2

S=S+a

i=1 j=1 l=3 i=2 j=1 l=1

i=1 j=2 l=1 i=2 j=1 l=2

i=1 j=2 l=2 i=2 j=1 l=3

i=1 j=2 l=3 i=2 j=2 l=1

i=2 j=2 l=2

i=2 j=2 l=3

A(N) – массивтен -шы элементті йшіру.

N:=N-1

i=k –дан N-“а дейін

a[i]:=a[i+1]

ц.с.


, я“ни
i=2 i=3



болады.
Итерациялы› процесті ±йымдастыру

Аргументті сызы›ты алмастыру ар›ылы кйпмЇшелікті есептеу
полином берілсін. алмастыру жасау ар›ылы кйпмЇшелігін аламыз.

Мысалы:

т/к

Мысалы: 10 депутаттыЈ 5 – уін таЈдау Щдісі ›анша?

i=10-5+1=6 дан i=10 дейін i – ді кйбейту.

1.a,b,c[i] енгіз

2. d₀ – ді табамыз:

I-этап

3. d_1,d₂ – ні табамыз:

Шйтпесе ц.с

Мектептегі Щр кластыЈ о›ушылар саны берілсін. Мектептегі жалпы о›ушылар санын табу керек.

Мектепте Щр класс а, б, в деп бйлінетінін ескерсек 2 йлшемді массив пайда болады.

кл [i, j] кл [1, 1] кл [2, 1] кл [3, 3]

кл [1, 2] кл [2, 2] кл [3, 3] . . .

кл [1, 3] кл [2, 3] кл [3, 3]

кл [i, j] =

S:=0

j:=1

S:=S+ кл [i, j]

j:=j+1

цикл соЈы
i:=i+1

цикл соЈы

СоЈы
4. реттелмеген массивте біртіндеп іздеу алгоритмі

Деректерге кйп ›олданылатын операциялардыЈ бірі – іздеу. Іздеу мЩселесі ЭЕМ-ніЈ дамуыныЈ ал“аш›ы жылдарынан бастап басты мЩселелердіЈ бірі болды. Аз кйлемді ішкі жады мен тізбекті – лента типті ›±рыл“ыларда са›тал“ан деректердіЈ арасынан керекті а›паратты іздеу ішкі жадыныЈ кеЈейтілуін талап етті.

Іздеу операциясы екі нЩтиже береді:

1. сЩтті іздеу

2. сЩтсіз іздеу.

Іздеу сЩтті болса, ізделінді элементтіЈ орналас›ан жері табылады, я“ни ол массивтіЈ элементініЈ номерін береді.

ІздеудіЈ бірнеше Щдістері бар:

1. 
   белгілі бір элементті іздеу
   
2. 
   кез келген элементті іздеу т.б.
   

Екі жиын берілсін: жЩне . А жиыны В жиыныныЈ ішкі жиыны болатын, болмайтынын аны›тау керек болсын.

Б±л есепті шешу Їшін екі Щдісті ›олдану“а болады:

1. Элементтер беттескенге дейін Щрбір а_i элементтерін сЩйкес b_i элементтерімен салыстыру

2. А жЩне В жиындарын реттеп алып, екі жиынныЈ элементтерін бір бірімен беттескенше салыстыру

ІздеудіЈ бірінші н±с›асында n, m-сандары аз бол“анда тиімді, ал олар йссе, онда Щ-ші Щдіс тиімді болады. АлгоритмніЈ негізгі мазм±ны оныЈ кЇрделілігінде.

АлгоритмніЈ кЇрделілігі итерация ±“ымымен байланысты.

Аны›тама. Итерация дегеніміз алгоритмді енгізілетін деректерге ›олдану операциясы. Шрбір келесі итерацияныЈ бастап›ы берілгендері болып оныЈ алдында“ы итерацияда аны›тал“ан мЩндер алынады.

Егер массив реттелмеген болса, онда біртіндеп іздеу Щдісін ›олдану“а болады:

A[1..n] массиві берілсін. P-“а теЈ элементті іздеу керек болсын.

1. i=1; бол“анда бастаймыз

2. егер a_i=p шарты орындалса, онда іздеу сЩтті ая›талады

3. Щйтпесе I:=i+1 деп келесі элементке кйшеміз

4. егер i<=n болса, онда 2-ші пунктке кйшеміз, ЩйтпесеЩздеу сЩтсіз ая›талады.

Б±л алгоритмніЈ кЇрделілігі n-1-ге теЈ, себебі элементтерді р-мен салыстыру саны сонша.

Егер массив реттелген болса, онда бинарлы-екілік іздеуді ›олдану“а болады. Оны логарифмдік іздеу немесе дихотомия Щдісі дейді.

М±нда екі кйрсеткіш пайдаланады: l=1 массивтіЈ ал“аш›ы элементін кйрсетеді, u=n массивтіЈ соЈ“ы элементін кйретеді:

1. l=1; u=n; болады

2. егер ul<=k<=a_u шартыныЈ орындалатынын білеміз. I=(l+u) div 2 деп аламыз , сонда I массивтіЈ ортасын кйрсетеді.

3. Егер ki болса, онда 4-ші пунктке кйшеді, егер k>a_i болса, онда 5-ші пунктке кйшеді, егер k=a_i болса, онда іздеу сЩтті ая›талады.

4. u=i-1 деп орналастырамыз жЩне 2-ші пунктке кйшеміз

5. l=i+1 деп орналастырамыз жЩне 2-ші пунктке кйшеміз.

Б±л алгоритмде кЇрделілік дЩрежесі -ге теЈ болады.
Реттеу, с±рыптау алгоритмі

Деректерге кйп ›олданылатын амалдардыЈ бірі – с±рыптау.

С±рыптау дегеніміз – массив элементтерін белгілі бір ережені са›тайтындай етіп, реттеп орналастыру.

С±рыптау ішкі жЩне сырт›ы деп бйлінеді. Сырт›ы с±рыптау“а сырт›ы жадыда“ы деректерді с±рыптау жатады. Ал ішкі с±рыптау“а ішкі жады“а деректерді реттеп орналастыру жатады.

Ішкі с±рыптау бірнеше Щдіспен орындалады:

1. Кйпіршіту Щдісі

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

a₁, a₂, a₃, … , a_n тізбегі берілген. Элементтерін йсу реті бойынша реттеу керек.

aрг n, a

нЩт a

басы бЇт i, на› Б

Щзір i≤n-1

Б:=a[i];

a[i+1]:=Б

i:=1;

бітті

ц. с.

а – ны шы“ару.

СоЈы.

МассивтіЈ ішінен еЈ Їлкен элемент табылады. Ол элемент р-шы орында т±рсын. Сол элементті n-ші орында“ы элементпен салыстырады. Егер n<>p болса, онда n-ші орында орналас›ан элементпен орындарын ауыстырады. Шрі ›арай ›ал“ан реттелмеген элементтердіЈ ішінен та“ы еЈ Їлкен элемент табылады да, ол (n-1)-ші элементпен салыстырылады, егер еЈ Їлкен элемент (n-1)-ші элементтен Їлкен болса, орнында ›алады да, болмаса орындарын ауыстырады. Осы процесс барлы› элементтерге ›олданылып шы“ады.

Алгоритмі келесідей болады:

Белгілеулер: a[1..n] –берілген массив болсын, r – массивтіЈ реттелмеген элементтерініЈ саны.

1. R=n болсын.

2. Max=max{a[1..r]} табамыз.

3. Max<>r жЩне a[max]<>a[r] болса, онда a{max] элементі мен a[r] элементі орындарын ауыстырады

4. Щйтпесе R=r-1 деп реттелмеген келесі элементтерге кйшеміз. Ал“аш›ы r элементтер – реттелмеген элементтерді ›±райды, ал соЈ“ы n-r элементтер йсуі бойынша реттеледі.

5. Егер r=1 болса, онда реттеу ая›талады, Щйтпесе 2-ші пунктке кйшеді.
3. Кірістіру ар›ылы с±рыптау.

Алдында ›арастырыл“ан кйпіршіту жЩне сызы›ты с±рыптау Щдістері кемімелі ›адаммен с±рыптау“а жатады. Шынында да, Щрбір с±рыптау итерациясын орында“ан сайын реттелмеген элементтер саны 1-ге кеміп отырады.

Ал кірістіру ар›ылы с±рыптау йзгеше принциппен орындалады:

МассивтіЈ ал“аш›ы 2 элементі реттеледі де реттелген s жиынын ›±райды. Сосын келесі екі элемент реттеледі де сол жа“ынан Їлкен элемент, оЈ жа“ынан кіші элемент орналаспайтындай етіп s –реттелген жиын“а кірістіріліп отырады. S жиын“а кірістірілетін элементтіЈ орны дихотомия Щдісімен аны›талады.

Кірістіру Щдісінде келесі ба“алаулар д±рыс:

Салыстыру саны=1+2+[log₂3]+1+[log₂4]+1+…+[log₂(n-1)]+1=(n-1)+log₂(n-1)!=nlog₂n;

Меншіктеу саны: min=0; max=3+4+5+…+n+1=(n+4)(n-1)/2

КЇрделілігі: O(n²)-меншіктеу саны бойынша, O(nlog₂n)-салыстыру саны бойынша.

1. 
   Реттелмеген массивте біртіндеп іздеу алгоритмі ›алай жЇреді?
   
2. 
   Реттелген массивте бинарлы іздеу алгоритмі ›алай жЇреді?
   
3. 
   С±рыптаудыЈ ›андай Щдістері бар?
   

°сынылатын Щдебиеттер

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

1. 
   негізгі тЇсініктер
   
2. 
   а›паратты са›тау
   
3. 
   деректер структурасыныЈ классификациясы
   
4. 
   деректер структурасына ›олданылатын амалдар
   
5. 
   программалау технологиясы
   

Деректер структурасы мен алгоритмдер программаныЈ негізгі ›±раушысы болып табылады. КомпьютердіЈ йзі сол деректердіЈ структурасы мен алгоритмдерден т±рады. Орнатыл“ан деректердіЈ структурасы екілік шамалар са›тал“ан жады сйзі жЩне регистрлер тЇрінде кйрінеді. АппаратураныЈ конструкциясына бекітілген алгоритмдер – орандау“а жататын, жады“а енгізілген деректерден команда – б±йры› тЇрінде ойластырыл“ан электронды логикалы› тізбекке айналдырыл“ан ›атаЈ ережелер. Сонды›тан кез келген компьютердіЈ ж±мыс негізінде тек ›ана деректердіЈ бір тЇрімен белгілі бір биттермен немесе екілік цифрлармен операцияларды орындауды білу жатады. Осы деректермен компьютер тек орталы› процессордыЈ б±йры›тар жЇйесімен аны›талатын, сЩйкес йзгермейтін алгоритмдердіЈ жиынымен ж±мыс істейді.

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

Кейбір программалау тілдерінде деректердіЈ типтері компиляторда аны›талса, кейбіреуінде типті аны›тап кйрсету керек болады. Программада деректердіЈ мЩндері ›анша ›ажет болса, сонша йзгеріп, ал типі йзгеріссіз ›алуы керек.