Algoritm haqida tushuncha. Dasturlash

Sayt bo'limlari

Muharrir tanlovi:

Reklama

uy - Mobil qurilmalar

). Bunday dasturlash tizimi yordamida dastur yaratish ikki bosqichdan iborat: 1) dasturning grafik interfeys elementlarini vizual rejimda yaratish; 2) dastur kodini ishlab chiqish. Ushbu yondashuv dasturlarni yaratishni sezilarli darajada osonlashtiradi, chunki grafik interfeysni qo'lda (protsessual tillarda) ishlab chiqish murakkab va ko'p vaqt talab qiladigan jarayondir.

Algoritmlarni o'rganish va bilishning ahamiyatini tushunish uchun birinchi qadam algoritm nimani anglatishini to'g'ri aniqlashdir. Dasturlashda algoritm bu aniq va aniq harakatlar ketma-ketligi“Algoritmlar: Qurilish va tahlil” (Kormen, Leiserson, Rivest, Shtayn) nomli mashhur kitobiga ko‘ra, “algoritm - bu ma’lum miqdor yoki miqdorlar to‘plami kiritilgan har qanday aniq belgilangan hisoblash protsedurasi va natijasi chiqish qiymati yoki qiymatlar to'plamidir." Boshqacha qilib aytganda, algoritmlar aniq belgilangan maqsadga erishish uchun yo'l xaritalariga o'xshaydi. Fibonachchi ketma-ketligi shartlarini hisoblash uchun kod ma'lum bir algoritmni amalga oshirishdir. Hatto ikkita raqamni qo'shishning oddiy funktsiyasi ham oddiy bo'lsa ham, algoritmdir.

Algoritm (dastur) yaratish uchun siz quyidagilarni bilishingiz kerak:

boshlang'ich vazifa ma'lumotlarining to'liq to'plami (ob'ektning dastlabki holati);

algoritmni yaratish maqsadi (ob'ektning yakuniy holati);

ijrochining buyruqlar tizimi (ya'ni ijrochi tushunadigan va bajarishi mumkin bo'lgan buyruqlar to'plami).

Olingan algoritm (dastur) quyidagi xususiyatlar to'plamiga ega bo'lishi kerak:

diskretlik(algoritm alohida bosqichlarga bo'linadi - buyruqlar);

noaniqlik(har bir buyruq ijrochining yagona mumkin bo'lgan harakatini belgilaydi);

aniqlik(barcha algoritm buyruqlari bajaruvchi buyruqlar tizimiga kiritilgan);

samaradorlik(ijrochi masalani chekli bosqichlarda hal qilishi kerak).

Aksariyat algoritmlar ham xususiyatga ega ommaviy xarakter(bir xil algoritmdan foydalanib, siz ko'plab shunga o'xshash muammolarni hal qilishingiz mumkin).

Ba'zi algoritmlar, masalan, Fibonachchi ketma-ketligini hisoblash uchun, intuitiv va tug'ma mantiqiy fikrlash va muammolarni hal qilish qobiliyatlari bilan bog'liq. Biroq, ko'pchiligimiz murakkab algoritmlarni o'rganishimiz yaxshi bo'lardi, shunda kelajakda biz mantiqiy muammolarni yanada samarali hal qilish uchun ularni qurilish bloklari sifatida ishlatishimiz mumkin. Aslida, odamlar elektron pochta xabarlarini tekshirish yoki musiqa tinglashda qancha murakkab algoritmlardan foydalanishidan hayron bo'lishingiz mumkin. Ushbu maqola algoritmlarni o'rganishning muhimligini ko'rsatadigan amaliy misollar bilan algoritm tahlilining ba'zi asosiy g'oyalari bilan tanishtiriladi.

Dasturlash tili - algoritmik tuzilmalar va ma'lumotlarni yozib olish qoidalari to'plami.

Algoritmni bajarish vaqtini tahlil qilish

Algoritmning eng muhim jihatlaridan biri uning tezligidir. Ko'pincha muammoni hal qiladigan algoritmni topish oson, lekin agar algoritm juda sekin bo'lsa, u qayta ko'rib chiqish uchun qaytariladi. Algoritmning aniq tezligi algoritm qayerda ishlashiga, shuningdek, amalga oshirish tafsilotlariga bog'liq bo'lganligi sababli, kompyuter olimlari odatda kiritilgan ma'lumotlarga nisbatan bajarish vaqti haqida gapirishadi. Misol uchun, agar kirish N butun sondan iborat bo'lsa, u holda algoritm N 2 ga proportsional ish vaqtiga ega bo'lishi mumkin, bu O(N 2) sifatida ifodalanadi. Bu shuni anglatadiki, agar siz algoritmni amalga oshirishni N o'lchamdagi kirishga ega kompyuterda ishga tushirsangiz, u C*N 2 soniya davom etadi, bu erda C kirish hajmi o'zgarganda o'zgarmaydigan ba'zi bir doimiydir.

Biroq, ko'pgina murakkab algoritmlarning bajarilish vaqti nafaqat kiritilgan ma'lumotlarning hajmiga, balki boshqa ko'plab omillarga ham bog'liq. Masalan, butun sonlar to'plamini saralash algoritmi, agar to'plam allaqachon tartiblangan bo'lsa, tezroq ishlashi mumkin. Qatlning eng yomon holati va o'rtacha ijro ishi haqida gapirish odatiy holdir. Eng yomon holatda bajarish vaqti - bu barcha mumkin bo'lgan kirishlarning "eng yomoni" ni hisobga olgan holda, algoritm ishlashi mumkin bo'lgan maksimal vaqt. O'rtacha bajarilish holati barcha mumkin bo'lgan kirishlar bo'yicha algoritmning o'rtacha ishlash vaqtidir. Bajarish vaqtining ikki turidan eng yomoni haqida fikr yuritish eng oson va shuning uchun ma'lum bir algoritm uchun ko'rsatkich sifatida tez-tez ishlatiladi. Algoritmning eng yomon va o'rtacha bajarilish vaqtini aniqlash jarayoni ancha murakkab bo'lishi mumkin, chunki Odatda barcha mumkin bo'lgan kirishlar uchun algoritmni ishga tushirish mumkin emas.

Yuqorida ta'kidlanganidek, bir xil algoritmni turli yo'llar bilan yozish mumkin. Siz algoritmni yozishingiz mumkin tabiiy til. Biz retseptlar, ko'rsatmalar va boshqalarni shunday ishlatamiz. Rasmiy ijrochilar uchun mo'ljallangan algoritmlarni yozish uchun maxsus dasturlash tillari. Har qanday algoritmni tasvirlash mumkin grafik jihatdan blok-sxema shaklida. Buning uchun maxsus nota tizimi ishlab chiqilgan:

Belgilanish	Tavsif	Eslatmalar
	Algoritmning boshlanishi va oxiri
	Ma'lumotlarni kiritish va chiqarish.	Ma'lumotlar chiqishi ba'zan boshqacha nomlanadi:
	Harakat	Hisoblash algoritmlarida bu topshiriqni belgilash uchun ishlatiladi
	Vilka	Vilkalar - novdalar va halqalarni amalga oshirish uchun zarur bo'lgan komponent
	Parametr bilan tsiklni boshlash
	Oddiy jarayon	Dasturlashda - protseduralar yoki pastki dasturlar
	Bloklar orasidagi o'tish

Keling, blok-sxema shaklida ikkita miqdorni yig'ish algoritmining tavsifiga misol keltiramiz:

Algoritmni tasvirlashning bunday usuli odamlar uchun eng vizual va tushunarli hisoblanadi. Shuning uchun, odatda, rasmiy bajaruvchi algoritmlar avvalo sxema ko'rinishida ishlab chiqiladi va shundan keyingina ulardan biri bo'yicha dastur tuziladi.

Tartiblash

Saralash ko'pincha dasturchilar tomonidan qo'llaniladigan algoritmning yaxshi namunasidir. Elementlar guruhini saralashning eng oson usuli bu guruhdan eng kichik elementni olib tashlash va uni birinchi o'ringa qo'yishdan boshlashdir. Keyin ikkinchi eng katta element chiqariladi va ikkinchi o'ringa qo'yiladi va hokazo. Afsuski, bu algoritmning ishlash vaqti O(N 2) bo'lib, u elementlarning kvadratiga mutanosib bo'lgan vaqtni oladi. Agar biz milliardlab elementlarni saralashimiz kerak bo'lsa, unda bu algoritm 10 18 amalni talab qiladi. Agar odatdagi ish stoli kompyuterlari soniyada taxminan 10 9 operatsiyani bajaradi deb faraz qilsak, bu milliard elementlarni saralashni tugatish uchun yillar kerak bo'ladi.

Yaxshiyamki, tezkor saralash, yig'ish va birlashtirish kabi bir qator ilg'or algoritmlar mavjud. Bu algoritmlar O(N * Log(N)) ish vaqtiga ega. Shunday qilib, milliardlab elementlarni saralash uchun zarur bo'lgan operatsiyalar soni shunday oqilona chegaralarga qisqartiriladiki, hatto eng arzon ish stoli kompyuter ham bunday tartiblashni amalga oshirishi mumkin. Bir milliard kvadrat operatsiyalar (10 18) o'rniga, bu algoritmlar faqat 10 milliard operatsiyani (10 10) talab qiladi, ya'ni. 100 million marta tezroq.

Eng qisqa yo'l

Bir nuqtadan ikkinchi nuqtaga eng qisqa yo'lni topish algoritmlari ko'p yillar davomida o'rganilgan. Ushbu algoritmlarni qo'llash bo'yicha ko'plab misollar mavjud, ammo taqdimotning soddaligi uchun biz quyidagi bayonotga amal qilamiz: biz bir nechta ko'cha va chorrahalarga ega bo'lgan shaharda A nuqtadan B nuqtagacha eng qisqa yo'lni topishimiz kerak. Ushbu muammoni hal qilish uchun juda ko'p turli xil algoritmlar mavjud va ularning barchasi o'zlarining afzalliklari va kamchiliklariga ega. Ularga sho'ng'ishdan oldin, oddiy qo'pol kuch algoritmining bajarilish vaqtini ko'rib chiqaylik. Agar algoritm A dan B gacha bo'lgan barcha mumkin bo'lgan yo'lni ko'rib chiqsa (bu tsikllarni hosil qilmaydi), hatto A va B kichik shaharchada bo'lsa ham, bizning hayotimizda tugashi dargumon. Ushbu algoritmning ishlash vaqti eksponent bo'lib, u ba'zi C uchun O(C N) sifatida belgilanadi. C ning kichik qiymatlari uchun ham N o'rtacha kattalashganda C N astronomik raqamga aylanadi.

Ushbu muammoni hal qilishning eng tezkor algoritmlaridan biri O(E+V*Log(V)) ish vaqtiga ega, bu erda E - yo'l segmentlari soni va V - kesishmalar soni. Algoritm 10 000 ta chorraha va 20 000 ta yoʻl segmentidan iborat boʻlgan shahardagi eng qisqa yoʻlni topish uchun taxminan 2 soniya vaqt ketadi (odatda har bir chorrahadan 2 ta yoʻl segmenti). Ushbu algoritm Dijkstra algoritmi sifatida tanilgan, u ancha murakkab va ustuvor navbatdagi ma'lumotlar strukturasidan foydalanishni talab qiladi. Biroq, ba'zi hollarda, hatto bu bajarilish vaqti juda sekin (masalan, Nyu-Yorkdan San-Frantsiskogacha bo'lgan eng qisqa yo'lni topishni olaylik - AQShda millionlab chorrahalar mavjud), bunday hollarda dasturchilar shu orqali bajarish vaqtini yaxshilashga harakat qilishadi. -evristika deb ataladi. Evristik - bu vazifaga tegishli bo'lgan narsaning yaqinlashishi. Eng qisqa yo'l muammosida, masalan, nuqtaning belgilangan joydan qanchalik uzoqligini bilish foydali bo'lishi mumkin. Buni bilib, siz tezroq algoritmni ishlab chiqishingiz mumkin (masalan, A* qidiruv algoritmi ba'zi hollarda Dijkstra algoritmiga qaraganda ancha tezroq ishlaydi). Bunday yondashuv har doim ham algoritmning eng yomon holatda bajarilish vaqtini yaxshilamaydi, lekin ko'pgina real ilovalarda algoritm tezroq ishlaydi.

Taxminiy algoritmlar

Ba'zan hatto eng ilg'or evristikaga ega bo'lgan eng ilg'or algoritm ham eng tezkor kompyuterda juda sekin ishlaydi. Bunday hollarda yakuniy natijaning aniqligini kamaytirish kerak. Eng qisqa yo'lni olishga harakat qilish o'rniga, o'zingizni, masalan, eng qisqa yo'ldan 10% kattaroq yo'l bilan cheklashingiz mumkin.

Aslida, hozirda ma'lum bo'lgan algoritmlar juda sekin optimal natijani beradigan juda ko'p muhim muammolar mavjud. Ushbu muammolarning eng mashhur guruhi NP (deterministik bo'lmagan polinom) deb ataladi. Agar muammo NP-to'liq yoki NP-qiyin deb nomlansa, bu hech kim optimal echimni olishning etarlicha yaxshi usulini bilmasligini anglatadi. Bundan tashqari, agar kimdir bitta NP-qiyin muammoni hal qilish uchun samarali algoritm ishlab chiqsa, u holda bu algoritm barcha NP-qiyin masalalarga qo'llanilishi mumkin.

NP-qiyin muammoning yaxshi namunasi sayohatchi sotuvchi muammosidir. Sotuvchi N shaharga tashrif buyurishni xohlaydi va u bir shahardan boshqasiga qancha vaqt ketishini biladi. Savol shundaki, u qanchalik tez barcha shaharlarga tashrif buyurishi mumkin? Bu muammoni hal qilishning eng tez ma'lum algoritmi juda sekin - va ko'pchilik bu har doim shunday bo'lishiga ishonadi - shuning uchun dasturchilar yaxshi yechim beradigan, lekin ko'pincha optimal bo'lmagan algoritmlarni izlaydilar.

Tasodifiy algoritmlar

Ba'zi muammolarni hal qilishda qo'llaniladigan yana bir yondashuv algoritmni tasodifiy qilishdir. Ushbu yondashuv algoritmning eng yomon vaqtini yaxshilamaydi, lekin ko'pincha o'rtacha holatda yaxshi ishlaydi. Tez tartiblash algoritmi randomizatsiyadan foydalanishning yaxshi namunasidir. Eng yomon holatda, tezkor tartiblash algoritmi elementlar guruhini O(N 2) da tartiblaydi, bu erda N elementlar soni. Agar bu algoritmda randomizatsiya ishlatilsa, u holda eng yomon holat ehtimoli ahamiyatsiz darajada kichik bo'ladi va o'rtacha hisobda tezkor tartiblash algoritmi O(N*Log(N)) vaqtida ishlaydi. Boshqa algoritmlar hatto eng yomon holatda O(N*Log(N)) ish vaqtini kafolatlaydi, lekin o'rtacha holatda sekinroq. Garchi ikkala algoritm ham N*Log(N) ga mutanosib ish vaqtiga ega bo‘lsa-da, tezkor saralash algoritmi kichikroq doimiy omilga ega – ya’ni. u C*N*Log(N) ni talab qiladi, boshqa algoritmlar esa 2*C*N*Log(N) dan ortiq amallarni talab qiladi.

Tasodifiy raqamlardan foydalanadigan boshqa algoritm raqamlar guruhining medianasini qidiradi va uning o'rtacha ishlash vaqti O (N). Bu raqamlarni saralaydigan va o'rtachani oladigan va O(N*Log(N)) da ishlaydigan algoritmga nisbatan ancha tezroq. O (N) vaqtida medianani topadigan deterministik algoritmlar (tasodifiy emas) mavjud, ammo tasodifiy algoritmni tushunish osonroq va ko'pincha bu deterministik algoritmlarga qaraganda tezroq.

Median qidiruv algoritmining asosiy g'oyasi raqamlar orasidan tasodifiy sonni tanlash va guruhdagi qancha raqam tanlangan raqamdan kamligini hisoblashdir. Aytaylik, N ta son bor, ularning K soni tanlangan sondan kichik yoki teng. Agar K yarmi N dan kam bo'lsa, biz mediana tasodifiy sondan katta bo'lgan (N/2-K)-chi son ekanligini bilamiz, shuning uchun biz tasodifiy sondan kichik yoki unga teng bo'lgan K sonlarni olib tashlaymiz. Endi biz mediana o'rniga (N/2-K) eng kichik sonni topmoqchimiz deylik. Algoritm bir xil, biz tasodifiy raqamni tanlaymiz va tasvirlangan amallarni takrorlaymiz.

Siqish

Algoritmlarning yana bir klassi ma'lumotlarni siqish uchun mo'ljallangan. Bu algoritm kutilgan natijaga ega emas (saralash algoritmi kabi), aksincha, ba'zi mezonlarga muvofiq optimallashtiradi. Ma'lumotlarni siqish holatida algoritm (masalan, LZW) ma'lumotlarning iloji boricha kamroq baytni egallashiga harakat qiladi, lekin ayni paytda uni asl ko'rinishiga ochish mumkin. Ayrim hollarda bu turdagi algoritmlar boshqa algoritmlar kabi usullardan foydalanadi, natijada yaxshi natijaga erishiladi, lekin optimal emas. Misol uchun, JPG va MP3 ma'lumotlarni shunday siqadiki, yakuniy natija asl nusxadan pastroq, lekin hajmi jihatidan ham kichikroq bo'ladi. MP3 siqish asl audio faylning barcha xususiyatlarini saqlab qolmaydi, lekin fayl hajmini sezilarli darajada qisqartirish bilan birga maqbul sifatni ta'minlash uchun etarli tafsilotlarni saqlashga harakat qiladi. JPG formati bir xil printsipga amal qiladi, ammo tafsilotlar sezilarli darajada farq qiladi, chunki... maqsad audio emas, balki tasvirni siqishdir.

Nima uchun barcha turdagi algoritmlarni bilishingiz kerak?

Algoritmlardan to'g'ri foydalanish uchun barcha tilga olingan algoritm turlarini bilish kerak. Agar siz muhim dasturiy ta'minotni ishlab chiqishingiz kerak bo'lsa, unda siz algoritmingiz tezligini taxmin qilishingiz kerak. Sizning taxminingizning to'g'riligi algoritmlarni bajarish vaqtini tahlil qilishda qanchalik malakali ekanligingizga bog'liq. Bundan tashqari, algoritmlarning tafsilotlarini bilish kerak, bu bizga dastur tezda ishlamaydigan yoki qabul qilinishi mumkin bo'lmagan natijalarni keltirib chiqaradigan maxsus holatlarni taxmin qilish imkonini beradi.

Albatta, ilgari o'rganilmagan muammolarga duch keladigan vaqtlar bo'ladi. Bunday hollarda siz yangi algoritm o'ylab topishingiz yoki eski algoritmni yangi usulda qo'llashingiz kerak. Algoritmlar haqida qanchalik ko'p bilsangiz, muammoning to'g'ri echimini topish ehtimoli shunchalik yuqori bo'ladi. Ko'pgina hollarda, yangi muammoni osongina eskisiga qisqartirish mumkin, ammo buning uchun siz eski muammolar haqida fundamental tushunchaga ega bo'lishingiz kerak.

Misol sifatida, tarmoq kalitlari qanday ishlashini ko'rib chiqing. Kommutatorga N ta kabel ulangan va bu kabellar orqali kelgan ma'lumotlar paketlarini qabul qiladi. Kommutator avval paketlarni tahlil qilishi va keyin ularni to'g'ri kabel orqali qaytarib yuborishi kerak. Kommutator, kompyuter kabi, diskret rejimda ishlaydi - paketlar uzluksiz emas, balki diskret oraliqlarda yuboriladi. Tez o'tkazgich har bir intervalda iloji boricha ko'proq paketlarni jo'natishga intiladi, aks holda ular to'planib qoladi va kalit ishdan chiqadi. Algoritmning maqsadi har bir intervalda paketlarning maksimal sonini jo'natish, shuningdek, boshqalarga qaraganda erta kelgan paketlar ham boshqalarga qaraganda tezroq yuborilishi tartibini ta'minlashdir. Bunday holda, "barqaror moslik" deb nomlanuvchi algoritm ushbu muammoni hal qilish uchun mos ekanligi ma'lum bo'ldi, garchi bu birinchi qarashda aniq bo'lmasa ham. Muammo va yechim o'rtasidagi bunday bog'lanishni faqat allaqachon mavjud algoritmik bilimlar yordamida aniqlash mumkin.

Haqiqiy misollar

Eng so'nggi algoritmlarni talab qiladigan haqiqiy muammolarni hal qilishning ko'plab misollari mavjud. Kompyuterda qiladigan deyarli hamma narsa, kimdir uzoq vaqt davomida ishlab chiqish uchun sarflagan algoritmlarga bog'liq. Hatto eng oddiy dasturlar ham sahna ortida ishlaydigan, xotirani boshqaradigan va qattiq diskdan ma'lumotlarni yuklaydigan algoritmlarsiz mavjud bo'lmaydi.

Murakkab algoritmlardan foydalanishning o'nlab misollari mavjud, ammo biz ikkita muammoni muhokama qilamiz, ularning echimi TopCoder-da ba'zi muammolarni hal qilish bilan bir xil ko'nikmalarni talab qiladi. Birinchi muammo maksimal oqim muammosi sifatida tanilgan, ikkinchisi dinamik dasturlashni o'z ichiga oladi, bu ko'pincha imkonsiz ko'rinadigan chaqmoq tezligida muammolarni hal qila oladigan texnikadir.

Maksimal oqimni topish algoritmi

Maksimal oqimni topish muammosi mavjud tarmoqdan biror narsani bir joydan ikkinchi joyga eng yaxshi ko'chirish uchun foydalanishdir. Ushbu muammo birinchi marta 1950-yillarda Sovet Ittifoqining temir yo'l liniyalari bilan bog'liq holda paydo bo'lgan. Qo'shma Shtatlar Sovet Ittifoqi o'zining temir yo'l tarmog'i orqali Sharqiy Evropadagi sun'iy yo'ldosh davlatlariga materiallarni qanchalik tez tashishini bilmoqchi edi.

Bundan tashqari, Qo'shma Shtatlar sun'iy yo'ldosh davlatlarni Sovet Ittifoqining qolgan qismidan uzib qo'yish uchun relslarning qaysi qismini eng oson yo'q qilish mumkinligini bilmoqchi edi. Ma'lum bo'lishicha, ikkala muammo bir-biri bilan chambarchas bog'liq edi va maksimal oqim muammosini hal qilish, shuningdek, minimal kesish muammosini ham hal qildi, bu oxir-oqibat Sovet Ittifoqini sun'iy yo'ldoshlaridan uzib qo'yishning eng arzon usulini ochib beradi.

Maksimal oqimni topish uchun birinchi samarali algoritm olimlar Ford va Fulkerson tomonidan ixtiro qilingan. Keyinchalik algoritm Ford-Fulkerson algoritmi deb nomlandi va kompyuter fanlari sohasidagi eng mashhur algoritmlardan biri hisoblanadi. So'nggi 50 yil ichida algoritm bir qator yaxshilanishlarga duch keldi, bu esa uni tezroq qilish imkonini berdi (garchi bu yaxshilanishlarning ba'zilari murakkabligi bilan qo'rqinchli bo'lsa ham).

Vazifa aniq belgilanganligi sababli, ko'plab turli ilovalar topildi. Algoritm to'g'ridan-to'g'ri Internetga ulangan, bu erda imkon qadar ko'proq ma'lumotlarni bir nuqtadan ikkinchisiga tashish muhimdir. Muammo turli biznes jarayonlarida ham uchraydi va operatsiyalarni tadqiq qilishning muhim qismi hisoblanadi. Misol uchun, agar bajarilishi kerak bo'lgan N ta xodim va N ta vazifa mavjud bo'lsa, lekin har bir xodim har bir vazifani bajara olmasa, maksimal oqimni topish N xodimni vazifalarga tayinlash uchun yechim beradi, agar har bir vazifa bajarilgan bo'lsa. . TopCoder SRM 200 dan bitiruv muammosi maksimal oqim muammosining yaxshi namunasidir.

Ketma-ket taqqoslash

Ko'pgina koderlar o'zlarining butun faoliyati davomida hech qachon dinamik dasturlashdan foydalangan holda algoritmni amalga oshirishlari shart emas. Biroq, dinamik dasturlash bir qator muhim algoritmlarda qo'llaniladi. Algoritmlardan biri bu ikkita ketma-ketlik o'rtasidagi farqni topish bo'lib, ko'pchilik dasturchilar buni tushunmagan bo'lsalar ham, ulardan foydalanganlar. Ushbu algoritm A ketma-ketlikni B ketma-ketlikka aylantirish uchun zarur bo'lgan qo'shishlar, o'chirishlar va tahrirlarning minimal sonini hisoblab chiqadi.

Masalan, "AABAA" va "AAAB" ketma-ketligini ko'rib chiqing. Birinchi ketma-ketlikni ikkinchisiga aylantirish uchun eng oddiy narsa - o'rtadagi B ni olib tashlash va oxirgi A ni B ga o'zgartirish. Bu algoritm ko'plab ilovalarga ega, jumladan DNK va plagiatni aniqlash bilan bog'liq ba'zi muammolar. Biroq, ko'pgina dasturchilar uni birinchi navbatda bir xil manba kodi faylining versiyalarini solishtirish uchun ishlatadilar. Agar ketma-ketlik elementlari fayldagi satrlar bo'lsa, u holda bu algoritm faylning bir versiyasini boshqasiga aylantirish uchun qaysi qatorlarni o'chirish, kiritish, o'zgartirish kerakligini aniqlash imkonini beradi.

Dinamik dasturlashsiz, bir ketma-ketlikdan ikkinchisiga o'tish uchun siz eksponensial o'zgarishlardan o'tishingiz kerak. Biroq, dinamik dasturlash algoritmning bajarilish vaqtini O(N*M) ga qisqartiradi, bunda N va M ikkita ketma-ketlikdagi elementlar soni.

Xulosa

Turli xil muammolar mavjud bo'lganidek, ularni hal qilish uchun ham ko'p turli xil algoritmlar mavjud. Biroq, siz hal qilmoqchi bo'lgan muammo qaysidir ma'noda boshqa muammoga o'xshash bo'lishi ehtimoli katta. Algoritmlarning keng doirasini chuqur tushunishni rivojlantirish orqali siz to'g'ri algoritmni tanlab, muammoni hal qilish uchun qo'llashingiz mumkin bo'ladi. Bundan tashqari, TopCoder-dagi musobaqalardagi muammolarni hal qilish ushbu sohadagi mahoratingizni oshirishga yordam beradi. Ushbu muammolarning aksariyati sun'iy va haqiqiy bo'lmagan ko'rinadi, lekin ular haqiqiy dunyoda har kuni talab qilinadigan bir xil algoritmik bilimlarni talab qiladi.

Turli darajadagi murakkablikdagi ilovalarni yozish uchun, avvalo, buni qanday qilish kerakligi haqida bilimga ega bo'lishingiz kerak. Va algoritmlash va dasturlashning eng asoslaridan boshlash tavsiya etiladi. Biz ular haqida maqolada gaplashamiz.

Bu murakkab texnik fanning nomi bo'lib, uning vazifasi yordamida ma'lumotlarni yaratish, qayta ishlash, uzatish, saqlash va ko'paytirish usullarini tizimlashtirish, shuningdek, maqsadga erishishga yordam beradigan ishlash tamoyillari va boshqaruv usullarini o'z ichiga oladi. "Kompyuter fanlari" atamasining o'zi frantsuz tilidan kelib chiqqan bo'lib, "axborot" va "avtomatlashtirish" so'zlarining gibrididir. Bu ma'lumotlarni yig'ish, qayta ishlash va uzatishning yangi texnologiyalarini ishlab chiqish va tarqatish tufayli paydo bo'ldi, bu ularni kompyuter tashuvchilarida yozib olish bilan bog'liq edi. Bu kompyuter fanining kelib chiqishi. Algoritmlash va dasturlash asoslari ushbu fanning eng muhim sohalaridan biridir.

U nima ish qiladi?

Kompyuter fanlari quyidagi muammolarga duch keladi:

Kompyuter texnologiyalari uchun apparat va dasturiy ta'minotni qo'llab-quvvatlash.
Odamlar va kompyuter komponentlari o'rtasidagi o'zaro ta'sirni ta'minlash vositalari.

"Interfeys" atamasi ko'pincha texnik qismga murojaat qilish uchun ishlatiladi. Bu erda bizda bepul dastur mavjud. Algoritmlash va dasturlash asoslari har doim keng auditoriyani yutib olishi kerak bo'lgan ommaviy tarqatish uchun mahsulotlar yaratishda qo'llaniladi. Axir, mashhur bo'lish uchun ishlab chiqilayotgan dastur ishlashi va optimal ko'rinishi kerak.

Algoritmlar taqdimoti

Ular sezilarli darajada yozilishi mumkin. Eng mashhurlari quyidagilar:

Og'zaki va formulali tavsif. Bu barcha individual holatlarda o'zaro ta'sir xususiyatlarini tushuntirib beradigan matn va aniq formulalarni joylashtirishni nazarda tutadi.
Blok diagrammasi. Bu dasturning o'zida va boshqa ilovalar yoki kompyuter apparatlari bilan o'zaro ta'siri xususiyatlarini tushunishga imkon beradigan grafik belgilar mavjudligini anglatadi. Ularning har biri alohida funktsiya, protsedura yoki formula uchun javobgar bo'lishi mumkin.
Bu vazifalarning xususiyatlari va tartibini ko'rsatadigan aniq holatlar uchun tavsiflashning alohida usullarini yaratishni nazarda tutadi.
Operator diagrammasi. Bu prototip yaratishni o'z ichiga oladi - u alohida operandlar bosib o'tadigan yo'llar asosida o'zaro ta'sirni ko'rsatadi.

Psevdokod. Dastur skeletining eskizi.

Algoritmni yozib olish

Dastur, funksiya yoki protseduraning o'z prototipini yaratishni qanday boshlash kerak? Buning uchun ushbu umumiy tavsiyalardan foydalanish kifoya:

Har bir algoritm o'z nomiga ega bo'lishi kerak, bu uning ma'nosini tushuntiradi.
Boshlanishi va oxiri borligiga ishonch hosil qiling.
Kirish va chiqish ma'lumotlarini tavsiflash kerak.
Muayyan ma'lumotlar bo'yicha muayyan harakatlarni bajarish uchun ishlatiladigan buyruqlarni belgilashingiz kerak.

Yozib olish usullari

Algoritmning beshta ko'rinishi bo'lishi mumkin. Ammo yozishning faqat ikkita usuli bor:

Rasmiy-og'zaki. Bu tavsifning asosan formulalar va so'zlar yordamida amalga oshirilishi bilan tavsiflanadi. Algoritm bosqichlarining mazmuni, shuningdek, bajarilish ketma-ketligi bu holda tabiiy kasbiy tilda erkin shaklda yoziladi.
Grafika. Eng keng tarqalgan. U blokli belgilar yoki algoritm diagrammalaridan foydalanadi. Ularning orasidagi aloqa maxsus chiziqlar yordamida ko'rsatiladi.

Biz dastur tuzilmasini ishlab chiqamiz

Uchta asosiy tur mavjud:

Chiziqli. Ushbu tuzilma bilan barcha harakatlar ketma-ketlikda va faqat bir marta amalga oshiriladi. Diagramma bajarilish tartibiga qarab yuqoridan pastgacha joylashtirilgan bloklar ketma-ketligiga o'xshaydi. Olingan birlamchi va oraliq ma'lumotlar hisoblash jarayonining yo'nalishiga ta'sir qila olmaydi.
Tarmoqlanish. Murakkab masalalarni hal qilishda amaliyotda keng qo'llanilishini topdi. Shunday qilib, agar dastlabki shartlarni yoki oraliq natijalarni hisobga olish zarur bo'lsa, unda kerakli hisob-kitoblar ularga muvofiq amalga oshiriladi va olingan natijaga qarab hisoblash jarayonining yo'nalishi o'zgarishi mumkin.

Tsiklik. Ko'p vazifalar bilan ishlashni osonlashtirish uchun dastur kodining ba'zi bo'limlarini ko'p marta takrorlash mantiqan. Qancha marta va nima qilish kerakligini belgilamaslik uchun tsiklik tuzilma qo'llaniladi. U berilgan shart bajarilgunga qadar takrorlanadigan buyruqlar ketma-ketligini nazarda tutadi. Looplardan foydalanish dastur yozishning murakkabligini sezilarli darajada kamaytirishga imkon beradi.

Dasturlash

Qaysi dasturlarda yaratilishi muhim. Shuni ta'kidlash kerakki, ularning ko'pchiligi muayyan ish sharoitlariga (masalan, brauzerda) "moslashtirilgan". Umuman olganda, dasturlash tillari ikki guruhga bo'linadi:

Funktsional.
Operator xonalari:

Protsessual emas;

Protsessual.

Qaysi biri tez-tez ishlatilishini taxmin qila olasizmi? Operator-protsessual - bu javob. Ular mashinaga asoslangan yoki mustaqil bo'lishi mumkin. Birinchisiga assemblerlar, avtokodlar va ramziy kodlash kiradi. Mustaqillar o'z yo'nalishi bo'yicha quyidagilarga bo'linadi:

protsessual;
muammoli;
ob'ekt.

Ularning har biri o'z qo'llash doirasiga ega. Ammo dasturlarni (foydali ilovalar yoki o'yinlar) yozish uchun ko'pincha ob'ektga yo'naltirilgan tillar qo'llaniladi. Albatta, siz boshqalardan foydalanishingiz mumkin, ammo haqiqat shundaki, ular omma uchun yakuniy iste'mol mahsulotlarini yaratish uchun eng rivojlangan. Ha, va agar siz hali qaerdan boshlash haqida aniq tasavvurga ega bo'lmasangiz, men sizga algoritmlash va ob'ektga yo'naltirilgan dasturlash asoslariga e'tibor berishingizni maslahat beraman. Endi bu juda mashhur yo'nalish bo'lib, unda siz ko'plab o'quv materiallarini topishingiz mumkin. Umuman olganda, algoritmlash va dasturlash tillarining asoslari hozir malakali ishlab chiquvchilarning etishmasligi tufayli kerak bo'lib, ularning ahamiyati kelajakda o'sib boradi.

Xulosa

Algoritmlar (va keyinchalik dasturlar bilan) bilan ishlashda siz barcha tafsilotlarni eng kichikigacha o'ylab ko'rishingiz kerak. Keyinchalik, kodning har bir ishlab chiqilmagan qismini aniqlash faqat qo'shimcha ishlarga olib keladi, ishlab chiqish xarajatlari va topshiriqni bajarish vaqtini oshiradi. Barcha nuanslarni puxta rejalashtirish va ishlab chiqish vaqt, kuch va pulni sezilarli darajada tejaydi. Xo'sh, endi ular ushbu maqolani o'qib chiqqandan so'ng siz algoritmlash va dasturlash asoslari haqida tushunchaga ega ekanligingizni aytishlari mumkin. Qolgan narsa bu bilimlarni qo'llashdir. Agar siz mavzuni batafsil o'rganmoqchi bo'lsangiz, men "Algoritmlash va dasturlash asoslari" (Semakin, Shestakov) 2012 kitobini tavsiya qilishim mumkin.

Har qanday jarayonni boshqarish muayyan qoidalar va aniq harakatlarni talab qiladi. Kompyuter - bu ma'lumotlarni yaratish, saqlash, qayta ishlash va uzatishni avtomatlashtirish uchun mo'ljallangan qurilma, ya'ni muayyan vazifani bajarish uchun aniq ko'rsatmalarga rioya qilish kerak.

Kompyuterda muammoni hal qilish uchun mo'ljallangan dasturlarni yaratish uchun uni hal qilish algoritmini tuzish kerak.

Algoritmlar, masalan, qo'shish, ko'paytirish, algebraik tenglamalarni echish, matritsalarni ko'paytirish va boshqalar qoidalari. Algoritm soʻzi algoritmi soʻzidan kelib chiqqan boʻlib, IX asrdagi Xorazm matematigi al-Xorazmiyning arabcha nomining lotincha transliteratsiyasi hisoblanadi. Al-Xorazmiy risolasining lotincha tarjimasi tufayli 12-asrda yevropaliklar pozitsion sanoq sistemasi bilan tanishdilar, oʻrta asrlarda Yevropada algoritm oʻnlik pozitsion sanoq sistemasi va undagi sanash qoidalari deb ataldi.

Boshqacha qilib aytganda, algoritm aniq ko'rsatma bo'lib, ko'rsatmalar inson faoliyatining deyarli barcha sohalarida mavjud. Jismoniy tajriba o'tkazish, shkaf yoki televizorni yig'ish yoki qismni qayta ishlash algoritmlari mumkin. Biroq, har bir ko'rsatma algoritm emas.

Ko'rsatma ma'lum talablarni qondirsagina algoritmga aylanadi. Algoritmning talablaridan biri noaniqlikdir, ya'ni. agar bir xil ma'lumotlarga qo'llanilsa, u bir xil natija beradi.

Kompyuterga nisbatan algoritm hisoblash jarayonini rasmiylashtirishga imkon beradi, bu mumkin bo'lgan dastlabki ma'lumotlarning ma'lum bir to'plamini qayta ishlashdan boshlanadi va ushbu dastlabki ma'lumotlar bilan aniqlangan natijalarni olishga qaratilgan. Hisoblash jarayoni atamasi boshqa turdagi ma'lumotlarni qayta ishlashga ham taalluqlidir, masalan, ramziy, grafik yoki audio.

Agar hisoblash jarayoni natijalarni olish bilan yakunlansa, u holda algoritm ko'rib chiqilayotgan dastlabki ma'lumotlar to'plamiga tegishli deyiladi. Aks holda, ular algoritm dastlabki ma'lumotlar to'plamiga taalluqli emasligini aytishadi. Har qanday qo'llaniladigan algoritm quyidagi asosiy xususiyatlarga ega:

· diskretlik;

· ishonch;

· samaradorlik;

· ommaviy xarakter.

Diskretlik - oddiy yoki oldindan belgilangan (kichik dastur) bosqichlarni ketma-ket bajarish. Manba ma'lumotlarini natijalarga aylantirish vaqt bo'yicha diskret ravishda amalga oshiriladi.

Aniqlik foydalanuvchi va foydalanilgan texnik vositalardan qat'i nazar, olingan natijalarning mos kelishidan iborat (ko'rsatmalarning bir ma'noli talqini).

Samaradorlik cheklangan miqdordagi amallarni bajargandan keyin natija olish imkoniyatini bildiradi.

Ommaviy xarakter algoritmni dastlabki ma'lumotlarning o'ziga xos qiymatlarida (umumiy shaklda ishlab chiqish) farq qiladigan o'xshash muammolarning butun sinfiga qo'llash imkoniyati yotadi.

Algoritmni belgilash uchun uning quyidagi elementlarini tavsiflash kerak:

· mumkin bo'lgan dastlabki ma'lumotlar, oraliq va yakuniy natijalar yig'indisini tashkil etuvchi ob'ektlar to'plami;

· boshlash qoidasi;

· axborotni bevosita qayta ishlash qoidasi (harakatlar ketma-ketligini tavsiflash);

· tugatish qoidasi;

· natijalarni chiqarish qoidasi.

Algoritm har doim ma'lum bir ijrochi uchun mo'ljallangan. Bizning holatlarimizda bunday ijrochi kompyuterdir. Kompyuterda amalga oshirish imkoniyatini ta'minlash uchun algoritm kompyuterga tushunarli tilda, ya'ni dasturlash tilida tasvirlangan bo'lishi kerak.

Algoritm va dastur tushunchalari unchalik aniq belgilanmagan. Odatda, dastur muammoni hal qilish algoritmining ma'lum bir foydalanuvchiga yo'naltirilgan yakuniy versiyasidir.

Shunday qilib, biz kompyuter dasturiga quyidagi ta'rifni berishimiz mumkin:

Algoritmlarni tavsiflashning asosiy usullari quyidagilardan iborat:

· og'zaki-formulali (tabiiy tilda);

· konstruktiv yoki blok-sxema;

· maxsus algoritmik tillardan foydalanish;

· grafik diagrammalardan foydalanish (grafik - bu har bir chiziq ikkita nuqtani bog'laydigan nuqtalar va chiziqlar yig'indisidir. Nuqtalar cho'qqilar, chiziqlar - qirralar deyiladi).

Dasturlarni kompilyatsiya qilishdan oldin ular ko'pincha yuqorida tavsiflangan usullardan biri yordamida berilgan muammoni hal qilish algoritmini yaratadilar.

Da og'zaki-formulali usul algoritm harakatlar ketma-ketligini tashkil etuvchi nuqtalar uchun formulalar bilan matn shaklida yoziladi.

Masalan, siz quyidagi ifodaning qiymatini topishingiz kerak:

y = 4a - (x + 3).

Og'zaki va formulali tarzda ushbu muammoni hal qilish algoritmini quyidagi shaklda yozish mumkin:

1. a va x qiymatlarini kiriting.

2. X va 3 ni qo‘shing.

3. a ni 4 ga ko‘paytiring.

4. 4a dan yig‘indini (x+3) ayiring.

5. Ifodani baholash natijasi sifatida y ni chiqaring.

Da blok-sxematik tavsifi algoritm strelkalar bilan nazorat chiziqlari (oqim yo'nalishlari) bilan bog'langan geometrik raqamlar (bloklar) bilan tasvirlangan. Bloklar harakatlar ketma-ketligini qayd etadi.

Algoritmni yozishning bunday turi eng katta afzalliklarga ega. Bu eng vizual: hisoblash jarayonining har bir operatsiyasi alohida geometrik shakl sifatida tasvirlangan. Bundan tashqari, algoritmning grafik tasviri turli shart-sharoitlarga, hisoblash jarayonining alohida bosqichlarining takrorlanishiga va boshqa tafsilotlarga bog'liq holda masalani yechish usullarining tabaqalanishini aniq ko'rsatadi.

Dasturlarni loyihalash muayyan talablarga javob berishi kerak (2-rasm). Hozirgi vaqtda dasturlar va dasturiy hujjatlarni ishlab chiqish, bajarish qoidalarini belgilaydigan yagona dastur hujjatlari tizimi (USPD) mavjud. ESPD, shuningdek, algoritmlarning oqim sxemalarini loyihalash qoidalarini belgilaydi (GOST 10.002-80 ESPD, GOST 10.003-80 ESPD).

Algoritmning xususiyatlaridan biri diskretlikdir, ya'ni. hisoblash jarayonini alohida bosqichlarga ko'rsatish va dasturning alohida bo'limlarini muayyan tuzilmalarga ajratish.

Har qanday hisoblash jarayoni elementar algoritmik tuzilmalarning kombinatsiyasi sifatida ifodalanishi mumkin:

· Kuzatish. Buyruqlarning yuqoridan pastgacha ketma-ket bajarilishini nazarda tutadi. Agar algoritm faqat ketma-ketlik tuzilmalaridan iborat bo'lsa, u chiziqli bo'ladi.

· Tarmoqlanish. Dasturning bajarilishi ikkita, bir nechta yoki ko'p filiallardan biri bo'ylab davom etadi. Filialni tanlash filialning kirish holatiga va bu erda olingan ma'lumotlarga bog'liq.

· Velosiped. Muayyan harakatlarni takroriy takrorlash imkoniyatini nazarda tutadi. Takrorlashlar soni tsiklning holatiga bog'liq.

· Funktsiya (kichik dastur). Asosiy dasturdan ajratilgan buyruqlar, agar ular asosiy dasturdan (uning istalgan joyidan) chaqirilsagina bajariladi. Xuddi shu funktsiyani asosiy dasturdan xohlagancha ko'p marta chaqirish mumkin.

Algoritmlarning uchta asosiy turi mavjud:

Zamonaviy dasturlash tizimlari odatda foydalanuvchilarga kuchli va qulay dastur ishlab chiqish vositalarini taqdim etadi. Bularga quyidagilar kiradi:

· kompilyator yoki tarjimon;

· integratsiyalashgan rivojlanish muhiti;

· dastur matnlarini yaratish va tahrirlash vositalari;

· standart dasturlar va funksiyalarning keng kutubxonalari;

· disk raskadrovka dasturlari, ya'ni. dasturdagi xatolarni topish va tuzatishga yordam beruvchi dasturlar;

· foydalanuvchilarga qulay muloqot muhiti;

· ko'p oynali ish rejimi;

· kuchli grafik kutubxonalar; kutubxonalar bilan ishlash uchun yordamchi dasturlar;

· o'rnatilgan assembler;

· o'rnatilgan yordam stoli;

· boshqa o'ziga xos xususiyatlar.

Algoritmlarni o'rganish va bilishning ahamiyatini tushunish uchun birinchi qadam algoritm nimani anglatishini to'g'ri aniqlashdir. Mashhur "Algoritmlar: Qurilish va tahlil" kitobiga ko'ra (Kormen, Leiserson, Rivest, Shtayn) "algoritm - bu kirishiga ma'lum miqdor yoki miqdorlar to'plami berilgan va natijasi bo'lgan har qanday aniq belgilangan hisoblash protsedurasi ( chiqish) qiymati yoki qiymatlar to'plami." Boshqacha qilib aytganda, algoritmlar aniq belgilangan maqsadga erishish uchun yo'l xaritalariga o'xshaydi. Fibonachchi ketma-ketligi a'zolarini hisoblash uchun kod bo'lagi ma'lum bir algoritmni amalga oshirishdir. Hatto ikkita raqamni qo'shishning oddiy funktsiyasi ham oddiy bo'lsa ham, algoritmdir.

Algoritmni bajarish vaqtini tahlil qilish

Biroq, ko'pgina murakkab algoritmlarning bajarilish vaqti nafaqat kiritilgan ma'lumotlarning hajmiga, balki boshqa ko'plab omillarga ham bog'liq. Masalan, butun sonlar to'plamini saralash algoritmi, agar to'plam allaqachon tartiblangan bo'lsa, tezroq ishlashi mumkin. Qatlning eng yomon holati va o'rtacha ijro ishi haqida gapirish odatiy holdir. Eng yomon holatda bajarish vaqti - barcha mumkin bo'lgan kirishlarning "eng yomoni" bilan algoritmning maksimal ishlash vaqti. O'rtacha bajarilish holati barcha mumkin bo'lgan kirishlar bo'yicha algoritmning o'rtacha ishlash vaqtidir. Ushbu ikki turdagi bajarilish vaqtining eng yomoni haqida fikr yuritish oson va shuning uchun ko'pincha ma'lum bir algoritm uchun benchmark sifatida ishlatiladi. Algoritmning eng yomon va o'rtacha bajarilish vaqtini aniqlash jarayoni ancha murakkab bo'lishi mumkin, chunki Odatda barcha mumkin bo'lgan kirishlar uchun algoritmni ishga tushirish mumkin emas.