Muhammad al-xorazmiy nomidagi tatu qarshi filiali tt-11-20 guruh talabasi qahramonova niginaning algoritimlarni loyihalash fanidan tayyorlagan mustaqil ishi-4 Bajardi: Qahramonova. N qabul qildi: Ro`ziqulova. M

MUHAMMAD AL-XORAZMIY NOMIDAGI TATU QARSHI FILIALI TT-11-20 GURUH TALABASI QAHRAMONOVA NIGINANING ALGORITIMLARNI LOYIHALASH FANIDAN TAYYORLAGAN MUSTAQIL ISHI-4 Bajardi: Qahramonova. N Qabul qildi: Ro`ziqulova. M

MAVZU:Ketma-ketliklar, to’plamlar, daraxtlar, graflarni ifodalash usullari

Algoritm – berilgan natijaga erishish uchun qilinishi kerak boʻlgan aniq koʻrsatmalar ketma-ketligi. Algoritm keng maʼnoda faqat kompyuterga oid atama boʻlmay, balki unda berilgan koʻrsatmalarni bajara oluvchi har qanday narsaga oiddir. Algoritm, algoritm – maʼlum bir turga oid masalalarni yechishda ishlatiladigan amallarning muayyan tartibda bajarilishi haqidagi aniq qoida (dastur). Kibernetika va matematikaning asosiy tushunchalaridan biri. Oʻrta asrlarda oʻnli sanoq tizimi boʻyicha toʻrt arifmetik amal bajariladigan qoidani Algaritm deb atashgan. "Bu qoidalarni matematikaga 9-asrda al-Xorazmiy tomonidan kiritilgan. Yevropada bunday qoidalar uning tug'ilgan yurtiga nisbatan lotinchalashtirilgan (Algoritmus yoki Algorithmus shaklida "algorizm" deyilgan), keyinchalik "algoritm"ga aylangan" (akademik A. N. Kolmogorov). Fanga "Yevklid algoritmi", "Gʻiyosiddin Koshiy algoritmi", "Laure algoritmi", "Markov algoritmi" deb ataluvchi algoritmlar maʼlum.

Algoritm tushunchasi tobora kengayib borib, kibernetikaning nazariy va mantiqiy asosi hisoblangan algoritmlar nazariyasi paydo boʻldi. Oʻzbekiston Respublikasida bir necha ilmiy tadqiqot muassasalari va hisoblash markazlarida Algoritmdan foydalanish sohasida samarali ishlar olib borilmoqda. Masalan Oʻzbekiston Fanlar akademiyasi "Kibernetika" ilmiy ishlab chiqarish birlashmasida, Oʻzbekistondagi barcha universitetlarda, Toshkent davlat texnika universitetida, Oʻzbekiston Respublikasi Makroiqtisod va statistika vazirligi qoshidagi Hisoblash markazi va boshqa muassasalarda olib borilayotgan ishlar bunga misol boʻla oladi.

Graflar nazariyasining asosiy tushunchalari. Matematik nazariyada va informatikada graf — bu tugunlar(uchlar)dan iborat bo'lgan bo'sh bo'lmagan to'plam va tugunlarni birlashtiruvchi yoylar majmuidir. Graf - bu murakkab chiziqsiz ko'pbog'lamli dinamik tuzilma bo'lib, murakkab ob'ektlarning xususiyatlari va munosabatlarini aks ettiradi. Ob'ektlar tugun yoki graf uzellari ko'rinishida va munosabatlar yoy yoki yo'naltirilgan qirralar kabi ifodalanadi. «Graf» tushunchasini birinchi marotaba 1936 yil vengriya matematigi Denni Kyonig kiritgan. Lekin graflar nazariyasi bo'yicha 1-ish Leonard Eylerga tegishli bo'lgan va u 1736 yilda bajarilgan edi. XVIII asrda mashhur shvetsariyalik matematik, mexanik va fizik Leonard Eyler (1707-1783 yy) Kyonigsberg ko’prigi haqidagi masalani yechish uchun birinchi marta graf tushunchasidan foydalanadi.

Graflarda eng qisqa yo’lni aniqlash haqida. Graflar nazariysida eng qisqa yo’lni aniqlash muhim klassik masalalaridan biri deb hisoblanadi. Uni hisoblash va echimlarni topish uchun bir qancha algoritmlari mavjud. Eng qisqa yo’l masalasi (inglizchada – shortest path problem) – bu grafning ikkita tugun orasidagi eng qichik yo’l (masofa, zanjir, marshrut) topish masalasidir, qaysidaki yoylarning vaznilarining yig’indisi minimal qiymatga ega. Qisqa (oddiy) zanjir geodezik zanjir ham aytiladi. Ushbu masalani adabiyotlarda bir nechta boshqa nomlanishi ham uchratish mumkin: minimal masofa masalasi, dilijans masalasi, qisqa masofa masalasi va boshqalar. Grafda eng qisqa masofani topish masalasi yo’naltirilgan, yo’naltirilmagan va aralash graflarda yechimini aniqlash mumkin.

Ikkilik daraxtlar. Barcha ma’lumot tugunlari ikkitadan ko’p bo’lmagan eng yaqin avlod tugunlariga ega bo’lgan daraxtlar binar daraxtlar deb ataladi. Graflar. Graf bu – tugunlar va ularni birlashtiruvchi bo’glanishlarmajmuasidir. Bog’langan graf. Har bir ma’lumot tugunlari juftligi orasidagi bog’lanishlarga ega bo’lgan graflar bo’glangan graflar deb ataladi. To’liq graf. Barcha mumkin bo’lgan bog’lanishlarga ega bo’lgan graf to’liq graf deb ataladi. Bunda n ta tugunli graf n(n-1)/2 ta bog’lanishga ega bo’ladi.

Foydalanilgan adabiyotlar ro’yxati 1.”Algoritmni loyihalash” fanidan o’quv qo’llanma U.Abdullayev.M.Ro’ziqulova 2. uz.wikisko.ru 3.www.wikipediya.uz