Базалық құрлымдардан олардың суперпозицияларын нақты бір есептің шарттарына сәйкес құру мүмкіндігі,модулділік,декомпозиция мүмкіндігі

Алгоритм тармақталған деп аталады

жүктеу/скачать 81,93 Kb. бет 6/10 Дата 18.08.2023 өлшемі 81,93 Kb. #105382 түрі Программа

Бұл бет үшін навигация:

• Алгоритм сызықты деп аталады
• O(1) – жұмыс уақыты тұрақты, ол тапсырма өлшеміне тәуелді емес, O(n) - тапсырма өлшемін екі еселеу, әрі керекті уақытты екі еселеу , O(n 3
• Ο – күрделіліктің жоғарғы бағасы ; Ω – күрделіліктің төменгі бағасы, Θ – күрделіліктің нақты бағасы
• Θ(g(n)), егер, n>n 0 үшін c 1 *g(n) 2 *g(n), теңсіздігін қанағаттандыратын оң константалар c 1 ,c
• үшін 0 және n 0 табылса ; f(n)= Ω(g(n)), егер, n>n 0
• : O(1), O(N), O(N 3 ); O(N), O(NlogN), O(2 N ) O(logN), O(N 3 ), O(2 N )
• O(1), O(n), O(2 n ) ; O(log n), O(n 2 ), O(n n ) O(nlog n) O(n 3 ), O(2 n )
• Динамикалық айнымалылар үймелерде программа орындалуының барысында құрылады

Алгоритм тармақталған деп аталады, егер оның орындалу жолы қандай-да бір шарттардың шынайылығына тәуелді болса Алгоритм циклдық деп аталады, егер ол, оның орындалуы алдын – ала белгілі болып табылатын бірдей әрекеттердің көп рет қайталануы керек екендігін көрсететіндей етіп құрылған болса Алгоритм сызықты деп аталады, егер оның командалары қандай-да бір шарттардан тәуелсіз табиғи түрде бірінен соң бірі тәртіппен орындалатын болса Алгоритм сұлбаларының фрагменттерінің осы алгоритм түрлеріне дұрыс сәйкестігі: «Тораптағы торап» түріндегі алгоритм «Циклдағы цикл» түріндегі алгоритм «Толық емес торапқа кірістірілген цикл» түріндегі алгоритм Cызықты программа болып табылатын мінездемелік белгілері: операторларды олардың жазылу реті бойынша орындау, программада цикл операторларының болмауы, программада шартты және шартсыз өту операторларының болмауы Алгоритмдердің асимптотикалық уақыттық күрделілік белгілеулеріне берілетін корректілі түсініктемелері: O(1) – жұмыс уақыты тұрақты, ол тапсырма өлшеміне тәуелді емес, O(n) - тапсырма өлшемін екі еселеу, әрі керекті уақытты екі еселеу , O(n3) - тапсырма өлшемін екі еселеу, керекті уақытты сегіз есе өсіреді Алгоритмдердің күрделілігінің асимптотикалық талдауында грек әріптері келесіні білдіреді: Ο – күрделіліктің жоғарғы бағасы ; Ω – күрделіліктің төменгі бағасы, Θ – күрделіліктің нақты бағасы Алгоритмдер күрделілігінің асимптотикалық бағасы Ω, Θ, Ο мен a және b сандарының арасындағы қатынастар үшін келесі пареллельдерді жүргізуге болады: f(n) = Ο (g(n)) ≈ a ≤ b; f(n) = Θ (g(n)) ≈ a = b; f(n) = Ω (g(n)) ≈ a ≥ b Алгоритмдер күрделілігінің асимптомикалық нақты бағалауының рефлексивтілік, симметриялық және транзитивтілік қасиеттері f(n) = Θ (f(n)) ; f(n) = Θ (g(n)) ↔g(n) = Θ (f(n)) ; f(n) = Θ (g(n)) және g(n) = Θ (h(n)) → f(n) = Θ (h(n)) Алгоритмдер күрделілігінің О-бағалануы үшін келесі арақатынастар шынайы: O(k*f) = O(f); O(f*g) = O(f)*O(g); O(f+g), O(f) және O(g) доминантына тең Алгоритмдер күрделілігінің асимптотикалық бағалануының дұрыс интерпретациясы: f(n)= Θ(g(n)), егер, n>n0 үшін c1*g(n)<=f(n)<=c2*g(n), теңсіздігін қанағаттандыратын оң константалар c1,c2 және n0 табылса ; (n)= Ο(g(n)), егер, n>n0 үшін 0және n0 табылса ; f(n)= Ω(g(n)), егер, n>n0 үшін 0<=c*g(n)<=f(n) теңсіздігін қанағаттандыратын оң константалар cжәне n0 табылса Кәдімгі NP-толық есептер: коммивояжер есебі иыққап жайындағы есеп гамильтон циклын табу есебі Алгоритм күрделілігінің кластары еңбексыйымдылығының өсу реті тәртібімен орналасқан варианттары: O(1), O(N), O(N3); O(N), O(NlogN), O(2N) O(logN), O(N3), O(2N) Алгоритм түсінігін қалыптастыру үшін келесі жолдар белгілі: ақырлы және ақырсыз автоматтар теориясы; есептеу (рекурсивті) функциялар теориясы; Черчтің -есептеулері , f(n)=2n/100-100 кезінде, f(n)=n! кезінде, кезінде f(n)=9.3n2+107.4n+103 функциясының тәртібі келеі түрде болады:O(n2), O(2n), O(nn) Жай өсетін функциялардан жылдам өсетін функцияларға ауысу жылдамдығы келесі функция критерилері бойынша реттелген, оны келесі варианттардан көруге болады: O(1), O(n), O(2n) ; O(log n), O(n2), O(nn) O(nlog n) O(n3), O(2n) Компьютердегі бүтінсанды және нақты арифметиканы салыстыру:Бүтін сандар өздерінің нақты мәндерімен көрсетіледі, ал нақтылар – жуықталған; Бүтін санды арифметика операциялары нақты арифметика операцияларына қарағанда жылдам орындалады; Бүтін санды деректер нақтылармен салыстырғанда анықталған мәндер диапазоны аз болады Рекурсивті триада (есепті рекурсивті әдіспен шешу этапы): параметризация база бөлу декомпозиция n=3, n=4, n=5 болған кезде Фибоначчи сандарын есептеу үшін рекурсивті шақырулар саны тең: 5,9,15 Горнер сұлбасын қолдана отырып, алдын-ала коэфиценттерді өңдеу арқылы және тікелей түрде x4+a1x3+a2x2+a3x+a4 көпмүшесінің мәндерін есептеу кезінде орындалатын көбейтулер саны: 2,3,9 Арифметикалық операциялардың күрлелілігіне байланысты өсу ретімен орналасқан нұсқалары:қосу, көбейту, бөлу ; алу, көбейту, бөлу ; қосу, көбейту, дәрежеге шығару Есептеулерді жылдамдату үшін геометриялық прогрессияның арифметикалық, прогрессияның шексіз кемуімен геометриялық прогрессияның қолданылатын формулалар: ; ; Көпмүше түріндегі деректер түрімен келесі операциялар орындалуы мүмкін: қиылысу айырым біріктіру Құрылымдалған деректер түрі: көпмүше жазбалар массивтер Сызықты құрама құрылым деректеріне: граф ағаш мультитізім Элементар деректерге: символдық түрдегі деректер, көрсеткіш түріндегі деректер, логикалық түрдегі деректер Нұсқаушылар үшін негізгі операциялар:меншіктеу, адресін алу,таңдау Нұсқаушы айнымалысы үш күйде бола алады:Жады бөлінген қандай-да бір айнымалының адресінен тұрады, Арнайы бос nil адресінен тұрады, Анықталмаған күйде болады Динамикалық айнымалылардың біркелкі корректілі бекітімдері: Динамикалық айнымалылар үймелерде программа орындалуының барысында құрылады, Динамикалық айнымалылардың өз атаулары болмайды, Динамикалық айнымалыларды жіберілетін сәйкес типтегі өлшемдерге арналған операцияларда қолдануға болады Сыртқы деректер құрылымына: тізбекті қатынау файлдары, деректер қоры, өз еркінше қатынау файлдары Сызықты емес құрылымдар: графтар,ағаш,мультитізім Деректер түрі анықтайды: компьютер жадысындағы көрсетілім форматын, осы түрге жататын айнымалы немесе тұрақтыны қабылдайтын, рұқсат етілген мәндер көпмүшесі, осы түрге қолданылатын мүмкін операциялар көпмүшесі Тек сызықты байланысқан құрылымдар: екілік байланысқан тізімдер, кезектер; бір байланысқан тізімдер, стектер; дөңгеленген тізімдер, дектер Төменде көрсетілген тізбек бойынша бірінші екі команда, бірінші төрт команда, барлық алты команда орындалғаннан кейін стек құрамы қалай өзгереді, бұл кезде стектің бастапқы күйі (стек басы – сол жақта) орналасқан: push(a), push (b), pop, push (c), pop, push (d) жауап: ba,ca,da Төменде көрсетілген тізбек бойынша бірінші екі команда, бірінші төрт команда, барлық алты команда орындалғаннан кейін стек құрамы қалай өзгереді, бұл кезде бастапқы күйде кезек бос, яғни (кезектің басы – сол жақта, ал соңы – оң жақта) орналасқан:enqueue(a), enqueue(b), dequeue, enqueue(c), enqueue(d),dequeuer жүктеу/скачать 81,93 Kb. Достарыңызбен бөлісу: