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

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

Шешілмейтін алгоритмдер туралы
түсінік. Алгоритмның күрделіліг.
Алгоритм түсінігінің функйия
түсінігімен байланысы.Алгоритмдік тіл
және оны орындаушылардың
сипаттамалары.
Жоспары:
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 с.
Назарларыңызға
рахмет!!!

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

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

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

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

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

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

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

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

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

Тармақталу алгоритмдері

Компьютерлік білім

Пәндер