Algoritm korrekt

Download 70.24 Kb.
Sana	22.01.2024
Hajmi	70.24 Kb.
	#143173

Bog'liq
Algoritm korrekt
Zoologiya (S.Dadayev, O.Mavlonov), 2 5244759494868600833, 2 5235889373790078203, attestatsiya Rep 2021 (2), Maktabgacha tarbiya yoshida bilish jarayonlarining rivojlanishi, 8-maruza, 2 5229185462416979013, Fagositoz-fayllar.org, 1. Psixikaning filogenetik taraqqiyoti, psixodiagnostika, O’zbekistonda ijtimoiy sohada amalga oshirilayotgan o’zgarishlar, 2 tema Qurılıs materiyallariń tiygargi ozgeshelikleri Qar, 8. Erkin Vohidov. O`zbegim, 1-mavzu Milliy iqtisodiyot va uni tavsiflovchi asosiy ko’rsatki-fayllar.org, Bet10

Bu sahifa navigatsiya:

• Algoritm samaradorligi. Algoritmni tahlil qilish uchun algoritmning vaqt murakkabligini tahlil qilish odatda kirish malumotlarining olchamiga qarab ishlash vaqtini baholash uchun
• 1. C doimiy 2. log(log(N)) 3. log(N) 4. N^C, 0 1 8. C^N, C>1 9. N!
• Algoritm samaradorligining asosiy sinflari
• Kvadrat tenglamaning ildizlarini topish vazifasi
• Yechish algoritmi

Algoritm korrekt Hisoblash algoritmlarining to'g'riligi(korrektligi) va shartliligi Hisoblash algoritmi - bu masalaning ixtiyoriy ruxsat etilgan boshlang'ich ma'lumotlari bo'yicha aniq tasvirlangan operatsiyalar ketma-ketligi bo'lib, uning natijasi masalaning raqamli yechimidir. Agar hisoblash algoritmi to'g'ri(korrekt) algoritm deb ataladi 1. hisoblash qurilmasi uchun elementar bo'lgan cheklangan miqdordagi operatsiyalarni bajargandan so'ng, o'zboshimchalik bilan ruxsat etilgan dastlabki ma'lumotlar muammoning echimiga aylantiriladi; 2.dastlabki ma'lumotlarning kichik buzilishlariga nisbatan hisoblash natijasi barqaror, ya'ni. hisoblash xatosi bo'lmasa, natija doimiy ravishda dastlabki ma'lumotlarga bog'liq; 3. natija hisoblash barqaror, ya'ni. agar natijaning hisoblash xatosi (yaxlitlash xatosi) nolga moyil bo'lsa, chunki mashina epsilon nolga intiladi. Agar ushbu uchta shartdan kamida bittasi buzilgan bo'lsa, algoritm noto'g'ri deb ataladi. Algoritm samaradorligi. Algoritmni tahlil qilish uchun algoritmning vaqt murakkabligini tahlil qilish odatda kirish ma'lumotlarining o'lchamiga qarab ishlash vaqtini baholash uchun ishlatiladi . Natija odatda "O" katta shaklida ifodalanadi. Bu algoritmlarni solishtirish uchun, ayniqsa katta hajmdagi ma'lumotlarni qayta ishlashda foydalidir Harakatlar ketma-ket bajarilgan taqdirda, algoritmning murakkabligi O(K + J) ga teng bo'ladi va shuning uchun O(max (K, J)) . Misol uchun, agar A n^2 va B n bo'lsa, u holda algoritmning murakkabligi O(n^2 + n) bo'ladi. Ushbu ro'yxatdagi funktsiya qanchalik yuqori bo'lsa, bu taxmin bilan algoritm tezroq ishlaydi. 1. C doimiy 2. log(log(N)) 3. log(N) 4. N^C, 0 1 8. C^N, C>1 9. N! Agar biz murakkablik tenglamasi ushbu funktsiyalarning bir nechtasini o'z ichiga olgan algoritmning murakkabligini baholamoqchi bo'lsak, u holda tenglamani jadvalda quyidagi funktsiyaga qisqartirish mumkin. Masalan, O(log(N)+N!)=O(N!). Algoritm samaradorligining asosiy sinflari 1 - doimiy. Kirish ma'lumotlarining hajmidan qat'iy nazar, belgilangan vaqt ichida ishlaydigan algoritmlarni tavsiflaydi. log n logarifmikdir. Muammoning o'lchami har bir iteratsiyada doimiy miqdorga kamaytiriladigan algoritmlarga xosdir. Misol: ikkilik qidiruv algoritmi. p - chiziqli. n ta element roʻyxatini skanerlovchi algoritmlarni tavsiflaydi. Misol: ketma-ket qidiruv algoritmi. n log n - /7-log-n. Shaxsiy maqsadlar usuli bilan ishlab chiqilgan algoritmlar uchun odatiy. Misollar: birlashtirish, tez tartiblash. n ~ kvadratikdir. Ikkita o'rnatilgan tsiklni o'z ichiga olgan algoritmlarni tavsiflaydi. Misollar: oddiy tartiblash algoritmlari, n * n matritsalarni qayta ishlash algoritmlari . n 3 - kub. Uchta ichki halqani o'z ichiga olgan algoritmlar uchun odatiy. Misol: murakkab chiziqli algebra algoritmlari. 2 n - eksponensial. n ta elementdan iborat ba'zi bir to'plamning barcha kichik to'plamlarini qayta ishlovchi algoritmlarni tavsiflaydi . "Eksponensial" atamasi ko'pincha eksponensialdan tezroq o'sishning juda yuqori tartiblarini bildirish uchun erkin ishlatiladi. Va! - faktorial. Ba'zi n elementlar to'plamining barcha almashtirishlarini qayta ishlaydigan algoritmlar uchun odatiy. (1)T: algoritm samarali deb ataladi agar real kirish ma'lumotlari uchun u tezkor amalga oshirilsa. (2)T: algoritm samarali deb ataladi agar u sifatli bajarilishni “to’liqqidirish”(полнiy перебор)ga nisbatan tezroq ta'minlasa."To'liq qidirish" usuliga qaraganda ancha yaxshi ishlashni ta'minlaydigan algoritmlar, deyarli har doim qimmatli evristik g'oyani o'z ichiga oladi, buning natijasida ushbu yaxshilanishga erishiladi; Bundan tashqari, ular ko'ribchiqilayotgan masalaning ichki tuzilishi va hisoblash qobiliyati haqida foydali ma'lumotlarni taqdim etadilar Kvadrat tenglamaning ildizlarini topish vazifasi, boshqa ko'plab vazifalar singari, oson vazifadir. Uni qog’oz va qalam yordamida juda oson yechish mumkin, ammo algoritmni to’gri tanlab dasturini tuzish va undan foydalanish orqali yechimni avtomatlashtirish mumkin. Ushbu laboratoriyada biz shunday dastur algoritmini ko’rib chiqamiz.Bilamizki, ko’rinishidagi tenglama kvadrat tenglama deyiladi. Ushbu tenglamani yechishning bir necha usullari mavjud. Ammo biz, Diskriminantlar usulidan foydalanamiz. Chunki bu usul dasturlash uchun eng optimal usul hisoblanadi.Diskriminant D harfi bilan belgilanadi. D= b2-4ac ekanligini esa, maktab kursidan bilamiz.Diskriminant uchun bir nechta shartlar mavjud: Agar D> 0 bo'lsa, unda tenglama 2 xil haqiqiy ildizga ega. Agar D = 0 bo'lsa, unda yagona ildizga ega yoki, ikkala haqiqiy ildiz teng bo'ladi. Agar D <0 bo'lsa, unda yechimga ega emas yoki, ikkala ildiz ham kompleks sonlardir. Yechish algoritmi juda oddiy. Diskriminant hisoblanadi, agar u 0 dan katta yoki unga teng bo'lsa, u holda ildizlar quyidagi formula yordamida hisoblanadi: yoki Kvadrat tenglama ildizlarini topish algoritmining blok sxemasini quyida ko’rishimiz mumkin. Download 70.24 Kb.

Download 70.24 Kb.