Muammoni o'zi nuqtai nazaridan aniqlash

Rekursiya
Rekursiya "muammoni o'zi nuqtai nazaridan aniqlash" degan ma'noni anglatadi. Bu algoritmlarni yozishda juda kuchli vosita bo'lishi mumkin. Rekursiya to'g'ridan-to'g'ri Matematikadan kelib chiqadi, bu erda o'zlari nuqtai nazaridan yozilgan ko'plab iboralar namunalari mavjud. Masalan, Fibonachchi ketma-ketligi quyidagicha aniqlanadi: F (i) = F (i-1) + F (i-2)

Rekursiya

Rekursiya - bu muammoning (yoki muammoning echimini) o'zi (sodda versiyasi) nuqtai nazaridan aniqlash jarayoni.

Masalan, "uyingizga yo'l toping" operatsiyasini quyidagicha aniqlashimiz mumkin:

Agar siz uyda bo'lsangiz, harakatni to'xtating.

Uyga bir qadam tashlang.

"uyingizga yo'l toping".

Bu erda uyga boradigan yo'lni topish uchun echim ikki qadam (uch qadam). Birinchidan, agar biz allaqachon uyda bo'lsak, biz uyga bormaymiz. Ikkinchidan, biz vaziyatni hal qilishni osonlashtiradigan juda oddiy harakatlar qilamiz. Nihoyat, biz butun algoritmni takrorlaymiz.

Yuqoridagi misol quyruq rekursiyasi deb ataladi. Bu erda eng so'nggi bayon rekursiv algoritmni chaqirmoqda. Quyruqning rekursioni to'g'ridan-to'g'ri ko'chadanga tarjima qilinishi mumkin.

Ma'bad maydonini topish uchun rekursiv "algoritm" ni qanday yozasiz?

Javob:
Rekursiyaning yana bir misoli - bu raqamlar ro'yxatidagi maksimal qiymatni topish. Ro'yxatdagi maksimal qiymat - bu birinchi raqam yoki qolgan raqamlarning eng kattasi. Algoritmning psevdokodini qanday yozamiz:

Function find_max( list )

possible_max_1 = first value in list
possible_max_2 = find_max ( rest of the list );
if ( possible_max_1 > possible_max_2 )
answer is possible_max_1
else
answer is possible_max_2
end
end
Rekursiv algoritm qismlari
Barcha rekursiv algoritmlarda quyidagilar bo'lishi kerak:

Asosiy ish (ya'ni qachon to'xtash kerak)

Base Case tomon ishlang

Rekursiv qo'ng'iroq (ya'ni o'zimizga qo'ng'iroq qiling)

"Asosiy ish bo'yicha ish" biz muammoni soddalashtiradi (masalan, ro'yxatni ikkiga bo'ling, ularning har biri asl nusxadan kichikroq). Rekursiv chaqiruv, biz muammoning sodda versiyasini hal qilish uchun bir xil algoritmdan foydalanamiz. Asosiy holat - bu mumkin bo'lgan "eng sodda" muammoning echimi (Masalan, "ro'yxatdagi eng katta raqamni topish" muammosidagi asosiy holat, agar ro'yxat faqat bitta raqamga ega bo'lsa ... va agar mavjud bo'lsa, ta'rifga ko'ra faqat bitta raqam, bu eng katta).

Oddiy misol: uchta raqamni qo'shing

Uchta raqamni qo'shish dastlabki ikkita raqamni qo'shib, so'ngra yana ikkita raqamni qo'shishga tengdir.

(Eslatma, Matlab-da funktsiyani barcha argumentlarsiz chaqirish mumkin. Nargin funktsiyasi kompyuterga qancha qiymatlar ko'rsatilganligini bildiradi. Shunday qilib add_numbers (1) ning narginasi 1 ga teng bo'ladi; add_numbers (1,1) ning narginiga ega bo'ladi. of 2; add_numbers (1,1,1) ning narg darajasi 3 ga teng bo'ladi.)

Matlab
function result = add_numbers(a, b, c)
if ( nargin() == 2 )
result = a + b;
else if ( nargin() == 3 )
result = add_numbers(a+b, c);
else
error('oops');
end
end
Rekursiv algoritmning 3 qismini aniqlang:
Barcha rekursiv algoritm quyidagi uch bosqichdan iborat bo'lishi kerak:

Asosiy holat: agar (nargin () == 2) natija = a + b;

"Asosiy holatga qarab ishlash": a + b birinchi parametrga aylanadi

Bu funktsiyaga yuborilgan parametrlar sonini (nargin) 3 dan 2 gacha qisqartiradi va 2 asosiy holat!

Rekursiv qo'ng'iroq: add_numbers (a + b, c);

Rekursiya nima uchun ishlaydi

Rekursiv algoritmda kompyuter muammoning oldingi har bir holatini "eslab qoladi". Ushbu ma'lumot kompyuter tomonidan "aktivizatsiya stekasida" (ya'ni har bir funktsiya ish joyining ichki qismida) "ushlab turiladi" .

Har bir funktsiya funktsiya uchun har bir qo'ng'iroq uchun o'z ish maydoniga ega .

Labirint namunasi:
Har bir xonaning shimoliy, janubiy, sharqiy va g'arbiy tomonlarida eshiklari bo'lishi yoki bo'lmasligi mumkin bo'lgan to'rtburchaklar xonalarni ko'rib chiqing.

Labirintdan chiqish yo'lini qanday topish mumkin? Javobni topish uchun bitta "algoritm" mavjud:

Hozirgi xonadagi har bir eshik uchun, agar eshik chiqishga olib boradigan bo'lsa, u eshikni oling.

Bu erda "hiyla-nayrang", albatta, eshik chiqadigan xonaga olib borishini qaerdan bilamiz? Javob biz emas, lekin biz buni kompyuterning o'zi hal qilishiga yo'l qo'yamiz.

Yuqoridagi algoritmning rekursiv qismi nimadan iborat? Uning "labirintadan eshigi" chiqadi. Labirintdan eshik chiqishini qaerdan bilamiz? Biz bilamiz, chunki qo'shni xonada (eshikdan o'tish) biz xuddi shu savolni beramiz, labirintdan qanday chiqamiz?

Nima bo'ladi, kompyuter barcha " nima bo'lsa " ni "eslab qoladi ". Birinchi eshikni olsam nima bo'ladi, ikkinchi eshikni olsam nima bo'ladi, agar keyingi eshikni olsam va hokazo. Va siz o'tib ketishingiz mumkin bo'lgan har bir eshik uchun kompyuter nima bo'lganligini eslaydi va undan keyingi har bir eshik uchun, va undan keyin va hokazo, oxirigacha topiladi.

Haqiqiy kodni amalga oshirishga yaqin.

Matlab
% return true if we can find our way out

function success = find_way_out( maze, room )
for every door in the room
new_room = go_through_door( maze, door )
if ( find_way_out ( maze, new_room ) )
take that door.
return true
end
end
% there were no ways out :(
return false
end
Savol: Yuqoridagi asosiy holat nima?

Javob: (Bu hiyla-nayrang savol edi) Kodda asosiy holat yo'q. Boshida xona chiqadigan joyni tekshirishingiz kerak. Agar shunday bo'lsa, rekursiya bo'lmaydi!

function success = find_way_out( maze, room )
if room is exit → return true
room ← mark as visited
% rest of code
...
end
Savol: Xonani tashrif buyurgan sifatida qanday belgilashingiz mumkin?

Javob: Turli xil texnikalar mavjud. Agar xona qurilish (yoki ob'ekt) bo'lsa, siz tashrif buyurgan maydon yo'nalishini xonaga qo'shishingiz mumkin. (masalan, room.visited = true;) Agar siz ob'ektlardan foydalanmasangiz, labirint bilan bir xil o'lchamdagi / shaklga ega bo'lgan mantiqiy bayroqlar matritsasiga ega bo'lishingiz va ushbu qiymatlardan foydalanishingiz mumkin.

Savol: Yuqoridagi algoritm bilan bog'liq boshqa muammolar bormi?

Javob: Bunga javobni quyidagi savolni o'ylab topishingiz mumkin: Agar labirint har bir devorda eshiklari bo'lgan bir xil o'lchamdagi to'rtburchaklar xonalarning ulkan panjarasi bo'lsa nima bo'ladi? Tasavvur qiling, siz birinchi eshikdan shimolga, so'ngra keyingi xonalar eshigi orqali sharqqa, keyin janubiy o'sha xonalar eshigi orqali, keyin g'arbga o'sha xonalar eshigi orqali o'tasiz. Qaerga tushasiz? Boshlagan joyingizga qayting! Eng yomoni, siz ushbu ko'chadan abadiy foydalanishni davom ettirishingiz mumkin. Qo'rqmas avantyur bu muammoni qanday hal qiladi?

Bunga bitta javob - bo'r parchasini ishlatish va har bir xonaning tagiga katta X qo'yish. Shunday qilib, polda X bo'lgan xonaga qaytib kelganingizda, kirishga hojat yo'qligini bilasiz. Dasturda "ko'rilgan" yoki "tashrif buyurilgan" mantiqiy bayroqdan foydalanish kerak. Har bir xonada bayroq bor. Har bir xona bayroqning noto'g'ri o'rnatilganidan boshlanadi. Bir xonaga tashrif buyurganingizda, siz bayroqni haqiqiy qilib o'rnatdingiz. Va nihoyat, "asosiy holatda" sizda quyidagi qator mavjud:

function success = find_way_out( maze, room )

% exit chack
if room is visited → return false
% rest of code
...
end
Rekursiyani kompyuter algoritmlariga bir xil darajada qo'llash mumkin:
Kompyuter bilan bog'liq ba'zi bir misollarga quyidagilar kiradi: Raqamlar ro'yxatini qo'shish, Fibonachchi ketma-ketligini hisoblash, Faktorial hisoblash va Sudoku.

Raqamlar ro'yxatini umumlashtirish:

Savol: Raqamlar ro'yxatini sarhisob qilishning rekursiv echimi qanday? Avval shuni ta'kidlash kerakki, [1 2 3 4 5 6 7 8 9]) ning yig'indisi [+ 3 4 5 6 7 8 9]) ning 1 + yig'indisiga teng))!

Javob:
Faktorial

Faktorialning ta'rifi qanday?

Javob: faktorial (X) = X * (x-1) * (x-2) * ... * 2

Hmmm, lekin "(x-1) * (x-2) * ... * 2" nimaga teng?

Javob: faktorial (X-1)

Agar biz ushbu ta'riflarni birlashtirsak nima bo'ladi!

Javob 3: faktorial (X) = X * faktorial (X-1);

Rekursiv faktorial funktsiyani yozishga imkon beradi.

Javob:
Fibonachchi

X joyda Fibonachchi sonining ketma-ketligi qanday ta'riflangan?

Javob: fib (x) = fib (x-1) + fib (x-2);

Bu rekursiv ta'rif.

Fibonachchi ketma-ketligidagi N sonini hisoblash uchun rekursiv funktsiyani yozishga ruxsat bering.

Javob:
Tartiblash
Rekursiyadan foydalanib raqamlar ro'yxatini qanday saralash mumkin?

1-maslahat: Uzoq ro'yxatni yoki qisqa ro'yxatni saralash osonroqmi?

Maslahat 2: Agar sizda ikkita tartiblangan ro'yxat bo'lsa, ularni qayta birlashtira olasizmi?

Javob
Sudoku

Sudoku-ni qanday hal qilishda kompyuterdan foydalanasiz? Raqamlarning har qanday kombinatsiyasini sinab ko'rishga nima deysiz? Izoh: bu qo'pol kuch ishlatish usuli. Mana bitta "algoritm":

Yuqoridagi chap "chelak" dan boshlab va har bir qatorda birma-bir ustun bo'ylab harakatlanish (keyin keyingi qator boshiga pastga va hokazo).

Paqir uchun yaroqli raqamni faraz qiling (nima yomon, shunchaki barcha 9 raqamni sinab ko'ring). IF, Gipoteza qilingan raqamga asoslanib, jumboqning qolgan qismini hal qilishingiz mumkin, siz jumboqni hal qildingiz!

Bu rekursiv algoritm! Har bir qutiga indeks / yorliq raqami berilgan deb taxmin qiling (1 dan 81 gacha):

Algoritmga umumiy nuqtai Pseudocode:

function solve_sudoku ( current_box_id )

if all the boxes are filled
return true; // solved!
end
// ignore already "filled" squares (assume they are correct!)
if the current box is filled
return the result of: solve_sudoku( next box );
end
// hypothesize all 9 possible numbers
for each possible number from 1 to 9
if that number is 'valid' (okay to put in box) // test row,col,square
try that number in the box
if you can "solve_sudoku" for the rest of the puzzle
return true; // success!
end
end
end
return false; // failure
end
Loop va quyruq rekursiyasi
Ba'zi rekursiv algoritmlar tsikllarga juda o'xshash. Ushbu algoritmlar "quyruq rekursivi" deb nomlanadi, chunki algoritmdagi so'nggi so'z algoritmni "qayta boshlash" dir. Quyruqli rekursiv algoritmlarni to'g'ridan-to'g'ri ko'chadanga tarjima qilish mumkin.

Mavzular ro'yxatiga qaytish

Rekursiv ta'rif

Rekursiv algoritm

O'rganiladigan mavzular

rekursiv algoritm bilan masalani echish
rekursiv algoritm bilan hisoblash funktsiyasi
Rekursiv algoritm bilan o'rnatilgan a'zolikni tekshirish
Mundarija
A recursive algoritm "kichik (yoki oddiy)» Input qadriyatlar bilan o'zini chaqiradi bir algoritm bo'lib, kichik (yoki oddiy) kiritish uchun qaytib qiymatiga oddiy operatsiyalar qo'llash orqali joriy kiritish uchun natija qo'lga qaysi. Umuman olganda, xuddi shu masalaning kichik versiyalari echimlaridan foydalangan holda muammoni echish mumkin bo'lsa va kichik versiyalar osonlikcha hal qilinadigan holatlarga kamaytirilsa, u holda bu muammoni hal qilish uchun rekursiv algoritmdan foydalanish mumkin. Masalan, rekursiv aniqlangan to’plam elementlari yoki rekursiv aniqlangan funktsiya qiymatini rekursiv algoritm yordamida olish mumkin.

Agar to'plam yoki funktsiya rekursiv ravishda aniqlansa, u holda uning a'zolarini yoki qiymatlarini hisoblashning rekursiv algoritmi ta'rifni aks ettiradi. Rekursiv algoritmning dastlabki bosqichlari rekursiv ta'rifning asosiy bandiga mos keladi va ular baz elementlarini aniqlaydi. Keyin ularga induktiv bandga mos keladigan qadamlar qo'yiladi, ular bir avlod elementi uchun hisoblashni darhol oldingi avlod elementlariga kamaytiradi.

Umuman olganda, kompyuterning rekursiv dasturlari takrorlanadigan algoritmlarga nisbatan ko'proq xotira va hisoblashni talab qiladi, ammo ular sodda va ko'p hollarda bu muammo haqida tabiiy fikrlash usuli.

1-misol: k - juft natural sonni topish algoritmi

Shuni esda tutingki, buni ma'lum bir k uchun 2 * ( k - 1 ) chiqarish orqali juda oson echish mumkin . Biroq, bu erda maqsad muammoni hal qilishdan ko'ra, rekursiyaning asosiy g'oyasini tasvirlashdir. Algoritm 1: Hatto ( musbat butun k ) Kirish: k , musbat butun Chiqish: k -th ham tabiiy soni (birinchi hatto 0 ) Algoritm: agar k = 1 , keyin qaytib 0 ; else qaytarish hatto ( k-1 ) +

2018-04-01 121 2 .

Bu yerda tashkil hisoblash ham ( k ) nisbatan kamayadi ham bir kichik kiritish qiymati uchun ham ( k-1 ). Hatto ( k ) oxir-oqibat hatto ( 1 ) gaaylanadi, bu birinchi qatorda 0 ga teng . Misol uchun, hisoblash uchun ham ( 3 ) , Algoritm ham ( k ) bilan, deyiladi k = 2 . Hisoblash yilda , hatto ( 2 ) , Algoritm ham ( k )k = 1 bilan chaqiriladi . Yildan ham ( 1 ) = 0, 0 hisoblash uchun qaytariladi ham ( 2 ) , va hatto ( 2 ) = Hatto ( 1 ) + 2 = 2 olinadi. Hatto ( 2 ) uchun ushbu 2 qiymati endi hatto ( 3 ) hisoblashga qaytariladi va hatto ( 3 ) = hatto ( 2 ) + 2 = 4 olinadi.
Ushbu algoritmni ning rekursiv ta'rifi bilan taqqoslash orqali ko'rish mumkin manfiy bo'lmagan juft sonlar to'plami, algoritmning birinchi qatori ta'rifning asosiy bandiga, ikkinchi qator esa induktiv bandiga to'g'ri keladi.

Taqqoslash uchun, xuddi shu masalani takrorlanadigan algoritm yordamida qanday hal qilish mumkinligini ko'rib chiqamiz.

Algoritm 1-a: Juft ( musbat butun k )
Kiritish: k , musbat butun son
Chiqish: k - juft juft son (birinchi juftlik 0 )

Algoritm:

int i , juft ;
i : = 1 ;
hatto : = 0 ;
while ( i hatto: = hatto + 2 ;
i : = i + 1 ;
} hatto
qaytib . 2-misol: 2- algoritmning k kuchini hisoblash algoritmi 2 Power_of_2 ( natural son
k)
Kiritish: k , natural son
Chiqish: k -2

algoritmning quvvati :

agar k = 0 bo'lsa , u holda 1 qaytadi ;
aks holda qaytaring 2 * Power_of_2 ( k - 1 ).

Taqqoslash uchun, xuddi shu masalani takrorlanadigan algoritm yordamida qanday hal qilish mumkinligini ko'rib chiqamiz.

Algoritm 2-a Power_of_2 ( tabiiy sonk)
Kiritish: k , natural son
Chiqish: k -2

algoritmning quvvati :

int i , quvvat ;
i : = 0 ;
quvvat : = 1 ;
while ( i quvvat : = kuch * 2 ;
i : = i + 1 ;
} quvvatni
qaytarish . Keyingi misolda tegishli rekursiv ta'rif mavjud emas. Bu muammoni hal qilishning rekursiv usulini ko'rsatadi. 3-misol:

Ketma- ket qidirish algoritmining 3-bosqichi uchun rekursiv algoritm SeqSearch ( L, i, j, x )

Kirish: L - bu massiv, i va j - musbat butun sonlar, i j va x - L da qidiriladigan kalit . Chiqish: Agar x bo'lgan L ko'rsatkichlar o'rtasidagi i va j , so'ngra chiqish, uning indeksi, yana chiqish 0 . Algoritm: agar i j bo'lsa , u holda { agar L ( i ) = x bo'lsa

, keyin qaytish i ;

boshqa Qaytish SeqSearch ( L, i 1, J, x + )
}
else qaytishini 0 .

Rekursiv algoritmlardan ob'ektlarni to'plamga a'zoligini tekshirish uchun ham foydalanish mumkin.

4-misol: x sonning natural son ekanligini yoki yo'qligini sinash

algoritmi Algoritm 4 Natural ( x soni )

Kiritish: x soni
Chiqish: agar x natural son bo'lsa " Ha " , boshqasi " Yo'q " Algoritmi: agar x <

0 , keyin " Yo'q " ni qaytaring

aks
holda x = 0 bo'lsa , " Ha " ni qaytaring
else return Natural ( x - 1 )

5-misol: w ifodaning taklif yoki yo'qligini tekshirish algoritmi (propozitsion shakl)

5-algoritm Taklif ( satr w )

Kirish: string w

Chiqish: " ha ", agar w taklif bo'lsa , yana " No "

Algoritm:

agar w deb 1 (rost), 0 (false), yoki bir taklif etish o'zgaruvchan, keyin "qaytib Ha "
bo'lsa, boshqa w= ~ W 1 , keyin qaytib Proposition ( w 1 )
boshqa
(agar w = w 1 w 2 yoki w 1 w 2 yoki w 1 w 2 yoki w 1 w 2 va)
Taklif ( w 1 ) = Ha va taklif etish ( w 2 ) = Ha
keyin qaytaring Ha,
aks holda qaytasiz Yo'q,
oxir

Rekursiv algoritm haqida tushunchangizni sinab ko'ring

Quyidagi gaplardan qaysi biri to'g'ri, qaysi biri to'g'ri emasligini ko'rsating.
Ha yoki Yo'q-ni bosing, so'ngra Yuboring.
Keyingi - Matematik induksiyaning birinchi printsipi

Jadvalga qaytish

Mundarija sahifasiga qaytish

Algoritmlarni loyihalashga kirish. Algoritmlarni ishlab chiqish va tahlil qilishning ilg'or usullari.

REJA:

Algoritm tushunchasi.

Algoritmlarni loyihalash.

Algoritmlarni loyihalashning asosiy bosqichlari.

ЭҲМ ларнинг пайдо бўлиши ( XX асрнинг 2-ярми) билан АЛГОРИТМ
тушунчаси ПРОГРАММАЛАШТИРИШ тушунчаси билан боғланди.

Кўплаб алгоритмик тиллар пайдо бўлди: Фортран, Паскаль, Бейсик….

XII асрда Европада аль – Хорезми. математик трактатининг лотинча таржимаси чиқди. Ўша пайтлар Алгоритм деганда ўнлик саноқ системасида арифметик амалларнинг бажарилаш қоидалари назарда тутилган. Hozirgi davrda algoritm barcha soxalarda qo’llanib kelinmoqda.

Инглиз математиги Алан Тьюринг 1935 – 1936 йилларда «мантиқий ҳисоблаш машинаси» назариясини яратди. Ишлаб чиқилган «Тьюринг Машина»си бўлажак математиклар ва компьютерщиклар учун мажбурий ўқитиладиган бўлди. Лондон меҳмонхоналарининг бирида : «Бу ерда кодларнинг бузувчиси ва информатиканинг пионери Алан Тьюринг (1912 – 1954), туғилган» деб ёзиб қўйилган.

Рус математиги Андрей Марков 1947 йил «нормал алгоритм» тушунчасини киритди ва тизимлашган ва қатъий алгоритмлар умумий назариясини яратди. Белгини қайта ишлашга мўлжалланган замонавий тиллар (Пролог) Марковнинг «нормал алгоритм» ларига асосланади.

Ўнли саноқ системасида Бутун сонлар ва ўнли каср билан арифметик амалларнинг бажарилиш қоидаси биринчи бўлиб, bуюк олим Мухаммaд ибн Мусo ал-Хорaзми (арабчадан таржимаси «Мухаммад Мусo ўғли Хоразмдан», қисқа қилиб Ал-Хоразмий дейилади) томонидан ишлаб чиқилган.

Ал-Хоразмий IX асрда Хива шаҳрида яшаб ижод қилган. Араб тилида ёзилган асарлари йўқолиб кетган, аммо XII асрда лотин тилига таржима қилинган нусхалари сақланиб қолинган. Шу орқали Ғарбий Европа Ўнли саноқ системасида Бутун сонлар ва ўнли каср билан арифметик амалларнинг бажарилиш қоидаси билан танишган.

Алгоритм таърифи. Электрон ҳисоблаш машиналарининг вужудга келишига қадар алгоритмга ҳар хил таъриф бериб келинди. Лекин уларнинг барчаси маъно жиҳатдан бир-бирига жуда яқин бўлиб, бу таъриф ҳозирги кунда қуйидагича талқин қилинади.

Таъриф. Алгоритм деб, бирор масалани ечиш учун маълум қоидага асосан бажариладиган амалларнинг чекли кетма-кетлигига айтилади ёки аниқ натижа берувчи содда ҳисоблашлар кетма-кетлиги.

Yoki boshqacha aytsak aлгоритм-bu to’g’ri aniqlangan hisoblash jarayoni bo’lib, natijada kirishda berilgan m-tlarni chiquvchi m-tlarga aylantirib beradi, ya’ni aлгоритм kiruvchi m-tlarni chiquvchi m-tlarga aylantiruvchi hisoblash qadamlari ketma-ketligidan iborat jarayondir. Masalan, amaliyotda juda ko’p uchraydigan masalalardan biri bu -elementlar ketma-ketligidan ma’lum birlarini aniqlash masalasi ham aniq aлгоритм asosida yechiladi. Konkret masala: (4,6,-9,43,-11,7,91,-15) sonlar ketma-ketligidan manfiylarini aniqlash masalasida, kiruvchi ketma-ketlikdan chiquvchi (-9,-11,-15) ketma-ketlikni hosil qilish kerak bo’ladi. Bunday masalalar ko’pincha oraliq masala sifatida uchraydi. Ma’lumki, bu masalani bir necha hil algoritmlar yordamida echish mumkin. Bunday masalalarni juda ko’p keltirish mumkin.

Algoritmlarni loyihalash. Algoritmni tanlash qo’yilgan masalaning shartlari va boshqa bir nechta parametrlar asosida amalga oshiriladi: ular elementlar soni, elementlar joylashish tartibi, EHM axitekturasi, elementlarga qo’yiladigan masala shartlari va b. bo’lishi mumkin. Shuning uchun, algoritmni loyihalashda masalaning qo’yilishi, qo’llash mumkin bo’lgan algoritmlar sinflari va yuqoridagi parametrlar juda chuqur o’rganilishi kerak. Algoritm korrekt deyiladi, agar unng natijasi barcha kiruvchi mt lar uchun aniq chiquvchi mt larni tashkil etsa. Bu holda ihlatilgan korrekt algoritm berilgan masalani yechib beradi deyiladi. Agar algoritm nokorrekt bo’lsa, uning natijasi ba’zi bir kiruvchi mt lar uchun noto’g’ri bo’ladi yoki umuman natija bermasligi mumkin. Ba’zi hollarda, ya’ni xatoliklarni tekshirib turish imkoni bo’lganda, nokorrekt algoritmlar ham foydali bo’lishi mumkin. Ko’pincha korrekt algoritmlardan foydalaish maqsadga muvofiq hisoblanadi.

Algoritm samaradorligi. Javob berilishi kerak bo'lgan birinchi jiddiy savol: qanday qilib “samarali algoritm” tushunchasini aniqlash mumkin? Bir qarashda samaradorlikning ishchi ta'rifi quyidagicha ko'rinishi mumkin.

1- ta'rif: algoritm samarador deb ataladi, agar ma'lumotlar kiritilganda uni amalga oshirish tezkor bajarilsa.

Albatta, samaradorlik nisbiy tushuncha bo’lib, bir nechta algoritmlarni solishtirish orqali aniqlanadi.

Xossalari:

Тушунарлилик –алгоритмда ижрочига берилаётган кўрсатмалар аниқ мазмунда бўлиши;

Дискретлилик – алгоритмларни чекли қадамлардан ташкил қилиб бўлаклаш имконияти ;

Чеклилик – бажарилаётган алгоритм чекли қадамларда натижага олиб келиши;

Натижавийлик - натижанинг бўлиши;

Оммавийлик – ҳар бир алгоритм мазмунига кўра бир турдаги масалаларнинг барчаси учун ҳам ўринли бўлиши .

Формаллик –командаларни механик бажариш имконияти.

Бу хосса роботлар, компьютерлар ва бошқа қурилмаларда командаларнинг кетма-кет бажарилишини таъминлайди.

Алгоритм турлари : Чизиқли алгоритм - деб ҳеч қандай шартсиз фақат кетма-кет бажариладиган жараёнларга айтилади.

Тармоқланувчи алгоритм - деб маълум шартларга мувофиқ бажариладиган кўрсатмалардан тузилган алгоритмга айтилади.

Такрорланувчи алгоритм - деб бирон бир шарт текширилиши ёки бирон параметрнинг ҳар хил қийматлари асосида такрорий хисблашларни бажарадиган алгоритмга айтилади.

Чизиқли алгоритм - деб ҳеч қандай шартсиз фақат кетма-кет бажариладиган жараёнларга айтилади. Чизиқли алгоритм структураси:

Тармоқланувчи ва циклик алгоритмлар

Algoritmlarning qo’llanish soxalari. Algoritmlarni amalda juda ko’p yo’nalihlarda qo’llash mumkin, masalan:

Inson genomini o’qish masalasi-ya’ni inson DNK siga kiruvchi 100 ming genlar ketma-ketligini identifikatsiya ilish; Internet; Elektron tijorat; Ishlab chiqarish va elektron tijoratda resurslardan optimal foydalanish va b.

Algoritmni ishlab chiqish va tahlil qilish usullari. Yuqoridan pastga qarab algoritmni loyihalash yoki ketma-ket (bosqichma-bosqich) algoritmni loyihalash usuli - bu asl muammo (algoritm) bir qator yordamchi pastki qismlarga bo'linganida (subalgoritmlar) sodda va elementar operatsiyalar nuqtai nazaridan hal qilingan holda algoritmlarni tuzish usuli hisoblanadi ( protseduralar).

"Pastdan-yuqoriga" usuli, aksincha, oldindan aniqlangan subalgoritmlarning to'g'ri to'plamiga tayanib, funktsional ravishda to'liqroq bajariladigan kichik vazifalarni tuzadi, ulardan umumiyroq narsalarga o'tadi va hokazo, biz echimni yoza oladigan darajaga yetguncha. Ushbu usul pastki qavatdagi dizayn usuli sifatida tanilgan.

Algoritmlarning tarkibiyli hosil qilish printsiplari (algoritmlarni ishlab chiqishning tarkibiy usullari) algoritmlarni asosiy tarkibiy algoritmik birliklaridan hosil qilish, ularning ketma-ket ulanishi yoki bir-birlariga joylashtirilishi algoritmni o'qilishini va bajarilishini kafolatlaydigan qoidalarni yuqoridan pastga va ketma-ketlikda bajarish tamoyillaridir.

Strukturalangan algoritm - bu asosiy algoritmik tuzilmalarni aniqlash va joylashtirish sifatida taqdim qilingan algoritmdir. Strukturalangan algoritmda statik holat (algoritmni yangilashdan oldin) va dinamik holat (yangilangandan keyin) bir xil mantiqiy tuzilishga ega, uni yuqoridan pastgacha kuzatib borish mumkin ("u ham o'qiladi, ham bajariladi"). Algoritmlarning strukturali rivojlanishi bilan uning tuzilishi va bajarilishining har bir bosqichida algoritmning to'g'riligini kuzatish mumkin.

Algoritmlarni (dasturlarni) loyihalash va ishlab chiqishda keng qo'llaniladigan usullardan biri bu modulli usul. Modul bu ma'lum bir algoritm yoki uning ba'zi bir bloklari bo'lib, ularni ajratib va ​​yangilash mumkin bo'lgan ma'lum nomga ega. Ba'zida modul barcha algoritmlar yordamchi bo'lsa ham, yordamchi algoritm deb ataladi.

Modul xususiyatlari: funktsional yaxlitlik va to'liqlik (har bir modul bitta vazifani bajaradi, lekin to'liq va to'liq bajaradi); avtonomiya va boshqa modullardan mustaqillik (vorislik modulining avvalgi modul ishlashidan mustaqilligi; bundan tashqari, ularning aloqasi faqat parametrlarni uzatish / qabul qilish va boshqarish darajasida amalga oshiriladi);

Algoritmlarning modulli dizaynining afzalliklari:

-turli ijrochilar tomonidan katta hajmli algoritmni (algoritmik kompleks) ishlab chiqish imkoniyati; -eng ko'p ishlatiladigan algoritmlar (subalgoritmlar) kutubxonasini yaratish va yuritish qobiliyati; algoritmlarni sinash va ularning to'g'riligini asoslash; dizaynni soddalashtirish va algoritmlarni o'zgartirish; algoritmlarni (yoki algoritmlarning komplekslarini) ishlab chiqish (loyihalash) murakkabligini kamaytirish; algoritmlarni amalga oshirishda hisoblash jarayonining kuzatilishi.

Algoritmni sinash - bu maxsus belgilangan testlar yoki test misollarida algoritmning to'g'riligi yoki noto'g'riligini tekshirish - ma'lum ma'lumotlar va natijalar bilan bog'liq muammolar (ba'zan ularni yaqinlashtirish etarli). Testlar to'plami minimal va to'liq bo'lishi kerak, ya'ni kirish ma'lumotlar to'plamining har bir alohida turini, ayniqsa alohida holatlarda, tekshirishni ta'minlaydi. Algoritmlarning ishlash vaqtlari:

n=

n

n*logn

n^2

n^3

1,5^n

2^n

n!

10

<1 s

<1 s

<1 s

<1 s

<1 s

<1 s

<4 s

30

<1 s

<1 s

<1 s

<1 s

<1 s

18min

10^25y

50

<1s

<1s

<1s

<1s

11min

36y

Juda kop

100

<1s

<1s

<1s

<1s

12892y

10^17y

----

1000

<1s

<1s

<1s

18min

---

----

----

10000

<1s

<1s

2min

12kun

--

---

---

100000

<1s

<2s

3soat

32y

---

---

---

1 mln.

<1s

20s

12kun

31710y

---

---

---