Foydalanilgan adabiyotlar ro‘yxati

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. 

Download 15,84 Mb.