|
Ta’lim tizimida dars jadvalini shakllantirishni tadqiqoti va uni yaratish algoritmi Mundarija
|
| bet | 15/25 | | Sana | 28.07.2024 | | Hajmi | 1,86 Mb. | | #268854 |
Bog'liq DissertatsiyaGrafikni bo'yash usuli uchun algoritm.
Rejalashtirish muammosini grafikni bo'yash muammosi sifatida ko'rish mumkin. Grafikni bo'yash vazifasi - har bir qo'shni cho'qqi juftligi boshqa rangda bo'yalgan bo'lishi uchun ba'zi bir grafikning uchlarini bo'yash uchun zarur bo'lgan minimal ranglar sonini (grafikning xromatik raqami) qidirish. Xromatik raqamni topish muammosi NP-to'liq muammo bo'lib, buning uchun ko'p hollarda turli xil ochko'z algoritmlar qo'llaniladi.
Grafikni bo'yash muammosi sifatida rejalashtirish masalasini bayon qilish uchun grafik tuziladi. Grafikning har bir cho'qqisi o'quv rejasida rejalashtirilgan darsdir. Agar har qanday ikkita cho'qqi o'rtasida qarama-qarshiliklar yuzaga kelsa, masalan, ikkala sinf ham bitta sinfda yoki bitta o'qituvchi bilan o'tkazilsa, u holda ular chekka bilan bog'lanadi, bu ushbu sinflarni bir vaqtning o'zida o'tkazishni taqiqlashga tengdir. Rejalashtirish muammosi grafikni rang berish uchun zarur bo'lgan ranglar sonini minimallashtirish muammosi sifatida shakllantirilishi mumkin. Har bir rang jadvalning bir davriga to'g'ri keladi. Grafikni mustaqil sifatida rang berish vazifasi rejalashtirishda unchalik samarali emas, lekin agar u boshqa algoritmlar bilan birlashtirilgan bo'lsa, foydali bo'lishi mumkin [8].
Imitatsiyon modellash algoritmi.
Rejalashtirish muammosini hal qilish uchun siz rejalashtirish paytida dispetcherning harakatlariga taqlid qilishga harakat qilishingiz mumkin. Bunday holda, algoritm to'g'ridan-to'g'ri jadval va o'quv rejasiga muvofiq jadvalga kiritilishi kerak bo'lgan darslar ro'yxati bilan ishlaydi.
Rejalashtirish jarayoni bo'sh jadvaldan boshlanadi. Bu tugallanmagan dastlabki jadval. Barcha mashg’ulotlar hisobga olinmagan sinflar ro'yxatida joylashgan. Keyinchalik, algoritm bir tugallanmagan jadvaldan ikkinchisiga o'tadi va ro'yxatga kiritilgan barcha tadbirlarni eng yaxshi tarzda tartibga solishga harakat qiladi.
Jarayon to'liq jadval tuzilmaguncha yoki ma'lum miqdordagi iteratsiyalar tugaguncha davom etadi.
Mana bu algoritmning diagrammasi:
1-bosqich. To'liq bo'lmagan jadval tuziladi (dastlab bu bo'sh jadval).
2-bosqich. Hali jadvalga kiritilmagan dars “tor joylar” tahlili asosida tanlanadi. Bu erda "tor joylar" eng kam manbalar: talabalar, o'qituvchilar va tomoshabinlar. Avvalo, eng kam resurslar uchun jadvallar tuziladi. Bular kam sinf fondidan foydalanadigan darslar, ularni o'tkazish vaqti va joyiga qat'iy shartlar qo'yadigan o'qituvchilar tomonidan o'tkaziladigan darslar va boshqalar bo'lishi mumkin [34].
3-bosqich. Tanlangan dars uchun uni jadvalga joylashtirishning barcha qat'iy cheklovlarni qondiradigan barcha mumkin bo'lgan variantlari aniqlanadi. Keyin har bir pozitsiya maxsus evristik maqsad funktsiyasi yordamida baholanadi va mashg'ulot eng yaxshi holatda joylashtiriladi.
4-bosqich. Agar 3-bosqichda jadvalda ziddiyat yuzaga kelsa, u holda "ziddiyatli" mashg'ulotlar jadvaldan chiqariladi va hisobga olinmagan sinflar ro'yxatiga qayta joylashtiriladi.
Imitatsiyon modellash algoritmini amalga oshirishda ro'yxatdan keyingi darsni tanlash, jadvaldagi eng yaxshi pozitsiyani aniqlash va natijada olingan jadvalni baholash uchun evristik qoidalarni ishlab chiqishga alohida e'tibor berish kerak.
Ushbu yondashuvning ijobiy xususiyati - bu muayyan universitet uchun jadval tuzishda hal qilinayotgan muammoning o'ziga xos xususiyatlarini batafsil ko'rib chiqish imkoniyati. Biroq ishlab chiqilgan tizimni boshqa ta’lim muassasalarida qo‘llash imkoniyati juda cheklangan. Shuningdek, universitetdagi kichik ichki o'zgarishlar bilan algoritmga jiddiy o'zgartirishlar kiritish kerak bo'lishi mumkin.
Rejalashtirishda dispetcherning harakatlariga asoslangan algoritmdan foydalanib, optimal jadvalni qidirishda foydalanuvchi va tizim o'rtasida faol muloqotni tashkil qilish mumkin. Bu faqat nisbatan kichik vazifalar uchun to'g'ri bo'lishi mumkin, chunki aks holda algoritmning foydalanuvchiga sezilarli darajada bog'liqligi bunday dialogni samarasiz qilishi mumkin.
|
| |
