Ашық кілтті қолданатын алгоритмдер


Диплом жұмысының өзектілігі: Евклид және Диофант, Ферма, Эйлер, Гаусс, Чебышев сонымен Эрмит еңбектерінде диофан түріндегі теңдеулердің шешу жөніндегілері маңызды ойлар бар болып табылады, сол уақыттар үшін үлкен болып саналатын сандарының ең жақын мәндерін іздеу үшін талаптар бар болып айқындалады. Соңғы кездерде екі он жылдардағы криптографиялар ЭЕМ-гі кең тарқалуындағы солармен қатар сұраныстардың дамуытуларына қарай сандар теорияларының алгоритмдіктері сұрақтарына дамуларының қарқынды болып келеді. Сонымен қатар есептеушілердегі машиналарының немесе лектрондықтардың құралдардың адамның барлық қызметтерімеен ой-өрісіне қарай жоғарланады. Бұндайсыз қазіргі кездегі криптографияны елестету мүмкін емес болып айқындалады. Жалпы мәтіндерді шифрлеу арқылы және солармен қатар оны бұзудыда ЭЕМ арқылы бүтін сандардың өңдеу ретіндегілерімен қатар елестетуге болатындығын білеміз, сонымен осындай амалдар орындалатын тәсілдері кейбір функциялары арқылы солай секілді бүтін сандарының белгілі бір жиынындада орында алатын болып саналады. Бұлардың барлығы қазіргі кезде криптографияларда олардың сандарының теорияларымен қатар болуына жағдай жасалынатын болып табылады. Сонымен қатар олармен байланысты, кейбір криптографиялар жүйелерінің тұрақтылығымен қатар тек кейбір сандықтар-теориялықта есептер арқылы да күрделілігімен қатар негізделетін болған болатын. Дегенмен ЭЕМ мүмкіндігі шекті болып айқындалады. Ұзындағы сандық тізбектерді белгілі бір өлшемді блоктарға бөлуге де тура келетіндігінде немесе әр блоктарды бөлек шифрлеуге тура келетін болып айқындалады. Осылардың әр қайсысы біз барлық шифрленетін сандардыңда теріс емес және берілген m санынан кіші емес деп санайтын болатындығымызда болып отыр. Сонымен қатар осындай шектеулер арқылы солармен байланысты одан әрі шифрлеуденде алынатын сандарғада қатысты болып айқындалады.
Соның негізіндегілеріндегі нақты қолданылатындағы шифрлеулер жүйесі алынатын болып табылады, авторлардың барлық есімдерінің алғашқы аттарына сәйкестігімен қатар RSA деп саналатын болатындығында болып отыр. Осындай функциялардың төмендегіндей болып келетіндігін айқындаймыз:
- функциясының мәндерінен қатар есептейтін әлдеқайда жылдам әдістері бар болып табылады;
- кері функцияларының мәндеріндегілері есетейтін жылдам әдістері бар болып табылады;
- функциясының «құпиясы» бар екендігіне, дегенмен оны анықтасақ, мәндерін тез есептеуге болатындығы болып табылады, сонымен қатар қарсы жағдайда есептеуге ауыр болатындығы, көп уақытты кетіретін, шешуге мүмкін емес есепке айналатын болып табылатындығында.
RSA осы жылдардың ішіндегі ұсынылған ашық кілттердің қолданатын алгоритмдерінің ішіндегілерінің ең оңай түсінуге және жүзеге асыруға болатын алгоритмдері болып айқындалады.
Бұл дипломдық жұмыс криптографияның ашық кілтті қолданатын алгоритмдердің бірі - RSA-ға арналған болып айқындалады.
Диплом жұмысының мақсаты: Криптографиялық кілттердіңкөмегімен желілерді қорғауды қамтамасыз ету және RSA алгоритмін қазіргі таңдағы технологияларды пайдалана отырып, ақпаратты қорғау саласында кеңінен қолдана алатын автоматтандыру жүйесін құру.
Жұмыстың мақсаты дипломдық жұмыс барысында шешілген келесі міндеттерді анықталған болатын:
- сандар теориясын, оның бөлімдерінің бірі жан сандарды зерттеу. Өте үлкен жай сандарды іздеу;
- екілік жүйедегі сандармен жұмыс жасау;
- ашық және жабық кілттердің құрылымын зерттеу;
- бір компьютерден екінші бір компьютерге ақпаратты шифрлеп жібергенде, барлық қауіпсіздік ережелерін сақтау және зерттеу болып табыалды.
Дипломдық жұмыс кіріспеден, үш бөлімнен, қорытындыдан, әдебиеттер тізімінен тұрады. Кіріспеде жұмыстың өзектілігі берілген, мақсаты қойылған, сол мақсатқа қол жеткізу міндеттерінен тұратындығын айтамыз. Сонымен қатар зерттеу объектісі және маңыздылығы анықталып қарастырылған болатын.
Бірінші бөлімде криптографияның негізгі түсініктерімен қатар олардың тарихы, олардың жұмыс істеу принциптерімен алгоритмдері, сонымен қоса RSA алгоритмдері пайдаланылатын математикалық негіздемелері туралы теориялық анықтамалар да орын алған болатын. Бірінші бөлімнің басты қорытындысы - криптографияның бастамасын түсіндірулерімен қатар, оның әдістемелерінен қатар алгоритмдеріндегі таныстыру болып табылады.
Екінші бөлім ашық кілтті қолданатын алгоритмдерге, соның ішінде, RSA алгоритміне арналған бөлім болып табылады. Осыларға орай қорытындылар жасалынды.
Үшінші бөлімде NET платформасына, оның құрылымы мен сипаттамасына арналған боылп айқындалады. Сонымен қатар бұл бөлімдегілер C-тың басқа объектілі-бағытталған болып программалардан айырмашылығын көрсетілген болып айқындалатындығында болып отыр.
Сонымен қатар олардағы жұмыстың қойылымына, яғни бағдарламалық бөлімге арналған болып табылады. Онда әрбір батырманың мақсатына дейін айтылып кеткен болып табылады.
1 НЫСАННЫҢ ЖАҒДАЙЫНЫҢ ТЕХНИКАЛЫҚ ШАРТТАРЫ
1. 1 Криптографияның негізгі түсініктемелері мен тарихы
Ақпараттарды оларды түрлендірулерімен қатар басқа адам оқи алмайтындай етіп қорғаулардағы мәселелері адамзат алдында бұрыннан тұрған мәселелердің бірі болып айқындалады. Криптографияның тарихы яғни - адамзат тілінің тарихының замандасымен байланысты болып келеді. Олармен бірге, жазу алғашқыда криптографиялық жүйелерінің болуына табылатын, себебі, ежелге қоғамда солармен тек ерекше таңдаулы адамдардан иелік ететін болып табылады. Ежелдегі Египет және Үндістан киелі кітаптарымен қатар соған мысал бола айқындалатындығында болып отыр. Криптография жазудың кең таралуындағы олармен байланыстары дербес ғылым ретінде қалыптаса басталатын болып келеді.
Криптография тарихтарында олармен қатар шартты түрде төрт қадамға бөлңп қарастыруға болады, олар төмендегідей:
- жай криптографиялар;
- ресми криптографиялар;
- ғылыми криптографиялар;
- компьютерлік криптографиялар болып.
Сонымен қатар жай криптографиялар үшін (XVI ғасырлар басында олармен қатар) қарсыластырылатын кез келген шифрлік мәтін мазмұнына қарай қатысты шатыстыру тән болып табылады. Мысалы, бастапқы қадамдағылары ақпаратты сақтаулары үшін криптографиямен қатар барабар кодтаулары арқылы және стеганография әдістері қолданатын болып келеді.
Көптеген қолданылыстағылардың шифрлар орын ауыстырулар және моноалфавиттіктері ауыстырулары арқылы жүзеге асырылатын болып табылады. Жарияланған мысалдардың бірі болып табылатын Цезарь шифры табылған болып келеді, олардың мәтіндегі алдыңғыдағы әріпті алфавитте одан алыс тұратын әріптерге ауыстырулары арқылы жүзеге асырылатындығында болып отыр. Басқа шифрлері, полибианды квадраттар, грек жазушысы Полибий шығарған, алфавитпен өлшемі 5 және 5 болатын квадратты кестеге кездейсоқ толтырылатын грек алфавитінің көмегімен жүзеге асатын жалпы моноалфавитті орын ауыстыру болып саналады. Барлық әріп квадратта одан төмен тұратын әріппен ауыстырылған болатын. Сондықтан ресми криптография қадамы (XVғ. аяғы-XX ғ. басы) криптоанализдің ресми және салыстырмалы түрде тұрақты шифрлерінің пайда болуымен байланысты болып айқындалады.
5B07. 19. РЭТ. 5101
5B07. 16. РЭТ. 01. 01
5B07. 15. РЭТ. 31. 01
5B07. 15. РЭТ. 01. 01
Әдеб.
Орындаған
Орындаған
Орындаған
Орындаған
Жетекші
Өлш.
. . Өлш.
. . Өлш.
. . Өлш.
. .
Бет
Беттер
ҚР Бжәне ҒМ ҚазККА
«РТ» кафедрасы
және ҒМ ҚазККА
«РТ» кафедрасы
Криптографиялық кілттердіңкөмегімен желілерді қорғауды қамтамасыз ету
Бекітемін
Н. бақылау
Н. бақылау
Н. бақылау
Н. бақылау
ҚолыКүніКүніКүніКүні
Бет
Бет
Бет
Бет
Құжат №
Мекебаева А. К.
Т. бақылау
Нурыллаев Н. Д.
Мекебаева А. К.
Кусамбаева Н.
Липская М. А.
5
54
Дж
Сонымен қатар Еуропа мемлекеттеріндегі осындай Қайта өрлеу дәуірлері кезіндегі пайда болған болатын, сондықтан ғылымдар мен сауданың дамуы ақпаратты қорғауларының әдістерімен қажет болған кезде пайда болып айқындалады. Осындай қадамдағы маңызды рөлдері Леон Батисте Альберти атқарылады, олар көп әліппелі орындар ауыстырудағылар алғаш ұсынған итальян архитекторы болып табылалған. Жалпы XVI ғасырда Блез Вижинер дипломатының атына ие болған бұл шифр берілген мәтінді кілтпен әріпті тізбекті қосу тәсілінен болып табылады. Осылардың «шифр туралы трактат» атты еңбегі криптологияларымен қатар олардың жөніндегі алғашқы еңбегі болып табылатындығында болып отыр. Ең алдымен бір рет баспа жұмыс болып Иоганн Трисемустың «Полиграфиялары» (1508 жыл) еңбегі болып айқындалады. Олар үлкен еместегі, алайда маңызды жаңалық ашқан болатын, полибиандік квадрататы қабылдауларындағы әдістері немесе әріп жұптарын шифрлеулері болып айқындалатын.
Көп әліппелі ауыстыруларының қарапайымдылығына әрі тұрақты әдісі болатындағына XIX ғасырларда Чарльз Уитстонмен ашылғандағы Плейфер шифры пайдаланылады. Уитстон маңыздылығы жаңалықтардағы «екілік квадрат» арқылы шифрлеу әдісін ашқан екен. Плейфер және Уитстон шифрлары бірінші дүниежүзілік соғысқа дейін пайдаланылады. Сонымен қатар XIX ғасырда голландықтар Керкхоффы сол уақыттарға дейінгілердегі өзекті болып табылатын криптографиялық жүйелерінің басты талаптарын ұсынылған болатын, дегенмен шифрлардың құпиялылығының алгоритм еместігімен қатар, кілттің құпиялылығына негізделуі қажет болып айқындалады. Ғылымға деігейіндегі оларға жоғары крипто тұрақтылықтармен қамтамасыз ететіндігі криптографияның соңғы сөзі болып шифрларды автоматтандыруға мүмкіндік берген роторлық крипто жүйе болып айқындалады.
Сондай жүйелердегі барлық болып 1790-жылы болашақ президент Томас Джефферсонмен пайдаланылған механикалық машиналары болып табылған болатындығында болып отыр. Сонымен жалпы әліппелі ауыстырулардағы роторлықтар машиналары көмегімен бір-біріне қарай айналымдағы жасайтындығы роторлардың вариациясы арқылы болып айқындалады.
Роторлық машиналардың практикалық жағынан сұранысқа XX ғасыр басында ие болып айқындалады. Сонымен қатар алғашқы қолданыстағы енген машиналары болып 1917-жылы Эдвард Хебернмен жасалынатындығы, Артур Кирхпен жаңартылған немістері Enigma машинасы болған болатын. Роторлық машиналар ІІ дүниежүзілік соғыс кезінде кең қолданылған болатын. Жалпы неміс Enigma машинасынан өзге Sigaba, Турех, Red, Orange, Purple2 пайдаланған болатын. Роторлық жүйелеріндегі-ресми криптографияның шырқау шегі болып табылады, өйткені олар салыстырмалы түрдегілердегі тұрақты шифрлар тарататын болған болатын. Роторлық жүйелердегілері байланысты сәтті криптошабуылдар 40-жылдары ЭЕМ-нің пайда болуымен мүмкін болып айқындалады.
Сонымен барлық ғылымилардағы криптографияның айрықша белгілерімен қатар (XX ғасырдың 30-60-жылдарымен қатар ) барлық жоғары математикалық негізделгендегі тұрақты криптожүйелерінің пайда болуымен қатар болып келеді. Сонымен қатар 30-жылдардың басына қарай ғылыми түрдегі криптографияның негізі болып айқындалатын математика бөлімдерімен қатар толық қалыптасқан болып отыр, жалпы ықтималдықтар теориясымен қатар немесе математикалық статистикаларымен, жалпы алгебралар арқылыда, сандар теориясымен, алгоритм теориялары арқылы ақпарат теорияларымен қатар, кибернетикалары болып табылады. Ерекше бөлімі болып Клод Шеннонның «Құпия жүйелердегі байланыс теорияларымен қатар» (1949) атты түрегі еңбегі болып келеді, мұнда ақпаратты криптографиялық қорғаудың теориялық принциптерімен қатар айқындалған болатын. Жалпы шеннон «араласулары» және сонымен «бөліну» атты ұғымдарды енгізілген болатын.
Сонымен жалпы 60-жылдардағы көшбасшылардағылары мен қатар мектептермен блоктық сандардың жасалуына көшті, олар роторлықтарымен криптожүйелермен салыстырғандағы аса тұрақты, алайда олардағы тек сандық электронды құрылымдарды жүзеге асырудағылары ғана қамтамасыз етілетін болды.
Сонымен қатар компьютерлік криптографиялардың (XX ғасырдың 70-жылдары) өнімділігі криптожүйелерінің таратуға жеткіліктілігі, шифрлеудің жоғары жылдамдығын қамтамасыз ететіндігі және олармен қатар «қолдық» және «механикалық» шифрлардің есептеулердің машиналарының шығуына байланысты пайда болып табылады.
Криптожүйелеріні алғашқы кластарымен қатар болып қолданулары кезіндегілерінің қуатты әрі жинақты есептеулерімен құралдарының пайда болуына байланыстылығы шыққан блоктық шифрлармен болып айқындалады. 70-жылдардағы шифрлеулерінің DES американдық стандарты жасалынған болатын Солардың авторларының бірі болғандығы Хорст мен Фейстел, олар блоктық шифрларымен қатар моделін айқындап, соның негізіндегі жасалынған аса тұрақты симметриялық криптожүйелерді пайдаланылатын.
Сондықтан DES-тердің жалпы пайда болуларымен қатар криптоанализ байланысты, американдық алгоритмдерге шабуылдары үшін бұлар криптоанализдердің жалпы түрдегі бірнеше тәсілдері жасалынады (сызықтық, дифференциалды және тағыда басқа), практикалық қолданылулары жағынан тек есептеулерінің машиналардың пайда болуымен мүмкін болып табылады.
Жалпы 70-жылдың ортасындағы қазіргі кездегі криптографияда төңкеріс болып айқындалады - асимметриялық криптожүйелердегі жалпы пайда болғандағы, ол жақтардағыларының арасындағылары бір-біріне құпия кілттің таратылуындағы қамтамасыз етілетін қолданылады. Осындай негізгі еңбек тердегі Уитфилд Диффимен және Мартин Хеллманмен 1976-жылы жарияланған «Қазіргі кездегі криптографиялары бағыттары» болып айқындалады. Бұл жердегі ең басындағы болып шифрліктері ақпараттардың кілтсіз таратылуларындағы принциптерімен қатар негізделген болып айқындалады. Асимметриялық криптожүйелердің жалпы идеяларына тәуелсіз қатысты болып айқындалады. Жалпы айтқанда Ральф Меркли болып қолданылды. Бірнеше жылдардан кейінгі Рон Ривест, Ади Шамир немесе Леонард Адлеман RSA жүйесін ашқан болатын, олар дегеніміз алғашқы уақыттардағы практикалық түрдегі асимметриялық криптожүйелерімен қатар болып қолданылды, олардың тұрақтылығымен үлкен сандарының факторизациясымен байланысты мәселесіне негізделген болып қолданылады. Асимметриялықтар криптографиялар бірден бірнеше қолданбалы болып бағыттар арқылы ашқан болатын, сонымен электронды сандық қолтаңба және электронды ақша болып айқындалды.
Жалпы айқтанда 80-90-жылдардағы фейстелдік еместігі шифрлар жасалды (SAFER, RC6), ал 2000-жылы ашық халықаралық сайыстан соң шифрлеудің АҚШ-тың жаңа ұлттық стандарттарының AES шықты болған болатын. Соғыстан кейінгілерінің кезеңнен бастап осы күндегі дейін есептеулері машиналардың пайда болуы болып криптографиялық әдістерінің жаңартылуларымен қатар өңделуін қамтамыз еткен болатын. Неліктен криптографиялық әдістерінің қолданулары ақпараттықтардың жүйелердің ең маңыздысы мәселесі болып айқындалды. Бір жағынанда, компьютерліктер торлардалары қолданулары арқылы кеңейді, негізіндегі, мемлекеттіктегі, әскери, коммерциялық және жеке түрдегілері ақпараттың өте үлкен мөлшеріндегі таратылатын ғаламдықтары торап интернет жүйесіндегілерінің қолданулары кеңейген болатын. Басқа жағындағылары, жаңа қуаттағылармен компьютерлердің пайда болуы болып табылған болатын, жүйелік немесе нейрондық есептеулердің технологиясымен қатар жақында ғана анықтаулары мүмкіндігі емес деп саналған криптографиялық жүйелердің дискредитациясына қол жеткізуге мүмкіндік берілген болатын. Ақпаратты түрлендірулері арқылы қорғаулар мәселесімен криптологиялары (kryptos - құпия, logos - ғылым) пайдаланатын болып табылады. Криптологиялары екі бағытқа бөлінетін болады - криптографиялары және криптоанализ болып табылады. Бұлардағы бағыттардың мақсаттары қарама-қарсы болып табылады.
Криптография ақпаратты түрлендіруде математикалық әдістерді іздеу және зерттеумен айналысады. Криптоанализдің айналысатын сфералар жүйесі - ақпараттың кілтін білмей шифрын анықтау.
Қазіргі криптография өзіне 4 үлкен бөлімді қосады:
- симметриялық криптожүйелер;
- ашық кілтті криптожүйелер;
- электрондық қолтаңба жүйелері;
- кілттерді басқарулары.
Криптографиялық әдістерінің қолданудың негізгі мақсаты - байланыс каналдары арқылы жасырын ақпаратты таратулары (мысалы, электрондық пошталар), жіберілгендігі хабарламалардың ақиқаттығы, шифрлі түрде ақпаратты сақтаулар болып табылады.
Криптографиялық жүйелерінің қаншалықты қиындары және сенімді болғанымен олардың практикалық қолданылуының әлсіз жағы-кілттерді үлестіру мәселесі болып табылады. Ол үшін ақпараттық жүйелерінің екі субьектісімен олардың арасындағы жасырын ақпараттарын алмасулары мүмкін және кілт солардың біреуімен генерацияланулары қажжет болып табылалады, жасырын түрдегі әрі қарай басқасына жіберілуі қажет болып табылады. Дегенмен барлық кілтті таратулар үшін криптожүйелерді қолдану қажет болып табылады. Бұл мәселені классикалық және қазіргідегі алгебрадан алынған нәтижелері негізінде шешулер үшін ашық кілтті жүйелер ұсынылатын болып табылады. Бұлардың барлық мәні ақпараттық жүйелерінің әрбірдегі хабар алушысымен екі кілт генерацияланады, олар бір-бірімен белгілі ережелерге сәйкес байланысты болады. Бір кілт ашық, екіншісі жабық болып жарияланатын болады. Ашық кілт жарияланады және кез-келген хабарлама жібергісісінің келетін адам үшін белгілі болып айқындалады. Құпия кілт жарияланбайтын болады.
Сонымен қатар бастапқы мәтіндегі хабар алушының барлық ашық кілтімен шифрленіп, оларға жіберілетін болады. Шифрленген мәтіндердің негізінен ашық кілтпен байланысты шифры анықталулары мүмкін емес болып табылады. Хабарламаны дешифрлеулер тек хабар алушыға ғана белгілі болатын жабық кілтті қолданулар арқылы ғана мүмкіндік болып саналады. Ашық кілтті криптографиялықтар жүйелер қайта оралмайтын немесе біржақты функциялар деп аталатындықтан ортақ қасиеті бар жұмыс істейтін болады. Берілген х үшін f(x ) мәнін есептеу оңай болып табылады , алайда тек y = f(x ) болса, х есептеудің оңай тәсілі жоқ дегенді білдіреді.
Жалпы біржақты функциялардың көптеген кластары ашық кілтті жүйенің көптүрлілігін тудындайтын болады. Алайда біржақтылары функциялардың барлығымен қатар ақпараттық жүйесінде қолдануға жарай берілмейтін болады. Қайта оралмайтындар деген түсініктемелерде теориялық қайта ораламсыздығы еместігі, белгіленген уақыттары интервалында қазіргі уақыттағы есептеу құралдарын пайдалану арқылы кері мәнін практикалық тұрғыдан есептей алмау болып айқындалады. Сонымен қатар, ақпаратты тиімді сақтаулары үшін ашық кілтті жүйелерге екі айқын әрі маңызды талап қойылатын болады:
- бастапқы мәтіндерінің түрленуі қайтымсыз болу қажет болады және ашық кілт негізінде қайта қалпына келмеу қажет болып табылады.
- ашық кілт негізінде жабық кілтті анықтаулары жаңа технологиялық тұрғыдан мүмкін емес болу қажеттігін білдіреді. Мұндай шифрды анықтауда күрделіліктерін төменгі бағасы көрсетілуі қажеттігін білдіреді.
Ашық кілтті шифрлеулер алгоритмдері кең қолданысқа ие болып табылады. RSA алгоритмдерінің ашық жүйелері үшін әлемдік дефакто стандарттары болып табылады. Қазіргі уақытта ұсынылатын ашық кілтті криптожүйелерінің қайтымсыз түрленудің төмендегідей топтарына жіктеліп қарастырылады, оларға жататындары мыналар:
- үлкен сандарды көбейткіштерге жіктеулер;
- соңғы өрісте логарифмді есептеулер;
- алгебралық теңдеулердің түбірлерін анықтаулар болып.
Ашық кілтті криптожүйелерді үш түрлі мақсатта қолдануға болады, оларға жататындар:
- жіберілген және сақтаудағы мәліметтердің өзіндік қорғаулары құралы ретінде болып саналады;
- кілттерді үлестіру құралы ретіндегеліре және ашық кілтті жүйелердег алгоритмдері дәстүрлі криптожүйелермен салыстырғанда аса көп еңбекті қажетті болып табылады;
- тұтынушыларды аутентификациялаулары құралы ретінде болып табылады.
1. 2 Күрделілік теориясыКүрделілік теориясында криптографиялық әдістерімен алгоритмдердің әр түрлі есептеулерінің күрделіліктеріне қарай әдістемелік талдаулар жасауға мүмкіндік бере алады. Олар дегеніміз криптографиялық әдістермен қатар алгоритмдерін салыстырулары арқылы, оның қаншалықты қауіпсіздігіне екендігін анықтайтын болады.
Алгоритмнің күрделілігіне жататындар : Алгоритмнің күрделілігі оның орындалуға байланысты керекті есептеуліктері қуаттарымен бірге есептеледі. Есептемелік алгоритмнің жалпы күрделілігімен қатар мынадай екі параметрмен өлшенетін болады, олар: T (уақытқа байланыстағылары туындайтын күрделілік) және S (кеңістікке байланыстылары туындайтын күрделілік және жадыға қойылатын талаптары) болып табылады. Дегенмен жалпы T және S , n айнымалысына тәуелділігі функция ретінде қарастырылатын болады. Мұндағы, n-бұл қабылданғандағы ақпараттардың шамасы болып табылады. Жалпы айтқанда есептемелік алгоритмнің күрделілігін жалпы функциясы арқылы жазылады. Олар күрделілік функциясының жай бөлшектерге жіктеулерінің түрлері болып табылады. Мысалыға айтар болсақ, егер 4 n 2 +7 n +12 алгоритмінің уақытқа байланыстылығы туындайтын күрделілігі болғандықтан, есептеулік күрделілігі n 2 болып келеді, оны О(n 2 ) деп белгілейтін боламыз.
Алгоритмдерді жалпы олардың уақыттық және де кеңістіктік күрделілігіне қатар олармен байланысты жіктейтін болады. Егерде алгоритм n -ға тәуелді болмаса, онда ондай алгоритмдерді тұрақты деп атап атады, О(1) деп белгілейді. Егер уақыттық күрделілігі О(n) болып табылса, онда алгоритмді сызықтық деп атайтын боламыз. Сонымен қатар жалпы алгоритмдердің квадраттықтылығы, кубтық немесе тағы да басқа түрлері болып табылады. Бұлар дегеніміз алгоритмдердің барлығы-полиноминалды болып айқындалады, ал олардың күрделілігімен қатар О(n m ), мұндағы m - тұрақты шама болып табылады. Уақыттық күрделілігімен қатар барлық жалпы қарастырылған полиноминалды алгоритмдерді полиноминалды уақыттық алгоритмдер деп санайтын боламыз.
... жалғасы- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.

Ақпарат
Қосымша
Email: info@stud.kz