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

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

Жоспары: 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) функциясы баяу өспейтін функциялар класын анықтайды.

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

Алгоритмдік тіл және программалау тілі ұғымы

*

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

Әр компьютердің өзінің машиналық тілі болады, ол командалар тілі немесе кодтар тілі деп аталады. Алгоритмдік тілде және программалау тілінде программа жазу – ыңғайлы болып табылады. Оларды белгілі бір машинада орындау үшін сол программалау тілін машина тіліне автоматты түрде аударатын түрлендіргіш программалар болуы керек, оларды транслятор деп атайды. Трансляторлар үш түрге бөлінеді: интерпретатор, компилятор және ассемблер. Интерпретатор – берілген прогамманың әрбір жолын (командасын) жеке-жеке аударып отырып орындайтын транслятор түрі. Компилятор – бірден барлық программа мәтінін толық аударып машина тіліндегі бір модуль түріне келтіреді де, сонан соң сол модульді компьютер жадына қайта жазып алып, оны кейін тек біздің алауымыз бойынша орындайды.

Әдебиеттер тізімі Қаленова Б.С. Практикалық информатика құралы,С.Қалкенова. –Өскемен, 2003. -126 6. курсы:Оқу

КунтД. Искусство программирования для ЭВМ. Том 1:основные алгоритмы./ Д.Кунт.- Москва, Сагнкт- Петербург, Киев,2000. Врит Н. Алгоритмы и структуры данных./Н. Врит. -М.:Мир, 1989.-360 с.

Назарларыңызға рахмет!!!


Пән: Математика, Геометрия


Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь