Axborot texnologiyalar universiteti mustaqil ish

9. Kommivoyajer masalasi algoritmlarni o’rganish, chuqurlik va eni bo’yicha aylanib o’tuvchi graflar, kommivoyajer masalasini yechish.

1. Kommivoyajer masalasi algoritmlarni o’rganish

2. Kommivoyajer masalasini yechish

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.

Albatta, algoritmni aniq sxema bo’yicha tuzish zarur bo’lib qoladigan sodda hollar ham mavjud. Bunday hollarda yechilish algoritmiavval biron kim tomonidan olingan masalalarni misol keltirish mumkin. Masalan, differensial tenglamalarni sonli integrallash uchun Eyler metodi. Bu metod masalani yechish uchun umumiy holda ifodalangan algoritmdir, lekin algoritmlash ijodiy ekanligini quyidagi algoritmlar nazariyasining ba’zi bir ma’lumotlaridan ko’rish mumkin. Agar bizdan biror algoritmni ishlab chiqish talab qilinsa, dastlab izlanayotgan algoritmni tuzish mumkinmi yo’qmi degan savolga javob izlash kerak. Chunki ba’zi hollarda algoritmni tuzish mumkin emasligini ko’rsatib berish mumkin. Ba’zi bir hollarda algoritmni tuzish mumkinligi isbotlanadi. Bunday isbot mavjud bo’lganligi bilan tuzilgan algoritmni amalgam oshirib bo’lmaydi yoki uning samaradorligi talabga javob bermaydi. Shunga qaramasdan bir nechta algoritmlar bitta amaliyotga qo’llanilayotganini topish mumkin. Bu holatda o‘chirilgan element o‘rinini eng chapdagi element egallaydi yaʼni 6. Bunga sabab element o‘chirilganda tuzilma o‘z xususiyatlarini saqlab qolishi zarur yaʼni tugunning chap tomonida undan kichik, o‘ng tomonida esa undan katta qiymat joylashishi kerak. Natija: Shunday qilib biz siz bilan binar daraxtdagi eng asosiy ikkita daraxt qurish va undan element o’chirish jarayonlarini o’rgandik. Uni quyidagicha belgilaymiz1 :  B x (A). O„rniga qo„yish qoidasiga quyidagi aniqliklarni kiritamiz: a) agar A faqat x o„zgaruvchidan iborat bo„lsa, u holda  B x (A) o„rniga qo„yish B formulani beradi; b) agar A formula x dan farqli y o„zgaruvchidan iborat bo„lsa, u vaqtda  B x (A) o„rniga qo„yish A ni beradi; d) agar A o„rniga qo„yish aniqlangan formula bo„lsa, u holda A formuladagi x o„rniga B formulani qo„yish natijasida o„rniga qo„yishning inkori kelib chiqadi, ya‟ni  B x (A) o„rniga qo„yish  B x (A) ni beradi. e) agar A1 va A2 formulalarda o„rniga qo„yish aniqlangan bo„lsa, u holda   B x (A A ) 1 2 o„rniga qo„yish    B x B x (A ) (A ) 1 2 ni beradi.