Sanoq sitemalari. Algoritmlarni loyihalash va tahlil qilish. Mundarija
Download 40.32 Kb.
|
kurs ishi
|
Sanoq sitemalari. Algoritmlarni loyihalash va tahlil qilish. Mundarija 1-bob. Sanoq sistemalari. 1.1. Sanoq sistemalari haqida. 1.2. Sanoq sistemalarida arifmetik amallar. 1.3. Ikkilik sanoq sistemasida arifmetik amallar bajarish. 1.4. Sakkizlik sanoq sistemasida arifmetik amallar bajarish. 1.5. O’n oltilik sanoq sistemasida arifmetik amallar bajarish. 1.6. Turli xil bo’lgan sanoq sistemalari ustida arifmetik amallar bajarish. 2-bob. Algoritmlarni loyihalash va tahlil qilish. 2.1.Algoritm tushunchasi. 2.2.Algoritmlarni loyihalash. 2.3.Algoritmlarni loyihalashning asosiy bosqichlari. O’quvchi yoshlarga kompyuter texnikasini o’rgatishdan avval uni nazariy jihatdan singdirish maqsadga muvofiq. Bunda sanoq sistemalari muhim o’ringa ega. Sanoq sistemasi bu – sonlarni o’qish va arifmetik amallarni bajarish uchun qulay ko’rinishda yozish usuli. Qadimda hisob ishlarida ko’proq barmoqlardan foydalanilgan. Shu sababli narsalarni 5 yoki 10 tadan taqsimlashgan . keyinchalik o’nta o’nlik maxsus nom - yuzlik , o’nta yuzlik – minglik nomini olgan va h.k Turli davrlarda turli xalqlar, qabilalar raqamlar va sonlarni ifodalashda turlicha belgidan foydalanganlar. Qadimda ba’zi xalqlar ishlatadigan sonlar alifbosi beshta, o’n ikkita, yigirmata, ba’zilari oltmishta belgini o’z ichiga olgan . Sonlar sistemasidagi raqamlar soni shu sistemaning asosi deb yuritiladi. Kundalik hayotimizda ishlatilayotgan o’nlik sanoq sistemasidagi sonlar ustida arifmetik amallar bajarish usullarini bilamiz. Mazkur usullari boshqa barcha pozitsiyaga bog’liq bo’lgan sanoq sistemasida qo’shish amalini ko’rsak, biz avval birliklarni, so’ng o’nliklarni, keyin yuzliklarni va hokazolarni o’zaro qo’shib boramiz. Bu jarayon barcha pozitsiyali sanoq sistemalar uchun o’rinli bo’lib, toki oxirgi qiymat bo’yicha eng katta razryadni qo’shishgacha davom etadi. Mazkur jarayonda shu narsani doim eslash kerakki, agar biror razryad sonlarini qo’shganimizda natija sanoq sistemasi asosi qiymatidan katta chiqsa, yig’indining sanoq sistema asosidan katta bo’lsa keying razryadga o’tkazish kerak. Masalan, o’nlik sanoq sistemasida: 19327510 + 7953810 198310 ___________ 27479610 Shuni yodda tutish kerakki, sanoq sistema asosining qiymati 10 deb hisoblanadi. Shu sababli ham sanoq sistemasi asosidan keying sonlar 11, 12, …. va h.k. deb yuritiladi. …. va h.k. deb yuritiladi. Hisoblash texnikasida va dasturlashda asosi 2,8 va 16 ga teng bo’lgan sanoq sistemalari qo’laniladi. Buni tushunish uchun, keling, misollarga murojat qilaylik. Masalan, sakkizlik sanoq sistemasida 8 ta raqamlar bor: 0, 1 , 2 , 3, 4, 5, 6, 7. O’n oltilik sanoq sistemasida raqamlardan keyin lotin alfbosidagi bosh harflardan foydalaniladi.O’n oltilik sanoq sistemasida 9 ta raqam va 6 ta harf bor: 0, 1 , 2 , 3, 4, 5, 6, 7.8,9, A,B,C,D,E,F Sanoq sistemalarining quyidagi jadvalini keltiramiz.
Ikkilik sanoq sistemasida 2 ta raqam: o va 1 mavjud. Shu sistemada qo’shish, ayirish va ko’paytirish amallari quyidagicha bajariladi:
Endi ikkilik sanoq sistemasidagi sonlar ustida turli arifmetik amallar bajarishga doir misollar ko’ramiz. 1-misol. 1101012 va 1100112 sonlarning yigindisini toping. Yechish. Bu sonlarni bir ustunga yozib, umumiy qoida bo’yicha qo’shamiz: + 1101012 1100112 __________ 1101000 2 Javob: 11010002 2-misol. 1010102 va 100112 sonlarning ayirmasini toping. Yechish. Bu sonlarni bir ustunga yozib, umumiy qoida bo’yicha ayiramiz: __ 1010102 1 00112 ______________ 10111 2 Javob: 101112 3-misol. 1100112 va 1012 sonlarning ko’paytmasini toping. Yechish. Bu sonlarni bir ustunga yozib, umumiy qoida bo’yicha ko’paytiramiz: X 1100112 1012 _______________ + 110011 110011 __________ 111111112 Javob: 111111112 4-misol. 10000100102 va 1101012 sonlarning bo’linmasini toping. Yechish. Bu sonlarni bir ustunga yozib, umumiy qoida bo’yicha bo’lamiz:
Javob: 10102 Endi sakkizlik sanoq sistemasidagi sonlar ustida turli arifmetik amallar bajarishga doir misollar ko’ramiz: 1-misol. 478 va 1358 sonlarning yigindisini toping. Yechish. Bu sonlarni bir ustunga yozib, umumiy qoida bo’yicha qo’shamiz: + 478 1358 __________ 2048 Javob: 2048 2-misol. 13458 va 3658 sonlarning ayirmasini toping. Yechish. Bu sonlarni bir ustunga yozib, umumiy qoida bo’yicha ayiramiz: __ 13458 3658 __________ 7608 Javob: 7608 3-misol. 548 va 1368 sonlarning ko’paytmasini toping. Yechish. Bu sonlarni bir ustunga yozib, umumiy qoida bo’yicha ko’paytiramiz: X 1368 548 __________ + 570 726 ___________ 100508 Javob: 100508 4-misol. 4248 va 218 sonlarning bo’linmasini toping. Yechish. Bu 10111sonlarni bir ustunga yozib, umumiy qoida bo’yicha bo’lamiz:
Javob: 248 Endi o’n oltilik sanoq sistemasidagi sonlar ustida turli arifmetik amallar bajarishga doir misollar ko’ramiz:
3-misol. 1F16 va 6416 sonlarning ko’paytmasini toping. Yechish. Bu sonlarni bir ustunga yozib, umumiy qoida bo’yicha ko’paytiramiz: X 1F16 6416 ______________ + 7C BA ___________ C1C16 Javob: C1C16 4-misol. 27116 va 7D16 sonlaining bo’linmasini toping. Yechish. Bu 10111sonlarni bir ustunga yozib, umumiy qoida bo’yicha bo’lamiz:
Javob: 516 Turli xil sanoq sistemalarida bo’lgan sonlar ustida arifmetik amallar bajarish. 1.Turli xil sanoq sistemalarida bo’lgan sonlar ustida qo’shish amalini bajarish. a) 175 +68 ifodani 2 lik sanoq sistemasidagi yechimni toping. Yechish : Buning uchun biz sanoq sistemalari uchun keltirilgan jadvaldan foydalanamiz. Berilgan sonlarni ikkilik sanoq sistemasiga o’tkazib, ikkilik sanoq sistemasidagi qo’shish amalini tadbiq etamiz. 175 =100012 68=1102 175 +68 =100012 + 1102 =101112 javob: 101112 b) Berilgan ifodani 12 lik sanoq sistemasidagi qiymatini toping. 15 12+2A16=? Yechish : Bu sonlarni 10 lik sanoq sistemasiga o’tkazamiz. Quyidagi formulaga qo’yamiz. N=акqk+ak-1 qk-1+……+ a1q1+a0q0+……… N1=1512 N2=2A16 1*121+5*120=12+5=1710 2*16+A=32+10=4210 1710+4210=5910 Bu chiqqan soni 12 lik sanoq sistemasiga o’tkazish uchun bu soni bo’lish qoidasi orqali topamiz. 59:12=4 q(11) javob : 4B12 2.Turli xil sanoq sistemalarida bo’lgan sonlar ustida ayirish amalini bajarish. a) 378 – E16 ifodani 8 lik sanoq sistemasidagi yechimni toping. Yechish : Buning uchun biz jadvaldan foydalanib, E16 sonini 8 lik sanoq sistemasiga o’tkazib, bir xil sanoq sistemasidagi ayirish amalini bajaramiz. E16 =168 teng bo’ladi. 378- E16 = 378 - 168 =218 javob: 218 b) Berilgan ifodani 7 lik sanoq sistemasidagi qiymatini toping. 4B16-657=? Yechish : 4B16 sonni 10 lik sanoq sistemasiga o’tkazamiz. Quyidagi formulaga qo’yamiz. N=акqk+ak-1 qk-1+……+ a1q1+a0q0+……… 4*161+В*160=64+11=7510 75:7= 10 (5) 4В16 =1057 1057 - 657 =407 javob : 407 3.Turli xil sanoq sistemalarida bo’lgan sonlar ustida ko’paytirish amalini bajarish. а) 158 * 215 ifodani 5 lik sanoq sistemasida ko’paytmasini toping. Yechish : Buning uchun biz jadvaldan foydalanib, 158 sonini 5 lik sanoq sistemasiga o’tkazib, bir xil sanoq sistemasidagi ko’paytirish amalini bajaramiz. 158 =305 teng bo’ladi. Endi bu sonlarni ko’paytirmiz 305 * 215 = 11 3 05 *305 215 _____________ + 3 0 11 0 _______________ 11 3 0 javob: 11 3 05 b) Berilgan ifodani 10 lik sanoq sistemasidagi qiymatini toping. АF16*238=? Yechish : Bu sonlarni 10 lik sanoq sistemasiga o’tkazamiz. Quyidagi formulaga qo’yamiz. N=акqk+ak-1 qk-1+……+ a1q1+a0q0+……… А*161+F*160=10*16+15*1=160+15=17510 2*8+3=1910 AF16 =17510 17510 *1910 = *17510 1910 _________________ + 1575 175 ____________________ 332510 javob 332510 4.Turli xil sanoq sistemalarida bo’lgan sonlar ustida ,bo’lish amalini bajarish. Sakkizlik sanoq sistemasidagi 11730 sonini o’n oltilik sanoq sistemasidagi 14 soniga bo’ling.Natijani 8 lik sanoq sistemasida ifodalang. Yechish : Buning uchun biz jadvaldan foydalanib, ikkinchi sonini 8 lik sanoq sistemasiga o’tkazib, bir xil sanoq sistemasidagi bo’lish amalini bajaramiz. 1416 =248 teng bo’ladi. Endi bu sonlarni bo’lamiz.. 117308 : 148 = 3768
Javob: 3768 Sanoq sistemalarida turli xil arifmetik amalarni bajarish uchun biz o’nlik sanoq sistemasidagi arifmetik amallarni yaxshi bilishimiz zarur. Kompyuterda 2,8,16 lik sanoq sistemalar qo’laniladi. Axborotlarni 2lik sanoq sistemasida kodlash uchun bu sanoq sistemalaridan foydalaniladi.Aynan 2,8,16 lik sanoq sistemalarini tanlash 8,16 sonlari 2 sonning darajasi bo’lganligi sababli, shuni xulosa qilib aytganda arifmetik amallarni turli xil bo’lgan sanoq sistemalarida qo’lash uchun matematika fanini chuqur o’zlashtirishimiz kerak bo’ladi. Turli xil sanoq sistemalarida arifmetik amallarni bajarish uchun ularni 10 lik sanoq sistemasiga o’tkazib olib bajariladi va keyin 10 lik sanoq sistemasiga chiqan soni o’sha sanoq sistemasidagi qonuniyat asosida o’tkaziladi. Ko‘plab algoritmik tillar paydo bo‘ldi: Fortran, Paskal, Beysik…. XII asrda Yevropada al – Xorezmi. matematik traktatining lotincha tarjimasi chiqdi. O’sha paytlar Algoritm deganda o‘nlik sanoq sistemasida arifmetik amallarning bajarilash qoidalari nazarda tutilgan. Hozirgi davrda algoritm barcha soxalarda qo’llanib kelinmoqda. Ingliz matematigi Alan Tyuring 1935 – 1936 yillarda «mantiqiy hisoblash mashinasi» nazariyasini yaratdi. Ishlab chiqilgan «Tyuring Mashina»si bo‘lajak matematiklar va kompyuterchiklar uchun majburiy o‘qitiladigan bo‘ldi. London mehmonxonalarining birida: «Bu yerda kodlarning buzuvchisi va informatikaning pioneri Alan Tyuring (1912 – 1954), tug‘ilgan» deb yozib qo‘yilgan. Rus matematigi Andrey Markov 1947 yil «normal algoritm» tushunchasini kiritdi va tizimlashgan va qat’iy algoritmlar umumiy nazariyasini yaratdi. Belgini qayta ishlashga mo‘ljallangan zamonaviy tillar (Prolog) Markovning «normal algoritm» lariga asoslanadi. O’nli sanoq sistemasida Butun sonlar va o‘nli kasr bilan arifmetik amallarning bajarilish qoidasi birinchi bo‘lib, buyuk olim Muxammad ibn Muso al-Xorazmi (arabchadan tarjimasi «Muxammad Muso o‘g‘li Xorazmdan», qisqa qilib Al-Xorazmiy deyiladi) tomonidan ishlab chiqilgan. Al-Xorazmiy IX asrda Xiva shahrida yashab ijod qilgan. Arab tilida yozilgan asarlari yo‘qolib ketgan, ammo XII asrda lotin tiliga tarjima qilingan nusxalari saqlanib qolingan. Shu orqali G’arbiy Yevropa O’nli sanoq sistemasida Butun sonlar va o‘nli kasr bilan arifmetik amallarning bajarilish qoidasi bilan tanishgan. Algoritm ta’rifi. Elektron hisoblash mashinalarining vujudga kelishiga qadar algoritmga har xil ta’rif berib kelindi. Lekin ularning barchasi ma’no jihatdan bir-biriga juda yaqin bo‘lib, bu ta’rif hozirgi kunda quyidagicha talqin qilinadi. Ta’rif. Algoritm deb, biror masalani yechish uchun ma’lum qoidaga asosan bajariladigan amallarning chekli ketma-ketligiga aytiladi yoki aniq natija beruvchi sodda hisoblashlar ketma-ketligi. Yoki boshqacha aytsak algoritm-bu to’g’ri aniqlangan hisoblash jarayoni bo’lib, natijada kirishda berilgan m-tlarni chiquvchi m-tlarga aylantirib beradi, ya’ni algoritm 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 algoritm 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: Tushunarlilik –algoritmda ijrochiga berilayotgan ko‘rsatmalar aniq mazmunda bo‘lishi; Diskretlilik – algoritmlarni chekli qadamlardan tashkil qilib bo‘laklash imkoniyati ; Cheklilik – bajarilayotgan algoritm chekli qadamlarda natijaga olib kelishi; Natijaviylik - natijaning bo‘lishi; Ommaviylik – har bir algoritm mazmuniga ko‘ra bir turdagi masalalarning barchasi uchun ham o‘rinli bo‘lishi . Formallik –komandalarni mexanik bajarish imkoniyati. Bu xossa robotlar, kompyuterlar va boshqa qurilmalarda komandalarning ketma-ket bajarilishini ta’minlaydi. Algoritm turlari : Chiziqli algoritm - deb hech qanday shartsiz faqat ketma-ket bajariladigan jarayonlarga aytiladi. Tarmoqlanuvchi algoritm - deb ma’lum shartlarga muvofiq bajariladigan ko‘rsatmalardan tuzilgan algoritmga aytiladi. Takrorlanuvchi algoritm - deb biron bir shart tekshirilishi yoki biron parametrning har xil qiymatlari asosida takroriy xisblashlarni bajaradigan algoritmga aytiladi. Chiziqli algoritm - deb hech qanday shartsiz faqat ketma-ket bajariladigan jarayonlarga aytiladi. Chiziqli algoritm strukturasi: Tarmoqlanuvchi va siklik algoritmlar 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: Download 40.32 Kb. Do'stlaringiz bilan baham: 
|