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



бет12/54
Дата15.09.2017
өлшемі4,87 Mb.
#32890
1   ...   8   9   10   11   12   13   14   15   ...   54

Черч тезисі


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

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

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

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


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

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

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

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

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



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

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

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

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

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


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

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

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

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

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

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

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



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

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

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

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

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

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

c1 f(n)2f(n) шарты орындалатындай n0 саны табылса. Мұндағы f(n) функциясы ең болмағанда n<=n0 үшін теріс емес болуы керек. Егер 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.


5-тақырып: «Іздеу алгоритмі. Реттеу немесе сұрыптау алгоритмі»

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

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

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

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

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

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

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

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


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

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

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

Мысалы:


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

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



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


Достарыңызбен бөлісу:
1   ...   8   9   10   11   12   13   14   15   ...   54




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет