O’zbekiston Respublikasi Toshkent shahridagi Muhammad Al-Xorazmiy nomidagi Toshkent axborot Texnologiyalari Universiteti Axborot xavfsizligi fakulteti Mustaqil ish Mavzu: Komivoyajer masalasi Fan nomi:Algoritmlarni loyihalash Guruh:CAL016 Bajardi:Fayzullayev Ruslan Tekshirdi:Turg’unov Abror
Reja: 1. Evristik algoritmlar 2. GTS algoritmini tuzish 3.Dag’al kuch usuli bilan tartiblash 4. Prima algoritmlari 5. Kruskal algoritmlari
Algoritm tushunchasi zamonaviy matematika va informatikaning asosiy tushunchalaridan biri hisoblanadi. Algoritm termini o’rta asrlar ulug’ matematigi al-Xorazmiy nomidan kelib chiqqan. XX asrning 30-yiligacha algoritm tushunchasi ko’proq matematik ma’no emas, balki metodologik ma’noni kasb etar edi. Algoritm deganda, u yoki bu masalalar sinfini yechish imkonini beruvchi aniq ifodalangan chekli qoidalar majmui tushunilgan. EHM larning paydo bo’lishi bilan algoritm tushunchasi yanada keng tarqaldi. EHM va dasturlash usullarining rivojlanishi algoritmlarni ishlab chiqish avtomatlashtirishdagi zaruriy
bosqich ekanligini tushunishga yordam berdi. EHM larning paydo bo’lishi algoritmlar nazariyasining rivojlanishiga olib keldi. Algoritmlarni tuzish – bu ijodiy ish bo’lib, ixtiyoriy zaruriy algoritmni tuzish uchun umumiy usullar mavjud emas, kishining ijodiy qobiliyatiga bog’liq. Algoritm tushunchasi zamonaviy matematika va informatikaning asosiy tushunchalaridan biri hisoblanadi. Algoritm termini o’rta asrlar ulug’ matematigi al-Xorazmiy nomidan kelib chiqqan. XX asrning 30-yiligacha algoritm tushunchasi ko’proq matematik ma’no emas, balki metodologik ma’noni kasb etar edi. Algoritm deganda, u yoki bu masalalar sinfini yechish imkonini beruvchi aniq ifodalangan chekli qoidalar majmui tushunilgan.
EHM larning paydo bo’lishi bilan algoritm tushunchasi yanada keng tarqaldi. EHM va dasturlash usullarining rivojlanishi algoritmlarni ishlab chiqish avtomatlashtirishdagi zaruriy bosqich ekanligini tushunishga yordam berdi. EHM larning paydo bo’lishi algoritmlar nazariyasining rivojlanishiga olib keldi. Algoritmlarni tuzish – bu ijodiy ish bo’lib, ixtiyoriy zaruriy algoritmni tuzish uchun umumiy usullar mavjud emas, kishining ijodiy qobiliyatiga bog’liq.
Dag’al kuch atamasi foydalanishga kiritilishi shu bilan bog’liki masala qismlarga bo’linganda ko’p holda bo’lish amallari haqida o’ylab o’tirmaydi.Masalan Berilgan a+b+c+d+e+f+g+h sonlar yig’indisini toping bajarish mumkin.Bu holda yig’indi asta-sekin oshib boradi.Ikkinchi ustunavval juft-jufti bilanqo’shib olib S1=a+b;S2=c+d;S3=e+f;S4=g+h keyin yana juftlab qo’shib olamiz.S5=S1+S2;S6=S3+S4;S=S5+S6 bu holda oraliq yig’indilar nisbatan kichik bo’ladi. Ikkita natural sonlar x va y uchun eng katta umumiy bo’luvchini (EKUB) topuvchi Evklid algoritmini eslash lozim.Agar bu sonlar katta bo’lsa masala ancha murakkab
bo’ladi.Agar ularning ayirmasi z=y-x (bu yerda x>y) xam EKUB ga bo’linishini hisobga olsak,masalani soddalashtirib x,z sonlar uchun EKUB ni topishga o’tish lozim.Ularni o’sish tartibida joylashtirib x
4-qadam z=y-x=8 bu yerda z=x=8 EKUB bo’ladi. Kruskal algoritmlari Keling, algoritm g'oyasini ifodalaylik. Birinchidan, daraxt qirralari to'plami bo'sh deb e'lon qilinadi. Keyin, iloji boricha, keyingi qadam qo'yiladi: barcha qirralardan, qirralardan, mavjud to'plamga qo'shilishi tsiklning shakllanishiga olib kelmaydi, eng arzon (eng past narx) chekka tanlanadi va mavjud to'plam. Bunday qirralar bo'lmaganda, algoritm tug'iladi va biz barcha uchlari bilan boshlang'ich grafikning grafigini yaratamiz. Ushbu grafostazda tsikllar yo'qligi sababli, u eng arzon (eng qimmat) daraxt bo'lib, boshqa yo'l bilan nominal daraxt deb ataladi. Biz misolda algoritm tushunchasini
amalga oshiramiz va butun jarayonni bosqichma-bosqich sxematik tarzda ifodalaymiz. Dastlabki grafik ko'rsatilgan. Prima algoritmlari Algoritm g'oyasi.Grafik uchlarini tanlash tanlanadi. Sung shu uchidan chiqadigan barcha qirralarning eng arzonini tanlaydi. Keyin ushbu daraxtga tegishli barcha tizmalarning eng arzoni tanlanadi. Bu chekkalar yoki tizmalar eng arzonlaridan bir nechtasi bo'lsa daraxtga qo'shiladi.Qirralarni qo'shish jarayoni shunday qo'shimchalar halqa hosil qilguncha davom etadi. Bunday daraxtni qurish jarayoni sekin va grafikning barcha uchlarini qamrab oladi. Shunday qilib, grafikning chetlaridan
daraxt hosil bo'ladi va qolgan uchlarini daraxtga qo'shish tsiklni hosil qiladi. Internet resurslari: 1. www.estudu.uz 2. www.tuit.uz 3. www.Math.uz 4. www.ziyonet.uz. 5. www.intuit.ru/department/ds/discmath/ 6. www.uni-dubna.ru/manzy/kurses/odm/lekcii/ 7. www.lvf2004.com/dop_t2r1part.html
