Axborotlashtirish texnologiyalari

Adabiyotlar
1. M.Aripov, A.Haydarov. Informatika asoslari. Toshkent. «O’qituvchi» 2002 yil.
297-302 betlar.
2. A.A.Abduqodirov, A.G’.Hayitov, R.R.Shodiyev. Axborot texnologiyalari.
Toshkent. «O’qituvchi» 2003 yil, 36-49 betlar.
14 MA’RUZA: GRAFLAR. GRAFLAR ASOSIDA ALGORITMLAR.


Reja


1. Eng qisqa yo’llar masalalarining turlari.
1. Sozli algoritmni tuzish.
3. Algoritmni psevdokodda ishlab chiqish
4. Algoritmni baholash.
Darsning maqsadi: Talabalarga graflar, graflar asosida algoritmlar? Graflarni boshqarish, optimallashtirish haqida ma’lumot berish.
Tayanch iboralar: Ma’lumotlar strukturasi, graf, yo’naltirilgan, simmetrik, asimmetrik.
Mashg’ulot vositalari: sinf doskasi, plakatlar, fundamental fan darsliklari, o’quv va uslubiy qo’llanmalar, informatika bo’yicha atamalar lug’ati, videoproyektor, ekran va kompyuterdan samarali foydalanish.
Mashg’ulot usullari: takrorlash, suhbat va savol-javob, munozara (mavzuni o’zlashtirishni mustahkamlash) tarzida muloqot o’tkazish, (talabalarning mustaqil, erkin fikrlash va so’zlashga o’rgatgan holda fikr mulohazalarini bayon qildirish, buning uchun har bir talabaga, tayanch iboralardan savollar tashlanadi, ular o’z fikrlarini bayon qiladilar, hamma talaba javobni bayon qilib bo’lgandan so’ng talaba bilan birgalikda javoblar yakun qilinadi).
Darsning xronologik xaritasi – 80 minut.
Tashkiliy qismi: Auditoriyaning jixozlanishi va sanitar sharoitlari, talabalar davomati – 2 minut.
Bilimlarni baholash: yangi mavzuni o’rganish uchun zarur bo’lgan material bo’yicha suxbat – 10 minut.
Yangi mavzuni bayon etish – 55 minut.
Mavzu o’zlashtirilgan darajasini aniqlash – 10 minut.
Uyga vazifa – 3 minut.

Yo’l tarmoqlari atlasi (karta) qismi berilgan bo’lib, undan A va B nuqtalar orasidagi “eng yahshi” marshrutni topish kerak bo’lsin. “Eng yahshi” marshrutni ko’p faktorlar belgilashi mumkin, masalan, tezlik cheklangan holda marshrutni o’tish vaqti, o’tish kerak bo’lgan shaharlar soni va boshqalar.

Biz masalani eng qisqa yo’llar faktori bo’yicha yechamiz. Masalaning modeli turlar yordamida tuziladi. Uzluksiz G turni har bir qirrasiga uning uzunligiga teng qiymat berilgan ko’rinishida tuzamiz. Bunday turda masofa irralar yig’indisiga teng bo’ladi. Masalaning maqsadi ikkita berilgan uchlar orasidagi eng qisqa marshrutni topishdir.
Umuman, eng qisqa yo’llar masalalari kombinator optimallashtirishning fundamental muammolaridandir. Ularning bir necha turlari mavjud, masalan, ikkita berilgan uchlar orasida, berilgan va qolgan barcha uchlar orasida, turdagi har bir uchlar juftliklari orasida va boshqalar.
Yo’l harajatlarini kamaytirish yechimini beradigan kommivoyajer Djek masalasini ko’ramiz. Djekning marshruti o’zi yashagan shahardan boshlanib, qolgan hamma shaharlarni bir martadan o’tib, yana o’z shahriga qaytib kelishi kerak. Demak, biz tuzayotgan ruyhatda har bir shahar faqat bir marta uchrashi kerak, Lekin Djek yashagan shahar ikki marta uchrab, ruyhatning birinchi va oxirgi elementlari bo’ladi. Undan tashqari, ruyhatdagi shaharlar tartibi Djekning marshrutini belgilaydi. Ruyhatdagi ikkita oxirgi shaharlar orasidagi yo’l narxi – bu butun marshrut narxi deb hisoblanadi. Demak, agar biz Djekga eng kichik narxdagi ruyhatni tuzib bersak, masalani yechgan bo’lamiz.
Masalani soddalashtirish uchun beshta shahar uchun yechim topamiz. Rasm. 1a – narxlar matrisasi. Rasm. 1b – turli model ko’rsatilgan.

-	1	2	7	5
1	-	4	4	3
2	4	-	1	2
7	4	1	-	3
5	3	2	3	-

Rasm 1-a). Narxlar matrisasi

Rasm 1-b). To’rsimon model

Masalani tarmoqlanish ko’rinishida tadqiq qilamiz. Quyidagi rasmlarda beshta shahar uchun kommivoyajer assimmetrik masalasining narxlar matrisasi berilgan.

	1	2	3	4	5
1	-	25	40	31	27
2	5	-	17	30	25
3	19	15	-	6	1
4	9	50	24	-	6
5	22	8	7	10	-

Rasm 1. Narxlar matrisasi

Rasm 2. To’rsimon model