549
Islamov E.R. Ta’lim muassasalaridagi dars jadvali tuzishda siqib chiqarish algoritmidan
foydalanish
TA’LIM MUASSASALARIDAGI DARS JADVALI TUZISHDA SIQIB CHIQARISH
ALGORITMIDAN FOYDALANISH
Islamov Erkinjon Revkatovich
Farg‘ona davlat universiteti, o‘qituvchi
e.islamov@yandex.ru
Annotatsiya.
Ta’lim muassasalarida dars jadvali tuzish masalasini kompyuterda yechish
uchun yaratilgan algoritm haqida qisqacha ma’lumot keltirilgan.
Kait so‘zlar.
Ta’lim muassasasi, dars jadvali, algoritm, siqib chiqarish algoritmi.
Аннотация.
Приведен краткий обзор алгоритма, созданного для решения задачи
составления расписания занятий в учебных заведениях на компьютере.
Ключевые слова
. Учебное заведение, расписание уроков, алгоритм, алгоритм
сжатия.
Abstract.
A brief overview of the algorithm created to solve the problem of scheduling
classes in educational institutions on a computer is given.
Key words.
Educational institution, timetable, algorithm, compression algorithm.
Ta’lim sohasidagi eng murakkab
masalalardan biri bu albatta, dars jadvali tuzish
masalasi hisoblanadi. Dars jadvali tuzish masalasi parametrlarning va tushunchalarning
ko‘pligiga hamda ta’lim muassasasining tipiga qarab turli murakkablikda bo‘lishi mumkin.
Aynan, maktablar uchun dars jadvali tuzish boshqa ta’lim muassasalari, xususan, kasb-
hunar kollejlari va oliy ta’lim muassasalari uchun dars jadvali tuzishga qaraganda ancha
murakkab masala hisoblanadi.
Maktab dars jadvalini qo‘lda tuzivchi dispetcherlar ko‘plab shartlarni e’tiborga olishga
harakat qiladi, lekin shartlarning ko‘pligi ularni to‘la bajarish imkonini yo‘qqa chiqaradi.
Shuni ham ta’kidlab o‘tish kerakki, qo‘lda tuzilgan dars jadvalining
xatosini tekshirish
ancha murakkab mashg‘ulot hisoblanadi, aksariyat xatolar o‘quv jarayoni boshlangandan
keyin aniqlanadi va tuzatiladi. Bu esa bir muncha vaqt, tartibsizliklar va yo‘qotishlar
evaziga bajariladi.
Masalani matematik (algoritmik) yo‘l bilan yechishning eng dolzarb qismi,
o‘zgaruvchilar va tushunchalarni to‘g‘ri tizimga solish hisoblanadi. Bunda tizimni shunday
qurish kerakki, u sodda, tushunarli, etarli va o‘lchami imkon qadar kichik bo‘lishi lozim.
Matematika fanlarining yangi soxalaridan biri bo‘lgan Jadvallar nazariyasi odatda eng
dolzarb bo‘lgan masalalarni yechishni o‘rganadi. Jadvallar
nazariyasi masalalarining
hayotiyligi, murakkabligi va qiziqarliligi bilan ko‘plab taniqli matematiklarni bu soxada
izlanishga chorladi. Bugungi kunga kelib nazariyaning asoslari, tushunchalari, muammolari
olimlar tomonidan tushuntirib berildi. Jadvallar nazariyasining ko‘plab masalalari
NP
-
murakkablikdagi masalalar hisoblanadi. Ma’lumki,
NP
-murakkablikdagi masalalarni
yechish bevosita masalaning o‘lchamiga ya’ni undagi ob’ektlar soniga bog‘liq bo‘ladi.
Ob’ektlar soni ko‘paygan sari masalani yechishga sarflanadigan vaqt supergeometrik
ravishda ortib boradi va uni amalda optimal yechimini topishning imkoni yo‘qdek tuyuladi.
Ma’lumki, jadval tuzishda har bir ob’yektning o‘ziga hos hususiyatlarini hisobga olish
talab etiladi. Masalan: obyektning o‘lchami, turi, og‘irligi, ish vaqti va shunga o‘xshash.
Bunday hususiyatlarning ko‘payib borishi jadvalni optimal tuzish masalasini vaqt me’yori
jihatidan olib qaraganda hal qilib bo‘lmas darajada murakkablashtirib yuboradi. Chunki,
optimal jadval tuzish uchun barcha variantlarni tekshirib chiqishga to‘g‘ri keladi.
Ob’yektning har bir hususiyati esa variantlar sonini keskin ortishiga sabab bo‘ladi.
550
Albatta, jadval tuzish masalasida ob’yektlarning bir nechta
turlari nazarda tutilishi
mumkin. Masalan: o‘quv dars jadvalida sinf, o‘qituvhi, o‘quv xonasi va fan turli ob’yeklar
hisoblanadi yoki poyezdlarning harakatlanish jadvalida: poyezd, shofyor, temir yo‘lni turli
obyektlar sifatida qarash mumkin. Jadval tuzishda har bir ob’yektning individual ish vaqti
muhim ahamiyat kasb etadi. Har bir ob’yekt o‘z ish vaqtining turli qismlarida boshqa
ob’yektlar bilan bog‘lana olish imkoniyatiga ega bo‘ladi.
Bugungi kungacha ham nazariyaning ayrim masalalari uchun chegaralangan vaqtda
optimal yechimni topishga imkon beruvchi algoritmlar topilmadi. Shuning uchun xozirda
bunday masalalar uchun eng optimal yechimni emas balki,
imkon qadar yaxshiroq
yechimlarni olishga imkon beruvchi algoritmlar qo‘llanilmoqda. Eng optimal yechimni izlab
topish esa barcha variantlarni tekshirib chiqishga majbur qilmoqda.
Jadvallar nazariyasi masalalarini EHMlarda yechish uchun hozirda quyidagi
algoritmlardan foydalanib kelinmoqda:
To‘la tekshirish algoritmlari;
O‘xshatib modellash algoritmlari;
Rang-barang graflar algoritmi;
Min-max algoritmlar;
Ochko‘z algoritmlar;
Genetik algoritmlar;
Gibrit algoritmlar va h.k.
Shuni ta’kidlab o‘tish joizki, yuqoridagi algoritmlarning birinchisidan ko‘pincha amalda
foydalanib bo‘lmaydi (juda ko‘p vaqtni talab etadi), qolganlari
esa eng optimal yechimni
topishni kafolatlamaydi.
Ushbu ishda jadvallar nazariyasining ko‘plab masalalari uchun qo‘llash mumkin bo‘lgan
yangi “siqib chiqarish algoritmi” nomli usul taklif qilinadi. Siqib chiqarish algoritmi
variantlarni tekshirishni talab qilmaydi, balki, birato‘la optimal yechimlarni aniqlashga
imkon yaratadi.
Siqib chiqarish algoritmi har bir ob’ektning joylardagi zichligini aniqlash yordamida
masalani yechimini topishga imkon beradi. Ob’ektning joylardagi ehtimolligini shu
joylardagi boshqa ob’ektlarning ehtimolligini e’tiborga olgan holda hisoblanadi. Albatta,
bunday ehtimolliklarni hisoblash ehtimollar nazariyasiga
asoslangan xolda yangi
tushunchalar bilan boyitilgan. Bu usulning yaratilishi ehtimollar nazariyasida ham yangi
tushunchalar va o‘zgarishlar kiritilishiga sabab bo‘lishi ehtimoldan xoli emas.
Siqib chiqarish algoritmi yangi tushuncha bo‘lib, u elementlarni belgilangan sohalarga
optimal taqsimlash masalasini yechish tartibidir. Biz o‘rganayotgan masala tabiat uchun
juda soddalik qiladi. Tabiat xodisalarining ro‘y berishi shuni ko‘rsatadiki, tabiat bizdan
ko‘ra soddaroq, osonroq va qulayroq usulni qo‘llaydi. Lekin,
yana shuni ham aytish
mumkinki tabiat xodisalarining barchasi albatta matematik nuqtai nazardan to‘g‘ri bo‘ladi.
Siqib chiqarish algoritmi – elementlarning joylardagi haqiqiy ehtimolliklarini (joylasha
olish ehtimolliklarini) bosqichma-bosqich aniqlashtirish yordamida ularni taqsimlash
usulidir.
Masalaning qo‘yilishiga (shartlar va cheklovlarga) qarab siqib chiqarish algoritmini
moslashtirish mumkin. Qizig‘i shundaki, har qanday holatda ham mazkur algoritm yaxshi
yechimlarni aniqlash imkonini beradi.
