|
Algoritm korrekt
|
| Sana | 22.01.2024 | | Hajmi | 70,24 Kb. | | #143173 |
Bog'liq Algoritm korrekt
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.
|
| |
