Алгоритом туралы түсінік. Қасиеттері. Есептеу процесі ұғымы. Алгоритм күрделілігі. Алгоритмнің уақытша күрделілігі. Алгоритмнің теориялық күрделілігі

Презентация қосу

СРО №2

Орындаған: Тұрсынова Ақерке Т-
311
ЖОСПАР:
Алгоритом туралы түсінік
Қасиеттері
Есептеу процесі ұғымы
Алгоритм күрделілігі
Алгоритмнің уақытша күрделілігі
Алгоритмнің теориялық күрделілігі
Алгоритм, алгорифм (ағылшынша: algorіthm, algorіsmus — Әл-Хорезмиді ң
атынан шыққан) — бастапқы берілген мәліметтермен бір м әнде
анықталатын нәтиже алу үшін қай амалды (жұмысты) қандай ретпен
орындау қажеттігін белгілейтін есептерді (м әселелерді) шешу
(математикалық есеп-қисаптар орындау, техникалы қ объектілерді жобалау,
ғылыми-зерттеу жұмысын жүргізу т.б.) тәсілдерінің дәл сипаттамасы.
Алгоритм — математика мен кибернетиканың негізгі ұғымдарыны ң бірі.
Агоритмді орындау алгоритмдік процесс деп аталады.
Жалпы Алгоритм деп алдын ала не істеу керек екені д әл к өрсетілген есептеу
процесін айтады. Есептеу процесі қандай болса да ал ғаш қы м әндерден
бастап, сол арқылы толық анықталған қорытынды шыққанша ж үргізіледі.
Алгоритм ұғымының алғышартына алгоритмдік процеспен қатар м үмкін
болатын алғашқы деректер жиынтығының нұсқауы ж әне қорытынды алу ға
байланысты жүргізілген процестің аяқтал ғанды ғын к өрсететін ереже енеді.
Белгілі бір бастапқы деректердің жиынына қолданыл ған Алгоритм тияна қты
қорытындыға келмеуі немесе есептеу барысы ая қталмай то қталуы м үмкін.
Егер есептеу процесі белгілі бір қорытынды алумен ая қталса (не ая қталмай
қалса), онда Алгоритм мүмкін болатын бастап қы деректерге қолданылады (не
қолдануға болмайды) деп ұйғарылады.
Алгоритм — қазіргі математикада, оның ішінде электронды есептеуіш машинада
қолданылатын негізгі ұғымдардың бірі. Белгілі бір теңдеу түбірінің жуық мәнін кез келген
дәлдікпен табу оған арналған Алгоритммен есептеледі. Компьютердің кең қолданылуына
байланысты Алгоритм жаңа мағынаға ие болды. Берілген есепті шешу барысында
орындаушыға біртіндеп қандай әрекеттер жасау керектігін түсінікті әрі дәл к өрсететін
нұсқау да Алгоритм деп аталады. Алогритмді орындаушы — адам, ЭЕМ немесе робот. Әрбір
нұсқау — бұйрық. Ал орындаушының жүзеге асыра алатын бұйрықтар жиыны б ұйры қтар
жүйесі деп аталады. Мысалы, у = (ax + b) (cx - d) функциясын есептеу ЭЕМ-да мынадай
әрекеттерден құралады:

а-ны x-ке көбейту R1 деп,
оған b-ны қосу нәтижесі R2 деп,
с-ны х-ке көбейту R3 деп,
сх-тан d-ны алу R4 деп,
R2-ні R4-ке көбейту у деп белгіленеді.
Алгоритмнің бұйрықтары бірінен кейін бірі кезекпен орындалады. Ба ғдарлама Алгоритм
тілінде жазу, бейнелеу мағынасын береді. Компьютерде Алгоритмні ң сызы қты, тарма қты,
циклді, логикалық, модельдік, параллельдік, тізбекті т.б. т үрлері қолданылады
21-ші ғасырдың ортасына дейін алгоритм
ұғымы есептеу әдістері ұғымымен
теңестірілді. Есептеу әдістерінде
қолданылатын арифметикалық, анализдік,
тригонометриялық операциялардың
орындалу алгоритм іспеттес болып жүрді.
Ондай проблемаларды шешу үшін қосымша
арнаулы дәлелдеулердің қажеті болмады.
Ал 21-ші ғасырдың 2-ші жартысынан бастап
сандық емес объектілерге қолданылатын
алгоритмдерге қатаң формулировка
берудің болмайтындығы белгілі болды.
Лейбництің тұжырымдамасы бойынша
алгоритмдік шешілмейтін есептер бар,
сондықтан кез келген математикалық
тұжырымдамалардың дұрыстығын
дәлелдейтін алгоритм құрастыру қажеттігі
туындады. Ол барлық теоремалардың
дұрыстығын дәлелдейтін болуы
керек.Анықтама. Әлдебір алгоритм
көмегімен есептелетін функцияны
есептелетін функция дейді.
Іс жүзінде алгоритм – функцияны беру әдісі. Ал функция таблица, схема, формула
түрінде берілуі мүмкін. Бірақ кейбір процестерде бастап қы енгізілген немесе
берілген деректер мен алынған нәтижедегі деректер арасында ғы байланысты
ұйымдастыратын функцияны құру қиын, күрделі.
1 – бағыт Рекурсивті функциялар – есептелетін функциялар ұғымымен
байланысты.
X және Y жиындары бар болсын. X жиыныны ң кейбір элементтеріне Y жиыныны ң
элементтері сәйкес келсе, онда Y – те X – тен б өлшекті функция берілген дейді.
Y жиынында сәйкес элементтері бар ж әне X элементтерден құрал ған жиынны ң
элементтер жиыны функцияның анықталу облысы деп аталады.
X жиынында сәйкес элеметтері бар Y жиыныны ң элементтер жиыны функцияны ң
мәндер облысы деп аталады.
Егер X –тен Y-тегі функцияның анықталу облысы X жиынымен беттессе, онда ол
функцияны барынша анықталған деп атайды.
Осы ұғымға және рекурсивті функция ға негізделіп алгоритмні ң д әл аны қтамасын
құруға болады.
Бұл сандар комбинациясынан күрделі функциялар құрылады:
S(x)=x+1 (бір аргументті бір орынды функция)
O(x,,,, x) =0 –n орынды нөлге теңбе теңдік функциясы.
I(x,,,, x)=X (1) n орынды өз аргументтерінен 1 мәні теңбе теңді
қайталану функциясы.
Бұл функциялар барынша анықталған және интуитивті есептелетін
функциялар. Бұл функцияларға қолданылатын қасиеттері бірдей
барлық операциялар / операторлар қолданылады. Функцияларға
осындай операторларды қолдану арқылы алынған бөлшек
функцияларда бөлшекті рекурсивті функциялар деп аталады.
Бөлшекті рекурсивті функциялар класы арифметикалық есептеулерді
жүргізуге болатын функция кластарымен беттеседі.
Бір есепті шешу үшін тек жалғыз алгоритм емес бірнеше
алгоритм құруға болатыны белгілі. Сондықтан есепті шешу
үшін барлық алгоритмдердің ішінен ең тиімдісін құру қажет
болады. Алгоритмді орындаушы-адам болған жағдайда
алгоритмнің күрделігі логикамен байланысты, себебі, есепке
құрылған алгоритмнің ішінде күрделі структура болса, одан
қандай нәтиже алынатынын алдын ала болжау мүмкін емес,
тек оны орындап болған соң нәтиженің дұрыстығы,
бұрыстығы зерттеледі, ал орындаушы-машина болса, оған
алгоритмнің структурасы қаншалықты күрделі екендігі әсер
етпейді, себебі машина үшін белгілі нұсқаулар берілді, ол соны
орындайды, мысалы: машинаға бәрібір – қосуды орындап
жатыр ма азайтуды орындап жатыр ма, әйтеуір техникалық
жабдығы дұрыс болса, алдына қойған проблема шешіледі.
Немесе алгоритмді жазғанда қайталану операторын
қолданбай ақ күрделі есепті шешудің өте көп қадамнан
тұратын тізбекті структурасын қолдануға болады, ал
машинаға бәрібір- циклды қолдандың ба, тізбекті қолдандың
ба, бірақ есептеу уақыты, алынған нәтиже адамды
қанағаттандырмауы мүмкін, сондықтан алгоритмнің
күрделілігі деген ұғым қажеттілігі шығады.
Анықтама. Алгоритмнен туындаған есептеу процесі деп осы алгоритмді орындау барысында
өткен тізбекті қадамдар алгоритмін айтады.

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

Анықтама. Алгоритмнің уақытша күрделілігі – оны орындауға қажетті Т уа қыты. Ол
элементарлы әрекеттер саны мен оны орындауға кеткен орташа уа қытты ң к өбейтіндісіне
тең:T=kt.t- уақыт орындаушы – машинадан т әуелді болса, алгоритмні ң к үрделілігі k-элементарлы
әрекеттер тізбегінің санынан тәуелді.
А алгоритмі бар болсын. Оған деректерді өңдеу көлемін к өрсететін а параметрі табылсын. Оны (а)
– есептің өлшемі дейді. Т арқылы алгоритмні ң орындалу уа қытын белгілесе, / -ар қылы әлдебір n-
нан тәуелді функцияны белгілейік.
Анықтама. T(n) алгоритмінің өсу реті f(n) бар, немесе бас қаша, алгоритмні ң теориялы қ
күрделілігі O*(f(n)) бар болады, егер c1, c2>0 тұрақтылары және барлық n<=n0 үшін

c
c1 f(n)n<=n0 үшін теріс емес болуы керек. Егер T(n) үшін T(n)<=cf(n) шарты орындалса, онда алгоритмні ң
теориялық күрделілігі O(n) болады. (n-нен үлкен «0» деп о қылады.).
Алгоритм қасиеттері
Алгоритмнің айқын, дәл өрнектелу қасиеті. Алгоритмде келтірілген барлық
әрекеттердің мағынасы айқын, нақты анықталған болу керек. Онда қандай
қадам көрсетілсе тек солар ғана орындалуы қажет. Есеп шығаруға
керектің бәрі анықталуы және орындаушыға түсінікті әрі нақты болуы тиіс.
Алгоритмнің үзіктілік қасиеті. Алгоритмнің үзік модульдерге бөлінуі, яғни
алгоритмді бірнеше кішкене алгоритмдерге жіктеу мүмкін болу керек. Бұл
қасиеті бойынша алгоритм аралық нәтиже беретіндей бірнеше ықшам
бөліктерге, ал олар одан кіші қадамдарға бөлінеді, яғни мәселені шешу
процесінің тізбегі жеке - жеке әрекеттер жіктеледі. Сондықтан алгоритмді,
екі - үш бқлікке бөліп, оларды жеке қабылдай алатын дәрежеде жұмыс
істелінуі қажет.
Алгоритмнің нәтижелік қасиеті. Кез - келген алгоритмнің нәтижесі болу
керек. Әрекеттердің шектеулі санынан кейін белгілі бір уақытта
қорытынды нәтиже алуымыз қажет.
Алгоритмнің жалпылық немесе ортақтық қасиеті. Алгоритм құрғанда
белгілі бір жеке проблемаға қарсы ғана арналмай, осы тәріздес мәселелер
шешуін толық қамтуға мүмкіндік беретіндей етіп құрылуы қажет.
Алгоритмнің формальды орындалуы. Алгоритмді орындағанда орындаушы
оныәр командасының мағынасын түсінуі де, түсінбеуі де мүмкін. Бірақ
алгоритмнің әр командасы орындаушының нақты бір әрекетті орындауын
талап етеді.
Алгоритм жазу жолдары
Алгоритмді компьютерде орындау үшін оларды алдын - ала
жазып алу керек. Жалпы жағдайда, алгоритм жазудың келесі
түрлері қабылданған:
Табиғи тіл
Алгоритмдік тіл
Программалау тілі
Блок - схема
Алгоритмдерді талдаудың негізгі әдістері:

Сөздік-формулалық (табиғи тілдерде);
Құрылымды немесе блок-схемалар;
Арнайы алгоритмдік тілдерді қолдану;
Граф-схемалар көмегімен (граф – әр сызық екі нүктені қосатын, нүктелер
мен сызықтар жиынтығы). Нүктелер шыңдар деп аталады, сызықтар –
қабырғалар;
Петри торының көмегімен.
Бағдарламаны жасау алдында көбінесе сөздік-формулалық және блок-
схемалық әдістер қолданылады. Кейде ассемблер сияқты төменгі
деңгейдегі тілдерде бағдарламаны жасау алдында, бағдарлама
алгоритмін кейбір жоғарғы деңгейдегі бағдарламалау тілінің
конструкцияларын қолдана отырып жазады. Күрделі бағдарламалық
жүйелер алгоритмдерінің бағдарламалық сипаттамаларын қолдану
ыңғайлы. Мысалы, ОЖ жұмыс істеу принциптерін сипаттау үшін Алголға
ұқсас жоғарғы деңгейдегі бағдарламалау тілі қолданылды
Сөздік-формулалық әдісте алгоритм әрекеттер тізбегін
анықтайтын, құрамында формулалары бар мәтіндік түрде
жазылады. Мысалы, келесі өрнектің мәнін анықтау қажет
болсын: у=2а-(х+6).Сөздік-формулалық әдістпен бұл есептің
алгоритмі келесі түрде жазылуы мүмкін:
а және х мәндерін енгізіңіз.
х және 6-ны қосу.
а на 2-ге көбейту.
2а –дан (х+6) қосындысын азайту.
Өрнектің есептелген нәтижесі ретінде у-ті шығару.

Ұқсас жұмыстар

Алгоритмдер туралы түсінік

Шешілмейтін алгоритмдер туралы түсінік. Алгоритм күрделілігі. Алгоритм түсінігінің функция түсінігімен байланысы. Алгоритмдік тіл және оны орындаушылардың сипаттамалары

Шешілмейтін алгоритмдер туралы тү сінік. Алгоритм кү рделілігі. Алгоритм тү сінігінің функция тү сінігімен байланысы. Алгоритмдік тіл жә не оны орындаушылардың сипаттамалары

Алгоритм күрделілігі

Шешілмейтін алгоритмдер туралы түсінік. Алгоритмның күрделіліг. Алгоритм түсінігінің функйия түсінігімен байланысы.Алгоритмдік тіл және оны орындаушылардың сипаттамалары

Шешілмейтін алгоритмдер туралы түсінік

Алгоритмдер туралы түсінік. Алгоритм күрделілігі

Алгоритм туралы мәлімет

Шешілмейтін алгоритмдер туралы түсінік. Алгоритм күрделілігі

Шешілмейтін алгоритмдер туралы түсінік. Алгоритм .күрделілігі. Алгоритм түсінігінің функция түсінігімен байланысы. Алгоритмдік тіл және оны сипаттамалар

Пәндер