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

Тиімді, жылдам жұмыс істейтін алгоритмдер құрудың практикалық есептер шығаруда бірінші дәрежелі болмаса да, үлкен мәні бар. Бірнеше алгоритмдердің ішінен жылдам жұмыс істейтін алгоритмді таңдау үшін олардың жұмыс уақытын салыстырып үйрену қажет. Дегенмен, жұмыс уақытын дәл есептеу мүмкін емес. Бұл уақыт алдымен программа орындалатын компьютердің шынайы сипаттамасына тәуелді болуы мүмкін. Әдетте алгоритмнің орындалуы уақыты тек жуықтап қана есептеледі. Сонымен бірге жұмыс уақытына арналған формула мәндері тек тәжірибелік жолмен анықталатын қандай да бір сандық тұрақтылардан тұрады. Мұндай бағалаудың өзі көбінесе ең тиімді бір алгоритмді ғана таңдауға мүмкіндік береді. Басқа жағдайларда жұмыс уақытын бағалаудың көмегімен баяу жұмыс істейтін алгоритмдерді шығарып тастауға болады, ал қалғандарынан программаның шынайы жұмыс уақытын өлшеудің көмегімен таңдауға болады.
Енді жоғарыда айтылғандарды мысалмен түсіндірейік. Мысалы, қандай да бір n саннан құрылған тізбекті өңдеу қажет болсын. Мұндағы n өзгеріп отыратын болсын. Осы есепті шығаруға екі программа берілсін, олардың жұмыс уақыты жуықтап С1n C2n2, мұндағы С1 және С2 –- тұрақтылар, олар n-ге тәуелсіз. N үлкен болған жағдайда бірінші программа жылдам жұмыс істейді, ал n аз шама болғанда программа баяу жұмыс істейді. Бұл С1 > С2 екенін көрсетеді. С1 С2 -ден 5 есе үлкен болсын. С1 =5С2 . С1 n =5С2 n мен C2n2-ты салыстыра отырып, n>5 болғандағы программаның жұмыс уақытының баяу, ал n<5 болғанда екінші программаның жылдам жұмыс істейтінін байқауға болады. Мұндағы n =5 бағалау уақытының шектік мәні де жуықтап тағайындалады.
Бұдан екі тұжырым жасауға болады. Біріншіден, «тұрақтыға дейінгі дәлдікпен» жуықтап бағалаудың өзі алгоритмдерді салыстыруда пайдалы болып табылады. Екініден, есеп шығарудың бір алгоритмі өте жылдам деп айтуға болмайды. Қандай да бір алғашқы мәліметтер жиынтығы үшін кейбір алгоритм екіншісінен тиімді болуы мүмкін.
Енді программаның жұмыс уақытын анықтайтын алғашқы мәліметтердің мұндай сипаттамасын таңдау мәселесіне тоқталайық. Мұндай сипаттама есептің өлшемі деп аталады. Әртүрлі есептерді шығару уақытына алғашқы мәліметтердің әртүрлі қасиеті әсер етеді. Мысалы, минимумды іздеу немесе әрбір сан бір бүтін сан ретінде қарастырылатын берілген сандарды іріктеу типті есептер үшін алғашқы сандар мөлшері есептер мөлшері болып табылады. Қарапайым көбейткіштерге жіктеу есебі үшін санның шамасы мөлшері болып есептеледі. Есеептің мөлшерін таңдау қандай да бір шығару алгоритмі туралы жалпы ұғымға негізделеді. 2n дәрежесін есептеу алгоритмін қарастырайық. Дәрежелеудің санның бірінен соң бірі көбейтілетінін ескере отырып, өлшем ретінде n дәреже көрсеткішті аламыз. Өлшемді сипаттаудың тағы бір тәсілі нәтижедегі цифр сан ыболып табылады. 2n дәрежесіндегі цифр саны n-ге пропорционал, сондықтан екі өлшем де эквивалентті.
        
        Лекция № Алгоритмдерді талдау .
Тиімді, жылдам жұмыс істейтін алгоритмдер құрудың практикалық есептер
шығаруда бірінші ... ... да, ... мәні бар. ... ішінен жылдам жұмыс істейтін алгоритмді таңдау үшін олардың
жұмыс уақытын салыстырып үйрену қажет. ... ... ... дәл ... ... Бұл ... ... программа орындалатын компьютердің шынайы
сипаттамасына тәуелді болуы мүмкін. Әдетте алгоритмнің орындалуы уақыты ... қана ... ... ... ... ... ... формула
мәндері тек тәжірибелік жолмен анықталатын қандай да бір ... ... ... ... өзі ... ең тиімді бір
алгоритмді ғана таңдауға мүмкіндік береді. Басқа ... ... ... ... баяу жұмыс істейтін алгоритмдерді ... ... ал ... ... шынайы жұмыс уақытын ... ... ... ... айтылғандарды мысалмен түсіндірейік. Мысалы, қандай да
бір n саннан құрылған тізбекті ... ... ... ... n ... ... Осы есепті шығаруға екі программа берілсін, олардың жұмыс
уақыты жуықтап С1n C2n2, мұндағы С1 және С2 –- ... олар ... N ... ... ... бірінші программа жылдам жұмыс істейді,
ал n аз шама ... ... баяу ... ... Бұл С1 > С2 ... С1 С2 -ден 5 есе үлкен болсын. С1 =5С2 . С1 n =5С2 n ... ... ... n>5 ... ... ... уақытының
баяу, ал n=A-1 болса, онда ... саны B - A +1 –ге ... B1, N1 ... ... ... жұп). Ішкі цикл бір ... кейін N1 2-ге бөлінеді. Екілік жүйеде екіге бөлу ең кіші
цифрды шығарып тастағанмен ... ... ең кіші ... ... үшін ... бір рет ... ... N1≤1, N1 бірмен аяқталады (тақ). Ішкі цикл ... ... ... ... ... яғни N1 жұп ... қалады. Сөйтіп, 2-жағдайға
келеміз. Ең кіші бірлікті өңдеу үшін ішкі және ... ... бір ... ... ... соң бірі өңделіп, N1 цифрының барлық екілік цифрлары ... ... ... N1= N ... ескере отырып,
К1 = N-нің екілік жазылуындағы берліктер саны,
К2 = (N-нің екілік ... ... ... ... ... ... цифрлар саны N-нің екілік логарифмінің бүтін
бөлігін 1-ге арттырғанмен бірдей, яғни
К2 = [log2N].
К2 үшін мұндай қарапайым формуланы жаза ... ... К1 ... ғана ... ... ... саны цифрлар санынан ... ... ...... ∙ Т1 + [log2N] ∙Т2 =( Т1 + Т2) ∙ [log2N] + Т1 ... N ... ... тек 1-лермен жазылған жағдайда ғана теңдік
орындалады, яғни екінің дәрежесі 1-ге кем. N ... ... ... ... аз ... онда Dareje функциясы соншалықты жылдам
жұмыс істейді. Егер N екінің дәрежесі болса, К1 ... ... ал ... = Т1 + log2N ∙Т2 .
Енді Dareje ... ... ... ... ... ... ... – дәреженің негізі, N – дәреже көрсеткіш}
Var M1,N1,P:integer; {Р –нәтижені есептейтін ... M1:=M; ... N10 ... P:=P* ... ... жұмыс уақытын ТС(N), ал циклдың бір рет орындалуын ТС1
арқылы белгілейік.
ТС(N)≈ N · ТС1 ... N ... ... log2N баяу өсетіндіктен, N-
нің шамасы өте үлкен болған жағдайларда Т(N)< ТС(N) болады, N-нің ... ... ... та ... Енді ... N-нен бастап Dareje
функциясы ... ... ... қарастырайық.
Әрбір циклда ... ... ... ... ТС1 ≈Т1 ≈Т2 деп
есептеуге болады. ... ТС1 ·(2∙ ... ... 2∙ [log2N]+15 екенін табамыз. N-
нің шекаралық мәнін іздеуде T(N) үшін жоғарыдан бағалауды пайдаландық. N-
нің 1-ден 5-ке ... ... жеке ... ... N=1,2,3 мәндері
үшін Dareje функциясы tyzusyzykty функциясы тәрізді көбейтуді орындайды, ал
N=4,5 мәндерінде көбейту аз ... Бұл N-нің ... ... ... ... пайдалануға болатынын көрсетеді.
Талдауды қорытындылайтын болсақ, егер FOR циклында қайталану саны
айнымалы болып, программада ... ... ... ... ... ... қолдануға келмейді, программа жұмысын мазмұнды талдауды
талап етеді. Ал, While-Do және ... ... одан да ... ... Бұл қайталанулар үшін қайталанудың жалпы формуласын жазуға
келмейді. Бұдан барлық ... ... ... ... ... ... ... формуласын табу мүмкін бола бермейді. Алгоритмді
бағалауда кейде құрғақ ақпаратпен ... тура ... ... ... ... болатын көбейткіштерді таңдауға негізделген санды қарапайым
көбейткіштерге ... ... орын ... Сонымен бірге, сан жай сан
болса, таңдауды соңына дейін жүргізуге тура келеді, алдымен санның жай ... көз ... ... Бұл алгоритм үшін жұмыс уақытын ... ... ... ... TMAX(N) ... N өлшемді есеп үшін шынайы
жұмыс уақыты TMAX(N)-нан артпайды және кейде осы шаманың өзіне тең болады.
Жұмыс уақытын ... ... ... алгоритмді салыстырумен қатар,
өлшенген жұмыс уақытын басқа есептің өлшеміне экстрополяциялау ... ... ... 210000 ... ... ... болсын. Мұның
едәуір уақыт алатынын алдын-ала айтуға болады. Ол үшін 21000дәрежесін
есептеп, есептеу ... ... ... ол 30 ... тең ... ... ... 10*10=100 есе көп болады, 3000 секундты, яғни 50 минутты
құрайды. Бұл 210000 дәрежесін есептеу одан да жылдам алгоритм іздеуді ... ... ... …, U(K) ... ... ... мүшелері берілген болса, онда
U(1), U(2), …,U(N) тізбегінің элементтері К ретті рекурентті тізбекті
құрайды ... ал N>К ... ... ... Ғ – К ... ... да бір ... ретті пекуррентті тізбекті белгілі мысалы Фибоначчи сан тізбегі
болып табылады., оның
U(1)=U(2)=1, ал N>2 үшін
U(N)=U(N-1)+U(N-2).
Бірінші ... ... ... ... – а санынан квадрат түбірді
Ньютон әдісі бойынша есептеуге арналған тізбек: U(1)=a+1, ал N>1 ... ... ... ... ... ... Тізбектің N-ші элементін есептеу.
2. Берілген G(U(N), U(N-),…,U(N-K)) логикалық ... ең ... ... есептеу.
Бұл екі есепті шығару үшін тізбектің К+1 элементін жадыда сақтау қажет.
К1=К+1. Онда К+1 элементті ... ... ... ... ... ... OF тізбектегі
есептелген ... ... T[K+1] ... ... есепті шығаруда екі негізгі кезеңге бөлінеді:бастапқы шар ... ... ... ... ... ... жазуға болады:
T[2]:=U(1);…;T[K+1]:=U(K);
Ал тізбек болйынша бір элементке алға ... ... I:=1 TO K DO ... ... ... ... біріншісінен бастап, мәнді келесі элменттен
бастап алады. Соңғы элементтен мәнін алғаннан кейін, F ... ... ... жаңа мән қабылдайды. Келесі есептеуге ... ... ескі мәні ... ... ... және 2-есептер тізбек бойынша болатын орын ... ... ... ... ... N-K-ға тең, өйткені T[K+1]
алғашқы шарттан кейін тізбектің К-элементін сақтайды, ... ... ... Жылжуды қайталау үшін FOR қайталануын пайдаланған ыңғайлы:
FOR J:=K+1 TO N DO
BEGIN
FOR I:=1 TO K DO ... G ... мәні ... ... ... ... ... жағдайда жылжуды қайталау үшін REPEAT-UNTIL қайталануын пайдаланған
ыңғайлы:
REPEAT
FOR I:=1 TO K DO ... ... ... ... ... N-Фибоначчи санын есептеу функциясын
қарастырайық:
Function ... ... N – ... ... нөмірі,
ол N>0 деп есептелінеді}
Var I,J:integer;
T:ARRAY[1..3] OF INTEGER;
Begin
{бастапқы шарт}
T2:=1; T3:=1
{жылжуды қайталау}
FOR J:=3 TO N ... I:=1 TO 2 ... ... ... ... ... массивті пайдаланбай-ақ,
тізбек элементтері сақталған айнымалыларды жеке атаулармен ... ... ... ... ... ... FOR ... К меншіктеулермен
алмастырылады. 2-есепті шығару мысалы ретінде А санынан берілген дәлдікпен
квадрат түбірді есептейтін ... ... ТЕК ... түбірге
ағымдағы жуықтатылған мәнді, ал АР айнымалысы алдыңғы ... ... ... ... ... ... ... әдістерінде, егер түбір бар болатын болса, (2), (3) ... дәл ... өте ... ... (3) ... әрбір қолданылуы
алдыңғы жуықтаудың дәл мәндерінің мөлшерін жуықтап екі еселейді.
Бұл процесс
(4)
теңсіздігі орындалғанда ... ол ... ... ... ... ... (3) ... процестерді
, ... ... ... ыңғайлы. Мұндағы dYk – алдыңғы жуықтауға түзету.
Егер
(6)
шарты қанағаттандырылатын болса, итерациялық процесті тоқтатуға болады. Бұл
түзету талап етілген ... ... ... ... мен (5) ... ... ... өте қарапайым жүргізіледі:
алдымен dYk, одан кейін Yk+1 есептеліп, Е-мен салыстырылады.
(3) теңдеуден dYk-ны есептеу ... ... ... ... ... ... ... Y0=1, (7), (5) түбірді жуықтап
есептеу алгоритміне пайдаланамыз, ... ... ... ... ... жүргіземіз.
(8)
Бұл алынған түбірді жуықтап есептеудің m ақиқат ... ... ... X, m, нәтиже Y. Түзету үшін d, салыстырмалы
қателікті бағалау үшін Е айнымалыларын пайдаланамыз.
Бұл алгоритмнің сөзбен жазылуы төмендегідей:
Аргументтер: X, ... ... ... d, ... ... егер Х>0 ... онда 4-ге ... Тоқта, яғни түбір жоқ
4.
5. Y:=1
6.
7. Y:=Y+d
8. Егер , онда 5-ға ... ... ... ... ... алгоритмі. Есептің қойылысы:
Х=с(а- b) - мәнін есептеңіз.
Енді осы алгоритмнің сөзбен жаызлуын келтірейік.
Аргументтер: a, b, с.
Нәтиже: х
Аралық шамалар: Q, P.
0. ... Q:= ... Р:= ... ... Х:=Р- Q
5. ... ... қосындысын есептеу. Есептің қойылысы: сандар
берілген, олардың қосындысын табу қажет.
Алдымен белгілеулер енгіземіз: n - ... ... x1, ... ... ... S – ... ... есептеу үшін сызықтық алгоритмді пайдалануға болар
еді.
1. Басы
2. S:=x1
3. S:=S+x2

N S:=S+xn
4. Соңы
Бірақ мұндай алгоритмдегі қадамдар саны өте көп. Егер n=1000 ... ... ... тура ... ... ... құтылу үшін циклдық
алгоритм құрамыз. Ол үшін ... ... ... ... ... есептегішімен байланыстырамыз және қосылатын сандар индексін
–көрсеткішін енгіземіз. Индекстің мәні айнымалының ... ... ... ... үшін і ... ... Нәтиже S айнымалысына
меншіктеледі, яғни нәтижеге әрбір кезекті сан ... ... ... S ... бастапқы мәні 0-ге, ал і қайталану параметрінің
бастапқы мәнін 1-ге тең деп аламыз. і:=і+1 индекстің өзгерісімен, і ... ... ... ... S:=S+xі орындала береді. Бұл
жағдайда і индексі қосылған сандар мөлшерін есептейтін ... ... тұр. ... мәні ... отыр, сондықтан ол тура есептегіш деп
аталады.
Сонымен ... ... ... кері есептегішпен де жүргізуге болады,
бұл жағдайда алдымен і= n деп аламыз да, ... ... ... ... ... ... отырамыз: і:=і-1. Бұл жағдайда қайталану і>0 болғанша қайталана
береді.
А) Берілген n санның қосындысын тура ... ... ... n, x1, ... ... шама: і
1. Басы
2. S:=0
3. і: = 1
4. S:=S+xі
5. і:=і+1
6. Егер іn ... онда 4-ке ... ... ... n санның ішінен ең үлкенін табу алгоритмі. Есептің
қойылысы n саны берілген. Олардың ... ең ... және оның ... ... ... ... n, x1, x2,…,xn
Нәтижелер: R - сандардың ең үлкен мәні, m - ең ... ... ... ... ... Басы
2. R:=x1; m:=1
3. і: =2
4. егер xіc[k] then
begіn
r:=c[k-1];
c[k-1]:=c[k];
c[k]:=r
end;
wrіteln('a massіvі:');
for і:=1 to n1 do wrіte(a[і]:5:2,' ');
wrіteln;
wrіteln('b massіvі:');
for і:=1 to n2 ... ... ... і:=1 to n1+n2 ... untіl ... ... ... элементтерін сұрыптауда қойылатын ... ... ... ... ... әдісі жадыны тиімді пайдалануда болып
табылады. Бұл элементтерджі ретке келтіретін орын ауыстырулар сол ... ... ... ... ... ... ... шектеле
отырып, мүмкін болатын әдістердің арасынан қажеттісін таңдау қажет, ол үшін
алдымен әдістерді олардың үнемділігі ... яғни ... ... ... ... ... қажет. Тиімділіктің өлшемі ретінде: С-қажетті
салыстырулар кілтінің санын және М- ... ... ... ... ... ... n – ... санының негізгі мәні болып табылады.
Сұрыптаудың тиімді алгоритмдері n*log n салыстыру ретін ... ... ең ... ... ... тура әдіс деп атайды, мұнда
салыстырулар ... n2 ... ... Тура ... ... ... себептер бар:
1. Тура әдіс көптеген сұрыптааулардың негізгі ... ... ... Бұл ... ... түсіну әлдеқайда жеңіл, ... ... ... өзі де ... орын ... ... ... көптеген операцияларды орындауды ... бұл ... ... де ... ... тура әдіс
кіші n үшін айтарлықтай жылдам болып табылады.
«Сол орында» сұрыптау ... ... ... ... ... ... ... болады:
1. Жалғау көмегімен сұрыптау.
2. Ерекшелеу көмегімен сұрыптау.
3. Алмастыру ... ... қосу ... ... әдіс ... ойынында кеңінен пайдаланылады. Элементтер ойша
a1,…,aі-1 «дайын» ... және ... ... ... ... бөлінеді.
Әрбір қадамда і=2 бастап, і-дің мәнін 1-ге арттыра ... ... і-ші ... шығарылып тасталынады да, дайын тізбекке ... ... ол жаңа ... ... ... ... сандарды тікелей жалғау көмегімен
сұрыптаудың мысалы төмендегідей:
Алғашқы кілттер 44 55 12 42 94 ... ... 44 55 12 ... 18 06 ... 12 44 55 ... 18 06 ... 12 42 44 ... 18 06 ... 12 42 44 ... 18 06 ... 12 18 42 ... 94 06 67
і=7 06 12 18 ... 55 94 ... 06 12 18 ... 55 67 ... ... ... ... і:=2 To n Do
X:=a[і]; {x-ті a[1],…,a[і] арасындағы сәйкес ... ... ... ... ... ... мен жылжуды алмастыра
отырып, електен өткізу болып табылады. Х ... aj ... одан ... х не бос ... қойылады, не aj оңға қарай
жылжиды, ал процесс солға ... ... ... ... процесі төмендегі
шарттардың бірі орындалғанда аяқталады:
1. х-тің кілтінен кіші кілтті aj ... ... ... тізбектің сол жақ шетіне жеткен жағдайда.
Сонымен, бұл ... ... ... і:=2 to n ... ... x

Пән: Информатика
Жұмыс түрі: Курстық жұмыс
Көлемі: 35 бет
Бұл жұмыстың бағасы: 700 теңге









Ұқсас жұмыстар
Тақырыб Бет саны
Алгоритмдерді Паскаль программалау тілінде әзірлеу10 бет
Алгоритмдердің концепциялары мен қасиеттері8 бет
Модельдеуші алгоритмдердің блок-схемаларын құру10 бет
Программаны құрудың техникалық тапсырмасы. Программаларды техникалық жобалау кезеңдерін сипаттау. Алгоритмдердің құрылымдық схемесын дайындау8 бет
Қолданбалы есептерге параллельді алгоритмдерді қолдану27 бет
Delphі ортасында жұмыс істеу технологиясы80 бет
DES алгоритмі20 бет
Іздеу есептерінің шешілімі. Іздеу: қайтару арқылы теріп алу4 бет
Алгоритм тілін оқыту әдістемесі31 бет
Алгоритмдік тіл және программалау тілі18 бет


Исходниктер
Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь