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

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

ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНСТРЛІГІ СЕМЕЙ
ҚАЛАСЫНЫҢ ШӘКӘРІМ АТЫНДАҒЫ МЕМЛЕКЕТТІК УНИВЕРСИТЕТІ

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

Орындаған: Анешова Т.Б
Тобы: Т-313
Тексерген: Рысжанова А. С
Жоспар:
1.Шешілмейтін алгоритмдер туралы түсінік.
2.Алгоритм күрделілігі.
3. Алгоритм түсінігінің функция түсінігімен
байланысы.
4. Алгоритмдік тіл және оны орындаушылардың
сипаттамалары.
Алгоритм дегеніміз - белгілі бір мәселені шешу үшін
қойылатын мақсатқа бағытталған іс-әрекеттердің тізбегі.
Олар тұрмыстық, есептеу, рекурсивті, қосалқы деп бөлінеді.
Дербес программаны құру үшін программалау тілін білу ғана
жеткіліксіз. Программаның түпкі негізі алгоритм ұғымынан
құралады. Себебі алгоритм көмегімен программист өзі
құрмақшы болып отырған программаға сәйкес мақсатқа
жетуі үшін орындауы қажет әрекеттердің тізбегін құрастыруы
керек. Алгоритмнің негізгі қызметі – берілген ақпаратты
өңдеу арқылы басқа, жаңа ақпарат құру.
Алгоритмнің тағы бір негізгі мінездемелерінің бірі –
оның күрделілігі. Әдетте алгоритмдер күрделілігінің
дәрежесі оперативті жады және процессорлық уақыт
сияқты қолданылатын компьютер ресурстарының
көлемімен бағаланады. Осыған байланысты
алгоритмнің уақыт бойынша күрделілігі және көлем
бойынша күрделілігі анықталады. Көп жағдайда уақыт
бойынша шектеулер басым рөл атқаратындықтан
уақыт бойынша күрделілік маңызды болып есептеледі.
Уақыт бойынша күрделілік орындалатын операциялар
санымен анықталады, алғашқы мәліметтерге тәуелді
(олардың көлеміне және шамасына)
Алгоритмнің уақыт бойынша күрделілігі – алгоритмнің
есепті шешуіне жұмсаған уақыты, ол есептің өлшемі n-ге
тәуелді функция. Бұл күрделіліктің есептің өлшемі өсудегі
шектік мінездемесі асимптотикалық уақыт бойынша
күрделілік деп аталады. Көлем бойынша күрделілік және
асимптотикалық көлем бойынша күрделіліктер де осыған
сәйкес анықталады Мысалы, егер алгоритм n өлшемді
енгізулерді cn2 уақытында, мұнда c – қандай да бір
тұрақты, өңдесе, онда уақыт бойынша күрделілік (n2) деп
айтады. Алгоритмдерді талдауда ең жақсы, ең жаман
және орта жағдайлар қарастырылады, сәйкес бағалаулар
беріледі. Алгоритмдерді құру мен талдауда олардың
тиімділігін салыстыру үшін теоретиктермен қарапайым
жол ұсынылған: полиномиалдық және экспоненциалдық
алгоритмдер арасындағы айырмашылық.
Қай алгоритм болса да негізгі қасиеттерді
қанағаттандыруы шарт:

Дискреттілік қасиет – орындалатын әрекеттер
тізбегі бірнеше қадамдарға бөлініп үздікті
құрылымды болуы керек. Және қадамдардың
орындарын ауыстыруға болмайды.
Түсініктілік қасиеті – орындаушыға түсінікті
және орындай алатын нұсқаулар жиынынан
командалардан тұруы қажет. Орындаушыдан
біртұтас әрекет жасауды талап ету керек.
Алгоритм орындаушыға бағытталуы керек.
Анықтылық қасиеті – детерминделген деп те аталады, бір
алгоритмді кез келген орындаушы орындай алатын болуы
керек. Қай орындаушы орындаса да алынатын нәтиже біреу
болуы керек. Орындаушы дербес шешім
қабылдамайтындай болып құрылуы керек, яғни анық,
егжей-тегжейлі ойластырылған, толық, жалғыз нәтижелі
болуы керек. Бір - екі минуттай деген сияқты нұсқаулар
болмау керек.
Ортақтық қасиеті – бір алгоритм барынша үлкен класқа
жататын есепті шешетіндей болуы керек, тек бастапқы
берілгендерді өзгерту арқылы ғана шешімді табуға
болатындай. Мысалы квадрат теңдеуді шешу алгоритмін
ах2+bx+c=0 жағдайына құрған дұрыс болады, ал 4x2+5x-
1=0 түріне құрса онда алгоритм дербес болады, неғұрлым
жалпы болуы керек.
Нәтижелілік қасиеті – алгоритмнің пункттері немесе
нұсқаулары шектелген, оның шегі есептің нәтижесін
беретіндей болуы керек. Алынған нәтиженің дұрыстығын
Алгоритмнің берілу тәсілдері:

формула бойынша

таблицалық түрде блок-схема көмегімен
Алгоритмдік тілде алгоритмнің сипатталауы:
Басы
Жай команда 1;
Жай команда 2;
Егер шарт
Онда 1 – серия
Әйтпесе 2 – серия
Әзір шарт
Ц.б.
Құрама команда
Ц.с.
Бітті . Соңы
Алгоритмдік конструкциялар:
1.Сызықты
2.тармақты
3.қайталану
4.рекурсивті
1969 жылы В. Дейкстр
өзінің «деректер
структурасы және
алгоритмдер» статьясында
кез келген алгоритмді жазу
үшін негізгі 3
конструкцияның –
сызықты, тармақты,
қайталану - жеткілікті
екенін дәлелдеген.
Сызықты алгоритмді
тізбекті алгоритм деп те
айтады.
Р алгоритмі тізбекті алгоритмдік конструкциямен
қарастырылады, егер Р алгоритмінің әрбір
қадамы бір рет орындалса, және әрбір i-ші
қадамнан соң (i+1)-ші қадам орындалып, i-ші
қадам соңғы қадам болмаса.
Р алгоритмі тармақты алгоритмдік
конструкциямен қарастырылады, егер алгоритмнің
қай қадамы орындалатыны енгізілген деректерден
тәуелді болса, және белгілі бір бастапқы деректер
таңдалынып алынған соң орындалатын тармақты
конструкция тізбекті конструкцияға келтіріледі.
Р алгоритмі қайталану алгоритмдік конструкциямен
қарастырылады, егер алгоритмнің қандай да бір қадамдар тобы
бастапқы берілгендерге байланысты бірнеше рет қайталануы
керек болса.Кез келген циклдік конструкцияның ішінде
тармақты конструкция да, тізбекті конструкция да болады.
R алгоритмі рекурсивті конструкциямен қарастырылады, егер
қандай да бір қадамда ол тура немесе жанама түрде қайтадан
өзіне қатысса, немесе белгілі бір қадамда оның алдыңғы
қадамында орындалған қадамдардың нәтижесі қайталанып
қолданылса.Кез келген алгоритмнің дәл немесе дұрыстығы
алгоритм моделімен негізделеді. Модель есепті шешуде
қолданылатын құралдар жиыны, яғни келесі қадамды анықтау
әдісі, қарапайым әрекеттер, қадамдар.
А.А. Марков –
математик, қалыпты
алгоритм түсінігін
енгізді. Жалпы
алгоритмдердің келесі
түрлері болады:
1.Тұрмыстық
2.Есептеу
3.Рекурсивті
Алгоритмдердің негізгі түрлері

сызықтық тармақталған циклдік

Мұнда Мұнда есепті Жеке
бұйрықтар шығару бұйрықтар
бірінен соң барысында немесе
бірі ілесу кейбір бұйрықтар
тәртібімен шарттарды тобы бірнеше
орындалады таңдау рет
мүмкіндігі қайталанады.
болады
Операциялардың реті алгоритмнің өз
структурасымен анықталған және
енгізетін шамалардың жеке мәндеріне
тәуелсіз, тізбектеліп орындалатын
алгоритмдерді сызықты алгоритмдер
дейді.Енгізетін шамалардың жеке
мәндерінен тәуелді бірнеше әрекеттердің
біреуінің орындалуын тағайындайтын
алгоритмдерді тармақталған
алгоритмдер дейді.
Сұрыптау дегеніміз массив элементтерін өсу не кему реті бойынша реттеу процесі.
Мысалы, n элементтен тұратын X массиві оны ң элементтеріні ң м әні бойынша егер
X1 ≤ X2 ≤...≤ Xn болса өсу реті, егер X1 ≥ X2 ≥ ... ≥ Xn. болса кему реті бойынша
сұрыпталады.
Сұрыптау алгоритмдерінің түрі өте көп, бірақ олардың бәрі негізгі үш алгоритм
бойынша құралады:
-алмастыру арқылы сұрыптау;
-таңдау арқылы сұрыптау;
-қою арқылы сұрыптау.
Мысал ретінде коллодаға карталарды реті бойынша салу керек деп алайы қ.
Карталарды алмастыру арқылы сұрыптау үшін үстелге карталарды бет жа ғымен
үстіне қаратып орналастырып, одан соң қате ретпен орналас қан карталарды ң орнын
алмастыру арқылы карталар реті бойынша орналас қанға дейін қайталау ар қылы
жасауға болады.
Үстелге қойылған карталарды таңдау арқылы сұрыптау үшін е ң кіші(е ң үлкен)
картаны таңдап, оны қолға алынады. Содан соң қалған карталардан е ң кіші (е ң
үлкен) картаны таңдап алдыңғы таңдалған картаның артына қояды. Бұл процесс
барлық карталар қолға жиналғанша қайталанады. Өйткені әр ретте үстелде қал ған
карталар ішінен мәні бойынша ең кіші (ең үлкен) карта та ңдалады, б ұл процесс
аяқтала келе карталар өсуі (кемуі) бойынша сұрыптал ған болады.
Қою арқылы сұрыптау үшін колодадан екі карта алынады ж әне бір-біріне қатысы
бойынша қажетті ретпен орналастырады. Колодадан алынған әрбір кезекті карта
бұрын реттелініп қойылған карталармен қатысы бойынша с әйкес орын ға қойылуы
тиіс.
Алгоритмдік тіл — деп алгоритмді бірыңғай
белгілермен ережелерді сақтай отырып жазу
жүйесін айтады. Алгоритмді жазуда қолданылатын
сөздер қызметші сөздер деп, ал математикалық
таңбалар, цифрлар, әріптер жиыны алгоритм
алфавиті деп аталады.
Алгоритмдегі идентификатор – айнымалының
атауы. Иднтификатор лат. әріптерімен, сандармен
белгіленеді.
Программалық тіл – алгоритмді компьютерге
түсінікті мәтін түрінде жазуға араналған
жасанды тіл.
Мыс: Паскаль, Бейсик, СИ, Дельфи, Пролог…
Назарларыңызға
рахмет

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

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

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

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

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

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

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

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

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

Алгоритм түсінігі

ТЬЮРИНГ МАШИНАСЫ жә не Марковтың нормальді алгоритмы

Пәндер