Скачать бесплатно программу составления школьного расписания

 
 

Пиликов Николай Петрович

Методика составления школьных
расписаний с использованием
персонального компьютера

Аннотация

 
Данная публикация знакомит читателя с уникальным, сравнительно недавно появившимся, алгоритмом составления школьного расписания. Сообщаются результаты тестирования единственной в мире программы, которая может не составлять, а составить школьное расписание в полностью автоматическом режиме. Опираясь на результаты десятков миллионов тестов (построенных школьных расписаний) развенчивается миф о невозможности составления школьного расписания без участия человека. Приводится описание программы «АФМ: Аннушка», предназначенной для тестирования алгоритма любым желающим.
Для понимания основного содержания публикации не требуется какой-либо специальной математической подготовки, таким образом, она адресована широкому кругу заинтересованных читателей.

1  Введение

За последнее полтора десятка лет в Российской Федерации было защищено не менее дюжены диссертаций по темам связанным с задачей составления учебных расписаний. За предыдущее, перед этим периодом, десятилетие количество защищенных диссертаций не меньше. Хотя в основном диссертации защищаются на звание кандидата технических наук и рассматриваются задачи составления расписания занятий для высшего учебного заведения, тем не менее данный факт свидетельствует о том, что к задачам составления школьного расписания проявляет внимание все больше и больше исследователей. Возможно этот поток работ связан с постоянным прогрессом и всеобщей доступностью вычислительной техники. Действительно на наших глазах произошли по истине удивительные процессы. Еще каких-нибудь тридцать пять лет назад, такую электронно-вычислительную машину, как EC1066, могло себе позволить приобрести только крупное, как правило оборонное, предприятие. Располагался такой компьютер в помещении площадью до нескольких сот квадратных метров, оборудованном мощной системой бесперебойного электропитания и системой поддержки микроклимата. Такие электронно-вычислительные машины в первую очередь предназначались для решения уникальных научно-технических задач, оказывающих влияние на обороноспособность страны.1 Сегодня у многих дома на письменных столах стоят персональные компьютеры. Но только вдумайтесь. Оперативная память такого персонального компьютера по сравнению с выше упомянутым гигантом больше в 1000 - 2000 раз. Быстродействие выше, более чем в 1000 раз. И это не описка. Более чем в тысячу раз.
Сегодня для образованного человека, который никогда не сталкивался (или еще не сталкивался) с проблемой автоматического составления расписания в школе, включая людей которые называют себя IT-специалистами уровня эксперта, утверждение о том, что не существует программного обеспечения которое могло бы решить данную задачу (составить расписание в автоматическом режиме без участия человека)2 кажется просто абсурдным. Логика их рассуждений очень проста: - «При таком развитии техники, этого просто не может быть». Вторым аргументом, как им кажется бьющим «наповал», является обращение к любой поисковой системе имеющейся в Интернете. По поисковому запросу: - «Программа для составления расписания уроков», открываются десятки ссылок. Очень быстро находятся программы обещающие качественное решение данной задачи в полностью автоматическом режиме.
Таким образом, мы сегодня имеем -
Во-первых. Массовое заблуждение неспециалистов (а точнее людей, не посвятивших несколько десятков часов, работе с данными программами) о том, что эту задачу легко решить и о том, что рынок до отказа забит такими программами.
Во-вторых. Огромную армию завучей, попытавшихся применить такие программы в своей работе, и понявших, что их обманули, унизили, оскорбили, надругались и т.п.
В-третьих. Широко распространенный миф среди людей, которые считают себя специалистами в области разработки таких программ, о том, что задачу составления школьного расписания в автоматическом режиме невозможно решить в принципе. И это (невозможность решения) строго доказанный математический факт.
Данная публикация посвящена, с одной стороны, развеиванию первого массового заблуждения о легкости решаемой задачи, и, с другой стороны, опровержению мифа о том, что такая задача не поддается решению в принципе.

2  Поколения ПО составления учебных расписаний

Первые публикации на тему применения вычислительной техники с целью автоматизировать составление расписания занятий появились в начале 60-х годов предыдущего столетия, таким образом задача составления учебного расписания с помощью вычислительной техники имеет достаточно продолжительную историю.3 За последние 60 лет интенсивных исследований была проведена огромная интеллектуальная работа многих тысяч специалистов по всему миру.
Совершенно не удивительно то, что программы для составления школьного расписания появлялись и совершенствовались по мере развития вычислительной техники. Поэтому обратимся (естественно в телеграфном стиле) к весьма условным периодам этого развития.
Не вдаваясь сильно в исторические изыскания и не рискуя сильно ошибиться, появление действующего компьютера (электронно-вычислительной машины - ЭВМ) и приносящего реальную пользу, можно отнести к 1945 году. Это появление (опять же не рискуя сильно ошибиться) можно обосновать огромной потребностью в вычислениях для военных нужд. Одной из первых задач которые решались на первых ЭВМ была задача составления баллистических таблиц для артиллерии и авиации. Не последнюю роль в потребности военных играла задача изучения атомного и термоядерного взрыва. В силу выше указанных причин, сам факт существования ЭВМ и принципы ее работы по началу оставались засекреченными.
Примерно десять лет понадобилось на то, что бы довести сведения о «тактико-технических характеристиках» первых ЭВМ до широкого круга узких специалистов - математиков занимающихся численными методами. Результат не заставил себя долго ждать. С 1955 года, вместе с появлением языка высокого уровня Fortran, наблюдался взрывообразный рост такой отрасли научных знаний, как прикладная математика. Сотни и тысячи практически важных задач стали предметом исследования математиков с применением электронно-вычислительной техники, что повлекло за собой разработку совершенно новых численных методов решения этих задач. По той причине, что стоимость компьютеров была совершенно не сопоставима с тем экономическим эффектом которые они могли принести для гражданского промышленного предприятия, единственными пользователями этой техники были военные и весьма узкий круг ученых. Другими словами те люди которые не знали слов - дорого, затраты или словосочетания - экономический эффект.
Но время шло. Технологии производства и проектирования вычислительной техники развивались стремительными темпами. В результате, производительность компьютеров росла не бывалыми шагами, а их стоимость быстро снижалась. Цены на компьютеры от астрономических неуклонно приближались к земным (хотя и еще заоблачным). К 1965 году весьма заметно вырос круг ученых которым для исследований была доступна вычислительная техника. К этому времени (начало шестидесятых годов), как было отмечено выше, и относятся первые публикации на тему составления на больших ЭВМ школьного расписания. Совершенно естественно, что работы поначалу имели постановочный характер, а позже теоретический.

2.1  Программы первого поколения

Около пятнадцати лет понадобилось на то, что бы придумать все что можно было легко придумать в отношении задачи составления школьного расписания. Этот период (с 1965 до 1980 года) вызывает резкие смешанные чувства. С одной стороны, были предложены красивые и оригинальные математические модели задачи составления школьного расписания (вершинная раскраска графов, реберная раскраска графов), а с другой стороны, вне всякого сомнения эти модели следует отнести к весьма упрощенному варианту организации учебного процесса. Другими словами, полностью задача не была решена и даже не сформулирована в деталях. Более того, в 1976 году появилась работа израйльских математиков [24] где, по их мнению, была доказана принципиальная трудность решения задачи составления школьного расписания, в том случае если преподавателям самостоятельно позволить задавать для себя, так называемые, методические дни.
Итак, к 1980 году не смотря на то, что производительность ЭВМ постоянно повышалась а их стоимость постоянно снижалась, в результате чего уже и некоторые гражданские промышленные предприятия перешли в категорию активных пользователей вычислительной техники, наша задача по прежнему оставалась до конца не решенной, а вычислительная техника для главного пользователя - школ, оставалась недоступной. Вот пожалуй к этому периоду можно было бы отнести программы первого поколения для составления расписания учебных занятий.

2.2  Программы второго поколения

В силу выше указанных двух причин (труднорешаемость задачи и недоступность вычислительной техники для конечного потребителя) интерес, в начале 80-х годов, к автоматическому составлению расписания занятий заметно ослабел (а может быть даже и полностью угас). Высшие учебные заведения, использующие данное программное обеспечение, взяли крен от собственно составления расписаний занятий к учету и контролю успеваемости студентов. Еще раз подчеркнем, что администрации школ в подавляющем большинстве даже и не догадывались о существовании таких программ.
Однако, к этому времени (естественно за рубежом) среди некоторых «яйцеголовых» студентов возникает мода на конструкторы из радиодеталей. Забрезжила эра персональных компьютеров. Мода оказалась весьма прилипчивой и круг «яйцеголовых» неуклонно расширялся. Весьма вероятно, что конструкторы из радиодеталей так и остались бы уделом кучки «ненормальных» если бы самый крупный в то время производитель пишущих машинок, а за одно и самых распространенных в то время ЭВМ, американская корпорация IBM, приблизительно в 1985 году, прозорливо не смекнула бы, что эти конструкторы, если им придать форму пишущей машинки, могли бы эти пишущие машинки заменить. Причем не просто заменить, а сделать из пишущей машинки сверхинтеллектуальную пишущую машинку составив конкуренцию «свинцовым технологиям» в издательском деле. Разумеется в то время никто, разве что кроме самых прозорливых, и предположить не мог, что конструкторы из радиодеталей когда нибудь смогут составить конкуренцию настоящим вычислительным устройствам.
Тем не менее, жребий был брошен, началось массовое производство убийц пишущих машинок. Не долго себя заставили ждать и идеи производства сначала «два в одном» (пишущая машинка плюс помощник бизнесмена - электронная таблица), потом «три в одном» (еще плюс бухгалтерская программа), потом «четыре в одном», и так далее, и так далее, и так далее. Вчерашние студенты по моновению волшебной палочки стали превращаться в миллиардеров, а бывшие конструкторы из радиодеталей все больше и больше стали походить на настоящие электронно-вычислительные машины. В технический и деловой язык вошла уважительная аббревиатура «Пи-Си» (PC), что означало персональный компьютер и уже в начале 90-х годов XX столетия ни у кого не вызывало сомнений, что у них на столе располагалась не игрушечная, а совершенно настоящая электронно-вычислительная машина.
Противоположные тенденции - взрывообразный рост производительности бывших игрушек, с одной стороны, и стремительное падение их цены, с другой стороны, сделали свое дело. В некоторых продвинутых школах на столе у руководителей появились, по сегодняшним меркам, здоровущие мониторы, которые как живой укор вопили: - «Наполни меня нужным программным обеспечением». Не мудрено, что вспомнилась уже казалось бы совсем забытая идея составления расписания учебных занятий. Тысячи любителей легкой наживы бросились писать программы для школ, гарантируя полную автоматизацию и невиданное улучшение всего, что только попадется под руку. К этому периоду, пожалуй можно отнести программы второго поколения, автоматизирующие процесс составления школьных расписаний.
В девяностых годах прошлого столетия индустрия персональных компьютеров переживала невероятный рост. Производительность персоналок увеличивалась вдвое чуть ли не каждый год и каждый год приносил инновационные программные продукты. У работающих в этой сфере «на ботинках рвались подметки». А программы по составлению школьных расписаний что-то никак не хотели составлять эти расписания ...
Сейчас конечно трудно сказать, знали или нет производители программ для составления школьного расписания о том наследстве которое им оставили их предшественники в 1965 - 1980-х годах прошлого столетия и о предупреждении израйльских математиков 1976 года о том, что эта задача труднорешаемая, но факт остается фактом - администрация учебных заведений потихоньку списывала старые добрые пишущие машинки заменяя их персональными компьютерами. Расписание по прежнему, за небольшими исключениями, составлялось в ручную.

2.3  Программы третьего поколения

К началу XXI века вместе с окончательным доминированием операционных систем с графическим пользовательским интерфейсом, приходит и конец программам второго поколения по составлению школьного расписания, которые использовали псевдографисеский интерфейс ушедшей операционной системы MS-DOS. Индустрия персональных компьютеров благополучно прекратила свое бурное развитие и перешла к пресловутой «стабильности». Персональная вычислительная техника преодолела рубеж производительности больших ЭВМ середины 80-х годов прошлого века, стоимость персоналок снизилась от стоимости легкового автомобиля до месячной зарплаты рядового инженера, все было готово для разработки программ третьего поколения.
И действительно, в самом конце прошлого столетия несметное количество производителей, в очередной раз но уже, как им казалось, на новом техническом и технологическом уровне взялись за разработку программ составления школьного расписания. На фоне прекращения заметного (хотя и плавного) роста производительности персональных компьютеров, стабилизации идей в области программного обеспечения развивались программы, которые можно было бы отнести к программам третьего поколения. Основной особенностью этих программ, как нам кажется, является то, что они могли бы разрабатываться учитывая как ошибки, так и оригинальные находки предшественников. Здесь в первую очередь имеются в виду разработчики девяностых. С математическими результатами шестидесятых, семидесятых и восьмидесятых дело обстоит проще. Если ты о них знаешь, то используешь, если не знаешь, то «придумываешь велосипед заново». Другой особенностью является то, что эти программы разрабатывались с использованием нового на то время - графического интерфейса пользователя. Нет сомнений в том, что графический интерфейс предоставляет разработчику принципиально б\'ольшие возможности по сравнению с псевдографическим (текстовым). Но в этом, в тоже время, кроется и опасность. Если мы начнем сравнивать имеющиеся на рынке (в использовании) программы составления школьного расписания, то обнаружим совершенно потрясающее разнообразие способов формирования (ввода) исходных данных, необходимых для расчета, хотя с математической точки зрения большинство программ делают (или по крайней мере, должны делать) совершенно одно и тоже. Таким образом, на качество программ составления школьного расписания стало оказывать существенное влияние логичность и удобство пользовательского интерфейса.
Сегодня, с высоты 2022 года, стоит отметить, что по сравнению с программами девяностых, программы третьего поколения (нулевых) весьма «поумнели», но оптимизма у разработчиков заметно поубавилось. Обещать полную автоматизацию всего, что только попалось под руку, уже никто (или почти никто) не берется.
Многие из проектов начатых на излете девяностых к настоящему времени прекратили свое существование в силу их невостребованности. Другие же продолжают развиваться и совершенствоваться. Третьи на протяжении последних двадцати лет застыли в своем развитии. Четвертые, появившиеся сравнительно недавно, и присосавшись к, так называемым, «современным платформам», предназначенным для решения совершенно других задач, обещают 97% расстановки учебной нагрузки, т.е. нахождение тупика, когда не существует ни одного места в сетке расписания куда можно было бы «приткнуть» оставшиеся 20 - 30 занятий. Таким образом, как ранее отмечалось, об окончательном и бесповоротном решении задачи составления учебного (школьного) расписания говорить было преждевременно.

3  Нужны ли такие программы?

Обычно, говоря о пользе (необходимости) использования программы по автоматизированному расчету учебного расписания, указывают такой фактор, как - на порядок сокращение трудозатрат (времени) завуча при его составлении. Часто указывают на то, что расписание с помощью компьютера может быть получено лучшего качества. Хотя этот довод, учитывая сказанное чуть ниже, является не безспорным. По нашему мнению следует согласиться с тем, что расчет расписания с помощью компьютера позволит, кроме экономии времени и получения лучшего качества расписания, с одной стороны, исключить субъективные оценки и личные симпатии по отношению к учителю (части учителей), при составления расписания, в том числе и при распределении педагогической нагрузки, а с другой стороны, позволит полностью исключить незаслуженные обвинения в адрес завуча или администрации школы со стороны учителей, в таких субъективных оценках и симпатиях, поскольку очевидно, что компьютер «лицо незаинтересованное» (во всем «виноват» компьютер). Тем самым, расчет распределения педагогической нагрузки и генерация расписания на компьютере, может улучшить психологический климат в учительском коллективе (соблюсти принципы справедливости и равноправия), точно так же как улучшает настроение игроков футбольной команды судья матча после того как разыгрывает право первого удара по мячу с помощью жребия.
В 2001 году компанией «Хронобус» было проведено анкетирование почти 1000 московских школ по вопросу необходимости создания и внедрения АРМ(а) «Расписание» [21]. Результаты анкетирования показали, что у всех школ имеется искреннее желание пользоваться такой программой, но никто этого не делает. Причем причиной дружного игнорирования подобных средств автоматизации является вовсе не отсутствие необходимой техники или денег, а качество предлагаемых на рынке программ. Фраза: - «Если бы мне предложили увеличить зарплату в полтора или два раза, за то что я пользуюсь такой программой составления школьного расписания, то я бы от этого предложения отказалась» была не редкостью. Другими словами по мнению завучей программы по составлению школьного расписания являются программным обеспечением с отрицательной стоимостью.
Сегодня по прошествию двадцати с лишним лет с момента выше указанного анкетирования у потенциальных пользователей программ по составлению учебных расписаний - завучей школ, к таким программам, еще в большей степени и не безосновательно сформировалось стойкое негативное, а часто и агрессивное отношение.4
Вводящая в заблуждение реклама о навязываемом «информационном пространстве школы» формирует представление об авторах этого пространства, как о мошенниках сбывающих тухлый товар. По мнению завучей школ с большим стажем работы, практика показывает, что данные программы могут быть использованы только в качестве инструмента для первоначальной расстановки предметов с последующей ее ручной доводкой, а так же сохранения информации и вывода ее на печать. После автоматизированного распределения предметов (программа, как правило, расставляет от 40 до 70 %) учитывать гигиенические требования к расписанию уроков практически невозможно, так как приходится не только доставлять оставшиеся не расставленные предметы, но и существенно изменять (до 60 %) автоматизированную расстановку предметов по принципу «лишь бы расставить».
В подтверждении сказанного можно привести цитату из работы 2016 года сотрудников Белорусско-Российского университета (Могилев) [22]. Опрос завучей школ (проводился опрос завучей могилевских школ) показал, что попытки использования программ предпринимались неоднократно, но в целом безуспешно.
Умудренные опытом мастера своего дела, рекомендуют начинающим при составлении расписания учебных занятий пользоваться десятком - другим советов, проверенных многолетним опытом и практикой, используя при этом, вместо компьютера, макеты таблицы расписания уроков из листов картона, цветной бумаги, широкого прозрачного скотча, клея, кармашков и т.п. И они безусловно правы. Использование компьютера в режиме обычного редактора (как, всем знакомого текстового редактора) или использование программ, заводящих процесс расстановки занятий в тупиковые ситуации, когда ни одного занятия невозможно пристроить в сетку расписания теоретически, ничего кроме неоправданных затруднений, неудобств и озлобленности принести не может.
Ожидание пользователей таких программ (завучей) сомнений не вызывает. По их мнению программы составления школьного расписания после ввода всех исходных данных, должны в полностью автоматическом режиме, составлять расписание по своему качеству превосходящее расписание составленное в ручную (или уж по крайней мене не хуже). Неадекватность ожиданий завучей и получаемого ими результата от таких программ, порождает агрессивное и даже враждебное отношение пользователей к этим программам и вместе с ними к автоматизаторам «раздвигающим за небольшие (или большие) деньги информационное пространство школы» и д\'оющим государственный бюджет.
Следует отметить, что разработчики программ по составлению школьного расписания в ходе «естественного отбора» поделились на три группы. Первая группа публично отстаивает точку зрения на то, что задачу автоматического расчета школьного расписания невозможно решить в принципе. И поэтому они «не будь бестолочами» даже и не пытаются этого сделать. А те кто пытается, по их мнению полные невежды. «У нас не программа расчета школьного расписания, а редактор школьного расписания. Мы не строим расписание вместо человека, а помогаем человеку построить самостоятельно (в ручном режиме) расписание» - с гордостью заявляют они.5
Вторая группа разработчиков декларирует в качестве цели - полную автоматизацию построения школьного расписания, но в своих рекламных материалах и руководствах пользователя дипломатично умалчивает о фактическом достижении поставленной цели. «Наша программа может строить расписание в автоматической режиме, в ручном режиме и в смешанном (полуавтоматическом) режиме» - не обманывая пользователей констатируют они. Внимание потенциальных пользователей на том, что конь может пить воду из реки, но не может ее выпить, а программа может строить (составлять) расписание в автоматическом режиме, но не может его построить (составить), эти разработчики не акцентируют. По нашему мнению это весьма взвешенная и достойная позиция, которая, несмотря на маленькую (или большую?) хитрость, может вызвать только уважение. Или, по крайней мере, не вызывает агрессивного отношения к разработчикам со стороны пользователей, честно их (пользователей) предупреждая: - «Результат не гарантирован и более того - маловероятен».
И наконец, третья группа разработчиков. «Введите исходные данные, нажмите кнопку расчет, и через несколько минут вы гарантированно получите расписание с расстановкой всех без исключения занятий. Ограничений на размерность задачи никаких. Классов хоть - 999. Преподавателей хоть - 2999. Совместителей хоть половина. Разделим класс на группы хоть до 256-ти групп. Ограничения для преподавателей и предметов любые. Каждый преподаватель выбирает для себя удобные для него рабочие дни и часы. Никаких окон у преподавателей. Занятия по предметам проводятся только в разрешенные для этих предметов часы. Неукоснительное соблюдение параллелей. Каждому предмету присваиваются баллы сложности. Точное соответствие с санитарными нормами распределения суммарной сложности предметов во времени гарантированно. Чередование в течении дня трудных и легких предметов.» - без стеснения заявляют они. Осталось только пообещать каждой «училке» по лохматому мужику, а каждому мужику по бутылке водки. Кстати говоря, на такой незатейливый ход идут разработчики наиболее беспомощных программ в плане автоматического составления расписания и к тому же неряшливых на вид (хотя есть одна, на вид весьма привлекательная, но очень беспомощная и бессовестная). Такие программы в Microsoft метко окрестили - food dog - «собачья еда».
Трудно сказать, что именно движет людьми, идущими на прямой и бесхитростный обман потребителей. Этот обман всегда становиться очевидным при первом же вводе учебного плана школы (вводе исходных данных задачи) в программу. По Российскому законодательству, в соответствии со ст. 179 Гражданского кодекса РФ, сделки совершенные под влиянием обмана могут быть признаны судом недействительными, при этом обманщик возвращает обманутому все полученные деньги, возмещает обманутому реальный ущерб и в добавок еще должен перевести в доход государства такую же сумму, что им была получена от продажи программы.6

4  Немного о сложности решаемой задачи

Стоит сказать два слова о сложности решения задачи составления школьного расписания.7 Квалифицированным пользователям персонального компьютера, уверовавшим в его всемогущество, не без помощи оголтелой пропаганды СМИ и фантастических историй о «неуловимых хакерах» за которыми скрывается банальное воровство с применением компьютера, кажется, что задача составления школьного расписания ничуть не сложнее задачи создания, например, качественного редактора текстов, или видеофильмов, или звукового редактора. Однако, как упоминалось ранее, число исследователей8 так или иначе изучавших эту задачу трудно поддается подсчету. Среди них десятки докторов технических и физико-математических наук,9 сотни кандидатов наук, не только технических, но и физико-математических, не говоря уже о тысячах рядовых любителях математических головоломок, безусловно включающих в себя многочисленную армию студентов технического и физико-математического профиля обучения. Среди исследователей задачи составления школьного расписания можно упомянуть и двух академиков - В.С.Танаева10 и В.С.Михалевича,11 можно было бы назвать и зарубежных ученых с мировым именем. Кроме ученых не обходили своим вниманием задачу составления школьного расписания выдающиеся бизнесмены12.
И тем не менее, не смотря на, без преувеличения, титанические усилия исследователей, говорить о полном и всеобъемлющем (или хотя бы удовлетворительном) решении задачи составления учебного расписания - до недавнего времени, не приходилось.
В качестве подтверждения сказанного приведем цитату известного отечественного математика [17].
... Так как задача составления расписаний хорошо всем известна по школьному быту, то на каждом курсе находится один или несколько студентов, обуреваемых идеей алгоритмизации составления расписания занятий. Поэтому я вынужден предупредить, что это очень сложная задача. ... Существует особая наука - теория расписаний, изучающая и систематизирующая задачи такого рода, а так же различные приближенные методы их решения (на точные методы надежды почти нет). Особое место среди них занимают эвристические методы, в которых делаются попытки описать логику и технику действий диспетчера. ...
Интересно одно наблюдение. Но прежде приведем еще одну цитату [23].
Гипотезу четырех красок можно с полным основанием назвать «болезнью четырех красок», так как она во многом похожа на заболевание. Она в высшей степени заразна. Иногда она протекает сравнительно легко, но в некоторых случаях приобретает затяжной или даже угрожающий характер. Никаких прививок против нее нее не существует; правда, люди с достаточно здоровым организмом после короткой вспышки приобретают пожизненный иммунитет. Этой болезнью человек может болеть несколько раз, и она подчас сопровождается острой болью, но ни одного летального исхода зарегистрировано не было. Известен по крайней мере один случай передачи болезни от отца к сыну, так что, может быть, она наследственна.
Здесь выдающийся американский математик иронизирует над старинной задачей о раскраске политической карты в четыре цвета, где страны имеющие общую границу должны быть окрашены в разные цвета. Представляется, что все сказанное им, можно отнести и на счет задачи составления школьного расписания. Так, автору этих строк вздумалось, в меру своей возможности, отследить дальнейшую карьеру людей защитивших диссертацию по соответствующей теме. Казалось бы, новосостоявшемуся ученому «сам Бог» велел обратить свои научные достижения в деньги. То есть, каким-то образом вывести свое детище на рынок, поскольку практически всегда после защиты диссертации остается некая программа или часть автоматизированной системы по составлению расписания занятий. Так вот - нет. Все известные автору случаи защиты диссертации по этой теме заканчиваются одним - после защиты, диссертант бросает эту задачу и, как правило, начинает (или продолжает) спокойную и размеренную карьеру преподавателя в вузе. Другими словами, приобретает к задаче составления учебного расписания пожизненный, стойкий иммунитет.
Заканчивая общие рассуждения о сложности решения задачи составления школьного расписания сошлемся еще на два мнения. Но прежде обратим внимание на то, кто это мнение высказывает.
Ни для кого не секрет, что некоторые школьные преподаватели информатики в припадках дидактических экспериментов поручают школьникам в качестве «домашнего задания» разработать программу составления расписания занятий для любимой школы. Школьники, естественно, засучив рукава с энтузиазмом берутся за решение этой задачи. В качестве выхлопа от данной идеи в сети Интернет можно встретить многочисленные рассуждения и теоретизирования по этому поводу выше указанного контингента. Чего только не придумывают и каких только мнений не высказывают пион\'Эры ... Не меньший ажиотаж данная тема вызывает и у людей с техническим образованием в попытках автоматизировать деятельность диспетчеров любимого вуза. Но эти мнения, мягко говоря, большого интереса не представляют. Профессиональные же математики, специалисты по теории расписаний, высказываются о проблеме составления учебного расписания чрезвычайно редко. Поэтому (или тем белее) их мнение на этот счет представляется весьма интересным.
Итак. Сотсков Юрий Назарович, доктор физ.-мат. наук, профессор, главный научный сотрудник Объединенного института проблем информатики НАН Беларусии, Минск, один из виднейших специалистов в области теории расписаний, автор ряда монографий по теории расписаний. В своей статье [1] в частности пишет:
... С математической точки зрения задача построения оптимального расписания учебных занятий является достаточно сложной, поскольку она принадлежит классу так называемых NP-трудных задач. ... В данной статье показано, как раскраска вершин графа может применяться для построения расписания учебных занятий. ...
... Задача раскраски вершин графа является NP-трудной, и, следовательно, ее обобщение, описанное в разд. 2, также является NP-трудной задачей. ...
Далее. Лазарев Александр Алексеевич, доктор физ.-мат. наук, профессор, главный научный сотрудник Института проблем управления им. В.А.Трапезникова РАН, Москва, один из виднейших специалистов в области теории расписаний, автор ряда монографий по теории расписаний. В своей статье [7] в частности пишет:
... Задача составления учебного расписания является хорошо известной задачей комбинаторной оптимизации «Составление временных таблиц» (timetabling). Даже нахождение допустимого расписания является NP-трудной в сильном смысле проблемой. Поэтому при ее решении необходимо использовать математические методы решения задач комбинаторной оптимизации. ...
Короче: - «Сливай воду, суши весла, туши свет ...»

5  Рынок ПО составления учебных расписаний

Рынок ПО составления учебных расписаний, который складывался вместе с рынком любого ПО для персональных компьютеров, представляется просто уникальным,13 или уж по крайней мере удивительным, или на худой конец весьма странным. Так в чем же его уникальность или странность?
Вам когда нибудь приходилось видеть такую рекламу: - «Купите наш пылесос, который не может всасывать пыль». Или такую: - «Все кастрюли которые мы вам можем предложить - дырявые». Или такую: - «Наш телевизор уникален - он никогда, ничего не показывает». Или такую: - «Купите у нас битые стекла, они могут пригодиться вам во время ремонта квартиры».
А вот рекламу: - «Купите нашу программу для составления школьного расписания, которая не может его составить, но зато может составлять», нам приходилось видеть сколько угодно. «Ну купите, купите, купите. Наша программа может же составлять расписание (не составить). Она вам расставит почти все занятия, ну а уж остальные, как нибудь сами. Выбираться из тупика, это же так интересно. Ну хоть за 15 долларов. Это же небольшие деньги, мы ведь столько работали ...».
Так сколько же стоит пылесос, который не всасывает пыль, дырявая кастрюля или телевизор, который никогда, ничего не показывает? Прежде чем ответить на этот нелегкий вопрос попробуем оценить количество потенциальных покупателей и сравнить его с количеством школ (завучей) которые уже совершили свою покупку.
Демографами установлено, что около 16% населения развитых стран являются школьниками. Именно эта цифра используется при строительстве новых школ в новых районах застройки [19]. Далее будем производить арифметические вычисления применительно к Российской Федерации (родина все-таки).14 Итак, население составляет примерно 140 млн. человек. Таким образом, школьников примерно 20 млн15. Школ около 41 тыс16. Значит среднее количество учеников в школе 490 человек. Но это среднее количество. Известно [19], что за последние 60 - 70 лет типовыми проектами школ, считались школы на 1000 - 1400 учеников. Отсюда вывод - имеется огромное количество школ с количеством учеников на много меньшим, чем наша средняя цифра - 490 человек. Очевидно, что это школы в сельской местности или в очень небольших городах. Отсюда же, более сильный вывод - огромному количеству школ, программы для составления расписания учебных занятий не нужны в принципе.
Оценить количество школ, которым такие программы не нужны в принципе, конечно же весьма трудно. Тем не менее, внимательно посмотрев на потолок увидим там цифру - 70%. Из чего следует, что 30% школ имеют количество учеников от 900 и более, а таким школам программа, которая, может не составлять школьное расписание, а может его составить, пригодилась бы. Получаем окончательную цифру - 12 тыс. школ. Вот это, пожалуй, потенциальная емкость рынка для Российской Федерации.
А что же мы имеем на сегодня в реальности? Вопрос не простой. Достоверная статистика отсутствует. Прежде всего на ум приходит одна программа, которая для всех школ РФ была этим школам «впендюрина бесплатно». Начало разработки этой программы относится к 1998 году, а окончание (последняя версия) к 2003 году. По внешнему виду, тем более для своего времени, программа конечно же неплохая. По сравнению с другими аналогичными программами, имеет весьма логичный и продуманный интерфейс пользователя. На наше субъективное мнение, лучший пользовательский интерфейс. Однако, хотя там и имеется кнопка Составить расписание, программа на редкость беспомощна в плане автоматического (без участия человека) составления расписания. Она не способна решить даже тех простых подзадач, с которыми другие программы легко справляются. Судя по отзывам в сети Интернет, этой программой, несмотря на всю ее псевдобесплатность, почти никто не пользуется. Так что, будем считать ее «радиационным фоном или реликтовым излучением» не влияющим на общую рыночную ситуацию.
Поехали дальше. Поставим такой вопрос. Имеются ли на рынке программы которые могут оказать завучу хоть какую-то помощь при составлении расписания? Например, многие завучи в ручную составляют расписание в два этапа. На первом этапе по их выражению: - «Разбираются с иностранцами». Другими словами, составляют расписание для преподавателей и классов, которые делятся на группы, при изучении иностранного языка. Вторым этапом идет - все остальное. По крайней мере две программы, представленные на рынке, с этим, первым этапом, справляются на зависть прекрасно. Здесь же можно спланировать время проведения элективных курсов. При этом расставляется от 10 до 40 процентов занятий. Так что, кое-какая польза от применения компьютера, оснащенного этими программами, конечно же есть. Причем одна из этих программ весьма агрессивно и настойчиво пытается достроить расписание. В некоторых случаях, пускай и редких, это ей удается. Другая же, при достраивании расписания до полного (финального), абсолютно беспомощна.
Так сколько же народу на сегодня пользуется ПО для составления расписания учебных занятий в Российской Федерации? Некоторые производители такого ПО, на своих сайтах публикуют информацию о своих клиентах. Правда, к этой информации стоит относится весьма осторожно. Как было отмечено выше, некоторые производители в «припадках маркетинга» идут на весьма бесхитростный обман потенциальных клиентов. И тем не менее, отделив зерна от плевел получим цифру - порядка 1500 школ. Что составляет около 12% емкости потенциального рынка. Следовательно 88% потенциальных клиентов еще не окучены.
Теперь остается перевести количество в качество. То есть, умножить количество потенциальных клиентов на цену одной лицензии ПО. Но для этого нужно знать цену такой лицензии.
Интересно, приходилось ли читателю держать в руках толстую книжку с примерно таким названием: - «Стоимость программного обеспечения». А нам приходилось. На самом деле, формула очень проста. Программное обеспечение, какой бы сложности и объема оно ни было, стоит ровно столько, сколько за него платит клиент (пользователь). Ярчайшим примером тому, является операционная система Windows от Microsoft. Наверное мало кто задумывался о том, что по количеству труда, таланта, знаний и т.п., высадка человека на Луну, по сравнению с этой операционной системой, является детскими шалостями. И тем не менее, сто пятьдесят баксов на бочку, и ты легальный пользователь.
Проблема только в том, что количество потенциальных клиентов - пользователей операционной системы и программы для составления школьного расписания несопоставимо, ни в первом, ни во втором приближении. Отсюда вывод: - «Не смотря на то, что некоторые просят по 15 долларов за дырявые кастрюли, программа которая действительно могла бы решить большинство проблем завучей, должна стоить дорого». Остается только ответить на вопрос: - «Что такое дорого?»
Конечно же, у каждого представления о «Дорого» свои. Но наверное, для завуча (или аналогичной должности, дорого это его месячная зарплата. Что собственно, мы и наблюдаем, или по крайней мере ранее наблюдали, в реальности. Первое время, на мировом рынке эти программы именно столько и стоили. Падение цен, как нам представляется, произошло именно из-за того, что вдруг обнаружилось - за 5000 долларов была куплена дырявая кастрюля. Теперь, те же дырявые кастрюли, предлагают по 500 долларов США17.
И наконец, перемножив количество на цену, получим примерную емкость рынка ПО для составления школьного расписания. То есть, рынок не менее денежно-емкий, чем, скажем, рынок различных систем автоматизированного проектирования в промышленности или строительстве. И к стати говоря, не менее науко-емкий. С другой стороны - не так уж это и много, если учесть, что у заместителя начальника таможни РФ по энергетике изъяли 1 тонну сто долларовых купюр (100 миллионов долларов США наличными) и 18 тонн золота (слитками, хранившимися в жилом помещении).

6  «Древнеегипетский» алгоритм решения задачи

Эта полукриминальная история произошла весной 2012 года. Один ученый-археолог, проработавший долгое время в Египте, обратился к своим знакомым программистам со странной просьбой. С его слов при переводе древнеегипетского папируса, датируемого 5697 годом шестой цивилизации18, он наткнулся на описание алгоритма составления школьного расписания. Авторство алгоритма приписывалось египетской жрице по имени Анушер. Собственно его просьба заключалась в том, что бы проверить на современном компьютере действительно ли этот алгоритм способен построить школьное расписание.
Часть одного из найденных древних рисунков
Рисунок 1: Часть одного из найденных древних папирусов
Поначалу друзья его подняли на смех. Особенно их насмешила гипотеза о девятой цивилизации. Но внимательно ознакомившись со странными записями все же решили их проверить. Итак, приступаем к описанию идеи этого алгоритма, по сути к краткому (в телеграфном стиле) изложению перевода древнего папируса. Предварительно скажем, что сама терминология этого алгоритма и организация древнеегипетской школы представляет отдельный исторический интерес, но поскольку данная публикация предназначена не для историков, излагать алгоритм будем в современной терминологии, привычной для живущего сейчас читателя.
Основное отличие древнеегипетского алгоритма (далее слово древнеегипетский будем опускать) составления школьного расписания от современных (часто используемых разработчиками программ составления школьного расписания) подходов заключается в том, что задача разбивается на части (этапы), или точнее, на ряд последовательно решаемых задач, при этом каждая решенная задача на предыдущим этапе является ограничением для задачи подлежащей решению на следующем этапе. В современной терминологии - применен метод декомпозиции решаемой задачи, часто именуемый в математической литературе - «Разделяй и властвуй».
Следует отметить, что каждая в отдельности из задач, которая последовательно решается в ходе расчета расписания, не является NP-трудной (нерешаемой). Это и позволяет с помощью последовательного решения серии легко решаемых задач, решить всю задачу составления школьного расписания целиком19.
Обратим внимание на то, что для решения каждой задачи по отдельности, естественно нужно ввести в компьютер (сформировать) все исходные данные для ее решения. Эти шаги (формирование исходных данных) при описании алгоритма, в виду их банальности, мы опускаем. Однако это не означает, что их нет.

6.1  Описание алгоритма

Первый этап алгоритма заключается в решении задачи установки запретов на проведение занятий в соответствии с санитарными нормами (если этот процесс вообще можно назвать задачей). Здесь имеется ввиду - недельная нагрузка для классов. Например, для РФ и многих других стран на постсоветском пространстве, при шестидневке для 11-х классов она составляет 36 часов (запретов нет), для 5-х классов 32 часа (четыре запрета). При пятидневке для 11-х классов 34 часа (один запрет), для 5-х классов 30 часов (пять запретов). Основным требованием решения этой задачи является установка запретов на проведение занятий в последний урок и, как правило, в последние дни недели (естественно, что если такие запреты вообще необходимы). Таким образом, построенное расписание на данном этапе состоит из множества временных участков (временных моментов - день, урок) в которые нельзя назначать (ставить) нагрузку, предусмотренную учебным планом школы.
Второй этап алгоритма заключается в решении задачи составления расписания для специальных помещений. Под специальными помещениями школы (в отличии от помещений общего назначения) имеются ввиду помещения предназначенные для проведения там только какого-то одного предмета, требующего для обучения специального оборудования. Например, физкультуры - спортзал, оснащенный спортивным инвентарем, информатики - компьютерный класс, оснащенный компьютерами, труда - мастерская, оснащенная необходимыми станками (швейными машинками) и т.п. Такие помещения имеются в каждой школе и, как правило, являются дефицитными. Другими словами их постоянно не хватает для качественного обучения, имеющегося контингента учащихся. Поэтому основным требованием для этой задачи является - стопроцентное (или близкое к тому) использование таких помещений. То есть, если школа работает шесть дней в неделю и там каждый день проводится по шесть уроков, то в специальном помещении за неделю должно пройти 36 занятий (6×6=36). Для пятидневки с семи уроками, каждую неделю загрузка должна составлять 35 занятий (5×7=35).20
Построенное на этом этапе расписание представляет из себя тройки - время проведения занятия, класс, специальное помещение. Если говорить совсем точно, то из четверок, поскольку за специальным помещением однозначно следует предмет. Преподаватели для учебных классов, на этом этапе алгоритма пока не назначаются, они будут назначены позже.
На третьем этапе алгоритма строится расписание для совместителей. Оказалось, что и древнеегипетские учебные заведения не гнушались работой совместителей. Основная особенность этой задачи заключается в том, что совместителям позволено в ультимативной форме заявлять дни по которым они будут работать. Кроме того, некоторому количеству совместителей позволено отказаться от работы в первый урок всех рабочих дней когда они преподают. Видимо этими совместителями были женщины и они не могли рано прибывать в древнеегипетскую школу, поскольку были заняты доставкой малолетних детей в древнеегипетские детские сады или ясли.
Задача решается с помощью алгоритма раскраски вершин обыкновенного графа при некоторой системе ограничений на цвета. С этой математической моделью можно подробно познакомиться с помощью уже упоминавшейся статьи [1] или с помощью других многочисленных журнальных статей, например, [4,12], а так же познакомившись с книгами[9,10]. Построенное на данном этапе расписание представляет из себя четверки - класс, преподаватель, время проведения занятия, предмет изучения.
Позже для каждого занятия (класс, преподаватель, время, предмет) «вручную» или с помощью алгоритма решения задачи о назначении подбирается помещение для проведения этого занятия. Алгоритм решения задачи о назначении описан во множестве современных учебников, в частности с ним можно познакомиться по книге[16].
Четвертый этап алгоритма состоит из решения задачи о проведении занятий по выбору учащихся (в нашей терминологии элективных курсов). Особенностью этой задачи является то, что некоторое количество классов, в некоторый учебный час, объединяются в потоки, что бы затем в этот час разделиться на небольшие группы и разойтись по своим элективным курсам. Построение расписания будет заключаться в том, что каждому потоку будет назначено время в которое будут проводиться элективные курсы, но преподаватели и помещения будут назначаться уже после того как все расписание будет окончательно построено. То есть, на этом этапе преподаватели для проведения элективных курсов и помещения не назначаются. Таким образом, построенное расписание состоит из множества двоек - поток (с включенными в него классами) и момент времени (день недели, номер урока). Отметим, что в поток может входить от одного до двух классов.
При построении такого расписания соблюдается правило - для любого потока в один учебный день может быть назначено не более одного учебного часа для проведения элективного курса. Кроме того, соблюдается другое правило - в любой момент времени (учебный час) не могут быть запланированы элективные курсы более чем для одного потока. В том случае, если суммарная нагрузка всех потоков превышает продолжительность учебной недели (в учебных часах), т.е. решение задачи заведомо не существует, то элективные курсы не могут быть запланированы более чем для двух протоков. Это правило (ограничение) представляется вполне разумным, поскольку при проведении элективных курсов резко возрастает потребность в помещениях для их проведения. Оно введено именно с той целью, что бы не возникло ситуации когда нескольким потокам в одно и тоже время требуется большое количество свободных помещений.
Как уже было отмечено, помещения для проведения элективных курсов, на этом шаге, так же как и преподаватели не подбираются, они будут подбираться вместе с преподавателями после построения всего расписания.
Алгоритмом решения задачи о проведении элективных курсов, является алгоритм раскраски верши обыкновенного графа с ограничениями на цвета, на который мы уже указывали при описании предыдущего шага.
Здесь интересно отметить, что в Российской Федерации в период с 2000 года по 2010 год намечалась реформа среднего образования, которая заключалась в так называемой профилизации обучения (см., например, [6]). При этом основные надежды возлагались на свободу выбора учащимися элективных курсов. Сейчас, с высоты 2022 года об этой реформе можно сказать следующее. «Всё педагогическое сообщество, с удивительной солидарностью, набрало полный рот соплей и харкнуло в рожу этим разработчикам». Не последнюю роль (а может быть и первостепенную) в этом процессе сыграли трудности составления школьного расписания с интегрированными в него часами для проведения элективных курсов. Хотя, конечно, не стоит сбрасывать со счетов банальную нехватку школьных зданий, т.е. свободных помещений для проведения элективных курсов.
На следующем этапе алгоритма (пятом) строиться расписание для уроков, как правило, по изучению иностранного языка. Особенностью этой задачи является то, что класс может быть разделен на группы (в нашем тестовом варианте на две), при этом количество предметов (иностранных языков) может быть больше одного (в нашем тестовом варианте до трех). Преподаватели не могут в ультимативном порядке заявлять о том в какие дни они будут работать. Однако, для преподавателей с небольшой недельной нагрузкой гарантирован один или два выходных (методических дня), которые им будут предоставлены автоматически. Точно также, как и на третьем этапе алгоритма, некоторые преподаватели, обучающие иностранному языку, могут потребовать освободить их от уроков в первый час рабочего дня когда они проводят занятия.
Задача о построении расписания по изучению иностранного языка, с разделением на группы, точно также, как на третьем и четвертом этапе алгоритма, решается с помощью раскраски вершин с ограничениями на цвета, обыкновенного графа. Построенное расписание на этом этапе состоит из четверок - момент времени, изучаемый предмет, класс (пары групп), пары преподавателей.
Точно так же, как и на третьем этапе алгоритма, позже с помощью алгоритма о назначении или «вручную», каждому занятию, а точнее, каждой группе учеников и их преподавателям подбираются помещения для проведения таких занятий.
После окончания 5-го этапа алгоритма, в зависимости от учебного плана школы, расставляется обычно от 40% до 50% всей учебной нагрузки, предусмотренной этим планом.
На шестом этапе алгоритма строиться (можно еще скать достраивается) расписание для всех оставшихся предметов без разделения на группы. У преподавателей нет возможности заявить ультиматум о том в какие дни они будут работать, но для части тех преподавателей у которых низкая нагрузка гарантирован один или два выходных (методических дня), которые им будут предоставлены автоматически. Для части преподавателей есть возможность отказаться от работы в первый урок.
Эта задача решается с помощью алгоритма раскраски с ограничениями на цвета, ребер двудольного мультиграфа. С идеей этого алгоритма можно познакомиться по книге[18] или по журнальным статьям[5,2,20,3]. Особенно стоит обратить внимание на работы Магомедова А.М. [13,14,15].
По окончании шестого (последнего) этапа вся сетка расписания оказывается заполненной занятиями без «окон» для всех классов. Построенное расписание представляет из себя четверки - класс, преподаватель, предмет, время. Помещение для проведения занятия пока не назначено.
После получения финального расписания, построенного на шестом этапе алгоритма, для всех запланированных занятий школы (кроме занятий в специальных помещениях), с помощью алгоритма решения задачи о назначении или «вручную» сопоставляются помещения где будут проводиться эти занятия. Для проведения занятий в специальных помещениях, расписание для которых было получено на втором этапе алгоритма, назначаются преподаватели.
Кроме того, на заключительном этапе составления расписания для всей школы, каждый преподаватель, желающий проводить элективные курсы, может решить для себя когда ему будет удобно их проведение. Время для таких кусов было зарезервировано на четвертом этапе алгоритма. И если этот преподаватель сможет набрать себе группу учеников, то он самостоятельно поставит свой элективный курс в расписание, вместе с подобранным им же самим помещением, которое в нужный момент времени не занято проведением других учебных занятий.
Из уже построенного (составленного, рассчитанного, финального) расписания, с помощью выше описанного алгоритма, при желании, легко можно построить расписание преподавателей и расписание кабинетов, что очень часто предусмотрено в программах составления школьных расписаний. Поскольку такие построения являются совершенно банальными, останавливаться на их описании мы не станем.
Общим правилом для всех ранее описанных шагов, является правило - у каждого класса в один день не может быть более одного урока по какому-либо предмету. Кроме того, общим правилом для преподавателей является то, что в любой день каждый преподаватель может проводить занятия по нескольким предметам (естественно в разные моменты времени), в том числе и у одного класса, например, алгебру и геометрию, физику и химию, родной язык и литературу и т.п..
Для большей наглядности всего выше сказанного проиллюстрируем алгоритм с помощью рисунка 2 на котором показаны все его этапы.

Рисунок 2: Блок-схема главной части «Древнеегипетского алгоритма»

6.2  Основные достоинства алгоритма

Скажем здесь буквально два слова о достоинствах выше описанного алгоритма.
В первую очередь к его достоинству стоит отнести то, что с его помощью гарантировано строится школьное расписание в полностью автоматическом режиме без участия человека.
Кроме того, обращение (работа) с программой составления школьного расписания должна становиться предельно простой, за счет того, что вся задача разделяется на шесть главных, с точки зрения пользователя, независимых подзадач. Как показывает практика, простота работы с программой по составлению школьного расписания является, наряду с полностью автоматическим его составлением, критически-важным свойством данного прикладного программного обеспечения.

6.3  Полнота модели учебного процесса

Модель организации учебного процесса, кроме базовых ограничений, предусматривает:
  • расчет расписания для шести дней по шесть уроков в день и для пяти дней по семь уроков в день;
  • ограничение нагрузки для классов разных параллелей в соответствии с санитарными нормами;
  • возможность одному и тому же преподавателю вести разные предметы;
  • запрет на проведения урока по какому-либо предмету более одного раза в день;
  • стопроцентную загрузку специальных помещений (физкультурный зал, каб. информатики, мастерские для уроков труда и т.п.);
  • для совместителей, планирование проведения уроков только в назначенные ими дни;
  • формирование потоков из классов и резервирование времени в сетке расписания для проведения в это время элективных курсов;
  • разделение классов на группы для проведения уроков по иностранному языку и/или других предметов с разделением классов на группы;
  • предоставление преподавателям методических дней при условии их невысокой загруженности.
Здесь мы очень кратко перечислили основные характиристики модели учебного процесса, более детально с этой моделью можно ознакомиться поработав с программой демонстрирующей работу алгоритма.

7  Тестирование алгоритма

Как видно из предыдущего раздела ничего сложного для понимания в работе алгоритма построения школьного расписания нет. Одна за другой решаются, связанные между собой последовательностью (порядком следования), отдельные легко решаемые (не NP-трудные) задачи до тех пор пока все они не будут исчерпаны. Тем не менее с уверенностью утверждать, что каждая из этих задач может быть решена, до проведения тестирования, не имелось никаких оснований. В отсутствие каких-либо теоретических обоснований алгоритма, что характерно для древнего Египта, проверить его работоспособность можно было только экспериментально, тем более, что именно такая задача и была поставлена ученым-археологом, наткнувшимся на древнюю рукопись (папирус) и сделавшим ее перевод.
Вполне естественно то, что первая мысль которая пришла в голову программистам - это создать обычное приложение для операционной системы Windows. Но что такое обычное win-приложение? Будучи активированным (запущенным на выполнение) оно ожидает поступления событий от пользователя, например, ввода исходных данных, нажатия мыши и т.п. А каким образом можно эти исходные данные получить, а позже занести в программу?
Слава Богу, а точнее слава США, в то время (2012 год), мало-мальски уважающая себя школа открыла свой сайт в сети Интернет и первое что появлялось на этом сайте, не считая фотографий с различных праздничных мероприятий, так это учебный план школы. Оставалось только его скопировать и ввести в программу в качестве исходных данных для расчета расписания. Вопрос. Сколько нужно для этого времени? Практика использования ныне предлагаемых рынком программ составления школьного расписания показала, что для ввода учебного плана вместе с формированием таблицы распределения педагогической нагрузки, требуется от 8-ми до 10-ти часов, мягко говоря, кропотливого труда. Предположим, что этот учебный план введен, а таблица распределения педагогической нагрузки сформирована, и о чудо ..., расписание построено. О чем это говорит. Ровным счетом ни о чем. Никакой гарантии того, что следующая задача будет решена - нет. Вот если бы расписание не было построено, то это говорило бы о многом, а именно, о том, что алгоритм не решает поставленной задачи. Другими словами, алгоритм в виде обычного win-приложения, в некотором смысле, практически не поддается тестированию. Как же быть?
Опять же - слава Богу, а точнее слава Microsoft, в современных версиях операционной системы Windows поддерживается так называемый режим консольного приложения. Кстати говоря, для некоторых молодых людей это является полным откровением, им никогда не доводилось видеть черных окошек с бегущими внутри этих окошек строчками текста. Действительно, это стиль больших ЭВМ из далекого прошлого и давно покинувшей сцену - MS-DOS. Многие из пользователей ПК о таких окошках просто не знают или никогда не обращали на них внимания. Для тех кто таких окошек никогда не видел или не обращал на них внимания, представим их вид на рисунке 3.

Рисунок 3: Часть монитора ПК с окошком консольного приложения
Действительно, человеку со стороны, понять, что там внутри происходит не так-то просто. Но у этих окошек есть одно преимущество. Они могут висеть на экране компьютера, производя нужные вычисления, без какого либо участия пользователя и день, и месяц, и ...  не берусь утверждать сколько. Именно это и требовалось для проверки (тщательного тестирования) алгоритма.
Далее ход рассуждений был следующий. Написание генератора исходных данных (грубо говоря, учебного плана типовой школы и таблицы распределения педагогической нагрузки) конечно же займет некоторое время, но зато, будучи один раз написанным такой генератор позволит получить неограниченное количество тестовых заданий для проверки алгоритма. Достаточно будет только лишь после решения очередной задачи передать управление этому генератору для построения нового (следующего) задания. Появится возможность получить статистически достоверные данные о качестве тестируемого алгоритма. Например, 80 процентов задач решено, а 20 нет, или наоборот. Нужно только лишь, число решаемых задач сделать достаточно большим. Именно так и предстояло поступить - консольное приложение, таким виделся выход из создавшейся ситуации.
Как говориться, быстро сказка сказывается, да не быстро дело делается. Придумать генератор исходных данных, адекватно отражающий все практические ситуации, пусть даже и типовой школы, оказалось не таким простым занятием. Но однажды сбылися мечты сумашедшие..., рано или поздно..., сколько веревочка не вейся... Генератор исходных данных закончен, древнеегипетский алгоритм запрограммирован, «все ошибки исправлены»,21 ловушки на ошибки расставлены, проверки результатов вычислений установлены.
Вначале программе предлагалось для составления расписания небольшое количество классов - от 9 до 14 (маленькая школа). Решения выскакивали как из пулемета. При увеличении количества классов - от 15 до 21 (средняя школа) решения выстреливались быстро, но уже не как из пулемета... скорее как из пистолета. Далее. Вот она... большая школа, до четырех классов в параллеле, общее количество классов от 22 до 28. Явно включились тормоза... Процесс стал напоминать ленивую утку переваливающуюся с ноги на ногу. Но одно радовало - строчка: «Количество не решенных задач = » постоянно показывала ноль.
Стало ясно. Для получения статистически достоверных данных, подтверждающих возможность решения любой разумной задачи в полностью автоматическом режиме, одного компьютера не достаточно. Небольшие арифметические расчеты показывали - что бы оперировать числами от шести и более знаков о количестве решенных задач, требуется не менее десятка компьютеров или одного, но 40-ка ядерного, которого на момент тестирования алгоритма в природе не существовало. А для десятка компьютеров (можно прикинуть количество выделяющегося от этих компьютеров тепла и издаваемый постоянный шум от вентиляторов) требуется отдельная комната. Но ничего, нас не остановишь... Десяток не десяток, а семь четырех-ядерных компьютеров, специально для проведения эксперимента, вскоре были введены в эксплуатацию.
В результате по прошествии года «насильственных действий» древнеегипетского алгоритма по отношению к достопочтенной четырех-ядерной семерки, и после десятков миллионов решенных задач, можно с уверенностью утверждать: - «Любая, без исключений, разумная, корректно заданная задача22 по расчету школьного расписания, может быть решена без участия человека в полностью автоматическом режиме». При этом, суммарное время расчета 1000 задач примерно следующее: для группы задач от 9 до 14 классов = 20 минут, для группы задач от 15 до 21 класса = 40 минут, для группы задач от 22 до 28 классов время расчета составляет от 6 до 8 часов, т.е. для этой группы в среднем, примерно, по пол минуты на одну задачу.
Таким образом, более чем годовой эксперимент, по проверке (тестированию) алгоритма составления школьного расписания в полностью автоматическом режиме, без участия человека, за время которого было решено несколько десятков миллионов тестовых заданий, был с успехом завершен. Практически для всех тестовых заданий (исходных данных) было полностью построено расписание, удовлетворяющее всем ограничениям.
К ученому-археологу возник резонный вопрос: - «Почему бы о результатах проведенного эксперимента не сообщить научной общественности путем, например, публикации в каком-нибудь авторитетном научном журнале»? На что он, не без некоторого стыда сообщил, что папирус им был вывезен из Египта контробандным путем и, что имеются основания опасаться в этой связи уголовного преследования.

Рисунок 4: Тюрьма народов ...
На этом и порешили: - «Не буди лихо, пока оно тихо», «Г...но не трогай, оно не воняет» и т.д. Широкая научная общественность осталась в неведении.
После семилетней паузы оставления «Древнеегипетского алгоритма» без движения сотрудники ООО «АФМ-Лаборатория» вспомнили о нем. Осенью 2020 года алгоритм ими был немного «отрихтован», что позволило несколько увеличить его быстродействие (сократить время расчета). Проведено очередное тестирование, не такое масштабное как ранее, но все же несколько миллионов расписаний было построено. Ранее полученный результат был подтвержден.
После завершения такого тестирования алгоритма составления школьного расписания (в 2020 году) встал вопрос: - «И что дальше?».
Прежде всего, бросается в глаза то, что консольное приложение, никого не сможет убедить в том, что действительно решается задача составления школьного расписания... разве что, самого программиста который написал это приложение. Создать черное окошко, с время от времени появляющимися там строчками типа: - «Количество решенных задач = 12547564» подсилу даже плохо успевающему пятикласснику. Таким образом, нормальный человек, просто не поверит такой, с позволения сказать, программе, и правильно сделает. Стало ясно - обойтись без полноценного win-приложения, с тем, что бы каждый желающий смог сформировать в нем исходные данные для своей школы и смог сам убедиться в правильности работы алгоритма, никак не получиться.

8  Тестовое Win-приложение

Сначала не плохо было бы, определится с целями создания такого приложения. По крайней мере, на виду две таких цели. Это - создание полноценного ПО со всеми вытекающими из этого последствиями, и - создание приложения демонстрирующего работу алгоритма, которое хуже или лучше сможет убедить человека в том, что его не обманывают. И ежику понятно, что по трудоемкости эти два проекта просто не сопоставимы. Вполне естественно, что было принято решение пойти по легкому пути.
Хорошо: - «Что требуется от такого win-приложения - демонстрации?». Прежде даже можно поставить другой вопрос: - «Какое оно должно быть?».
Во-первых. Для такой демонстрашки вполне достаточно примитивнейшего интерфейса. Важно лишь то, что бы пользователю были видны те исходные данные которые предлагаются программе для расчета (сгенерированные естественно случайным образом) и результаты этого расчета. По крайней мере, теоретически у пользователя будет возможность проверить соответствие исходных данных и полученного с помощью программы результата. Сложна ли такая проверка?... Ответ однозначный: - «Да уж не проста...». Особенно если знать какое количество ловушек и проверок содержится в консольном приложении для постоянной верификации получаемых результатов, а так же размер кода этих проверок и ловушек. Есть ли другие способы убеждения?... Разве что, передача всем интересующимся... исходных текстов программы. Но вот, например, в Microsoft это не принято23.
Во-вторых. Снимается проблема файла помощи, руководства пользователя, и прочих бантиков и прибамбасов совершенно необходимых для полноценного программного обеспечения.
В-третьих. Помня о том, что распространенной практикой, среди компаний разрабатывающих ПО для составления школьных расписаний, является поставка, в качестве примеров, специально подобранных исходных данных, для введения пользователей в заблуждение, и поэтому пользователям в обязательном порядке должна быть предоставлена возможность формировать свои собственные исходные данные для проверки качества предлагаемого ПО.
Так и сделали. В честь древнеегипетской жрицы Анушер программу, на русский манер, назвали - Аннушка. По заверению ученого-археолога, Анушер - женское имя.
Хоть пользовательский интерфейс и является до предела примитивным, тем не менее рассказать потенциальному пользователю о том какие кнопки, клавиши и их комбинации следует нажимать для работы с программой, совершенно необходимо. Что и будет далее сделано более-менее подробно.
Обычной практикой описания работы с программой является раздел с описанием ее установки на ПК пользователя. Но мы с целью экономии бумаги и времени читателя делать этого не станем, надеясь на то, что пользователь и сам догадается о том, что после скачивания с сайта производителя и запуска установочного файла ему понадобиться только разглядеть кнопку Далее и все время на нее нажимать, пока на рабочем столе не появиться иконка программы, изображенная на рисунке 5.

Рисунок 5: Иконка программы

8.1  Главное окно программы

После того, как программа скачена, установлена и запущена, на экране ПК пользователя должно появиться ее главное окно, изображенное на рисунке 6.

Рисунок 6: Главное окно программы
Для пояснения того, что пользователь видит воспользуемся следующим рисунком 7.

Рисунок 7: Верхняя левая часть главного окна программы
А видит пользователь, ниже заголовка окна - главное меню программы. Поскольку в этом главном меню почти ничего интересного нет, оставим его без комментариев, а интересные пункты этого меню оставим на потом.
Ниже главного меню - панель управления.
Розовая мечта большинства пользователей ПО это то, что бы на экране была видна только одна огромная кнопка. Здесь же мы видим аж целых пять. Назначение первых двух (если считать слева направо) пояснять не станем, а назначение остальных поясним далее по мере необходимости.
Ниже панели управления располагаются четыре вкладки. Нас из этих вкладок будет интересовать только одна - Расписание классов, у которой имеются две кнопки - Найти подстроку и Вывод в файл Excel. Об этих кнопках разговор пойдет позже.
Еще ниже располагается сетка расписания, в одной из ячеек которой виден синий квадратик и, наконец, в самом низу - панель состояния (она видна, если хорошенечко приглядеться, к рисунку 6 и в которой можно разглядеть надпись Последняя показанная форма = 0).
Синий квадратик указывает на ячейку которая является текущей (имеющий фокус ввода). Если пользователь начнет кликать мышкой по сетке расписания или перемещаться по ней с помощью клавиш, то синий квадратик будет следовать за указателем мышки (или в соответствии с назначением клавиш). Другими словами, перемещаться в текущую ячейку сетки расписания.

8.2  Окно Список решаемых задач

Не долго думая жмем на кнопку панели управления - Начать новую задачу. На экране ПК сразу же появиться окно - Список решаемых задач, изображенное на рисунке 8.

Рисунок 8: Окно Список решаемых задач
Прежде всего скажем о том, что в этом окне имеются две кнопки - Продолжить и Закончить. Важно то, что такие кнопки имеются практически во всех окнах которые будут появляться в программе.
Назначение кнопки Продолжить, достаточно понятно. При ее нажатии, если все вводимые данные окна сформированы правильно и при необходимости прошли проверку, то появится очередное (следующее) окно. Назначение кнопки Закончить поясним чуть позже. Теперь что касается вводимых исходных данных имеющихся в данном окне.
Как видно из рисунка 8 в этом окне имеются семь пунктов:
  1. Формирование основных параметров школы;
  2. Формирование санитарных ограничений;
  3. Расписание для специальных помещений;
  4. Расписание для совместителей;
  5. Расписание потоков;
  6. Расписание для классов с разделением на группы;
  7. Финальное расписание.
Каждый из этих пунктов является не чем иным, как отдельной, из последовательно решаемых задач при составлении расписания занятий. При этом первый, второй и последний пункты отмечены галочкой, эти пункты находятся в неактивном состоянии (т.е. пользователю запрещено их редактировать и соответствующие окна обязательно появятся на экране ПК при составлении расписания занятий).
Первый пункт запрещено редактировать поскольку без его наличия задача составления расписания теряет свой смысл. Второй пункт запрещено редактировать поскольку при составлении школьных расписаний необходимость указывать санитарные запрещения возникает практически всегда, а последний пункт запрещено редактировать поскольку хоть какое-то расписание программа должна построить (хоть как-то или чем-то завершить свою работу).
Оставшиеся четыре пункта (задачи) пользователь программы может редактировать. То есть выбрать - будут такие задачи решаться или нет. О самих задачах более подробно будет сказано в следующих разделах.
И наконец, о чем уже наверное читатель и сам догадался, для выбора соответствующей задачи пользователю необходимо кликнуть мышкой по соответствующему пункту, после чего в квадратике этого пункта появиться галочка.
Поскольку нам предстоит познакомиться со всеми окнами программы, предназначенными для формирования исходных данных, будем считать, что в данном окне отмечены галочками (выбраны) все пункты.

8.3  Нулевой этап алгоритма

8.3.1  Окно Базовые параметры школы

Итак, после того как пользователь решил для себя какие задачи ему (программе) предстоит решить и нажал в текущем окне на клавишу Продолжить, появиться новое (следующее по порядку) окно - Базовые параметры школы, изображенное на рисунке 9.

Рисунок 9: Окно Базовые параметры школы
Мы видим, что в этом окне (точно так же, как и во всех последующих) программа уже автоматически подставила на соответствующие места исходные данные, полученные ей случайным образом. Но при этом у пользователя имеется возможность исправить предлагаемые данные.
В частности, можно с помощью клика мышкой поменять вариант сетки расписания - 5 дней в неделю, 7 часов в день, на вариант - 6 дней в неделю, 6 часов в день. Кроме того, можно предлагаемое, в данном случае, программой значение Количество классов равное 19-ти изменить на нужное пользователю. При этом, вводимое значение может находиться в интервале от 12 классов до 28-ми.
После того как изменения будут корректно внесены (или без внесения изменений) пользователь может нажать на кнопку Продолжить. Понятно, что если пользователь попытается игнорировать ограничения по количеству классов, то программа не оставит этого без внимания и аккуратно (можно сказать - тактично и бережно) обругает его с помощью окошка, изображенного на рисунке 10.

Рисунок 10: Окошко Сообщение об ошибке
При вводе значения количества классов важно помнить, что программа, по умолчанию, предназначена для составления расписания занятий одновременно в средней (2-я ступень образования) и старшей (3-я ступень образования) школе, т.е. для классов начиная, с пятого (начало средней школы) и заканчивая одиннадцатым классом (конец старшей школы). Причем одновременно в средней и старшей школе. Таким образом, все параметры расписания школы (преподаватели, учебные предметы и т.д.) будут одновременно рассчитываться как для средней так и для старшей школы. Следовательно, классы начальной школы (с 1-го по 4-й) останутся за пределами внимания программы.

8.3.2  Окошки сообщений об ошибках

Посмотрим еще раз внимательно на рисунки 9 и 10. На рисунке 9 хорошо видно, что пользователь предупрежден о том, что в качестве значения поля Количество классов могут быть числа от 12 до 28. Представленное на рисунке 10 окошко Сообщение об ошибке фактически дублирует уже имеющуюся у пользователя информацию. Таким образом, для такого пользователя рисунок 10 (точнее говоря окошко Сообщение об ошибке) не представляет большого интереса, кроме того, программа должна всегда реагировать на его неправильные действия.
При разработке программы была поставлена следующая задача. Представим себе, что цель пользователя не в том, что бы протестировать алгоритм составления учебного расписания, а в том, что бы «завалить программу» при помощи ввода (формирования) абсурдных исходных данных. Естественной реакцией разработчиков на такое предположение (а это предположение нужно иметь ввиду при разработке любой программы), оказалась задача тщательной проверки вводимых пользователем исходных данных. Как результат, количество окошек с сообщениями об ошибках пользователя перевалило за весьма и весьма внушительное число.
Таким образом, с одной стороны, программа предусматривает обругивание пользователя обильно, часто и смачно, а с другой стороны дисциплинированного и дружески настроенного пользователя конкретный вид такой ругани мало интересует. Более того, есть еще и третья сторона, а именно. Подробное описание всех окошек об ошибках пользователя может удвоить (а то и больше) размер предлагаемого к прочтению текста.
Опираясь на выше представленную логику было принято решение о том, что бы исключить из настоящего описания упоминания о том, что программа может среагировать сообщением об ошибке пользователя при вводе им неверной информации. То есть, само сообщение об ошибке будет являться своего рода руководством пользователя.
Исключения из этого правила будут сделаны только в тех случаях, когда пользователя подобные сообщения могут серьезно озадачить или поставить в тупик.

8.4  Первый этап алгоритма

8.4.1  Окошко Количество параллелей в школе

На первый взгляд очередное появившееся, после нажатия кнопки Продолжить, окошко - Количество параллелей в школе, изображенное на рисунке 11, может показаться лишним и совершенно ненужным.

Рисунок 11: Окошко Количество параллелей в школе
Появление этого окошка объясняется тем, что вводимые в нем данные могут существенно расширить, если можно так выразиться, диапазон применения программы.
По умолчанию программа в поле ввода Самый старший класс школы помещает цифру 11, а в поле ввода Количество параллелей в школе цифру 7. Эти значения ориентированы на «Советскую» (ныне «Российскую») систему среднего образования, используемую в настоящее время, и в некоторых постсоветских странах. Основное отличие «Советской» системы среднего образования, например, от «Европейской» заключается в том, что учащиеся начиная с первого и до самого старшего класса обучаются в одном и том же здании.
В отличии от такого положения дел, почти во всех странах Европы, обучение для каждой ступени среднего образования (1-й, 2-й и 3-й) проводится в отдельных (разных) зданиях. Вопрос о том, хорошо это или плохо здесь не обсуждается. Возможно, что когда-нибудь в «Прекрасной России будущего» вместо танков, пушек, бомб и истребителей, начнут строить просторные школьные здания для детей, и тогда может возникнуть необходимость рассчитывать расписания отдельно для каждой ступени среднего образования, размещающейся в отдельном здании.
Поскольку «глупая программа» не в состоянии сама догадаться какой класс, в таком случае, является самым старшим (тринадцатый или девятый, как, например в Италии) и какое количество параллелей имеется в школе (школьном здании), ее необходимо, что называется, «ткнуть носом» (т.е. указать эти данные в явном виде). Обратим внимание на то, что после изменения значения поля Самый старший класс школы значение верхнего предела для количества параллелей в школе, будет автоматически пересчитываться и программа не позволит пользователю выйти из этого диапазона.
Для пользователя же, должно быть ясным, что программа по умолчанию предполагает - в школе имеются все параллели без пропусков. То есть, случай когда какая-либо из параллелей отсутствует, например, шестые или девятые классы, исключен из рассмотрения. Чисто теоретически, указанное ограничение несколько снижает область применения программы, но практически, случай с отсутствием параллели вряд ли может встретиться в жизни (в практике использования данной программы). При этом пользователь может легко исправить данное ограничение в «ручном» режиме путем несложных манипуляций с автоматически полученными данными.

8.4.2  Окно Список классов с параллелями

Следующее окно, изображенное на рисунке 12, как обычно уже заполнено некими автоматически созданными данными.

Рисунок 12: Окно Список классов с параллелями
Эти данные как обычно24 можно исправить пользователю в соответствии с решаемой им задачей.
При исправлении пользователь должен руководствоваться тремя правилами:
  1. Название класса представляет из себя обычный текст, длинна которого не может превышать 7-ми символов;
  2. У самых старших классов номер параллели должен быть равен 1, у самых младших, должен быть равен количеству параллелей в школе;
  3. Номера стоящие в верхних ячейках, не могу быть больше номеров, стоящих в нижних ячейках. То есть, в нижней ячейке номер может быть либо больше, либо таким же (программа за выполнением этого правила следит).

8.4.3  Окно Учебная нагрузка параллелей

Для следующего окна, изображенного на рисунке 13, программа предлагает не случайно полученные данные, а нагрузку параллелей, предусмотренную санитарными нормами.

Рисунок 13: Окно Учебная нагрузка параллелей
Поскольку, как уже не раз отмечалось, программа довольно «глупа» и не в состоянии читать мысли пользователя, ему предоставляется возможность данные о нагрузке параллелей скорректировать в соответствии с санитарными нормами для соответствующих возрастных параллелей или в соответствии со здравым смыслом.
Редактирование значений нагрузок осуществляется стандартным способом, но в рамках неприятной (можно сказать противной) надписи - Нагрузка параллелей должна быть от: 29 до: 35, а нагрузка всей школы не менее: 582. При этом возникает два вопроса:
  1. Откуда взялись эти цифры?
  2. Зачем нужны такие ограничения?
Ответ на первый вопрос достаточно прост. Цифра 29, это константа принятая из тех соображений, что о здоровье младших школьников государство серьезно задумывается. Цифра 35 равна часовой продолжительности учебной недели (в случае сетки расписания 6 на 6 эта цифра примет значение равное 36-ти). Цифра 582, не что иное, как результат некоего бесхитростного вычисления, которая будет каждый раз меняться в зависимости от значений величины нагрузки параллелей, их количества и количества классов в школе.
Теперь, зачем нужны такие ограничения. Как высказался один из программистов ООО «АФМ-Лаборатория»: - «Что бы жизнь медом не казалась». Ну, а если серьезно, то такие ограничения вызваны некими соображениями по поводу дальнейшего существования решения предстоящих задач. Об этих соображениях мы здесь, голословно и бездоказательно рассуждать не станем.

8.4.4  Окошко Формирование санитарных ограничений для классов

Появление следующего окошка, изображенного на рисунке 14, информирует пользователя о том, что уже можно решать задачку Формирование санитарных ограничений для классов и предлагает ему воспользоваться кнопкой Сформировать.

Рисунок 14: Окошко Формирование санитарных ограничений для классов
Если пользователь нажмет кнопку Сформировать, то окошко моментально изменит свой вид, на представленный рисунком 15, а кнопка Сформировать превратиться в кнопку Продолжить.

Рисунок 15: Окошко После решения задачки
Но это еще не все изменения. Внимательный пользователь заметит, что некоторые ячейки сетки расписания окрасились красным цветом. Проницательный же пользователь сообразит, что красным цветом окрашены те ячейки, в которых не могут быть помещены данные о проводимых занятиях в связи с ограничениями, накладываемыми санитарными правилами, нормами или здравым смыслом.
Теперь настало время объяснить назначение кнопки окошка Закончить и кнопки панели управления Продолжить начатую задачу.

8.5  Кнопки Закончить и Продолжить начатую задачу

Вполне допустима мысль о том, что прежде чем перейти к следующему окну для формирования очередной порции исходных данных, пользователю захочется более внимательно ознакомиться с уже полученными (промежуточными) результатами, решаемой общей задачи. И такую возможность программа конечно же должна ему предоставить. Кроме того не исключен случай перерыва на обед или прекращения работы пользователем до следующего дня (следующего раза).
При таких обстоятельствах у пользователя, при работе с любым окном программы, есть право и возможность нажать на кнопку Закончить, находящуюся рядом с кнопкой Продолжить. После такого нажатия соответствующее окно исчезнет, а пользователь может либо нажать на кнопку панели управления Выход, либо покрутить сетку расписания вверх и вниз внимательно вглядываясь на полученный результат.
Рисунок 16 представляет сетку расписания для шестых и седьмых классов в которой часть ячеек окрашена красным цветом.

Рисунок 16: Часть сетки расписания для шестых и седьмых классов
Если пользователь выйдет из программы и далее после некоторого перерыва, например, на следующий день, снова ее запустит, то сетка расписания окажется в том состоянии при котором работа последнего сеанса была прекращена.
Как уже читатель наверное догадался, для продолжения решения задачи составления расписания занятий, пользователю следует нажать на кнопку панели управления Продолжить начатую задачу. После такого нажатия появится окно, являющееся очередным окном для ввода исходных данных. Естественно, что если пользователь не собирается покидать программу и нажмет на кнопку Продолжить начатую задачу после ознакомления с сеткой расписания, результат будет точно таким же.

8.6  Второй этап алгоритма

8.6.1  Окно Список специальных помещений

Итак, лихо расправившись с двумя разделами списка решаемых задач, а именно:
  1. Формирование основных параметров школы;
  2. Формирование санитарных ограничений;
пользователь может приступать к третьему разделу тщательно тестируемого алгоритма - Расписание для специальных помещений. Разумеется если в свое время, в окне Список решаемых задач, напротив этого раздела им была поставлена галочка.
Данный раздел начинается с окна Список специальных помещений, которое изображено на рисунке 17.

Рисунок 17: Окно Список специальных помещений
Как не трудно догадаться из рисунка 17, количество специальных помещений ограничено интервалом от 1 до 3. При этом, во время редактирования данных пользователь должен помнить о том, что длинна названий помещений и предметов не может превышать значения в 15 символов.
Еще раз напомним, что специальными помещениями в рамках терминологии принятой в программе, являются помещения оснащенные специальным оборудованием и которых не хватает для нормального ведения учебного процесса, а поэтому их заполненность должна приближаться к 100%. Кроме тог, следует иметь ввиду, что специальное помещение может быть логическим понятием, включающим в себя, два физических помещения. Например, «Первый компьютерный класс» и «Второй компьютерный класс».

8.6.2  Окно Распределение нагрузки классов в специальных
помещениях

Очередное окно предназначенное для распределения нагрузки классов среди специальных помещений представлено на рисунке 18.

Рисунок 18: Окно Распределение нагрузки классов в специальных помещениях
В процессе редактирования таблицы, представленной на рисунке 18, ее ячейки могут быть окрашены тремя цветами - красным, желтым или зеленым, что можно видеть на рисунке 19.

Рисунок 19: Таблица с окрашенными ячейками в два цвета
Окраска ячеек красным цветом означает, что нагрузка помещения превышает свой предел, окраска желтым цветом означает, что нагрузка помещения достигла своего предела и не может быть увеличена. Зеленый цвет означает, что в некоторых ячейках еще можно, имеющиеся значения увеличить. При этом общая величина нагрузки помещения по мере редактирования таблицы постоянно отражается в столбце Нагрузка.
Максимальное значение нагрузки для отдельного класса в специальном помещении для сетки расписания - 5 дней в неделю, 7 часов в день, не может превышать значения равного четырем, и значения равного пяти для расписания - 6 дней в неделю, 6 часов в день. Естественно, что при наличии строк таблицы окрашенных красным цветом, после нажатия кнопки Продолжить программа вернет пользователя к дальнейшему редактированию таблицы до тех пор пока не останется ни одной строки красного цвета.
Если пользователю не нравиться исправлять заранее помещенные в таблицу данные, то он может нажать на кнопку Очистить, и начать формирование таблицы, что называется «с чистого листа».
Такой вариант развития событий иллюстрируется рисунком 20.

Рисунок 20: Таблица нагрузок классов очищенная от данных
Обратим внимание читателя на то, что если какое-либо значение в столбце с заголовком Нагрузка окажется нулевым, то программа в этом случае вернет пользователя для дальнейшего редактирования таблицы нагрузок классов. Это продиктовано тем, что решение задачи с такими исходными данными представляется совершенно бессмысленным.

8.6.3  Окошко Расчет расписания для специальных помещений

Завершающим окошком, при решении задачи построения расписания для специальных помещений, является окошко, изображенное на рисунке 21.

Рисунок 21: Окошко Расчет расписания для специальных помещений
После нажатия на кнопку Рассчитать она превратиться в кнопку Продолжить, а вместо надписи, информирующей о том, что все готово для расчета, появиться улыбающаяся рожица. Хотя, чему тут радоваться - решенная задача весьма банальна.
Окошко с радующейся рожицей изображено на рисунке 22.

Рисунок 22: Окошко после окончания расчета
Заметим, что в сетке расписания появились ячейки окрашенные салатовым цветом в которых через запятую указаны название предмета и название специального помещения.
Как обычно, пользователь может либо продолжить ввод исходных данных, либо прервать данное занятие до следующего раза, нажав на кнопку Закончить.

8.7  Третий этап алгоритма

8.7.1  Окно Формирование списка совместителей и их нагрузок

Следующий раздел программы - Расписание для совместителей, как уже наверное догадался читатель, открывается окном, изображенном на рисунке 23.

Рисунок 23: Окно Формирование списка совместителей и их нагрузок
Как видно из этого рисунка количество совместителей можно выбрать из интервала от 1 до 8. Следует отметить, что максимальное количество совместителей, которое может ввести пользователь, зависит от количества классов для которых составляется расписание занятий. Так число 8 появилось в данном окне из расчета, что количество классов в школе равно 28-ми. При количестве классов в школе равным 12-ти, максимальное количество совместителей уменьшиться до числа 3.
Как ранее было сказано, совместители отличаются от штатных преподавателей, в рамках терминологии описываемой программы тем, что им позволено в ультимативной форме требовать для себя назначение занятий в указанные ими дни. А это означает, что с увеличением количества совместителей стремительно увеличивается вероятность того, что искомого расписания занятий для всей школы не существует. Таким образом, авторы программы настоятельно рекомендуют пользователям не злоупотреблять этим видом расчета для «своих в доску» штатных преподавателей.
Исключение может быть сделано только, например, для директора школы которому не хватает директорской зарплаты и он вынужден вести занятия в классах, но по некоторым дням он в школе гарантированно отсутствует, или для завуча, который то же, в некоторые дни гарантированно отсутствует в школе.
Окончательная рекомендация здесь будет такая - если есть возможность избежать составления расписания для совместителей, то обязательно это сделайте.
Наконец отметим, что для тех кто не любит что-то исправлять, а предпочитает в начале работы иметь «чистый лист», существует кнопка Очистить. Изображение окна после нажатия этой кнопки мы здесь не приводим в виду его банальности.
И последнее, ФИО совместителя не может превышать 23-х символов, название предмета 20-ти, максимальная нагрузка совместителя во все рабочие дни, которых максимум 2, не может превышать 8-ми часов, максимальная нагрузка в отдельный день 4-х часов.

8.7.2  Окно Формирование таблицы рабочих дней совместителей

Следующим окном, в случае составления расписания для совместителей, будет окно, изображенное на рисунке 24.

Рисунок 24: Окно Формирование таблицы рабочих дней совместителей
Как видно из рисунка 24 в таблице рабочих дней присутствуют три цвета - розовый, светло-зеленый и синий. Ячейка окрашенная в розовый цвет означает то, что в этот день у этого совместителя - день не рабочий. Ячейка окрашенная в светло-зеленый цвет означает то, что в этот день у этого совместителя - день рабочий. Синий квадратик в правой части ячейки означает то, что эта ячейка является текущей (имеет фокус ввода).
Столбец с заголовком - Дней, автоматически формируется программой исходя из данных, внесенных пользователем в предыдущем окне (см. рис. 23).
Редактирование таблицы рабочих дней совместителей пожалуй следует (можно) начать с нажатия кнопки Очистить. Для перекраски розовой ячейки в светло-зеленую нужно по этой ячейке произвести двойной клик мышкой или после выделения нужной ячейки с помощью нажатия соответствующих клавиш нажать клавишу Enter.
На экране ПК появится окошко с вопросом, изображенное на рисунке 25.

Рисунок 25: Окошко с вопросом
После нажатия на кнопку Да окошко исчезнет, а ячейка окажется перекрашенной. Должно быть ясно, что для совершения обратного действия, т.е. перекраски ячейки из светло-зеленого цвета в розовый нужно нажать на кнопку Нет. При этом, если у некоторого совместителя количество окрашенных в светло-зеленый цвет ячеек может оказаться больше чем показано цифрой, имеющейся в столбце с заголовком - Дней, то программа не позволит пользователю осуществить такое действие.
Вот в общем-то и все, что касается этого окна. Можно переходить к описанию следующего по очереди.

8.7.3  Окно Формирование запретов на первый урок для
совместителей

Редактирование окна, изображенного на рисунке 26, практически ничем не отличается от редактирования предыдущего (см. рис. 24).

Рисунок 26: Окно Формирование запретов на первый урок для совместителей
Смысл цветов тот же. Действия для изменения цветов те же.
Единственно о чем стоит упомянуть это то, что количество совместителей получивших возможность не приходить в школу к первому уроку не может превышать двух. И еще раз напомним, что любое увеличение ограничений, в том числе и это, увеличивает вероятность столкновения с ситуацией, когда решения задачи составления расписания занятий не существует. Так-что не стоит «своим в доску совместителям» без крайней необходимости предоставлять возможность, устанавливаемую с помощью данного окна.

8.7.4  Окно Формирование таблицы распределения педагогической
нагрузки совместителей

Следующее окно, которое должно появиться на экране ПК пользователя, и изображено на рисунке 27, имеет довольно страшненький, если не сказать устрашающий вид.

Рисунок 27: Окно Формирование таблицы распределения педагогической нагрузки
Но на самом деле не все так страшно. Начнем понемногу разбираться.
Самая первая (левая) колонка представляет из себя номера строк таблицы. Далее в следующей колонке идут названия классов, о чем свидетельствует заголовок этой колонки - Класс.
Далее идут колонки количество которых совпадает с количеством совместителей. То есть, эти колонки относя к совместителям. Каждая из таких колонок имеет два заголовка. Один заголовок располагается в первой строке таблицы, другой во второй.
Верхний заголовок состоит из трех частей, при этом вторая и третья часть отделены друг от друга запятыми. Перечислим эти части:
  1. Число, заключенное в квадратные скобки;
  2. ФИО совместителя;
  3. Название предмета которому будет учить преподаватель (совместитель).
Число заключенное в квадратные скобки не что иное как - Нагрузка всего, взятая из окна Формирование списка совместителей и их нагрузок (см. рис. 23).
Что такое ФИО совместителя и Название предмета пояснять не станем.
Прежде чем объяснить что такое Введенная нагрузка, представляющая из себя нижний (второй) заголовок колонки, разберемся с цветами в которые окрашена таблица.
В этой таблице имеются четыре цвета - синий, светло-синий, розовый и светло-зеленый. Синим цветом окрашена текущая ячейка (имеющая фокус ввода), которую пользователь может редактировать. Светло-синим цветом выделена текущая строка таблицы и текущая колонка таблицы, сделано это для удобства ориентации пользователя в таблице. Розовым цветом окрашены ячейки в которых отсутствует величина (значение) нагрузки совместителя в некотором классе, а светло-зеленым цветом - ячейки в которых это значение имеется (не нулевое).
Общая рекомендация по редактированию данной таблицы следующая. Для начала пользователь может покликать по таблице мышкой или постучать клавишами со стрелками с целью понять - как должна выглядеть таблица после окончания ее редактирования. После чего можно нажать на кнопку Очистить. Мало того, что в таблице исчезнут ячейки окрашенные светло-зеленым цветом, но и еще изменятся все заголовки таблицы, расположенные в ее второй строке. Для наглядности продемонстрируем состояние этих заголовков рисунком 28.

Рисунок 28: Часть окна Формирование таблицы распределения нагрузки
Из рисунка видно, что все значения заголовка Введенная нагрузка оказались нулевыми. Проницательный читатель уже наверное смекнул, что далее придется редактировать таблицу. Делать это можно стандартным способом, принятым в программе - двойной клик мышкой по нужной ячейке или после наведения с помощью клавиш со стрелками синего указателя на нужную ячейку - нажатие клавиши Enter.
В результате указанных действий на экране ПК должно появиться небольшое окошко Ввод нагрузки совместителя, изображенное на рисунке 29.

Рисунок 29: Окошко Ввод нагрузки совместителя
Из этого рисунка видно, что ячейка готова принять число (значение) от нуля до двух. Значение ноль предусмотрено на тот случай если пользователю будет необходимо изменить ранее введенное ненулевое значение на нулевое, т.е. для некоторого класса отобрать нагрузку у некоторого совместителя.
После ввода в ячейку нагрузки, величина Введенная нагрузка (т.е. заголовок колонки) изменится на введенную нагрузку.
Задача пользователя будет заключается в добавлении (редактировании) нагрузок до тех пор пока каждое число в каждом заголовке колонки - Введенная нагрузка, не окажется равным каждому числу, заключенному в квадратные скобки, в каждом заголовке первой строки таблицы.
Достигнув желаемого можно будет нажать на кнопку Продолжить для перехода к следующему окну. Заметим, что народная мудрость: - «Как получилось, так и хотели», программой принята не будет.

8.7.5  Окошко Построение расписания для совместителей

Завершающим окошком при решении задачи Расписание для совместителей будет стандартное окошко, сначала с надписью о готовности всех исходных данных для решения задачи, а потом с улыбающейся рожицей. Поскольку изображения таких окошек мы уже приводили, повторяться не будем, а перейдем к окнам появляющимися при решении следующей задачи - Расписание потоков. Отметим только лишь, что в сетке расписания появятся ячейки окрашенные сиреневым цветом, изображенные на рисунке 30, в которых будут отражены - фамилии совместителей и их предметы.

Рисунок 30: Появление ячеек окрашенных сиреневым цветом

8.8  Четвертый этап алгоритма

8.8.1  Окошко Количество потоков и старших параллелей
объединяемых в потоки

Прежде чем нажать на кнопку Продолжить, появившегося окошка Количество потоков и старших параллелей объединяемых в потоки, изображенного на рисунке 31, пользователю программы стоило бы хорошенечко подумать.

Рисунок 31: Окошко Количество потоков и старших параллелей объединяемых в потоки
Для того, что бы выбор вводимых данных был пользователем вполне осмысленным следует пояснить - что именно, в терминах программы, подразумевается под распространенным словом - поток.
В программа «АФМ: Аннушка» под термином поток подразумевается множество учащихся состоящее из одного или двух классов, как правило (желательно) из одной параллели. Целью формирования потока (множества учащихся) является разделение потока на отдельные группы учащихся по интересам и проведение для этих групп занятий по элективным курсам. Для осуществления этой цели для каждого потока резервируется время в сетке расписания занятий всей школы.
По умолчанию, при формирование потоков программа руководствуется следующими правилами:
  • Потоки формируются из учащихся старших параллелей;
  • Количество старших параллелей из которых формируются потоки определяется пользователем;
  • Потоки формируются из всех классов без исключения, входящих в старшие параллели, количество которых задано пользователем;
  • Любой класс может входить в потоки только один раз.
Таким образом, если пользователь в поле ввода - Количество старших параллелей введет цифру 1, то потоки будут формироваться только из всех одиннадцатых (самых старших) классов. Если будет введена цифра 2, то из всех одиннадцатых и десятых классов, если цифра 3, то из всех одиннадцатых, десятых и девятых классов. При вводе конкретного значения в это поле пользователь должен руководствоваться указанным интервалом - от 1 до 3.
Следующее поле - Количество потоков, ограничено интервалом - от Минимума до Максимума. Другими словами программа не позволит пользователю ввести число большее максимума и меньшее минимума.
Возникает вопрос - откуда берутся эти числа?
Максимум равен количеству классов, входящих в старшие параллели. В данном примере это 12 классов. Если пользователь задаст именно это число потоков, то в каждый поток будут входить только по одному классу.
Если пользователь введет число потоков соответствующее минимуму, то в каждый поток будет входить по два класса, при четном количестве классов и по два класса кроме последнего потока, при нечетном количестве классов. Понятно, что последний поток в этом случае, будет состоять только из одного класса.
После того, как пользователь определился с количеством параллелей и количеством потоков он может нажимать кнопку Продолжить.

8.8.2  Окно Формирование потоков

После того, как пользователь нажмет на кнопку Продолжить появиться окно Формирование потоков, изображенное на рисунке 32.

Рисунок 32: Окно Формирование потоков
По мнению разработчиков программы, правила формирования потоков, принятые в этой программе по умолчанию достаточно разумны. Однако, не предоставить пользователю возможности руководствоваться своими правилами, было бы весьма опрометчиво.
На этот случай в окне Формирование потоков имеется кнопка Очистить. После ее нажатия окно будет иметь вид, изображенный на рисунке 33.

Рисунок 33: Окно Формирование потоков после его очистки
Проницательный читатель уже наверное сообразил, что пользователю можно редактировать не только названия потоков, но и классы, входящие в эти потоки. Строго говоря, такое редактирование можно было бы проводить и без очищения окна (таблицы формирования потоков), но как показалось разработчикам программы кнопка Очистить может придать процессу редактирования особый шарм.
На редактировании названий потоков особо останавливаться не будем - все как обычно, подводим курсор к нужной ячейке, давим на клавиши. Поясним подробно процесс редактирование классов, входящих в потоки.
Предположим, что мы находимся не в самом начале процесса редактирования, а где-то в середине этого процесса. Окно Формирование потоков будет выглядеть так, как изображено на рисунке 34.

Рисунок 34: Окно Формирование потоков при редактировании
Из этого рисунка видно, что часть классов уже помещено в таблицу формирования потоков, а текущей ячейкой, которая окрашена в светло-голубой цвет, является ячейка в которую пользователь только собрался поместить очередной класс. Для этого он должен либо сделать двойной клик мышкой по этой ячейке либо нажать клавишу Enter. После одного из таких действий на экране ПК появиться дополнительное окошко Выбор класса, изображенное на рисунке 35.

Рисунок 35: Окошко Выбор класса
В этом окошке имеются три колонки. Центральная колонка состоит из старших классов, которые можно включать в потоки. Самая правая колонка уточняет - к какой параллели относится тот или иной класс. А первая (левая) колонка состоит из отметок, показывающих, включен уже класс в потоки или нет. Как не трудно догадаться, отметка [Включен] свидетельствует о том, что этот класс уже включен в какой-то поток и этот класс повторно включить, в тот же или какой-то другой поток, не получиться. Отметка же [       ], состоящая из квадратных скобок внутри которых ничего нет, свидетельствует об обратном.
Для помещения класса в выбранную ячейку таблицы формирования потоков нужно в окошке Выбор класса подвести курсор (голубую полоску) к нужному классу и совершить стандартное для программы действие - двойной клик мышкой, нажатие клавиши Enter или нажатие кнопки Выбрать. После чего окошко исчезнет, а в выделенной ячейке Таблицы формирования потоков появиться название выбранного класса. Для помещения следующего класса в следующую ячейку действия должны повториться.
Отметим, что если пользователю захочется очистить какую-либо ячейку от названия класса, ему нужно будет навести курсор на эту ячейку и в окошке Выбор класса выбрать первую (самую верхнюю) строку списка - ***** УДАЛИТЬ КЛАСС ИЗ ЯЧЕЙКИ *****. Кроме того, уже имеющиеся в ячейках таблицы классы (уже выбранные классы), можно еще и заменять. Попробуйте это сделать без объяснения «могучей техники процесса».
После того, как пользователь закончит редактирование таблицы формирования потоков и нажмет кнопку Продолжить некоторые классы, присутствующие в окошке Выбор класса могут остаться не выбранными, а некоторые потоки остаться без выбранных для них классов. Поскольку «бестолковая программа» самостоятельно не может определить - забыл ли пользователь выбрать некоторый класс или делает это совершенно сознательно, программа попросит его уточнить данное обстоятельство с помощью вопроса (окошка вопрос), представленного на рисунке 36.

Рисунок 36: Окошко Вопрос
Если пользователь нажмет кнопку Нет, то программа перейдет к следующему окну для формирования исходных данных. При этом, если какой-либо поток остался без выбранного класса, то количество потоков будет программой автоматически скорректировано (уменьшено). Если какой-либо класс остался не выбранным, то в расписании для этого класса не будет зарезервировано времени на проведение элективных курсов.

8.8.3  Окно Формирование нагрузок потоков

После того как пользователь все же «разберется» с «бестолковой программой» на экране ПК появиться очередное окно Формирование нагрузок потоков (см. рис. 37).

Рисунок 37: Окно Формирование нагрузок потоков
Действия пользователя при редактировании этого окна (таблицы нагрузок потоков) настолько банальны, что описывать здесь мы их не станем, отметим лишь, что цифра 0 и цифры больше 3-х не пройдут, поскольку цифра 0 - бессмысленна, а цифра 3 является максимальной нагрузкой для любого потока.

8.8.4  Окошко Построение расписания для потоков

Как всегда завершающим штрихом решения задачи, в данном случае задачи Расписание потоков, будет являться окошко Построение расписания для потоков, которое мы здесь как и в прошлый раз приводить не станем, поскольку сообщения о готовности решить задачу и улыбающиеся рожицы могут сильно утомить читателя. Однако отметим, что появившиеся ячейки в сетке расписания, относящиеся к потокам, будут окрашены цветом, напоминающим нечто среднее между серым и голубым (см. рис. 38).

Рисунок 38: Окраска потоковых ячеек серо-голубым цветом

8.9  Пятый этап алгоритма

8.9.1  Окно Формирование учебного плана для предметов
с разделением на группы

В отличии от предыдущей задачи - Расписание потоков для планирования и проведения элективных курсов, которая в Российской Федерации является «далекой экзотикой» и чем-то малознакомым, задача - Расписание для классов с разделением на группы, является повсеместно решаемой, и задачей весьма почтенного возраста. Как правило, в средней и старшей школе, в первую очередь, классы делятся на группы при изучении иностранного языка, что обусловлено спецификой этого предмета.
Обратим внимание на то, что не следует путать обучение по предметам с разделением на группы, например, такого предмета как «Труд», с рассматриваемой далее задачей. При обучении предмету «Труд», класс тоже может разделяться на две группы - мальчики и девочки. Мальчики идут в мастерскую и обучаются работе на токарных, фрезерных и сверлильных станках, а девочки идут в другое оборудованное помещение, обучаться работе на швейных машинках. Но расписание для такой задачи не что иное, как задача - Расписание для специальных помещений. Просто логическое специальное помещение эквивалентно, двум физическим специальным помещениям - слесарная мастерская и швейная мастерская.
Назовем основные параметры задачи, которую нам предстоит рассмотреть.
  • Количество предметов, при изучении которых в школе, классы могут быть разделены на группы, лежит в интервале от одного до трех;
  • Максимальная недельная нагрузка для такого предмета в отдельном классе равна трем часам;
  • Минимальная недельная нагрузка по предмету для классов всей школы, принята равной количеству классов в школе для которых составляется расписание (средняя и старшая школа).
Теперь можно представить очередное окно, подлежащее осмыслению (см. рис. 39).

Рисунок 39: Окно Формирование учебного плана для предметов с разделением
Как обычно таблица, имеющаяся в этом окне, уже заполнена случайно сформированными данными. Пользователь, после того как определиться с количеством предметов, может либо начать исправлять эти данные, либо нажать на кнопку Очистить и преступить к самостоятельному заполнению таблицы, не забывая о том, что максимальная длинна названия предмета составляет 20 символов, а максимальная нагрузка класса не должна превышать 3-х часов.
Отсутствие значения нагрузки в соответствующей ячейке или нагрузка равная нулю означает то, что в данном классе данный предмет не преподается (не изучается).
Контроль (проверка) правильности заполнения таблицы будет осуществятся программой после нажатия кнопки Продолжить. В случае выявления ошибок заполнения таблицы, программа не позволит пользователю перейти к следующему окну, возвращая его снова и снова к редактируемой таблице, до тех пор пока не сочтет ее правильно заполненной. Думается, что представленное окно, в отличии от следующего не должно доставить пользователю особых хлопот.

8.9.2  Окно Расчет количества преподавателей для предметов
с разделением на группы

Окно которое может доставить неприятности пользователю представлено на рисунке 40.

Рисунок 40: Окно Расчет количества преподавателей для предметов с разделением
Спрашивается - каким образом производится расчет количества преподавателей? Очень просто. Общая учебная нагрузка школы по некоторому предмету делиться на норму нагрузки отдельного преподавателя, которая составляет 18 часов в неделю. Именно эта вычисленная и округленная до целого числа цифра заноситься в крайний правый столбец таблицы.
Пользователь, вычисленное значение, может корректировать, но в пределах от некоторого, вычисленного Минимума до некоторого Максимума. Понятно, что чем больше преподавателей получат нагрузку, тем меньшая недельная нагрузка окажется у каждого из них для начисления заработной платы.
Максимум вычисляется достаточно просто - это удвоенное значение Минимума. А вот с Минимумом не так все просто, как хотелось бы. Понятно, что чем меньше преподавателей, тем больше их недельная нагрузка и тем выше заработная плата (тем хуже преподаватели учат своему предмету). Разработчики программы, пребывая в полной уверенности в том, что найдется огромное количество пользователей которые при редактировании таблицы будут сокращать количество преподавателей до тех пор пока их недельная нагрузка не достигнет значения в 39 часов, решили ограничить значение количества преподавателей значением - Минимум. При этом величина минимума не столько вычисляется, сколько подбиралась разработчиками.
Возникает резонный вопрос - а, что если нет такого количества преподавателей, которое определено минимумом. Ответом на него может быть пословица: - «По одежки протягивай ножки». Значит придется корректировать учебный план или составлять расписание вручную.
Буем предполагать и надеяться, что пользователю все же удастся втиснуться в предлагаемый интервал значений, а нажатие на кнопку Продолжить приведет к появлению следующего окна.

8.9.3  Окно Список преподавателей и запретов на первый урок

С появившимся окном, изображенном на рисунке 41, все просто.

Рисунок 41: Окно Список преподавателей и запретов на первый урок
Пользователю предстоит только отредактировать колонку ФИО преподавателя и далее в крайнем правом столбце, имеющим заголовок Запрет, с помощью стандартных приемчиков (двойной клик мышкой по нужной ячейке или с помощью клавиши Enter) определиться с тем, кому будет позволено не приходить в школу к первому уроку. Правда, в случае небольшого количества преподавателей, таких может оказаться не больше одного. Окошко с вопросом - есть ли у преподавателя запрет на первый урок или нет, мы здесь не приводим по причине его банальности. И наконец напомним, что длинна ФИО преподавателя не может превышать 23-х символов.
Кроме того, еще раз напомним золотое правило разработчика школьных расписаний - если есть возможность избежать каких-либо ограничений, в данном случае предоставление преподавателю права не приходить к первому уроку, непременно воспользуйтесь такой возможностью.

8.9.4  Окно Распределение педагогической нагрузки в классах
с разделением на группы

Следующее окно, изображенное на рисунке 42 представляет из себя автоматически полученное распределение педагогической нагрузки для преподавателей по предметам с разделением на две группы.

Рисунок 42: Окно Распределение педагогической нагрузки в классах
Пользователь программы может либо приступить к исправлению распределения, полученного автоматически, либо нажать на кнопку Очистить для того, что бы выполнить такое распределение полностью «вручную» с «чистого листа». Разумеется, ничто не может ему помешать нажать на кнопку Продолжить для перехода к следующему, заключительному (при решении задачи Расписание для классов с разделением на группы) окошку.
Остается пояснить - как осуществляется такое редактирование?
Прежде всего нужно сказать о том, что каждая строчка таблицы соответствует нагрузке какого-либо класса, которая была запланирована три шага (три окна) назад (см. рис. 39), и эта нагрузка должна быть подкреплена двумя преподавателями.
Ячейка окрашенная в грязно-желтый цвет является текущей (имеющий фокус ввода), которую можно редактировать. Перемещать фокус ввода ячейки, как обычно можно с помощью мышки и клавиш со стрелками. Ячейки окрашенные зеленым цветом свидетельствуют о том, что нагрузка преподавателя не превышает предельного значения равного 24-м часам в неделю. Если вдруг, при автоматическом распределении нагрузки, значение нагрузки преподавателя превысит максимум (24 часа), то ячейка окажется окрашенный красным цветом.
При нажатии на кнопку Очистить все ячейки окажутся окрашенными розовым цветом (см. рис. 43), что означает - ячейки ждут назначения своих преподавателей.

Рисунок 43: Ячейки окрашенные розовым цветом
Теперь собственно о редактировании (назначение преподавателей). Проницательный читатель уже наверное догадался о том, что для вызова окошка со списком преподавателей нужно прибегнуть к стандартным приемчикам (перемещение курсора к нужной ячейке, двойной клик мышкой или нажатие на клавишу Enter).
Появившееся справа от таблицы, после осуществления такого действия, окошко Выбор преподавателя, изображено на рисунке 44.

Рисунок 44: Окошко Выбор преподавателя
Как видно из этого рисунка окошко Выбор преподавателя состоит из двух колонок. Первая - число в квадратных скобках, ни что иное, как недельная нагрузка преподавателя, а вторая - ФИО преподавателя. Выбор осуществляется с помощью стандартных приемчиков, которые не станем повторять. Если редактируемая ячейка не содержала никакого значения, то в ней появится выбранное из списка значение (ФИО Преподавателя), если ячейка содержала какое-то значение (ФИО Преподавателя), то это значение будет заменено выбранным. Естественно предположить, что после каждого такого акта выбора, вся колонка с недельной нагрузкой преподавателей будет пересчитываться.
Поскольку нагрузок для классов обычно бывает значительное количество, процесс редактирования таблицы распределения педагогической нагрузки может весьма затянуться. Стоит ли принять распределение нагрузки которое предлагает программа или начать такое распределение редактировать, учитывая «человеческий фактор», решать пользователю.

8.9.5  Окошко Построение расписания для классов с разделением
на группы

Для некоторых предыдущих задач мы не стали приводить изображения окошек информирующих о том, что все данные сформированы для начала решения задачи и последующего сообщения - Готово..., украшенное веселой рожицей.
На этот раз мы такое изображение приведем (см. рис. 45).

Рисунок 45: Окошко Построение расписания для классов с разделением
Связано это с тем, что окошко имеет не две, а три кнопки. Кроме кнопок Рассчитать и Закончить имеется еще одна кнопка - Остановить расчет. При появлении на экране ПК данного окошка, кнопка Остановить расчет находится в неактивном состоянии (нажимать на нее бесполезно). Активной она станет только после того, как пользователь нажмет кнопку Рассчитать.
При тестировании программы среди миллионов заданий были редкие случаи когда процесс расчета расписания, хоть и ненадолго, но все же затягивался. Именно для такого случая и для нетерпеливого пользователя предназначена эта кнопка. Если процесс расчета не будет завершен за доли секунды и в описываемом окошке появиться вместо улыбающейся рожицы, надпись Идет расчет... и крутящееся колесико, а пользователь не пожелает ждать окончания расчета, ему можно будет нажать на кнопку Остановить расчет и расчет будет остановлен.
Вероятнее всего, пользователю не удастся разглядеть ни надпись Идет расчет..., ни крутящееся колесико, ни активную кнопку Остановить расчет поскольку он будет завершен за доли секунды, но пользователю знать о «такой неприятности» нужно.
Прежде чем начать описание очередного окна по формированию исходных данных для решения следующей задачи обратим внимание на кнопку панели управления Возврат к пройденному шагу... и поясним ее назначение.

8.10  Кнопка панели управления Возврат к пройденному шагу...

Дело в том, что практически все алгоритмы, имеющиеся в программе, для построения учебного расписания очень активно пользуются генератором случайных чисел. Это приводит к тому, что если пользователь попробует решить туже задачу с точно такими же исходными данными, то практически наверняка он поучит от программы другое решение.
Трудно сказать, является ли это недостатком программы или ее достоинством. Тем не менее, при таких обстоятельствах у пользователя появляется возможность решать одну и туже задачу, с одними и теми же исходными данными, ранее сформированные им для решения этой задачи, неограниченное число раз. Другими словами до тех пор пока решение задачи, по тем или иным критериям, пользователю не придется по душе или не станет любо. Но кнопка Продолжить в любом из окон, обязывает пользователя двигаться только вперед (к следующему по счету окну).
Как же вернутся пользователю к уже пройденному окну, не начиная новой задачи?
Понятно, что прежде всего следует избавиться от очередного окна на экране ПК, поскольку это окно монопольно захватывает на себя все действия пользователя. Для этого жмем на кнопку Завершить, после чего окно исчезнет, а кнопка панели управления Возврат к пройденному шагу... станет доступна.
Для тех кто был не очень внимателен или забыл о существовании такой кнопки панели управления, покажем ее на рисунке 46.

Рисунок 46: Кнопка панели управления Возврат к пройденному шагу...
После нажатия на эту кнопку на экране ПК появиться окно, изображенное на рисунке 47, с помощью которого можно выбрать шаг (окно) к которому пользователь хочет вернуться.

Рисунок 47: Окно Выбор окна (шага) для возврата к нему
Каждым из пунктов этого окна является название окна (шага), только из тех шагов, которое пользователем уже были пройдены. Для удобства эти пункты пронумерованы. Выбор шага осуществляется стандартным для программы способом - двойной клик мышкой по нужной строчке, либо после подведения курсора к нужной строчке с помощью нажатия клавиши Enter, либо после подведения курсора к нужной строчке, нажатием на кнопку Возврат к шагу ХХ. На место ХХ программа, естественно, подставить выбираемый номер.
Перед тем как программа позволит пользователю осуществить свой выбор, она попросит у пользователя подтверждения его намерений с помощью вопроса, изображенного на рисунке 48.

Рисунок 48: Окошко с вопросом
Программа предупреждает пользователя о том, что во всех окнах, следующих за выбранным ему придется заново формировать исходные данные, в том числе и те, которые им уже были введены. При выборе им одного из предлагаемых пунктов, перед пользователем появиться окно на которое он указал, и у него появится возможность продолжить решение общей задачи с выбранного места. В частности, пользователь может подправить ранее введенные исходные данные или еще раз решить (пересчитать) какую-то отдельную задачу без исправления исходных данных, из списка отмеченных в окне - Список решаемых задач. При этом, решение окажется другим (будет отличаться от ранее полученного).
Есть еще и другой способ возврата к решению уже пройденных задач, без повторного ввода уже сформированных исходных данных (если они были введены пользователем), но о нем будет рассказано после описания формирования финального расписания.

8.11  Пункты главного меню Запомнить/Вспомнить текущее
расписание

При возврате пользователя к уже пройденному шагу решения задачи или пересчете расписания, нет никакой гарантии, что полученное новое расписание окажется лучше, по тем или иным критериям, предыдущего (ранее рассчитанного). Таким образом, пользователь нуждается в некой «страховке» во время борьбы хорошего с еще лучшим.
Одним из способов такой «страховки» может оказаться полезным пункт главного меню программы - Запомнить текущее расписание, изображенный на рисунке 49.

Рисунок 49: Пункт главного меню Запомнить текущее расписание
Как видно из рисунка 49, следующий пункт меню - Вспомнить расписание находится пока в неактивном состоянии. Причина этому простая - пользователь еще ни разу не запоминал текущее расписание. Как только он это сделает, пункт Вспомнить расписание станет активным (ярким) и пользователь при желании сможет восстановить расписание в том состоянии, как оно было запомнено. Отметим, что «запоминание» и «вспоминание» расписания будет предварять вопрос программы на подтверждение таких действий. При «вспоминании» расписания окошко с вопросом будет выглядеть так, как изображено на рисунке 50.

Рисунок 50: Окошко с вопросом

8.12  Шестой этап алгоритма

8.12.1  Окно Список учебных предметов

Начиная с этого окна пользователь приступает к решению последней и самой сложной задачи - Финальное расписание. Это окно, изображенное на рисунке 51, имеет достаточно простой вид.

Рисунок 51: Окно Список учебных предметов
После того, как пользователь введет число предметов, изучаемых в школе, он может приступать к редактированию названий этих учебных предметов. Обратим внимание на то, что редактирование числа предметов должно заканчиваться нажатием клавиши Enter, иначе количество строк таблицы не будет изменено.
При редактировании названий предметов пользователю не стоит забывать о том, что максимальное число символов из которых состоит название предмета не может превышать значения равного 14-ти.

8.12.2  Окно Формирование учебного плана для предметов без
разделения на группы

Автоматически сформированный программой учебных план, представлен на рисунке 52.

Рисунок 52: Окно Формирование учебного плана
В отличии от предыдущего окна, данное окно весьма затейливо. К тому же для его правильного формирования пользователю придется изрядно потрудиться.
Объяснение начнем с самой верхней строки окна - Предельное значение нагрузки учебного плана, изображенного на очередном рисунке 53, уже показанного окна.

Рисунок 53: Часть окна Формирование учебного плана
Как видно из рисунка 53, в данном примере это значение равно числу 647. Откуда взялось это число и что оно означает?
Как известно, для каждого класса санитарными нормами может быть предусмотрена предельная нагрузка учебных занятий в зависимости от параллели класса (возраста учащихся). Если просуммировать предельную нагрузку всех классов и вычесть из этого значения нагрузку, которая уже была включена в расписание для всех классов (уже назначена, расставлена) на предыдущих шагах расчета расписания, то полученное значение пользователь и увидит на экране ПК (в первой строке обсуждаемого окна).
Если пользователь нажмет на кнопку Очистить, что ему лучше всего и нужно будет сделать, то вторая сверху строка - Текущее значение нагрузки учебного плана покажет число ноль. После такого действия задачей пользователя будет редактирование таблицы учебного плана до тех пор, пока текущее значение не окажется равным предельному. При этом программа будет следить за тем, что бы пользователь не ввел нагрузку больше предельной.
Теперь о структуре таблицы и ее цветах. В первой колонке отображаются номера строк, во второй названия учебных предметов, введенные пользователем на предыдущем шаге (в предыдущем окне).
Первая строка (самая верхняя) таблицы, отображает список классов для которых формируется расписание. Причем перед названием каждого класса в квадратных скобках указано число равное предельному значению еще не распределенной учебной нагрузки этого класса. В процессе редактирования таблицы это число остается неизменным. Во второй (следующей) строке, в квадратных скобках отображается текущее значение нагрузки класса, сформированной пользователем в процессе редактирования таблицы.
Если пользователь понажимает клавиши со стрелками, то он быстро сообразит, что ячейка окрашенная темно-синим цветом является текущей (имеющей фокус ввода), ячейки окрашенные в светло-синий цвет отображают текущую колонку и текущую строку таблицы. Ячейки окрашенные розовым цветом означают то, что для текущего класса и текущего предмета нагрузка имеет нулевое значение. Если нагрузка для соответствующего класса и предмета ненулевая, то ячейка окрашивается зеленым цветом.
Для изменения нагрузки, отображаемой в текущей (имеющей фокус ввода) ячейке, пользователю следует воспользоваться стандартным приемчиком (двойной клик мышкой или нажатие клавиши Enter), после чего появится окошко, изображенное на рисунке 54.

Рисунок 54: Окошко редактирования значения нагрузки класса по предмету
Значение нагрузки равное нулю, означает отсутствие нагрузки. Предельное значение нагрузки зависит от количества учебных дней в неделю, заданных пользователем для школы. При пяти учебных днях, предельная нагрузка составляет 4 часа, при шести учебных днях - 5 часов.
Таким образом, ничего сложного процесс редактирования учебного плана школы из себя не представляет, если не считать продолжительность самого этого процесса.
Отметим, что программа следит за соответствием не только числа Текущего значения учебного плана его предельному значению, но и за соответствием аналогичных чисел для каждого класса. Если пользователь ошибочно попытается превысить предельное значение нагрузки для какого-то класса, то программа не позволит ему этого сделать.

8.12.3  Окно Список преподавателей

Следующее окно, изображенное на рисунке 55, на счастье, такое же простое, как и окно Список предметов. Правила редактирования в этом окне те же самые, что и в окне Список предметов.

Рисунок 55: Окно Список преподавателей
После того как пользователь введет значение количества преподавателей, не забывая при этом нажать клавишу Enter и обращая внимание на допустимый интервал этого значения, он может приступать к редактированию списка (фамилий преподавателей). Под ФИО преподавателя программой отводится 23 символа, о чем не следует забывать. Заканчивается процесс редактирования таблицы, как обычно, нажатием на кнопку Продолжить.

8.12.4  Окно Формирование таблицы компетентности преподавателей

Следующее окно - единственное в программе, имеющее, кроме таблицы, четыре кнопки. В дополнении к уже известным пользователю кнопкам Продолжить, Очистить и Закончить, присутствует еще одна - Пропустить. Как видно из рисунка 56, эта кнопка располагается внизу окна, самой первой (самой левой).

Рисунок 56: Окно Формирование таблицы компетентности преподавателей
На первый взгляд наличие такой кнопки может показаться странным, но это только на первый взгляд. Дело в том, что единственным назначением этого окна (составления таблицы компетентности) является подготовка исходных данных к автоматическому распределению педагогической нагрузки преподавателей, которая будет осуществляться на следующем шаге (в следующем окне) программы.
Если пользователь твердо уверен в том, что «бестолковая программа» не сможет распределить педагогическую нагрузку «так как нужно», то он может не трудиться понапрасну и нажать кнопку Пропустить, тогда следующее окно окажется, как бы в состоянии после нажатия кнопки очистить. То есть, заранее подготовленным к «ручному» способу распределения педагогической нагрузки, который потребует от пользователя, пожалуй, самых больших усилий при формировании исходных данных.
Для тех, кто не хочет на следующем шаге (в следующем окне) воспользоваться возможностью «ручного» распределения педагогической нагрузки и не станет нажимать кнопку Пропустить, поясним процесс редактирования таблицы компетентности.
Смысл редактирования таблицы достаточно прост - каждому преподавателю сопоставить те учебные предметы, которые он мог бы преподавать. Как правило это пара предметов, например, родной язык и литература, алгебра и геометрия и т.п. В редких случаях преподаватель подготовлен для преподавания трех предметов. В программе, с запасом, предусмотрен случай на четыре предмета. Естественно, что указание хотя бы одного предмета - обязательно.
Смысл раскраски ячеек стандартный. Есть предмет, нет предмета (красный, зеленый). Текущая ячейка, текущая строка (синий, светло-синий). Вызов окошка выбора предмета то же стандартный - двойной клик мышкой или клавиша Enter.
Окошко выбора предмета (Список предметов), изображено на рисунке 57.

Рисунок 57: Окошко Список предметов
Как видно из рисунка 57, таблица списка предметов состоит из трех колонок. В третьей колонке (самой правой) размещаются названия предметов, в средней колонке в круглых скобках указано число рекомендованного (не минимального) количества компетентных преподавателей, а в первой колонке (левой), в квадратных скобках, указано число равное количеству преподавателей компетентных преподавать соответствующий предмет, которое сформировал пользователь. Поскольку после нажатия на кнопку Продолжить программа будет контролировать необходимый минимум преподавателей способных преподавать каждый предмет, первые две колонки могут оказать существенную помощь для правильного заполнения Таблицы компетентности.
Действия пользователя при выборе предмета из списка, точно такие же, как и в аналогичных окошках. Как и обычно, до тех пор пока пользователь не завершит сопоставление предметов для всех преподавателей, программа не позволит ему добраться до следующего окна, если, конечно, он не воспользуется кнопкой Пропустить. Кроме того, программа проконтролирует что бы для каждого предмета имелся хотя бы один компетентный преподаватель.

8.12.5  Окно Распределение педагогической нагрузки

На следующем рисунке 58 представлена таблица распределения педагогической нагрузки после ее автоматического формирования.

Рисунок 58: Окно Распределение педагогической нагрузки
Разумеется, что если на предыдущем шаге пользователем была нажата редкосная кнопка Пропустить, то вся колонка с заголовком Преподаватель окажется окрашенной розовым цветом и без фамилий преподавателей в ячейках. Кроме того, в этом окне пользователю доступна окраска всей колонки в розовый цвет путем нажатия на кнопку Очистить, на случай если пользователь заметит всю глупость автоматического распределения нагрузки и нецелесообразность частичного редактирования такого распределения.
Теперь осталось только повторить - как начать редактирование колонки. Но проницательный читатель об этом уже наверное и сам догадался. Рисунку, со списком преподавателей для выбора, присвоен очередной номер 59.

Рисунок 59: Окошко Список преподавателей
С целью экономии бумаги и времени читателя, комментировать процесс выбора преподавателя мы не станем, отметим лишь, что максимальная недельная нагрузка преподавателя, текущее значение которой заключено в квадратные скобки, составляет 25 часов. Если вдруг при автоматическом распределении нагрузки какому-то преподавателю будет распределено нагрузки более 25-ти часов, то ячейки с этим преподавателем окажутся окрашенными в красный цвет и снижать нагрузку такому преподавателю нужно будет пользователю в «ручном» режиме.

8.12.6  Окно Запреты на работу в первый урок

Следующее окно является на столько банальным, что кроме упоминания о нем пожалуй ничего говорить и не нужно. Тем более приводить его рисунок.
Хотя стоит еще раз отметить, что любые ограничения легко могут привести к несуществованию решения задачи и поэтому программа будет уговаривать пользователя не предоставлять преподавателям возможности появляться в школе только ко второму уроку. В то же время, пользователь имеет полное право и возможность поэксперементировать на этот счет с получением решения.

8.12.7  Окно Построение расписания для классов без разделения
на группы

Вопреки наметившейся тенденции экономии бумаги, рисунок следующего окна показать все же придется. Тем более, что разговор пойдет не столько о рисунке, сколько о процессе расчета финального расписания.
Как наверное уже предположил проницательный читатель, первоначально окно будет содержать сообщение о том, что все готово для начала расчета и три кнопки - Рассчитать, Остановить расчет и Закончить. Разумеется, первоначальное состояние кнопки Остановить расчет - неактивна.
На рисунке 60 представлено окно во время расчета расписания (еще до того, как появиться очень довольная и улыбающаяся рожица).

Рисунок 60: Окно Построение расписания для классов без разделения на группы
Первое, что может прийти в голову, глядя на этот рисунок - нахрена козе баян и к чему столько наворотов?
Поясним содержание этого окошка, двигаясь слева направо.
Прежде всего обращает на себя внимание крутящееся колечко (на рисунке оно разумеется не крутиться) свидетельствующее о том, что процесс расчета идет. Под этим колечком располагаются «цифровые часики» показывающие время продолжающегося расчета. Далее надпись - Идет расчет расписания, придется подождать..., за которой следует некая служебная информация, предназначенная в первую очередь для разработчиков программы.
Так вот, нахрена козе баян?
Дело в том, что если количество классов (по меркам программы) невелико - от 12 до, скажем 17, то пользователь всю эту «красоту» может просто не увидеть, поскольку расчет, как правило закончиться за доли секунды. Однако, при количестве классов подходящих к своему пределу, обстановка может резко измениться. А именно. Если пользователю повезет (именно повезет), то расчет может закончиться за доли секунды или за секунды. А если не повезет, то расчет расписания может затянуться на несколько десятков минут. Причем предсказать заранее длительность расчета нет никакой возможности. Вот именно на такой случай и рассчитано, крутящееся колесико, «цифровые часики» и прочие удовольствия. Для особо нетерпеливых предназначена кнопка Остановить расчет, прибывающая, в отличии от остальных, в активном состоянии. Но мы будем надеяться на то, что пользователь довольно быстро увидит окошко, изображенное на следующем рисунке 61.

Рисунок 61: Окно Построение расписания для классов без разделения на группы
Остается только добавить, что разработчики программы решили ячейки наполненные результатом финального расчета никак не раскрашивать.

8.13  Дополнительные возможности Win-приложения

8.13.1  Кнопка панели управления Автогенерация данных

Для не очень внимательных читателей и тех людей кто не обладает феноменальной памятью, на рисунке 62 еще раз представим изображение этой кнопки.

Рисунок 62: Кнопка панели управления Автогенерация данных
После обсуждения назначения кнопки панели управления Возврат к пройденному шагу... нами было упомянуто о том, что есть еще один способ возврата к пересчету уже решенных задач.
Скептически настроенный читатель может сказать: - «Вот еще один пример борьбы хорошего с еще лучшим». Но не стоит делать поспешных выводов. Обратим внимание читателя на то, что в случае возврата с помощью кнопки Возврат к пройденному шагу..., к некоторому шагу (окну) алгоритма, исходные данные сформированные пользователем на этом шаге, не считая окошек с предложением решить очередную задачу, сохраняются. Другими словами программа оставляет их не тронутыми. Но на следующем шаге (в следующим по счету окне) программа тупо начинает заменять данные введенные пользователем, своими - автоматически генерируемыми, что может совершенно не соответствовать желанию пользователя. Если такими данными являются всего-навсего одно или два числа, то с подобной ситуацией еще можно было бы смириться, но если программа уничтожит, например, таблицу распределения педагогической нагрузки на заполнение которой пользователь потратил целый день работы, то...
При этом ситуация, когда у пользователя может возникнуть желание пересчитать все ранее полученные расписания с абсолютно теми же данными, является вполне рабочей и встречающейся на практике достаточно часто. Как же тогда быть?
Как быть, как быть... да запретить... и дело с концом.
Вот для такого запрета программе - менять уже введенные данные пользователя, и предназначена кнопка Автогенерация данных. Поскольку программа весьма «бестолкова» и с первого раза не понимает чего от нее хотят, после того, как пользователь кликнет мышкой по кнопке Автогенерация данных, она симулируя слабоумие переспросит его с помощью окошка, изображенного на рисунке 63.

Рисунок 63: Окошко с вопросом
После того как пользователь подтвердит свое желание, кнопка Автогенерация данных, затоив тайную обиду на пользователя потухнет, а окошко с вопросом исчезнет с экрана ПК. Далле пользователь может нажать на кнопку Возврат к пройденному шагу... и выбрать из окна - Выбор окна (шага) для возврата к нему, желаемый для него шаг алгоритма. Здесь сразу стоит отметить, что подлая кнопка Автогенерация данных, вспомнив о своей обиде и желая отомстить пользователю, запретит ему использование любых управляющих элементов во всех окнах программы, предназначенных для формирования исходных данных, кроме кнопок Продолжить и Закончить.
Находясь под такими наложенными санкциями пользователю имеет смысл выбирать только те шаги (пункты) алгоритма, с помощью которых производиться расчет той или иной задачи. Как можно видеть из рисунка 64 такие пункты отмечены в окне выбора текстовыми стрелочками, а для большей наглядности и привлечения к ним внимания, на рисунок нанесены еще и красные изгибающиеся стрелки.

Рисунок 64: Часть окна Выбор окна (шага) для возврата к нему
Действительно, какой смысл выбирать окно в котором практически все запрещено, хотя формально никаких запретов на это нет.
Далее подумаем над возможной ситуацией, связанной с запретом автогенерации исходных данных. Предположим, что пользователь начал решать свою задачу, дошел (имея ввиду шаги алгоритма) до некой середины, и не долго думая, осуществляет запрет автогенерации данных. Потом нажимает кнопку Продолжить начатую задачу. И что дальше? А дальше не будет не только автогенерации данных, но и будет запрет пользователю вводить свои данные. Что может содержатся в появившимся окне? Либо ничего, если пользователь в первый раз решает задачу, либо мусор, оставшийся от ранее решаемой задачи не совместимый с уже введенными пользователем исходными данными. В следствии чего пользователю, могла бы представиться возможность наблюдать поведение спятившей программы.
Таким образом, мы приходим к выводу о том, что осуществлять запрет автогенерации можно только в том случае, если пользователем были сформированы (введены) все без исключения исходные данные. А когда, все без исключения, такие данные введет пользователь? Ответ прост - после того как он нажмет кнопку Продолжить на форме Запреты на работу в первый урок под номером 28, а последней показанной формой окажется форма Построение расписания для классов без разделения на группы под номером 29. Следовательно, в случае несоблюдения пользователем выше описанного правила, быть ему обруганным программой с помощью окошка, изображенного на рисунке 65 и показанного вопреки нашего установленного правила - не приводить рисунков с руганью программы.

Рисунок 65: Сообщение об ошибке
На этом мы наше повествование о борьбе хорошего с еще лучшим и пресловутой Автогенерации данных заканчиваем, плавно переходя к другой мульке25 программы.

8.13.2  Кнопка Вывод в файл Exel

После появления окошка, изображенного на рисунке 61, и нажатия пользователем на кнопку Закончить, у пользователя может возникнуть желание самостоятельно «доделать» («допилить») расписание (построить расписание преподавателей и кабинетов). Теперь, после того, как все самые сложные расчеты закончены, этот процесс не может вызвать каких-либо серьезных затруднений, если использовать всеми любимую и популярную программу Excel.
Процесс переноса полученного расписания из программы «АФМ: Аннушка» в программу Excel осуществляется с помощью кнопки Вывод в файл Excel панели управления вкладки Расписание классов. После нажатия на эту кнопку на экране ПК появится окошко с вопросом, изображенное на рисунке 66.

Рисунок 66: Окошко с вопросом
После положительного ответа на этот вопрос пользователю остается только воспользоваться этим файлом, расположенном в папке Документы.

8.13.3  Кнопка Найти подстроку

При формировании дополнительных расписаний в программе Excel, может оказаться очень полезной кнопка Найти подстроку, находящаяся на той же панели управления вкладки Расписание классов.
Окошко, которое появиться после нажатия на эту кнопку, изображено на рисунке 67.

Рисунок 67: Окошко Поиск подстроки
После ввода пользователем подстроки в поле ввода Текст, например, фамилии преподавателя, и нажатия кнопки Найти, окошко примет другой вид (см. рис. 68), и будет оставаться таким, до тех пор пока не отыщутся все ячейки с введенным текстом. При этом каждая найденная ячейка будет постоянно переходить в состояние - текущая, и следовательно будет отмечаться синим квадратиком.

Рисунок 68: Окошко Поиск подстроки

8.13.4  Просмотр «длинного» содержания ячеек

Если содержание ячейки вкладки Расписание классов окажется слишком длинным и поэтому такое содержание не будет видно целиком, то для увеличенного рассмотрения этого содержания можно воспользоваться специальным окошком, изображенном на рисунке 69.

Рисунок 69: Окошко Сообщение
Как наверное уже догадался проницательный пользователь, вызов окошка осуществляется с помощью стандартного приемчика - подведение курсора к нужной ячейке, двойной клик мышкой или нажатие клавиши Enter.

8.14  Архивирование и восстановление расписания

В самом начале 90-х годов прошлого века у автора этих строк состоялся «поучительный» диалог с одним из своих коллег.
- А если персональный компьютер сломается?
- Персональные компьютеры не ломаются!
Именно так тогда оценивалась перспектива длительного, а главное, надежного хранения информации на тогдашних ПК26. Теперь такого пожалуй никто не скажет. Пользователи ПК с длительным опытом работы на них, знают, что выход почти подряд из строя двух жестких дисков - дело вполне обычное, не говоря уже о переустановке операционной системы. Из чего, неотвратимо следует вывод.
Дублируйте важные данные на разные носители!
Именно для такого дублирования и предназначены пункты главного меню программы Архивирование расписания F2 и Восстановление расписания F3, изображенные на рисунке 70.

Рисунок 70: Пункты главного меню Архивирование и Восстановление

8.14.1  Пункт главного меню Архивирование расписания

После нажатия клавиши F2 или соответствующего выбора пункта главного меню программы появиться окно, изображенное на рисунке 71.

Рисунок 71: Окно Архивирование данных расписания
В этом окне пользователю предстоит выбрать физический носитель, имеющийся на его ПК, для архивирования. Подчеркнем, что по смыслу вей этой затеи с архивированием оно должно производится именно на другой физический, а не логический, носитель. Удобнее всего для этой цели использовать флешку.
После того как выбор носителя будет сделан, кнопка Архивировать данные перейдет в активное состояние и ей можно будет воспользоваться. По окончании архивирования в корне выбранного носителя появится файл AFM_annushka_ХХ.zip в котором и будут содержаться все необходимые данные для восстановления расписания. Точнее - для восстановления данных, хранящихся на ПК пользователя. Окончание - _ХХ соответствует второй серии цифр из версии программы «АФМ: Аннушка».
По мнению разработчиков программы у возможности архивирования данных есть еще одно полезное назначение - это обмен данными между пользователями программы. Один пользователь прикрепляет полученный файл к письму электронной почты, а другой пользователь, получив такой файл имеет возможность его использовать в качестве восстановленных данных. Как говориться - простенько и со вкусом.

8.14.2  Пункт главного меню Восстановление расписания

В случае необходимости восстановления данных программы, пользователь после нажатия клавиши F3 или соответствующего выбора пункта главного меню, увидит на экране стандартное окно выбора файла. Поскольку окно стандартное мы здесь не приводим его изображения и не делаем каких-либо комментариев по этому поводу. После выбора в этом окне архивного файла появится окно, изображенное на рисунке 72.

Рисунок 72: Окно Восстановление данных программы
Далее пользователю останется только нажать кнопку Восстановить данные.

9  Заключение

То, что изготовление (написание) текстов является очень не простым занятием (искусством) было известно давно. Более того, по нашему мнению это занятие является более затейливым, чем программирование. При составлении данного текста в голове все время крутились такие слова, как:
- Вычесывание;
- Вылизывание;
- Вырубание;
- Выскребание;
- Выделывание.
А так же:
- Шлифовка;
- Рихтовка;
- Заделка;
- Обрезка;
- Пристройка;
- Обточка;
- Подчистка;
- Строгать;
- Тисать;
- Утюжить;
- Пользовательский интерфейс;
- Повторное тестирование;
- Переделка.
Авторы этого текста далеки от мысли, что ими был произведен идеальный продукт (как сам предлагаемый текст, так и собственно программа). Мысль о том, что совершенству предела нет, для авторов проста и понятна, как дважды два - четыре.
Основные принципы, которых пытались придерживаться авторы при подготовки текста это:
  • Понятность (и отсутствие двусмысленности);
  • Подробность;
  • Полнота.
Нет сомнений в том, что достичь своей цели им так и не удалось. Поэтому мы с удовольствием примем все замечания заинтересованных читателей, которые пришлют нам свои вопросы, пожелания, комментарии, примеры, которые вызывают у них затруднения и которые не рассматривались здесь.
Написание (разработка) данного повествования носит ярко выраженный итерационный характер. Не редкость, когда работа начинается не сначала, а с конца или середины. Все время приходится восклицать: - «Как же мы забыли об этом и пропустили!». В следующей редакции этого текста, не рассмотренные вопросы будут непременно рассмотрены. Непонятные места будут разъяснены. Понятия описанные не подробно, будут описаны подробно. Все ошибки и несуразицы пользовательского интерфейса устранены.
Ждем Ваших отзывов! Как о данном тексте, так и о смой программе (особенно о замеченных в ней ошибках). И удачи в работе при тестировании «Древнеегипетского» алгоритма составления школьных расписаний.

Литература

[1]
Балтак С.В., Сотсков Ю.Н. Построение расписания учебных занятий на основе раскраски вешин графа // Информатика, 2006, № 3, с. 58 - 69.
[2]
Бородин О.В. Раскраски и топологические представления графов // Дискретный анализ и исследование операций. 1996, Том 3, № 4, с. 3 - 27.
[3]
Бородин О.В. Обобщение теоремы Коцига и предписанная раскраска ребер плоских графов // Математические заметки. 1990, Том 48, Выпуск 6, с. 22 - 28.
[4]
Визинг В.Г. Раскраска вершин графа при мажоритарных ограничениях на используемые цвета // Дискретный анализ и исследование операций. 2009, Том 16, № 4, с. 21 - 30.
[5]
Визинг В.Г. О связной раскраске графов в предписанные цвета // Дискретный анализ и исследование операций. 1999, Серия 1, Том 6, № 4, с. 36 - 43.
[6]
Галкина Т.И., Сухенко Н.В. Организация профильного обучения в школе. - Ростов н/Д: Феникс, 2007. - 288 c.
[7]
Гафаров Е.Р., Лазарев А.А. Математические методы оптимизации при составлении учебного расписания // Новые информационные технологии в образовании. Сборник научных трудов. - М.: 1С-Паблишинг, 2013, Часть 2, с. 51 - 55.
[8]
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: Мир, 1982. - 416 с.
[9]
Дистель Р. Теория графов: Пер. с англ. - Новосибирск: Изд-во Ин-та математики, 2002. - 336 с.
[10]
Емеличев В.А., Мельников А.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука. Гл. ред. физ.-мат. лит., 1990. - 384 с.
[11]
Ичбана Д., Кнеппер С. Бил Гейтс и сотворение Microsoft. - Ростов-на-Дону: Издательство «Феникс», 1997. - 352 с.
[12]
Карпов Д.В. Динамические правильные раскраски вершин графа. // Записки научных семинаров ПОМИ. 2010, Том 381, с. 47 - 77.
[13]
Магомедов А.М., Магомедов Т.А. Интервальная на одной доле правильная реберная 5-раскраска двудольного графа // Прикладная дискретная математика. 2011. №3(13), с. 85 - 91.
[14]
Магомедов А.М. Цепочечные структуры в задачах о расписаниях // Прикладная дискретная математика. 2016. №3(33), с. 67 - 77.
[15]
Магомедов А.М. Кусочечно-непрерывные пути в задачах построения и оптимизации расписаний // Информационные технологии и вычислительные системы. 1/2018. с. 78 - 84.
[16]
Пападимитру Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. Пер. с англ. - М.: Мир, 1985. - 512 с.
[17]
Романовский И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. - Издание 2-е, исправленное. - СПб.: Невский диалект, 2000. - 240 с.
[18]
Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. - М.: Мир, 1984. - 455 с.
[19]
Смирнов В.В. Перербургские школы и школьные здания. История школьного строительства в Санкт-Петербурге - Петрограде - Ленинграде 1703 - 2003 гг. - СПб.: Издательство «Русско-Балтийский информационный центр "БЛИЦ"», 2003. - 144 с.
[20]
Стеценко О.П. Об одном виде раскраски ребер графа в предписанные цвета // Дискретная математика. 1997. Том 9, выпуск 4, 92 - 93.
[21]
Урнов В.А. Расписание - наиболее востребованный АРМ в образовании // Информатика и образование. 2001, № 4, с. 47 - 52.
[22]
Филипенко А.С., Овсянников К.В., Болотов С.В. Анализ требований к школьному расписанию с учетом специфики белорусского законодательства // ПФМТ. 2016, выпуск 4(29), с. 103 - 106.
[23]
Харари Ф. Теория графов. - М.: Мир, 1973. - 302 с.
[24]
Even S., Itai A., Shamir A. On the complexity of timetable and multicommodity flow problems // SIAM J: Comput. Vol. 5, No. 4, December 1976, 691-703

Ссылки:

1Поэтому весь этаж где располагалась такая ЭВМ обтягивали мелкой металлической сеткой, дабы исключить возможность «электронного подглядывания» со стороны заклятых врагов советской власти.
2Подчеркнем - не составлять, а составить. То есть, не расставить 97% учебной нагрузки (найти тупик), а расставить всю нагрузку без исключения, и кроме того, всегда, то есть во всех случаях при условии допустимых исходных данных.
3Самой же задаче составления учебного расписания (без помощи вычислительной техники) по всей видимости, уж никак не менее трехсот лет.
4Зафиксированы случаи когда завучи - в общем то, культурные и воспитанные люди, услышав словосочетание: - «Программа для составления школьного расписания» мгновенно переходили на матершину.
5«Не достигнув желаемого, они сделали вид, что желали достигнутого» - Мишель де Монтель.
6При этом стоит отметить, что легенды окружающие российское правосудие (а точнее отсутствия правосудия, что естественно наруку мошенникам) мы здесь не обсуждаем.
7Здесь мы не будем останавливаться на теории NP-трудных задач, поскольку обсуждение этого вопроса увело бы читателя далеко в сторону от интересующей нас темы, а так же носило бы явно преждевременный и поверхностный характер. Заинтересованному же читателю, можно порекомендовать обратиться к пожалуй самому цитируемому в нашей стране изданию по данной теме [8]. Для полного понимания данной публикации под NP-трудными задачами можно понимать - практически нерешаемые задачи, хотя это не совсем точный (или совсем не точный) «перевод».
8Имеются ввиду русскоязычные публикации, которых по сравнению с англоязычными не так много. Скорее всего их число не превышает общего вклада Российской Федерации в сфере высоких технологий, который оценивается в пределах 0.4 - 0.6 % (от нуля целых четырех десятых процента до нуля целых шести десятых процента) от общемирового.
9Правда, физико-математических наук на порядок меньше.
10Танаев Вячеслав Сергеевич (1940 - 2002) - белорусский математик, директор НИО «Кибернетика» НАН РБ, доктор физико-математических наук (1978), профессор (1980), действительный член Национальной академии наук Беларуси (2000). Область научных интересов: исследование операций, теория расписаний, методы оптимизации.
11Михалевич Владимир Сергеевич (1930 - 1994) - украинский математик и кибернетик, академик АН Украины, академик РАН (1991; академик АН СССР с 1984). Труды по теории оптимальных статистических решений, системному анализу, теоретической и экономической кибернетике. Государственная премия СССР (1981).
12Существует легенда [11] о том как, теперь один из самых богатых людей на планете, а тогда юный (шестнадцати летний) Билл Гейтс вместе со своим старшим другом Полом Алленом «решили» эту задачу, взамен получили за программирование машинное время и заработали 2400 долларов карманных денег.
13Утверждение про уникальность рынка ПО составления школьного расписания, пожалуй все же не верно. Очень похожая ситуация сложилась на рынке ПО автоматического перевода текстов (в частности технических, написанных человеком для человека, тексты на языках программирования, естественно, не в счет) с одного языка на другой, например, с английского на русский. Точно так же, эта задача весьма внятно была сформулирована не менее шестидесяти лет назад. Точно так же, решалась усилиями многих тысяч исследователей. До настоящего времени в попытках решить задачу перевода прилагаются фантастические усилия. Приблизительно те же результаты - близкие к нулевым. Если программе автоматического перевода не предлагать специально подобранный текст (как порой делают разработчики подобного ПО в своих демоверсиях) понять из перевода: - «Это вообще о чем?», практически не возможно.
В качестве другого примера, можно было бы привести ПО распознавания речи. Судя по программам обучения иностранному языку, кое-какие результаты в этом направлении все же имеются (отличить правильное произношение от неправильного - удается), но до окончательного решения проблемы еще очень и очень далеко. Мечта о вводе в компьютер данных или команд с голоса, все еще остается мечтой.
Третьем примером могло бы быть ПО распознавания рукописного текста (не путать с распознаванием типографского текста, это принципиально различные задачи). Многолетние усилия огромный армии исследователей пока-что увенчались практически нулевым результатом.
14Следует отметить, что расчеты могут очень сильно варьироваться выбирая в качестве примера другие страны. Так, например, Франция имеет население в два раза меньше чем РФ, однако школ там в два раза больше. Таким образом, «школо-оснащенноесть на душу населения» отличается в этих странах в четыре раза. Правда, такой расчет произведен без учета того, чт во Франции совсем другая систем образования чем в России.
15По данному показателю в последние 18–19 лет наблюдалась противоречивая динамика. На начало 2000/2001 учебного года в стране было 20553,5 тысяч школьников. На начало 2011/2012 учебного года их было 13737,8. После этого начинается их рост. На начало 2013/2014 учебного года в школах училось 13877,4 тысяч человек. В 2017 году количество школьников составило 15705,9 тысяч человек. В 2018 году школьников было уже 16137,3 тысяч.
16По данным Счетной палаты, начиная с 2001 года, сельские школы сократились почти вдвое: с 46000 до 24000, городские – на четверть, с 23000 до 18000. По данным Росстата, в 2018 году всего в России было 41349 школ.
17В Эрефии по 80 долларов.
18Ученый-археолог убежден, что люди (разумные существа) периодически осуществляют самоуничтожение своей цивилизации с помощью войн с применением ядерного (водородного или аналогичного оружия массового уничтожения). По его мнению (расчетам) мы живем в эпоху девятой цивилизации.
19Слава тебе, Господи, что ты создал все нужное не трудным, а все трудное - не нужным. (Сковорода Григорий Саввич, 1722 - 1792) Сковороду Г.С. называют «первым философом Российской империи».
20Реально при пятидневной учебной неделе и принятых в РФ санитарных ограничениях загрузка специальных помещений может составлять только 33 часа. По четвергам и пятницам помещения загружаются не на 7, а на 6 часов.
21Ха, ха...
22Что такое разумная задача, более менее понятно, а вот что такое корректно заданная задача, вопрос очень и очень не простой. В первом приближении можно считать задачу корректно заданной, если ее решение существует. А вот вопрос: - «При каких условиях (ограничениях) решение задачи существует?» к сожалению на сегодня остается без ответа.
23Впрочем, передача кода генератора исходных данных и кода проверки правильности составленного расписания вполне возможна, поскольку этот код никакой коммерческой ценности не представляет.
24О том, что все окна при своем появлении заполняются тестовыми данными, которые пользователь может исправить мы больше напоминать не будем.
25Мулька - то же, что и цацка. По английски - фича.
26Скорее всего под впечатлением постоянных и регулярных поломок (сбоев) тогдашних супер-ЭВМ.


File translated from TEX by TTH, version 4.15.
On 01 Jun 2022, 13:47.

Скачать бесплатно программу составления школьного расписания
 
 
Мой индивидуальный словарный запас
Как составить график работы для воспитателей детского сада?
Как составить график работы официантов?
Как составить график работы для продавцов минимаркета?
Как составить график работы для операторов call-центра?
Как составить оптимальный график работы для персонала аптечной сети?
Как составить оптимальный график работы для персонала парка атракционов?
Помощь при составлении графиков работы сотрудников