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

Қазақстан Республикасының Білім және ғылым министрлігі

Семей қаласының Шәкәрім атындағы Мемлекеттік университеті

Жаратылыстану - математика ғылымдар факультеті

СӨЖ №2

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

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

Семей 2015 жыл

Жоспар:

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

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

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

Алгоритмдік тіл және оны орындаушылардың сипаттамалары.

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

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

Алгоритмнің уақыт бойынша күрделілігі - алгоритмнің есепті шешуіне жұмсаған уақыты, ол есептің өлшемі 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-есептер де (шифрлеу есептері және т. б. ) бар.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пәндер