ПоәК 14 07 20. 01/03-2013 03. 09. 2013 ж. №1 басылым

Черч тезисі

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

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

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

1. 
   Есептелетін функция деген не?
   
2. 
   Рекурсияны қалай түсінесіз?
   
3. 
   Черч тезисінің мағынасы?
   

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

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

4. 
   есептеу процесі ұғымы
   
5. 
   алгоритм күрделілігі
   
6. 
   алгоритмнің уақытша күрделілігі
   
7. 
   алгоритмнің теориялық күрделілігі
   

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

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.
   

8. 
   алгоритмнің итерациялық ұғымы
   
9. 
   реттелмеген массивте біртіндеп іздеу алгоритмі
   
10. 
    реттелген массивте бинарлы іздеу алгоритмі
    
11. 
    сұрыптау – деректерді өңдеудің жаңа процесі.
    
12. 
    “көпіршіту” әдісімен сұрыптау
    
13. 
    “сызықты” сұрыптау
    
14. 
    “бинарлы” сұрыптау
    

Мысалы:

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