Namangan davlat universiteti informatika kafedrasi

Nazorat savollari:
1. Optimallashtirishning mohiyati nima?
2. Nisbiylikni tushuntiring?
3. Muammolar yechimi qanday usullar yordamida topiladi?


2-Mavzu: Sun’iy neyron modeli.
Ishdan maqsad: Kompyuterning aniq masalalarini yechish uchun resurslar hajmini o’lchash. Algoritm vazifalarini klassifikatsiyalash.
Masalaning qo`yilishi: Berilgan hisoblash murakkabligini yordamida berilgan masalalarni yechish.
Uslubiy ko’rsatmalar: Hisoblash murakkabligi- bu algoritmlarni hisoblashda bajariladigan kompyuter komandalari soni. Agar komanda ketma-ket bajarilsa- u holda vaqtinchalik murakkablik bo’ladi.
Xotira - algoritmda ishlatiladigan xotiraning birlik yoki o’zgaruvchilar soni.
Misol
Masalan : ax² + b x + c ni a=3, b=4, x=7 qiymatlar uchun hisoblang.
Vaqtinchalik murakkablik - 5
Hotira - 9
Masalani (a x + b) x + c holatga keltiramiz va – 4 vaqtinchalik murakkablikka ega bo’lamiz
Mashq_Misol'>Mashq
Misol:
•x16 = x x x x x x x x x x x x x x x x yoki
•x16 = (((x2 )2)2)2
X6 = 3 ta ko’paytiruvdan foydalanib
X33 = 6 ta ko’paytiruvdan foydalanib
Hisoblash murakkabligini o’lchashni baholash
Agar algoritmning vaqtinchalik murakkabligi aniqlansa, u holda kiruvchi ma’lumotlarni mavjud hisoblashlarni bajarmagan holatda algoritmning ish vaqtini batafsil baholash mumkin.
Misol
Qishloqda yashovchi aholining o’rtacha yoshini hisoblash
Time A ( n ) = n + 1
Funksiyalar murakkabligini solishtirish. Ikkita funksiyaning vaqtinchaligini tekshiramiz
Time A (n) = 3n + 1 и Time B (n) = n 2
Mashq
Masalada ikkita algoritm berilgan:
Time A (n) = 2 n2 Time B (n) = 40 n + 700
N qaysi algoritm uchun ko’proq foydali ekanligini solishtiring.
Algoritmlarni qo’llashFoydalanuvchi natijani qancha vaqt kutish kerakligini biladi. Biz foydalanuvchi uchun qanoatlantiruvchi vaqtda kompyuter qancha operatsiyalarni bajarishini baholashimiz mumkin - masalan 1016
Agar funksiya 3n + 1 < 1016, algoritm A doim qo’llanilsa 10n < 1016 funksiya uchun algoritm A faqat n < 16 uchun qo’llanilsa, Ruhsat etilgan chegaralar U masalaning murakkabligi - Bu murakkablik eng tezkor U algoritm uchun.
U yechim uchun A algoritm qurilgan bo’lsin. U holda vaqtinchalik murakkablik Time A(n) U vaqtinchalik murakkablik Time A(n) yuqorinU vaqtinchalik murakkablik chegarasi bo’lib hisoblanadi. f(n)- TimeB (n) ≤ f(n) bilan U uchun B algoritm mavjud bo’lmasa, u holda vaqtinchalik murakkablik quyi chegarasi hisoblanadi.