Черч тезисі

Алгоритмдік – есептелетін бөлшекті сандық функциялар класы барлық бөлшекті рекурсивті функциялар класымен беттеседі.

Бөлшекті рекурсивті функция ұғымы есептелетін бөлшекті функция интуитивті ұғымының ғылымы эквиваленті бола алады.

Рекурсивті функция ұғымы қатаң. Сондықтан кәдімгі математикалық техника есепті шешетін функция рекурсивті болуы мүмкін емес деп дәлелдейді.

Интуитивті есептелетін функция ұғымы қатаң емес математикалық ұғым. Бірақ ол бөлшекті рекурсивті функция – қатаң математикалық ұғыммен байланысады.

Өзін тексеру сұрақтары

1. Есептелетін функция деген не?

2. Рекурсияны қалай түсінесіз?

3. Черч тезисінің мағынасы?

Ұсынылатын әдебиеттер

1. Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.

2. Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.

3. Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.

4. Острейковский В.А. Информатика, Москва, 2000 г.

5. Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.

4-тақырып: «Алгоритм күрделілігі ұғымы. Шамалар ұғымы. Алгоритмдік тіл ұғымы»

Дәріс жоспары:

4. есептеу процесі ұғымы

5. алгоритм күрделілігі

6. алгоритмнің уақытша күрделілігі

7. алгоритмнің теориялық күрделілігі

Бір есепті шешу үшін тек жалғыз алгоритм емес бірнеше алгоритм құруға болатыны белгілі. Сондықтан есепті шешу үшін барлық алгоритмдердің ішінен ең тиімдісін құру қажет болады. Алгоритмді орындаушы-адам болған жағдайда алгоритмнің күрделігі логикамен байланысты, себебі, есепке құрылған алгоритмнің ішінде күрделі структура болса, одан қандай нәтиже алынатынын алдын ала болжау мүмкін емес, тек оны орындап болған соң нәтиженің дұрыстығы, бұрыстығы зерттеледі, ал орындаушы-машина болса, оған алгоритмнің структурасы қаншалықты күрделі екендігі әсер етпейді, себебі машина үшін белгілі нұсқаулар берілді, ол соны орындайды, мысалы: машинаға бәрібір – қосуды орындап жатыр ма азайтуды орындап жатыр ма, әйтеуір техникалық жабдығы дұрыс болса, алдына қойған проблема шешіледі. Немесе алгоритмді жазғанда қайталану операторын қолданбай ақ күрделі есепті шешудің өте көп қадамнан тұратын тізбекті структурасын қолдануға болады, ал машинаға бәрібір- циклды қолдандың ба, тізбекті қолдандың ба, бірақ есептеу уақыты, алынған нәтиже адамды қанағаттандырмауы мүмкін, сондықтан алгоритмнің күрделілігі деген ұғым қажеттілігі шығады.

Анықтама. Алгоритмнен туындаған есептеу процесі деп осы алгоритмді орындау барысында өткен тізбекті қадамдар алгоритмін айтады.

Анықтама. Алгоритмнің күрделілігі – осы алгоритмді есептеу процесінде қолданылған элементарлы қадамдар саны.

Анықтама. Алгоритмнің уақытша күрделілігі – оны орындауға қажетті Т уақыты. Ол элементарлы әрекеттер саны мен оны орындауға кеткен орташа уақыттың көбейтіндісіне тең:T=kt.

t- уақыт орындаушы – машинадан тәуелді болса, алгоритмнің күрделілігі k-элементарлы әрекеттер тізбегінің санынан тәуелді.

А алгоритмі бар болсын. Оған деректерді өңдеу көлемін көрсететін а параметрі табылсын. Оны (а) – есептің өлшемі дейді. Т арқылы алгоритмнің орындалу уақытын белгілесе, / -арқылы әлдебір n-нан тәуелді функцияны белгілейік.

Анықтама. T(n) алгоритмінің өсу реті f(n) бар, немесе басқаша, алгоритмнің теориялық күрделілігі O^*(f(n)) бар болады, егер c₁, c₂>0 тұрақтылары және барлық n<=n₀үшін

c₁f(n)<T(n)<c₂f(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-тақырып: «Іздеу алгоритмі. Реттеу немесе сұрыптау алгоритмі»

Дәріс жоспары:

8. алгоритмнің итерациялық ұғымы

9. реттелмеген массивте біртіндеп іздеу алгоритмі

10. реттелген массивте бинарлы іздеу алгоритмі

11. сұрыптау – деректерді өңдеудің жаңа процесі.

12. “көпіршіту” әдісімен сұрыптау

13. “сызықты” сұрыптау

14. “бинарлы” сұрыптау

1. таблицалық шамалардың түрлері, оған қолданылатын амалдар

Математикада тізбектер элементтері әр түрлі индекспен берілетін бір ғана әріппен белгіленеді. немесе i= 1, n мұндай тізбектерді сақтау үшін таблица құру тиімді. Сондықтан оларды таблицалық шама деп атайды. Алгоритмдік тілде таблицалық шама былай сипатталады:

Элементтер типі. таб таблицалық шаманың аты [өлшемі]

Мысалы:

бүт. таб класс [1:11]

Таблицалық шаманың индексі біреу немесе көп болуы мүмкін. Бір индекесті таблицалық шамалар векторлар, 2- өлшемді немесе индексті таблицалық шамалар матрицалар деп аталады. Кейде төртбұрышты таблицалық шамалар дейді.

есебін шығару

алг A1 (бүт. n, нақ. таб. x[1..n], нақ. S )

арг n, x

нәт S

басыбүт

i = 1

S = 0

әзір i<=n

ц. б.

S = S + x[i]

i = i+1

ц. с.

S = S/n

соңы

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

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

Матрица бірнеше жол және бірнеше бағаннан тұратын реттелген ақпарат жиыны. Оның элементтері сан, символ, өрнек болуы мүмкін. Матрицаның бірінші индексі, оның жол санын, екінші идексі баған санын анықтайды. Баған және жол индексінің қиылысуы матрицаның элементінің адресін береді. Матрица индексі тік жақшаға алынады (A[2, 4]).

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

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

...

i:=1 ден N – ға дейін

ц. б.

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

ц . б.

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

ц. с.

...

ц. с.

...

2. Массивті баған бойынша енгізу.

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

ц. б.

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

ц. б.

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

ц. с.

3. Өлшемдері бірдей 2 массивті енгізу

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

ц. б.

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

ц. б.

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

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

ц.с.

4. Матрица элементінің ізін есептеу, яғни S= ді есептеу;

S:=0;

i=1 ден n ға дейін

ц.б.

S:=S+b[i,j]

ц.с.

...

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

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

ц.б.

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

ц.с.

немесе

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

ц.б.

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

ц.б.

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

ц.с.

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

S=0;

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

ц.б.

S:=S+b[i,j]

ц .с

7. Матрица элементтерін жол бойынша қосу

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

ц.б

S:=0

J=1 ден М-ға дейін

ц.б

S:=S+b [i,j]

ц.с

D[i]=S

ц.с

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

i:=1 ден N-ға дейін

ц.б

j:=1 ден M-ға дейін

ц.б

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

ц.с

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

i=1 болғанда

а_12-ні р-ға аламыз, а₂₁-ді а₁₂-нің орнына қоямыз, а₂₁-нің орнына р-дан қоямыз, т.с.с., сонда:

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

ц.б.

j:=i+1 ден N-ға дейін

ц.б.

p=a[I,j];

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

a[j,i]=p;

ц.с.

9. Матрицаны векторға көбейту:

, i=1,n

i:=1 ден N-ға дейін

ц.б

S:=0

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

ц.б.

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

ц.с.

C[i]:=S

ц.с.

10. Матрицаны матрицаға көбейту:

A(NXK) ; B(KXM)

, i=1,N; J=1,M; * ;

a = b=

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

ц.б

j=1 ден М-ға дейін

ц.б

S:=0

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

Ц. б

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

ц.с

С[i,j]=S

ц.с

i=1 j=1 l=1

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

11. Массивтен элементті өшіру:

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]

	а	б	в
1 кл
2 кл
3 кл
. . .	. . .	. . .	. . .
11 кл

кл [i, j] =

алг қосу (бүт таб кл [1:11,1:3], бүт S)

арг кл

нәт S

басы бүт i,j

S:=0

i:=1

әзір i≤11

цикл басы

j:=1

әзір j≤3

цикл басы

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

j:=j+1

цикл соңы

i:=i+1

цикл соңы

Соңы