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

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

Қазақстан Республикасының Білім және ғылым министрлігі
Семей қаласының Шәкәрім атындағы Мемлекеттік университеті
Жаратылыстану – математика ғылымдар факультеті

СӨЖ №2

Орындаған: Бекбосунова Мариям Т- 311

Тексерген: Рысжанова Айжан Сайлаухановна

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

Алгоритмдік тіл деп – орындалатын әрекеттерді, амалдарды бірыңғай ж әне д әл
жазуға арналған, өз тіліміздің кейбір сөздерімен пайдаланатын белгілер мен
ережелер жүйесін айтады. Алгоритмдік тіл бір жа ғынан таби ғи тілге жа қын,
сондықтан оны қарапайым мәтін түрінде жазады және о қиды. Алгоритмдік тіл –
математикалық белгілер сандар, шамалар мен функция атаулары, арифметикалы қ
белгілері, жақша және басқа да символдармен қатар белгілі бір қызмет атқаратын
терминдер қамтиды. Алгоритмдік тілде мәтін құруға пайдаланылатын қарапайым
белгілер – тілдің символдары деп, ал ондай символдар жиынын – оны ң алфавиті деп
атайды.
Алгоритмдерді жәні алгоритмдік тілде құрылған амалдар тізбегін
компьютерге түсінікті командалар мәтіні түрінде жазуға арналған жасанды
тілдерді программалау тілдері деп атайды. Паскаль, Си, Дельфи, Бейсик, Фортран
тәрізді программалау тілдері – ағылшын тіліндегі кейбір с өздерді алгоритм құруда
кеңінен пайдаланады. Ол сөздердің саны онша көп емес, оларды түйінді сөздер деп
атайды. Әр компьютердің өзінің машиналық тілі болады, ол командалар тілі
немесе кодтар тілі деп аталады. Алгоритмдік тілде және программалау тілінде
программа жазу – ыңғайлы болып табылады. Оларды белгілі бір машинада орындау
үшін сол программалау тілін машина тіліне автоматты түрде аударатын түрлендіргіш
программалар болуы керек, оларды транслятор деп атайды. Трансляторлар үш түрге
бөлінеді: интерпретатор, компилятор және ассемблер.
Алгоритмнің графиктік түрде кескінделуі
Алгоритмнің графиктік түрде кескінделуі – кең таралған әдіс. Б ұл –
жазудың түсінікті, анық, көрнекі түрі болып табылады. Алгоритмдерді
графиктік жолмен жазудың мемлекеттік стандарты аны қтал ған. Онда кез-
келген амал белгілі бір геометриялық фигурамен өрнектеледі. Олар
фигуралар немесе блоктар, амалдар немесе операциялар символы деп те
аталады. Блоктар бағытталған сызықтармен байланысып, бірінен со ң бірі
ретімен орналысады. Ақпарат өңдеудің әрбір буыны немесе орындалатын
операциялар реті алгоритм схемасымен айқындалады. Алгоритм схемасын
оның блок схемасы деп аталады. Алгоритм блоктарының ішінде
орындалатын іс-әрекеттің мазмұны жазылады. Блок схемада пайдаланатын
фигуралар оның блоктары, ал оларды бір-бірімен қосатын
сызықтар байланыс сызықтары деп аталады.
Алгоритм жазу жолдары
Алгоритмді компьютерде орындау үшін оларды алдын-ала
жазып алу керек. Жалпы жағдайда, алгоритм жазуды ң келесі
түрлері қабылданған:
1) табиғи тілдегі жазылуы;
2) белгілі бір түйінді сөздер – терминдер ар қылы қыс қаша
тізбекті түрде жазу;
3) графиктік жолмен жазу;
4) программалау тілдеріндегі жазылуы.
Бірақ табиғи тілде жазылған алгоритм компьютерде
орындалмайды, өйткені бұл жағдайда дәлдік, на қтылы қ
сақталмайды. Алгоритмдерді графиктік жолмен жазу, кейіннен
осы программалау тіліндегі программа ға айналдыру ж ұмысы
мемлекеттік стандартпен бекітіліп, а қпарат өндеу ж ұмысында
кеңінен қолданылады.
Қолданылған ақпарат көздері:

1. О. Камардинов «Информатика», Алматы,2006
2. http://referat700.ru/news/algoritmder_k/
3. Алгоритмдер теориясы: Оқу –әдістемелік кешен.
Б.Д.Сыдықов. Алматы: Нур-Принт, 2012 жыл

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

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

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

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

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

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

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

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

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

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

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

Пәндер