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

Algoritmlarni ifodalash

Algoritmlarni ko‘pgina belgilar, shu jumladan, ifodalash mumkin tabiiy tillar, psevdokod, oqim jadvallari, drakon-jadvallar, dasturlash tillari yoki boshqaruv jadvallari (tomonidan qayta ishlangan tarjimonlar). Algoritmlarning tabiiy tildagi ifodalari keng va noaniq bo‘lib, murakkab yoki texnik algoritmlar uchun kamdan-kam qo‘llaniladi. Psevdokod, oqim jadvallari, drakon-jadvallar va boshqaruv jadvallari - bu tabiiy tilga asoslangan bayonotlarda uchraydigan ko‘plab noaniqliklardan qochadigan algoritmlarni ifodalashning tuzilgan usullari. Dasturlash tillari birinchi navbatda algoritmlarni kompyuter tomonidan bajarilishi mumkin bo‘lgan shaklda ifodalash uchun mo‘ljallangan, lekin ko‘pincha algoritmlarni aniqlash yoki hujjatlashtirish usuli sifatida ishlatiladi.
Vakillarning xilma-xilligi mavjud va berilganni ifodalash mumkin Turing mashinasi dastur mashinalar jadvallari ketma-ketligi sifatida (qarang cheklangan holatdagi mashina, davlat o‘tish jadvali va boshqaruv jadvali ko‘proq uchun), oqim sxemalari sifatida va drakon-jadvallar (qarang holat diagrammasi ko‘proq uchun), yoki ibtidoiy shakl sifatida mashina kodi yoki yig‘ilish kodi "to‘rtliklar to‘plamlari" deb nomlangan (qarang Turing mashinasi ko‘proq).
Algoritmlarni quyidagicha Turing mashinasini tavsiflashning qabul qilingan uchta darajasiga ajratish mumkin:
1 Yuqori darajadagi tavsif
“… Dastur tafsilotlarini inobatga olmagan holda algoritmni tasvirlash uchun nasr. Ushbu darajada, biz mashinaning lentasini yoki boshini qanday boshqarishini eslatib o‘tishning hojati yo‘q. "
2 Amalga oshirish tavsifi
“... nasr Turing mashinasining boshidan foydalanish uslubini va lentada ma’lumotlarni saqlash usulini aniqlash uchun ishlatiladi. Ushbu darajada biz davlatlar yoki o‘tish funksiyalari haqida batafsil ma’lumot bermaymiz. "
3 Rasmiy tavsif
Eng batafsil "eng past daraja" Turing mashinasining "holat jadvali" ni beradi.
Uchala darajada tasvirlangan oddiy "Qo‘shish m + n" algoritmiga misol uchun qarang Algoritm misollar.
Yilda kompyuter tizimlari, algoritm asosan misolidir mantiq dasturiy ta’minot ishlab chiquvchilari tomonidan mo‘ljallangan "maqsadli" kompyuter (lar) uchun samarali bo‘lishi uchun dasturiy ta’minotda yozilgan chiqish berilgan (ehtimol bekor) kiritish. Optimal algoritm, hattoki eski apparatda ishlaydi, maqbul bo‘lmaganidan yuqori (yuqori) natijalarga olib keladi vaqtning murakkabligi) samaraliroq qo‘shimcha qurilmalarda ishlaydigan xuddi shu maqsad uchun algoritm; shuning uchun algoritmlar, xuddi kompyuter texnikasi kabi, texnologiya hisoblanadi.
"Elegant" (ixcham) dasturlar, "yaxshi" (tezkor) dasturlar : "Oddiylik va nafislik" tushunchasi norasmiy ravishda paydo bo‘ladi Knuth va aniq ichida Chaitin:
Knut: "... biz xohlaymiz yaxshi estetik ma’noda ba’zi bir algoritmlar. Bitta mezon - bu algoritmni bajarish uchun sarflangan vaqt…. Boshqa mezon - algoritmning kompyuterlarga moslashuvchanligi, soddaligi va nafisligi va boshqalar. "
Chaitin: "... dastur" oqlangan "bo‘lib, demak, u o‘zi ishlab chiqaradigan mahsulotni ishlab chiqarish uchun eng kichik dasturdir"
Chaitin o‘zining ta’rifiga quyidagicha qo‘shiladi: "Men sizga dasturning nafisligini isbotlay olmasligingizni ko‘rsataman’"- shunga o‘xshash dalil hal qiladi Muammoni to‘xtatish (o‘sha erda).
Algoritm va funksiyalarni algoritm bilan hisoblash mumkin: Berilgan funksiya uchun bir nechta algoritmlar mavjud bo‘lishi mumkin. Bu dasturchi uchun mavjud bo‘lgan ko‘rsatmalar to‘plamini kengaytirmasdan ham to‘g‘ri. Rojersning ta’kidlashicha, "bu ... tushunchasini farqlash muhimdir algoritm, ya’ni prosedura va tushunchasi algoritm bilan hisoblanadigan funksiya, ya’ni prosedura bo‘yicha xaritalash. Xuddi shu funksiya bir nechta turli algoritmlarga ega bo‘lishi mumkin ".
Afsuski, yaxshilik (tezkorlik) va nafislik (ixchamlik) o‘rtasida o‘zaro kelishuv bo‘lishi mumkin - nafis dastur hisoblashni bajarish uchun kamroq nafisga qaraganda ko‘proq qadam tashlashi mumkin. Evklid algoritmidan foydalanadigan misol quyida keltirilgan.
Kompyuterlar (va kompyuterlar), hisoblash modellari: Kompyuter (yoki inson "kompyuteri")) cheklangan turdagi mashina, "diskretli deterministik mexanik qurilma" uning ko‘rsatmalariga ko‘r-ko‘rona amal qiladigan. Melzak va Lambekning ibtidoiy modellari ushbu tushunchani to‘rt elementga qisqartirdi: alohida, ajralib turadigan joylar, alohida, ajratib bo‘lmaydigan hisoblagichlar (agent va ko‘rsatmalar ro‘yxati samarali agentning qobiliyatiga nisbatan.
Algoritmni simulyasiya qilish: kompyuter (komputer) tili: Knut o’quvchiga "algoritmni o’rganishning eng yaxshi usuli - uni sinab ko’rish ... darhol qalam va qog’ozni olib, misol orqali ishlash" ni maslahat beradi. Ammo haqiqiy narsani simulyasiya qilish yoki bajarish haqida nima deyish mumkin? Dasturchi algoritmni simulyator / kompyuter / komputer qila oladigan tilga tarjima qilishi kerak samarali ijro etish. Tosh bunga misol keltiradi: kvadrat tenglamaning ildizlarini hisoblashda hisoblashchi kvadrat ildiz otishni bilishi kerak. Agar ular bajarilmasa, unda algoritm samarali bo‘lishi uchun kvadrat ildiz chiqarib olish uchun bir qator qoidalarni taqdim etishi kerak.
Bu shuni anglatadiki, dasturchi maqsadli hisoblash agentiga (kompyuter / komputer) nisbatan samarali bo‘lgan "tilni" bilishi kerak.
Ammo simulyasiya uchun qanday modeldan foydalanish kerak? Van Emde Boas "biz asoslasak ham kuzatadi murakkablik nazariyasi beton mashinalar o‘rniga mavhumlikda modelni tanlashda o‘zboshimchalik saqlanib qoladi. Aynan shu nuqtada simulyasiya kiradi ". Tezlikni o‘lchashda ko‘rsatmalar to‘plami muhim ahamiyatga ega. Masalan, Evklidning qolgan qismini hisoblash algoritmidagi kichik dastur, agar dasturchi bo‘lsa, juda tez bajariladi.modul"ko‘rsatma faqat ayirishdan ko‘ra mavjud (yoki yomonroq: faqat Minskiyning" kamayishi ").
Tarkibiy dasturlash, kanonik tuzilmalar: Per Cherkov-Turing tezisi, har qanday algoritmni ma’lum bo‘lgan model tomonidan hisoblash mumkin Turing tugadiVa Minskiy namoyishlari uchun Turing to‘liqligi faqat to‘rtta ko‘rsatmani talab qiladi - shartli GOTO, sharsiz GOTO, topshiriq, HALT. Kemeny va Kurtzning ta’kidlashicha, "intizomsiz" so‘zsiz GOTO va shartli IF-THEN GOTOlardan foydalanish natijaga olib kelishi mumkin "spagetti kodi", dasturchi tuzilgan dasturlarni faqat shu ko‘rsatmalardan foydalangan holda yozishi mumkin; boshqa tomondan" yomon tuzilgan dasturlarni tuzilgan tilda yozish ham mumkin ". Tausvort uchtasini ko‘paytiradi Bohm-Jakopini kanonik tuzilmalari: SEKUYeNCYe, IF-THEN-BOSHQA va WHILE-DO, yana ikkita: DO-WHILE va Case. Tuzilgan dasturning qo‘shimcha afzalligi shundaki, u o‘zini o‘zi qarz beradi to‘g‘riligining dalillari foydalanish matematik induksiya.
Kanonik oqim sxemasi belgilari: A deb nomlangan grafik yordamchi oqim sxemasi, algoritmni tavsiflash va hujjatlashtirish usulini taklif qiladi (va bitta kompyuter dasturi). Minsky mashinasining dastur oqimi singari, oqim sxemasi har doim sahifaning yuqori qismidan boshlanadi va pastga tushadi. Uning asosiy ramzlari atigi to‘rttadan iborat: dastur oqimini ko‘rsatuvchi yo‘naltirilgan o‘q, to‘rtburchak (SEQUYeNCYe, GOTO), olmos (IF-THEN-ELSE) va nuqta (OR-galstuk). Böhm-Jakopini kanonik tuzilmalari ushbu ibtidoiy shakllardan yasalgan. Sub-tuzilmalar to‘rtburchaklar ichida "joylashishi" mumkin, lekin faqat bitta ustki tuzilishdan chiqish sodir bo‘lganda. Belgilar va ulardan kanonik tuzilmalarni qurish uchun foydalanish diagrammada ko‘rsatilgan.