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

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

Жоспары:

I Кіріспе бөлім

1. Алгоритм, алгоритмдік анықтама.

2. Алгоритмнің қасиеттері және оған қойылатын талаптар.

3. Алгоритмнің күрделілігі, күрделілік.

4. Алгоритмнің берілу тәсілдері.

ІІ. Негізгі бөлім

1. Алгоритмдік тіл.

2. Алгоритм түсінігінің функция түсінігімен байланысы.

Алгоритм дегеніміз - алға қойылған мақсатқа жету үшін немесе берілген есепті шешу үшін түсінікті де нақты ережелер бойынша орындаушыға жинақы түрде берілген реттелген нүсқаулар тізбегі. Бұл анықтамада алгоритм мен оның қасиеттерін байланыстыратын негІзгі ұғымдар беріліп отыр. Алгоритм - математика мен кибернетиканың негізгі ұғымдарының бірі. Агоритмді орындау алгоритмдік процесс деп аталады.

Алгоритмді жазудың немесе берілу тәсілдерінің 3 түрі бар:

1. Сөзбен ауызша беріледі.

2. Блок-схема түрінде.

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

Блок-схема дегеніміз -Информацияны өңдеу алгоритмін МЕСТ

(мемлекеттік стандарт) -те бекітілген символдарды пайдаланып, графикалық түрде жазу.

Әлдебір алгоритм көмегімен есептелетін функцияны- есептелетін функция дейді. Кез - келген берілген деректерді (үзілісті, дискретті) әлдебір санау жүйесінде натурал сандармен кодтауға болады, онда

Олардың барлық алмастыруы есептеу операцияларының тізбегіне келтіріледі, ал өңдеу нәтижесі солайынша бүтін сан болып қалады. Кез келген алгоритм берілген сандық функция үшін бірдей, оның мәнін есептейді, ал оның элементарлы қадамдары қарапайым арифметикалық және логикалық операциялар болады. Мұндай функциялар есептелетін функциялар деп аталады.

Функция- таблица, схема, формула түрінде берілуі мүмкін. бірақ кейбір процестерде бастапқы енгізілген немесе берілген деректер мен алынған нәтижедегі деректер арасындағы байланысты ұйымдастыратын функцияны құру қиын, күрделі.

1 - бағыт рекурсивті функциялар - есептелетін функциялар ұғымымен байланысты.

x және y жиындары бар болсын. x жиынының кейбір элементтеріне y жиынының элементтері сәйкес келсе, онда y - те x - тен бөлшекті функция берілген дейді. y жиынында сәйкес элементтері бар және x элементтерден құралған жиынның элементтер жиыны функцияның анықталу облысы деп аталады. x жиынында сәйкес элеметтері бар y жиынының элементтер жиыны функцияның мәндер облысы деп аталады. Егер x -тен y-тегі функцияның анықталу облысы x жиынымен беттессе, онда ол функцияны барынша анықталған деп атайды. Осы ұғымға және рекурсивті функцияға негізделіп алгоритмнің дәл анықтамасын құруға болады.

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

Алгоритмнің уақытша күрделілігі - оны орындауға қажетті Т уақыты. Ол элементарлы әрекеттер саны мен оны орындауға кеткен орташа уақыттың көбейтіндісіне тең:T=kt. t- уақыт орындаушы - машинадан тәуелді болса, алгоритмнің күрделілігі k-элементарлы әрекеттер тізбегінің санынан тәуелді. Алгоритмнің уақыт бойынша күрделілігі - алгоритмнің есепті шешуіне жұмсаған уақыты, ол есептің өлшемі n-ге тәуелді функция. Бұл күрделіліктің есептің өлшемі өсудегі шектік мінездемесі асимптотикалық уақыт бойынша күрделілік деп аталады

Күрделілік (Сложность; complexity) - өңделетін мәліметтердің көлеміне байланысты осы алгоритм сипаттайтын программаның орындалу уақытына тәуелділікті анықтайтын алгоритм сипаттамасы. Күрделілікті программаның мазмүны бойынша бағалауға болады. Сөйтіп, егер программада қадамдар саны сыртқы циклда тте тең және қабаттасқан циклда nге тең қабаттасқан цикл орындалса, онда күрделілік m*nre пропорционал болады. Алгоритмнің жұмыс уақытын өрнектейтін функцияның ретіне карай формальды түрде анықталады.

Алгоритмның күрделілігінің f(n) функциясының негізгі бағалауы Q бағасы. Мұндағы n деректер көлемінің шамасы немесе кірістің ұзындығын білдіреді.

Алгоритмның күрделілігінің негізгі бағасы f(n) =Q (g(n) ), егер g>0, n>0 болғанда мынадай оң c1, c2, c0, болса: c1 g(n) <=f(n) <=c2 g(n) . n>n0 болғанда мынадай c1 мен c2 табуға болады, ұлкен n үшін f(n) мәні мына c1 g(n) және c2 g(n) екеуінің аралығында болды.

Бұл жағдайда g(n) функциясын f(n) функциясының асимтотикалық нақты бағасы деп атайды. Мысалы heapsort сұрыптау әдісі үшін күрделілік бағасы f(n) =Q болады, яғыни g(n) =n log n. f(n) =Q (g(n) ) теңдіктен g(n) =Q (f(n) ) туындайды.

Q бір мезгілде функция өсімінің жоғары және төменгі бағанын береді. Көбінесе бұл бағаларды жеке құраструға тура келеді.

0 бағасы алноритм қыиындығының f(n) функциясының өсуінің жоғары асимтотикалық бағасын береді. W бағасы алноритм қыиындығының f(n) функциясының өсуінің төменгі асимтотикалық бағасын береді және тұрақты көбейткішке дейін дәлдікпен g(n) функциясына қарағанда f(n) функциясы баяу өспейтін функциялар класын анықтайды.

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