Nazariy topshiriqlar To'la tanlov algoritmi



Download 23,89 Kb.
bet1/3
Sana04.10.2020
Hajmi23,89 Kb.
#49546
  1   2   3
Bog'liq
1-topshiriq


Nazariy topshiriqlar

1.To'la tanlov algoritmi

To'la tanlov (yoki brute force) algoritmini analiz qilishdan oldin algoritm dunyosida asosan 2 ta asosiy tushuncha juda muhim ahamiyatga egadir.

Misol tariqasida tushuntirshga harakat qilaman. Sizga savol qo’limda ma’lumot bor, ushbu ma’lumotni Toshkentdan Londonga yuborishim kerak bu holda qaysi yo’llar orqali yuborsam bo’ladi (masalan:Telegram, facebook, google drive, yandex disk). Siz aytishingiz mumkin ma’lumotni telegramdan yuborishimiz maqul deb chunki tez va qulay. Bu javob doim ham to’g’ri bo’lmaydi sababi siz javob berishdan oldin mendan so’rashingiz kerak edi. Ma’lumotning hajmi qancha deb. Mendagi ma’lumot hajmi 10Gb edi. Endi siz aytgan usul o’zini oqlamasligi mumkin sababi telegram orqali yuborilgan axborot (100Gb lik) tarmoq tezligi 25Mb/s bo’lganda ham yetib borish vaqti 8 soat 53 min 20s da yetib boradi. Eng optimal yo’l samolyotda ma’lumotni yuborsam maqsadga muvofiq bo’ladi.

Istalgan muammoni hal qilishda masala yechimining vaqt va xotiradan oladiga joy jihatlariga alohida e’tibor qaratiladi. Yuqoridagi masala agar ma’lumot telegram orqali yuborilsa biz vaqtdan yutqazar edi.

Algoritmlashda Time Complexity va Space complexity degan tushunchalar mavjud. Endi to’la tanlov algoritmi ni analiz qiklishga kirishsak

To'la tanlov (yoki brute force) algoritmi - matematik muammolarni hal qilish usuli. Har qanday variantni tugatib, echim topish usullari sinfiga tegishli. To'liq qidirishning murakkabligi muammoni hal qilishning barcha mumkin bo'lgan echimlari soniga bog'liq. Agar qaror qabul qilish maydoni juda katta bo'lsa, unda to'liq qidiruv bir necha yil yoki hatto asrlar davomida natijalarga olib kelmasligi mumkin.

To'la tanlov (yoki brute force) algoritmi yuqoridagi vaqt va xotiradan oladigan joy ni deyarli hisobga olmaydi. Bu esa masala yechimini topadi lekin eng yomon holatlarda yechadi degani

NP (non-deterministic polynomial) sinfidagi har qanday muammoni to'liq izlash orqali hal qilish mumkin. Bu holda, har qanday aniq echimdan ob'ektiv funktsiyani hisoblash barcha mumkin bo'lgan echimlarning soniga qarab, ko'paytirilgan vaqt ichida amalga oshirilishi mumkin bo'lsa ham, to'liq qidiruv eksponensial vaqtni talab qilishi mumkin.

Misol tariqasida quyidagi savollarni nazariy jihatdan yechishga harakat qilamiz - bu sayohat qiluvchi sotuvchi muammosi (Traveling Salesman Problem TSP). Aytaylik, sotuvchi butun mamlakat bo'ylab 10 ta shaharga tashrif buyurishi kerak. Qat'iy belgilangan masofani minimallashtirish uchun qaysi shaharlarga borish kerakligini qanday aniqlash mumkin? To'la tanlov (yoki brute force) yechimi oddiygina har bir marshrut uchun umumiy masofani hisoblash va keyin eng qisqa yo'lni tanlashdir. Bu ayniqsa samarali emas, chunki aqlli algoritmlar yordamida ko'plab mumkin bo'lgan yo'nalishlarni yo'q qilish mumkin.


Download 23,89 Kb.

Do'stlaringiz bilan baham:
  1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish