Nimatullaev Davron Yakuniy nazorat ishi

Nimatullaev Davron

Yakuniy nazorat ishi

CAL016

Variant № 39

1. 
   Grafik kenglik boʼyicha aylanish algoritmining afzalligi nimada?
   
2. 
   Matritsaning taʼrifii aytig va misol keltiring.
   
3. 
   Takrorlanuvchi jarayonlar algoritmlarining tahlili.
   

1. Mashina grafikasi algoritmlarini ikki darajaga bo'lish mumkin: pastki va yuqori. Pastki darajadagi algoritmlar guruhi grafik ibtidoiylarni (chiziqlar, doiralar, to'ldirishlar va boshqalar) amalga oshirish uchun mo'ljallangan. Ushbu algoritmlar yoki shunga o'xshashlar yuqori darajadagi grafik kutubxonalarida (BGI Turbo-Paskalda) ko'paytiriladi yoki ish stantsiyalarida grafik protsessorlarida (Silicon Grafics va boshqalar) apparat vositalarida qo'llaniladi.

Quyi darajadagi algoritmlar orasida quyidagi guruhlarni ajratish mumkin.

Amaldagi matematik usullarning ma'nosida eng sodda va amalga oshirishning soddaligi bilan ajralib turadi. Qoida tariqasida, bunday algoritmlar bajarilgan hisoblar hajmi yoki kerakli xotira resurslari nuqtai nazaridan eng yaxshi emas.

Shuning uchun biz murakkabroq matematik old shartlarni (lekin ko'pincha evristik) ishlatadigan va samaraliroq bo'lgan algoritmlarning ikkinchi guruhini ajratib olishimiz mumkin.

Uchinchi guruhga apparat qiyinchiliklarisiz bajarilishi mumkin bo'lgan algoritmlar kiritilishi kerak (parallelizatsiya, rekursiv, eng oddiy buyruqlarda bajarilishi mumkin). Dastlabki ikki guruhda keltirilgan algoritmlar ham ushbu guruhga kirishi mumkin.

Va nihoyat, to'rtinchi guruhga maxsus maqsadga ega algoritmlar kiradi (masalan, zinapoyaning ta'sirini yo'q qilish uchun).

Yuqori darajadagi algoritmlar, birinchi navbatda, ko'rinmas chiziqlar va sirtlarni olib tashlash algoritmlari. Ko'rinmas chiziqlar va sirtlarni olib tashlash vazifasi kompyuter grafikasida asosiy o'rinni egallamoqda. Uch o'lchovli tasvirni yaratish sifati va tezligi ushbu muammoni hal qiladigan algoritmlarning samaradorligiga bog'liq.

Ko'rinmas chiziqlar va sirtlarni olib tashlash vazifasi kulrang (haqiqiy) tasvirlarni qurish (bo'yash) bilan bog'liq, ya'ni. tananing sirt xususiyatlarini (shaffoflik, sinish, yorug'likning aks etishi) hisobga olgan holda yorug'lik manbalarining soni va tabiati bilan bog'liq hodisalarni hisobga olish.

Shuni ham unutmaslik kerakki, yuqori darajadagi algoritmlarda ob'ektlarning chiqishi pastki darajadagi algoritmlarni amalga oshiruvchi ibtidoiy vositalar tomonidan ta'minlanadi, shuning uchun past darajadagi samarali algoritmlarni tanlash va ishlab chiqish muammolarini e'tibordan chetda qoldirib bo'lmaydi.

Kompyuter grafikasini qo'llashning turli sohalari uchun algoritmlarning xilma-xilligi birinchi o'ringa chiqishi mumkin. Ilmiy grafika uchun algoritmning ko'p qirrali xususiyati katta ahamiyatga ega, tezlik fonga tushib ketishi mumkin. Harakatlanuvchi ob'ektlarni ko'paytiradigan modellashtirish tizimlari uchun tezlik asosiy mezon hisoblanadi, chunki deyarli real vaqtda tasvirni yaratish kerak.

Raster grafikasining o'ziga xos xususiyatlari, inson o'z faoliyatida duch keladigan oddiy tasvirlar (chizmalar, grafikalar, xaritalar, badiiy rasmlar va boshqalar) cheksiz nuqtalar to'plamidan iborat tekislikda bajarilishi bilan bog'liq. Rasterli displeyning ekrani muayyan fizik o'lchamlarga ega bo'lgan diskret elementlarning matritsasi bilan ko'rsatilgan. Bundan tashqari, ularning soni sezilarli darajada cheklangan. Shunday qilib, siz bir nuqtadan boshqasiga aniq chiziq chizolmaysiz, faqat bu chiziqni diskret matritsada (tekislikda) namoyish etish bilan taxminiy ulanishingiz mumkin. Bunday samolyot, shuningdek, butun son, panjara yoki raster tekisligi deb ataladi. Ushbu panjara 1 ga teng kvadrat shaklida ko'rinadi.

Chiziqlar, doiralar, ellipslarning qurilishi

Chiziq chizishning eng oson usuli bu y = ax + b tenglamasi. Bunday holda, natijalar eng yaqin butun songa yaxlitlanishi kerak, shunda chiziq notekis bo'ladi.

Aksincha, berilgan koordinatalar (x1, y1), (x2, y2) bilan 2 nuqtani bog'lash kerak, keyin:

a = (y2-y1) / (x2-x1); b = y1 - a * x1;

Doira tenglamasi quyidagicha:

x = xc + r * cos (a); y = yc + r * sin (a),

bu erda (xc, yc) aylana markazining koordinatalari, r - radius, a - joriy nuqta (x, y) uchun burchak.

Bu tenglamaga muvofiq to'g'ridan-to'g'ri aylanani burchakda (a = 0..360 DA qadam bilan) o'rnatish orqali mumkin. Ammo, agar qadam juda kichik bo'lsa, koordinatalarni yaxlitlash natijasida aylana notekis bo'ladi va ba'zi fikrlar bir necha bor ta'kidlanadi. Odatda, burchakdagi qadam 1 / r radianga teng tanlanadi (ko'pincha bo'shliqlar yoki koordinatalarda o'zgarish bo'lmasligi uchun burchakni o'zgartirish bosqichi o'zgaruvchan bo'lishi kerak).

Siz taxminiy segmentlar uchun oddiy algoritmni amalga oshirishingiz mumkin.

Masalan, 6 segmentning koordinatalari 60 graduslik bosqichlarda olinadi, keyin ular to'g'ri chiziqlar bilan bog'lanadi.

Tez qurilishi uchun aylananing simmetriyasidan foydalaniladi (nuqta koordinatalari doiraning faqat 1/8 qismini hisoblaydi - 0 dan 45 darajagacha bo'lgan segment uchun). Bundan tashqari, siz aylananing keyingi nuqtasining oldingi nuqtasidan (takrorlanish formulasi) koordinatalarini ifoda etsangiz, sinus / kosin operatsiyalaridan uzoqlashishingiz mumkin:

x2 = xc + (x1-xc) * CA + (y1-yc) * SA;

y2 = yc + (y1-yc) * CA - (x1-xc) * SA, qaerda

SA = sin (DA), CA = cos (DA).

Qaytarilish formulasining boshlang'ich nuqtasi: x1 = xc, y1 = yc + r.

Doira qurishda, piksellarning vertikal va gorizontal o'lchamlari bir-biriga to'g'ri kelmasligini yodda tutish kerak (VGA 640x480 tashqari) va doiralar ellipsga bo'linadi. Bunga yo'l qo'ymaslik uchun siz hizalanish koeffitsientlarini kiritishingiz kerak (GetAspectRatio tomonidan belgilanishi mumkin). Ellipsning o'zi uran bilan tavsiflanadi:

x = xc + rx * cos (a); y = yc + ry * sin (a),

bu erda rx, ry yarim radius.

Ular uchun qurilishning umumiy tamoyillari doiralar bilan bir xil.

Bresenham algoritmi

Bresenham algoritmi 1965 yilda raqamli plotterlar uchun ishlab chiqilgan va keyinchalik rastrli displeylar uchun foydalanila boshlangan.

Algoritmning g'oyasi shundaki, bitta koordinatani boshqasi o'zgartiradi, ikkinchisi esa koordinatalar tarmog'ining eng yaqin tugunidan tegishli nuqtaning joylashishiga qarab o'zgarmaydi yoki birlashadi. Segment nuqtasidan tegishli ortogonal koordinatadagi eng yaqin tugungacha bo'lgan masofa xato deb nomlanadi. Algoritm shunday tuzilganki, ikkinchi koordinatani hisoblash uchun faqat ushbu xatoning belgisini aniqlash kerak. Delta xato qiymati quyidagi ifodaga muvofiq aniqlanishi mumkin:

Delta = Yuz - Yot,

bu erda Yuz - X = 1 nuqtadagi eng yaqin tugunning Y koordinatasi, Yf - X = 1 nuqtadagi Y koordinatasi.

Agar X = 1 uchun Y nuqta kesimining koordinatasi 1/2 ga teng bo'lsa, u holda koordinata panjarasining tugunlari (1,0) va (1,1) segmentdan bir xil masofada joylashgan va (1,1) tugun “eng yaqin” deb tanlangan. Shunday qilib, agar Yf> = 1/2 bo'lsa, Delta> = 0, aks holda Yf <1/2, Delta <0 uchun hisob-kitoblarni tashkil qilish uchun Delta qiymatini emas, balki d = Delta qiymati sifatida belgilangan boshqasini ishlatish qulayroq bo'ladi. - 1/2. X koordinatani 1 ga o'zgartirganda, d ning qiymati burchak koeffitsienti qiymatiga o'zgaradi: d = d + dY / dX. Algoritmning har bir bosqichida X koordinatasi, d qiymati hisoblab chiqiladi va d belgisi tahlil qilinadi. Bundan tashqari, agar d> = 0 ekanligi aniqlansa, Y 1 ga ko'payadi va d ning qiymati undan 1-ni olib tashlash orqali o'rnatiladi.

2. Matritsa tushunchasi (matematikada) XIX asr o'rtalarida U.Hamilton va A.Keyli asarlarida kiritilgan. Nazariyaning asoslarini K.Vayerstrass va F.Frobenius yaratgan (XIX asrning 2-yarmi – XX asr boshlari). I.A. Lappo-Danilevskiy ko'plab matritsa argumentlarining analitik funktsiyalari nazariyasini ishlab chiqdi va bu nazariyani analitik koeffitsientli differentsial tenglamalar tizimlarini o'rganishda qo'lladi. Matritsaga oid tushunchalar notalar zamonaviy matematikada va uning qo'llanilishida keng tarqalgan.

mxn o'lchovli matritsa - bu m qatorlar va n ustunlarda joylashgan sonlar jadvalidir.

Matritsa А, В, С, … lotin alifbosi harflari bilan ifodalanadi. Undagi sonlar elementlar deyiladi. Har bir a_ij element ikkita indeksga ega, ya’ni i - satr nomeri, j - ustun nomeri, ular kesishmasida a_ij element joylashadi. Matritsalar quyidagicha beriladi:

A={a_ij}_mxn yoki A={a_ij}, i=1,n; j=1,m.

Masalan:

3.Hozirgi paytda o’nlik sanoq tizimida arifmetik amallarni bajarish usullari hisoblash algoritmlariga soddagina misol bo’la oladi xolos. Hozirgi zamon nuqtai nazaridan algoritm tushunchasi nimani ifodalaydi? Ma’lumki, inson kundalik turmushida turli-tuman ishlarni bajaradi. Har bir ishni bajarishda esa bir qancha elementar (mayda) ishlarni ketma-ket amalga oshirishga to’g’ri keladi. Mana shu ketma-ketlikning o’zi bajariladigan ishning algoritmidir. Ammo bu ketma-ketlikka e’tibor bersak, biz ijro etayotgan elementar ishlar ma’lum qoida bo’yicha bajarilishi kerak bo’lgan ketma-ketlikdan iborat ekanligini ko’ramiz. Agar bu ketma-ketlikdagi qoidani buzsak, maqsadga erishmasligimiz mumkin.

Masalan, shaxmat o’yinini boshlashda shohni yura olmaymiz, chunki bu o’yin algoritmida yurishni boshqa bir shaxmat donalaridan boshlash kerak yoki palov pishirish algoritmida birinchi navbatda qozonga suv solib ko’ringchi, osh qanday bo’lar ekan. Berilgan matematik ifodani soddalashtirishda amallarning bajarilish ketma-ketligiga e’tibor bermaslik noto’g’ri natijaga olib kelishi barchaga ma’lum.

Demak ishni, ya’ni qo’yilgan masalani bajarishga mayda elementar ishlarni muayyan ketma-ketlikda ijro etish orqali erishiladi. Bundan ko’rinib turibdiki, har bir ish qandaydir algoritmning bajarilishidan iboratdir. Algoritmni bajaruvchi algoritm ijrochisidir. Algoritmning ijrochisi masalaning qanday qo’yilishiga e’tibor bermagan holda natijaga erishishi mumkin. Buning uchun u faqat avvaldan ma’lum qoida va ko’rsatmalarni qat’iy bajarishi shart. Bu esa algoritmning juda muhim xususiyatlaridan biridir.

Umuman, ajgoritmlarni ikki guruhga ajratish mumkin. Birinchi guruh algoritmning ijrochisi faqat inson bo’lishi mumkin ( masalan palovni faqat inson pishira oladi), ikkinchi guruh algoritmlarning ijrochisi ham inson, ham EHM bo’lishi mumkin (faqat aqliy mehnat bilan bog’liq bo’lgan masalalar). Ikkinchi guruh algorimtlarning ijrochisini EHM zimmasiga yuklash mumkin. Buning uchun algoritmni EHM tushunadigan biror tilda yozib, uni mashina xotirasiga kiritish kifoya.

Shunday qilib, biz algoritm deganda, berilgan masalani yechish uchun ma’lum tartib bilan bajarilishi kerak bo’lgan chekli sondagi buyruqlar ketma-ketligini tushunamiz.

Biror sohaga tegishli masalani yechish algoritmini tuzish algoritm tuzuvchidan shu sohani mukammal bilgan holda, qo’yilgan masalani chuqur tahlil qilishni talab qiladi. Bunda masalani yechish uchun kerak bo’lgan ishlarning rejasini tuza bilish muhim ahamiyatga ega. Shuningdek, masalani yechishda ishtirok etadigan ob’ektlarning qaysilari boshlang’ich ma’lumot va qaysilari natijaligini aniqlash, ular o’rtasidagi o’zaro bog’lanishni aniq va to’la ko’rsata bilish, yoki dastur (programma) tuzuvchilar tili bilan aytganda, masalaning ma’lumotlar modelini berish lozim.

Berilgan masala algoritmini yozishning turli usullari mavjud bo’lib, ular qatoriga so’z bilan, bloktarh (bloksxema) shaklida, formulalar, operatorlar yordamida, algoritmik yoki dasturlash tillarida yozish va hokazolarni kiritish mumkin.

Endi biror usulda tuzilgan algoritmning ayrim xossalari va algoritmga qo’yilgan ba’zi bir talablarni ko’rib chiqaylik.

1. Algoritm har doim to’liq bir qiymatlidir, ya’ni uni bir xil boshlang’ich qiymatlar bilan ko’p marta qo’llash har doim bir xil natija beradi.

2. Algoritm birgina masalani yechish qoidasi bo’lib qolmay, balki turli-tuman boshlang’ich shartlar asosida ma’lum turdagi masalalar to’plamini yechish yo’lidir.

3. Algoritmni qo’llash natijasida chekli qadamdan keyin natijaga erishamiz yoki masalaning yechimga ega emasligi haqidagi ma’lumotga ega bo’lamiz.

Yuqorida keltirilgan xossalarni har bir ijrochi o’zi tuzgan biror masalaning algoritmidan foydalanib tekshirib ko’rishi mumkin. Masalan:

ax2 + bx + с = 0

kvadrat tenglamani yechish algoritmi uchun yuqorida sanab o’tilgan algoritmning xossalarini quyidagicha tekshirib ko’rish mumkin.

Agar kvadrat tenglamani yechish algoritmi biror usulda yaratilgan bo’lsa, biz ijrochiga bu algoritm qaysi masalani yechish algoritmi ekanligini aytmasdan a, b, с larning aniq qiymatlari uchun bajarishni topshirsak, u natijaga erishadi va bu natija kvadrat tenglamaning yechimi bo’ladi. Demak, algoritmni ijro etish algoritm yaratuvchisiga bog’liq emas.

Xuddi shuningdek a, b, с larga har doim bir xil qiymatlar bersak, algoritm har doim bir xil natija beradi, ya’ni to’liqdir.

Yaratilgan bu algoritm faqatgina bitta kvadrat tenglamani yechish algoritmi bo’lib qolmay, balki a,b,c larning mumkin bo’lgan barcha qiymatlari uchun natija hosil qiladi, binobarin u shu turdagi barcha kvadrat tenglamalarning yechish algoritmi bo’ladi.

Algoritmning oxirgi xossasi o’z-o’zidan bajariladi, ya’ni kvadrat tenglamani yechish albatta chekli qadamda amalga oshiriladi.

Dastur tuzuvchi uchun EHMning ikkita asosiy parametri o’ta muhimdir: hisoblash mashinasi xotirasining hajmi va mashinaning tezkorligi. Shuningdek, algoritm tuzuvchidan ikki narsa talab qilinadi. Birinchidan, u tuzgan dastur mashina xotirasida eng kam joy talab etsin, ikkinchidan, eng kam amallar bajarib masalaning natijasiga erishsin. Umuman olganda, bu ikki talab bir-biriga qarama-qarshidir, ya’ni algoritmning ishlash tezligini oshirish algoritm uchun kerakli xotirani oshirishga olib kelishi mumkin. Bu xol, ayniqsa murakkab masalalarni yechish algoritmini tuzishda yaqqol seziladi. Shuning uchun ham bu ikki parametming eng maqbul holatini topishga harakat qilish kerak.