1 maruza: Algoritm va uning ta’riflari Asosiy savollar

Algoritmni raqamlash
Algoritmni raqamlash ularning tadqiqot va tahlilida muhim rol o'ynaydi. Har qanday algoritmni cheklangan so'z sifatida ko'rsatish mumkin (ma'lum alifbo belgilarining ketma -ket ketma -ketligi sifatida ifodalanadi) va cheklangan alifbodagi barcha sonli so'zlar majmui hisoblanishi mumkin, shuning uchun ham barcha algoritmlar to'plami sanaladi. Bu shuni anglatadiki, natural sonlar to'plami va algoritmlar to'plami o'rtasida birma-bir xaritalash, ya'ni har bir algoritmga raqam berish qobiliyati.
Algoritmlarning raqamlanishi bir vaqtning o'zida barcha algoritmik hisoblanadigan funktsiyalarning raqamlanishi bo'lib, har qanday funktsiya cheksiz sonli sonlarga ega bo'lishi mumkin.
Raqamlashning mavjudligi sizga algoritmlar bilan xuddi raqamlar kabi ishlash imkonini beradi. Raqamlash, ayniqsa, boshqa algoritmlar bilan ishlaydigan algoritmlarni o'rganishda foydalidir.
X boshlang'ich ob'ektlar to'plami va kerakli ob'ektlar to'plami Y bilan ma'lum bir ommaviy muammo bo'lsin. Ommaviy masalaning echimi bo'lishi uchun X va Y to'plamlarining elementlari konstruktiv ob'ektlar bo'lishi zarur. Shunday qilib, bu elementlarning elementlarini natural sonlar bilan sanash mumkin. X∈ X boshlang'ich ob'ekt bo'lsin, uning sonini n (x) bilan belgilaylik. Agar boshlang'ich x uchun ommaviy masalada n (y) raqami bilan kerakli y∈ Y ob'ektini olish kerak bo'lsa, biz f: Nn → N arifmetik funktsiyani aniqlaymiz, f (n (x)) = n (y).
Ommaviy masalalar uchun arifmetik funktsiyalarni tuzishga misol sifatida massaviy muammolarni ko'rib chiqing.
1. Agar natural sonlar qatori] berilgan bo'lsa, unda unga 2x1, 3x2, ... p (n) xn natural son berilishi mumkin, bu erda p (n) n -bosh raqam. Masalan, 5 uzunlikdagi qatorni ko'rib chiqing:
] 2x13x25x37x411x5.
Bu raqamlash f arifmetik funktsiyasini belgilaydi (masalan, f (73500) = f (22315372110) = 20315272113 = 4891425).
2. Har qanday ratsional son qandaydir natural songa ega. Muammoning kerakli ob'ektlari to'plamining raqamlanishi ahamiyatsiz:
("Ha", "yo'q") a (1, 0). Bu ommaviy muammo uchun siz oldingi misolning texnikasi yordamida bitta argumentning arifmetik funktsiyasini tuzishingiz mumkin yoki siz uchta argumentli funktsiyani (dastlabki uchlik elementlarining uchta raqami) ko'rib chiqishingiz mumkin.
3. Dastur matnlarining raqamlanishini quyidagicha amalga oshirish mumkin: har qanday dasturni 256 arli sanoq sistemasida raqam yozish sifatida qabul qilish mumkin (agar dasturni yozishda ASCII jadvalining belgilaridan foydalanilgan bo'lsa).
Ommaviy muammodan arifmetik funktsiyaga o'tish massaviy muammoning echimi borligi haqidagi savolni arifmetik funktsiya qiymatlarini uning argumentidan hisoblashning samarali usuli borligi haqidagi savolga kamaytirishga imkon beradi. (lar).