1. Algoritm tushunchasi. Algoritmlarni loyihalashning asosiy bosqichlari. Algoritm tahlili tushunchasi

Hayec algorismus ars prayesens dicitur, qua bilan / Talibus Indorum fruimur bis quinquye figuris.
bu quyidagiga tarjima qilinadi:
Algoritm - bu hozirgi paytda biz hind figuralarini ishlatadigan san’at, ularning soni beshdan ikki marta.
She’r bir necha yuz satrdan iborat bo‘lib, yangi uslubdagi hind zarlari bilan hisoblash san’atini umumlashtiradi (Tali Indorum) yoki hind raqamlari
"Algoritm" ta’rifi bo‘yicha turli xil qarashlarni batafsil taqdim etish uchun qarang Algoritm tavsiflari.
Norasmiy ta’rif "operasiyalar ketma-ketligini aniq belgilaydigan qoidalar to‘plami" bo‘lishi mumkin, barcha kompyuter dasturlarini (shu jumladan raqamli hisob-kitoblarni amalga oshirmaydigan dasturlarni) o‘z ichiga oladi va (masalan) har qanday belgilangan byurokratik prosedura yoki oshpaz kitobi resept.
Umuman olganda, dastur oxir-oqibat to‘xtab qolgandagina algoritm bo‘ladi^[30] - Garchi; .. bo‘lsa ham cheksiz ilmoqlar ba’zan kerakli bo‘lishi mumkin.
Algoritmning prototipik misoli Evklid algoritmi, bu ikkita butun sonning maksimal umumiy bo‘luvchisini aniqlash uchun ishlatiladi; misol (boshqalar ham bor) tomonidan tasvirlangan oqim sxemasi yuqorida va keyingi qismda misol sifatida.
Boolos, Jeffri va 1974, 1999 quyidagi iqtibosda "algoritm" so‘zining norasmiy ma’nosini taklif eting:
Hech bir inson etarlicha tez, etarlicha uzoq yoki etarlicha kichik yozolmaydi ("cheksiz va kichikroq cheksiz ... siz molekulalar, atomlar, elektronlar ustida yozishga urinib ko‘rgan bo‘lar edingiz). ularning nomlarini bir nechta yozuvlarda birin ketin yozish orqali o‘rnatiladi. Ammo odamlar ma’lum darajada cheksiz to‘plamlar holatida bir xil darajada foydali narsa qilishlari mumkin: Ular berishi mumkin ni aniqlash bo‘yicha aniq ko‘rsatmalar n to‘plamning uchinchi a’zosi, o‘zboshimchalik bilan cheklangan uchun n. Bunday ko‘rsatmalar aniq bir shaklda berilishi kerak ularning ortidan hisoblash mashinasi kelishi mumkin edi, yoki tomonidan belgilar bo‘yicha juda oddiy operasiyalarni bajarishga qodir bo‘lgan odam.
An "son-sanoqsiz cheksiz to‘plam" uning elementlari butun sonlar bilan bitta-bitta yozishmalarga kiritilishi mumkin bo‘lgan narsadir. Shunday qilib, Boolos va Jefri algoritm an-dan butun sonlarni "yaratadigan" jarayon uchun ko‘rsatmalarni nazarda tutishini aytmoqdalar o‘zboshimchalik bilan nazariy jihatdan o‘zboshimchalik bilan katta bo‘lishi mumkin bo‘lgan "kirish" tamsayılari yoki butun sonlari. Masalan, algoritm algebraik tenglama bo‘lishi mumkin y = m + n (ya’ni ikkita o‘zboshimchalik bilan "kirish o‘zgaruvchilari" m va n mahsulot ishlab chiqaradigan y), ammo turli mualliflarning tushunchani aniqlashga urinishlari shundan dalolat beradiki, bu so‘z bundan ham ko‘proq narsani anglatadi (qo‘shimcha misol uchun):
Aniq ko‘rsatmalar ("kompyuter" tushunadigan tilda) tez, samarali, "yaxshi" uchun "kompyuter" ning "harakatlari" ni ko‘rsatadigan jarayon (kerakli ichki ma’lumotlar va imkoniyatlar bilan jihozlangan mashina yoki odam) o‘zboshimchalik bilan kiritilgan tamsayılar / belgilarni topish, dekodlash va keyin ishlov berish m va n, belgilar + va = … Va "samarali "oqilona" vaqtda ishlab chiqarish, chiqish-butun son y belgilangan joyda va belgilangan formatda.
Tushunchasi algoritm tushunchasini aniqlash uchun ham ishlatiladi aniqlik- tushuntirish uchun markaziy tushunchadir rasmiy tizimlar ning kichik to‘plamidan boshlab vujudga keladi aksiomalar va qoidalar. Yilda mantiq, algoritmni bajarishni talab qiladigan vaqtni o‘lchash mumkin emas, chunki u odatiy jismoniy o‘lchov bilan bog‘liq emas. Davom etayotgan ishni tavsiflovchi bunday noaniqliklardan, ta’rifining mavjud emasligi kelib chiqadi algoritm bu atamaning aniq (qandaydir ma’noda) va mavhum ishlatilishiga mos keladi.
Algoritmlar kompyuterlarning ma’lumotlarni qayta ishlashida muhim ahamiyatga ega. Ko‘pgina kompyuter dasturlarida ishchilarning ish haqini hisoblash yoki o‘quvchilarning hisobot kartalarini bosib chiqarish kabi belgilangan vazifani bajarish uchun kompyuter bajarishi kerak bo‘lgan aniq ko‘rsatmalarni - aniq tartibda batafsil bayon qiluvchi algoritmlar mavjud. Shunday qilib, algoritmni a tomonidan simulyasiya qilinishi mumkin bo‘lgan har qanday operasiyalar ketma-ketligi deb hisoblash mumkin Turing to‘liq tizim. Ushbu tezisni tasdiqlaydigan mualliflar orasida Minskiy (1967), Savage (1987) va Gurevich (2000) mavjud:
Minskiy: "Ammo biz Turing bilan birga" tabiiy ravishda "samarali deb atash mumkin bo‘lgan har qanday prosedurani (oddiy) mashina tomonidan amalga oshirilishini davom ettiramiz. Garchi bu o‘ta tuyulishi mumkin bo‘lsa ham, argumentlar ... uning foydasiga rad etish qiyin ".
Gurevich: "... Turingning o‘zining tezis foydasiga norasmiy argumenti kuchliroq tezisni oqlaydi: har bir algoritmni Tyuring mashinasi tomonidan simulyasiya qilish mumkin ... Savage [1987] ga ko‘ra, algoritm Turing mashinasi tomonidan aniqlangan hisoblash jarayonidir".
Turing mashinalari tugamaydigan hisoblash jarayonlarini belgilashi mumkin. Algoritmlarning norasmiy ta’riflari odatda algoritm har doim tugashini talab qiladi. Ushbu talab rasmiy prosedura algoritmini umumiy holatda imkonsiz yoki yo‘qligini hal qilish vazifasini bajaradi - bu katta teorema tufayli. hisoblash nazariyasi nomi bilan tanilgan muammoni to‘xtatish.
Odatda, algoritm ma’lumotni qayta ishlash bilan bog‘liq bo‘lsa, ma’lumotlarni kirish manbasidan o‘qish, chiqish moslamasiga yozish va keyingi ishlov berish uchun saqlash mumkin. Saqlangan ma’lumotlar algoritmni bajaruvchi sub’ektning ichki holatining bir qismi sifatida qaraladi. Amalda davlat bir yoki bir nechtasida saqlanadi ma’lumotlar tuzilmalari.
Ushbu hisoblash jarayonlarining ba’zilari uchun algoritm qat’iy belgilangan bo‘lishi kerak: yuzaga kelishi mumkin bo‘lgan barcha sharoitlarda uning qo‘llanilish uslubida ko‘rsatilgan. Bu shuni anglatadiki, har qanday shartli qadamlar muntazam ravishda, har holda alohida ko‘rib chiqilishi kerak; har bir ish uchun mezon aniq (va hisoblash mumkin) bo‘lishi kerak.
Algoritm aniq qadamlarning aniq ro‘yxati bo‘lganligi sababli, hisoblash tartibi har doim algoritmning ishlashi uchun hal qiluvchi ahamiyatga ega. Ko‘rsatmalar odatda aniq ro‘yxatlangan deb taxmin qilinadi va "yuqoridan" boshlanib, "pastga" tushgan deb ta’riflanadi - bu g‘oyani rasmiy ravishda tasvirlaydigan fikr boshqaruv oqimi.
Hozirga qadar algoritmni rasmiylashtirish bo‘yicha munozaralar quyidagilarni o‘z zimmasiga olgan majburiy dasturlash. Bu eng keng tarqalgan tushuncha - vazifani diskret, "mexanik" vositalar bilan tavsiflashga urinish. Ushbu rasmiylashtirilgan algoritmlarning yagona konsepsiyasi tayinlash jarayoni, bu o‘zgaruvchining qiymatini belgilaydi. Bu "intuitivligidan kelib chiqadi"xotira"skretchpad sifatida. Bunday topshiriqning namunasini quyida topish mumkin.
Algoritmni tashkil etadigan ba’zi bir muqobil tushunchalar uchun qarang funksional dasturlash va mantiqiy dasturlash.