Применение метода моделируемого отжига к задаче составления школьного расписания

Содержание

Введение…………………………………………………………………………………………………………….3

Цель курсовой работы………………………………………………………………………………………..4

Постановка задач курсовой работы…………………………………………………………………..5

Реализация задач курсовой работы

Задача 1)………………………………………………………………………………………….6

Задача 2)………………………………………………………………………………………….20

Задача 3)………………………………………………………………………………………….23

Задача 4)………………………………………………………………………………………….26

Заключение……………………………………………………………………………………………………………29

Список используемой литературы……………………………………………………………………….30

Приложения…………………………………………………………………………………………………………..31

Введение

Программа, выбранная мною для реализации в качестве курсовой работы – программа, генерирующая расписание для школы. Подобных программ написано довольно много, но ни одна из них просто не может удовлетворять всем параметрам и нюансам, которые необходимо учесть при составлении расписания в каждой конкретной школе. Ведь какой-то учитель любит приходить пораньше на работу, и уходить пораньше. Другой лучше придет попозже, третьему удобно работать с окнами, потому что в это время он проверяет тетради…. К тому же в каждой школе есть свои особенности: факультативы, коррекционные классы, своя нагрузка…. Все невозможно учесть. Моя мама работает учителем в средней школе, и не раз мне приходилось слышать от нее недовольства по поводу составленного расписания. Именно поэтому у меня возникла идея написать программу, генерирующую расписание для конкретной школы – школы №5, в которой я училась.

Цель курсовой работы

Разработать программу, позволяющую максимально автоматизировать трудоемкий процесс составления школьного расписания, применяя метод моделируемого отжига.

Постановка задач курсовой работы

1) Сбор и анализ информации, которую необходимо учитывать при составлении расписания. Изучение необходимого для написания программы материала.

2) Составление реляционной схемы данных.

3) Разработка программы и удобного пользовательского интерфейса.

4) Обзор уже существующих программ, генерирующих школьное расписание.

Реализация задач курсовой работы

1) Первая задача на пути к реализации проекта – сбор всевозможной информации по теме курсовой работы. Так как программа составляется для конкретной школы, то и информацию я естественно искала в этой школе. Сначала я поговорила с мамой, потом с завучем, занимающимся составлением расписания в средней школе №5. Я изучила множество документов и материалов, прослушала полезную информацию и даже ряд пожеланий. Этих материалов оказалось достаточно для детального представления процесса составления расписания. Вот список материалов, собранных мною:

1. Образец расписания на 1 четверть 2008-2009 учебного года на понедельник (внешний облик), который висел в учительской. (Приложение 1)

2. Примерный учебный план для образовательных учреждений Российской Федерации на 1998 и 2004 года. (Приложение 2)

3. Учебный план средней общеобразовательной школы №5 на 2008-2009 учебный год. (Приложение 3)

4. Выдержки из «Охраны здоровья детей» по поводу балловой оценки предметов. (Приложение 4)

5. Требования к составлению расписания от Министерства Образования. (Приложение 5)

6. Таблица И.Г. Сивкова. Трудность каждого предмета здесь ранжируется в баллах:

Математика 11 баллов

Иностранный язык 10 баллов

Физика, химия 9 баллов

История 8 баллов

Русский язык, литература 7 баллов

Естествознание, география 6 баллов

Физкультура 5 баллов

Труд 4 балла

Черчение 3 балла

Рисование 2 балла

Пение 1 балл

7. Расписание уроков на 1 полугодие 2008-2009 года в баллах и соответствующие схемы распределения нагрузки в течение недели. (Приложение 6 и приложение 7)

Изучая найденный материал, я почерпнула для себя много интересной и полезной информации. Оказалось, что составление расписания – это целая наука! Ведь необходимо руководствоваться учебным планом, балловой оценкой предметов, дневной нагрузкой…. Учебный план необходимо составлять, отталкиваясь от примерного учебного плана, составленного Министерством Образования. Учебный план – это нагрузка для класса, количество часов каждого предмета в неделю. А ведь есть коррекционные классы, есть классы, которым необходима дополнительная нагрузка. Поэтому здесь необходим индивидуальный подход, несмотря на то, что есть примерный учебный план. Моя программа будет включать в себя процедуру создания учебного плана. Учебный план меняется ежегодно, расписание же может меняться 4 раза в год. Существует и учебный план для начальной школы, но расписание составляет сам учитель, поэтому мой проект составляет расписание только для 5-11 классов. Но и здесь есть свои исключения: физкультуру, музыку и иностранный язык в начальных классах ведут другие учителя, поэтому всё же при составлении общего расписания нужно будет учесть и некоторые уроки 1-4 классов. Я думаю, что для учителей (не классных руководителей), преподающих в начальной школе, нужно составить график работы обычным образом (естественно отталкиваясь от правил составления расписания для начальной школы), после чего классные руководители начальных классов досоставляют расписание сами.

Очень заинтересовала меня балловая оценка предметов. О существовании этой системы я слышала, но никогда раньше ей не интересовалась. Каждый предмет имеет свой уровень сложности восприятия, и это необходимо учитывать при составлении расписания, ведь, при правильно составленном расписании занятий, наибольшая интенсивность нагрузки (количество баллов за день по сумме всех предметов) для учащихся старших классов должна приходиться на вторник и (или) среду; для школьников младшего и среднего звена – на вторник и четверг при несколько облегченной среде. При этом следует помнить, что в течение дня оптимальные значения показателя работоспособности приходятся на интервал 10-12 часов, то есть основная учебная нагрузка должна приходиться на 2,3,4 уроки. Также есть замечание по поводу сдвоенных уроков: в начальных классах их проведение недопустимо, так как степень утомления детей возрастает в таком случае в 7 раз! Допускаются сдвоенные уроки лишь в старших классах! Этот факт необходимо учесть при составлении программы, так же как и максимальное количество занятий для каждого класса. Балловая система неоднозначна, но изменения её незначительны. В программе будет предусмотрено изменение таблицы с баллами, зарисовка схем нагрузки учебной недели для каждого класса, начиная с 5. Естественно, проект предполагает подбор нескольких вариантов расписания, подходящих всем требованиям. Ведь есть ещё такие требования как: максимально допустимая недельная нагрузка в часах, чередование в течение дня и недели основные предметы с уроками музыки, изо, труда, физкультуры (для начальных классов), с предметами естественно-математического и гуманитарного циклов (для среднего и старшего звена), максимальное количество баллов по каждому дню.

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

При подготовке к написанию работы, я изучила множество материалов, необходимых для реализации проекта. Я познакомилась со следующими понятиями: алгоритм имитации отжига, эвристика, целевая функция, транзакция.

Алгоритм имитации отжига

Алгоритм имитации отжига (англ. Simulated annealing) — общий алгоритмический метод решения задачи глобальной оптимизации, особенно дискретной и комбинаторной оптимизации. Один из примеров методов Монте-Карло. Экзотическое название данного алгоритма связано с методами имитационного моделирования в статистической физике, основанными на технике Монте-Карло. Исследование кристаллической решетки и поведения атомов при медленном остывании тела привело к появлению на свет вероятностных алгоритмов, которые оказались чрезвычайно эффективными в комбинаторной оптимизации. Впервые это было замечено в 1983 году. Сегодня этот алгоритм является популярным как среди практиков благодаря своей простоте, гибкости и эффективности, так и среди теоретиков, поскольку для данного алгоритма удается аналитически исследовать его свойства и доказать асимптотическую сходимость. Алгоритм основывается на имитациифизического процесса, который происходит при кристаллизациивещества из жидкого состояния в твёрдое, в том числе при отжигеметаллов. Предполагается, что атомы уже выстроились в кристаллическую решётку, но ещё допустимы переходы отдельных атомов из одной ячейки в другую. Предполагается, что процесс протекает при постепенно понижающейся температуре. Переход атома из одной ячейки в другую происходит с некоторой вероятностью, причём вероятность уменьшается с понижением температуры. Устойчивая кристаллическая решётка соответствует минимумуэнергии атомов, поэтому атом либо переходит в состояние с меньшим уровнем энергии, либо остаётся на месте. (Этот алгоритм также называется алгоритмом Н. Метрополиса, по имени его автора).

Алгоритм имитации отжига - алгоритм решения различных оптимизационных задач. Он основан на моделировании реального физического процесса, который происходит при кристаллизации вещества из жидкого состояния в твёрдое, в том числе при отжиге металлов.

Целью алгоритма является минимизация некоторого функционала. В процессе работы алгоритма хранится текущее решение, которое является промежуточным результатом. А после работы алгоритма оно и будет ответом.

Основные шаги алгоритма:

1. Выбор начального решения и начальной температуры

2. Оценка начального решения

3. Основной шаг алгоритма

1) Случайное изменение текущего решения

2) Оценка измененного решения

3) Критерий допуска

4. Уменьшение температуры и, если температура больше некоторого порога, то переход к основному шагу

Выбор начального решения

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

Оценка решения

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

Основной шаг алгоритма

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

Случайное изменение решения

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

Критерий допуска

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

Если измененное решение имеет меньшую энергию, то оно принимается за текущее. Если же измененное решение имеет большую энергию, то оно принимается с вероятностью P = exp(-δE/T), где:

P — вероятность принять измененное решение,

δE — модуль разности между энергией оптимального решения и энергий измененного решения,

T — текущая температура.

Уменьшение температуры

Важной частью алгоритма является уменьшение температуры. При большой температуре вероятность выбора менее оптимального решения высока. Однако, в процессе работы алгоритма температура снижается, и вероятность выбора менее оптимального решения снижается.

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

Выбор начальной и пороговой температуры

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

Области применения:

1. Создание пути

2. Реконструкция изображения

3. Назначение задач и планирование

4. Размещение сети

5. Глобальная маршрутизация

6. Обнаружение и распознавание визуальных объектов

7. Разработка специальных цифровых фильтров

При помощи моделирования такого процесса ищется такая точка или множество точек, на котором достигается минимум некоторой числовой функции , где . Вводится последовательность точек пространства X. Алгоритм последовательно находит следующую точку по предыдущей, начиная с точки , которая является начальным приближением. Алгоритм останавливается по достижении точки .

Точка по алгоритму получается на основе текущей точки следующим образом. К точке применяется оператор Α, который случайным образом модифицирует соответствующую точку, в результате чего получается новая точка . Точка становится точкой с вероятностью , которая вычисляется в соответствии с распределением Гиббса:

Здесь Qi > 0 — элементы произвольной убывающей, сходящейся к нулю положительной последовательности, которая задаёт аналог падающей температуры в кристалле. Скорость убывания и закон убывания могут быть заданы по желанию создателя алгоритма.

Алгоритм имитации отжига похож на градиентный спуск, но за счёт случайности выбора промежуточной точки должен будет попадать в локальные минимумы реже, чем градиентный спуск. Алгоритм имитации отжига не гарантирует нахождения минимума функции, однако при правильной политике генерации случайной точки в пространстве X, как правило, происходит улучшение начального приближения.

Метод моделируемого отжига широко применяется в обработке и распознавании изображений. Известно, однако, что моделируемый отжиг не определяет однозначно алгоритм отыскания глобального оптимума, а лишь указывает, что искомый алгоритм принадлежит обширному классу алгоритмов, отличающихся друг от друга процессом изменения специального параметра - так называемой "температуры " отжига. Только при определенной зависимости этой температуры от времени алгоритмы моделируемого отжига обеспечивают сходимость к глобальному максимуму оптимизируемой функции.

Эвристика

Эвристика (др. греч ευρίσκω «отыскиваю», «открываю») — наука, изучающая творческую деятельность, методы, используемые при открытии новых концептов, идей и взаимосвязей между объектами и совокупностями объектов, а также методики процесса обучения. Эвристические методы (другое название эвристики) позволяют ускорить процесс решения задачи.

Эвристикой, в зависимости от контекста, называют

· эвристический алгоритм, представляющий совокупность приёмов в поиске решения задачи, которые позволяют ограничить перебор;

· способ обучения, берущий свои истоки от сократовской майевтики.

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

Основным назначением эвристики является построение моделей процессов решения какой-либо новой задачи. Существуют следующие типы таких моделей:

· модель слепого поиска, которая опирается на так называемый метод проб и ошибок;

· лабиринтная модель, в которой решаемая задача рассматривается как лабиринт, а процесс поиска решения — как блуждание по лабиринту;

· структурно-семантическая модель, которая считается в настоящее время наиболее содержательной и которая отражает семантические отношения между объектами, входящими в задачу.

Целевая функция

Функция, связывающая цель (оптимизируемую переменную) с управляемыми переменными в задаче оптимизации.

В широком смысле целевая функция есть математическое выражение некоторого критерия качества одного объекта (решения, процесса и т.д.) в сравнении с другим. Примером критерия в теории статистических решений является, например, среднеквадратический критерий точности аппроксимации. Цель – найти такие оценки, при которых целевая функция достигает минимума.

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

Транзакция

Транза́кция (англ. transaction) — в информатике, группа последовательных операций, которая представляет собой логическую единицу работы с данными. Транзакция может быть выполнена либо целиком и успешно, соблюдая целостность данных и независимо от параллельно идущих других транзакций, либо не выполнена вообще и тогда она не должна произвести никакого эффекта. Транзакции обрабатываются транзакционными системами, в процессе работы которых создаётся история транзакций.

Различают последовательные (обычные), параллельные и распределённые транзакции. Распределённые транзакции подразумевают использование больше чем одной транзакционной системы и требуют намного более сложной логики (например, two-phase commit — двухфазный протокол фиксации транзакции). Также, в некоторых системах реализованы автономные транзакции, или под-транзакции, которые являются автономной частью родительской транзакции.

Пример: Необходимо перевести с банковского счёта номер 5 на счёт номер 7 сумму в 10 денежных единиц. Этого можно достичь, к примеру, приведённой последовательностью действий:

Начать транзакцию

прочесть баланс на счету номер 5

уменьшить баланс на 10 денежных единиц

сохранить новый баланс счёта номер 5

прочесть баланс на счету номер 7

увеличить баланс на 10 денежных единиц

сохранить новый баланс счёта номер 7

Окончить транзакцию

Эти действия представляют собой логическую единицу работы «перевод суммы между счетами», и таким образом, являются транзакцией. Если прервать данную транзакцию, к примеру, в середине, и не аннулировать все изменения, легко оставить владельца счёта номер 5 без 10 единиц, тогда как владелец счета номер 7 их не получит.

В идеале транзакции разных пользователей должны выполняться так, чтобы создавалась иллюзия, что пользователь текущей транзакции — единственный. Однако в реальности, по соображениям производительности и для выполнения некоторых специальных задач, СУБД предоставляют различные уровни изоляции транзакций. Уровни описаны в порядке увеличения изоляции транзакций и надёжности работы с данными

• 0 — Неподтверждённое чтение (Read Uncommited, Dirty Read, грязное чтение) — чтение незафиксированных изменений своей транзакции и конкурирующих транзакций, возможны нечистые, неповторяемые чтения и фантомы


• 1 — Подтверждённое чтение (Read Commited) — чтение всех изменений своей транзакции и зафиксированных изменений конкурирующих транзакций, нечистые чтения невозможны, возможны неповторяемые чтения и фантомы


• 2 — Повторяемое чтение (Repeatable Read ,Snapshot) — чтение всех изменений своей транзакции, любые изменения, внесённые конкурирующими транзакциями после начала своей недоступны, нечистые и неповторяемые чтения невозможны, возможны фантомы


• 3 — Упорядоченный — (Serializable, сериализуемый) — упорядоченные (сериализуемые) транзакции. Идентичен ситуации при которой транзакции выполняются строго последовательно одна после другой. То есть транзакции, результат действия которых не зависит от порядка выполнения шагов транзакции (запрещено чтение всех данных изменённых с начала транзакции, в том числе и своей транзакцией). Фантомы невозможны.

Чем выше уровень изоляции, тем больше требуется ресурсов, чтобы их поддерживать.

В СУБД уровень изоляции транзакций можно выбрать как для всех транзакций сразу, так и для одной конкретной транзакции. По умолчанию в большинстве баз данных используется уровень 1 (Read Commited). Уровень 0 используется в основном для отслеживания изменений длительных транзакций или для чтения редкоизменяемых данных. Уровни 2 и 3 используются при повышенных требованиях к изолированности транзакций.

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

Первые коммерческие СУБД (к примеру, IBM DB2), пользовались исключительно блокировкой доступа к данным для обеспечения свойств ACID. Но большое количество блокировок приводит к существенному уменьшению производительности. Есть два популярных семейства решений этой проблемы, которые снижают количество блокировок: Журнализация изменений (write ahead logging, WAL) и механизм теневых страниц (shadow paging)^[2]
. В обоих случаях, блокировки должны быть расставлены на всю информацию, которая обновляется. В зависимости от уровня изоляции и имплементации, блокировки записи также расставляются на информацию, которая была прочитана транзакцией.

При упреждающей журнализации, используемой в Sybase и MS SQL Server до версии 2005, все изменения записываются в журнал, и только после успешного завершения — в базу данных. Это позволяет СУБД вернуться в рабочее состояние после неожиданного падения системы. Теневые страницы содержат копии тех страниц базы данных на начало транзакции, в которых происходят изменения. Эти копии активизируются после успешного завершения. Хотя теневые страницы легче реализуются, упреждающая журнализация более эффективна.

Дальнейшее развитие технологий управления базами данных привело к появлению безблокировочных технологий. Идея контроля за параллельным доступом с помощью временных меток (timestamp-based concurrency control) была развита и привела к появлению многоверсионной архитектуры MVCC. Эти технологии не нуждаются ни в журнализации изменений, ни в теневых страницах. Архитектура, реализованная в Oracle 7.х и выше, записывает старые версии страниц в специальный сегмент отката, но они все ещё доступны для чтения. Если транзакция при чтении попадает на страницу, временная метка которой новее начала чтения, данные берутся из сегмента отката (то есть используется «старая» версия). Для поддержки такой работы ведётся журнал транзакций, но в отличие от «упреждающей журнализации», он не содержит данных. Работа с ним состоит из трёх логических шагов:

1. Записать намерение произвести некоторые операции


2. Выполнить задание, копируя оригиналы изменяемых страниц в сегмент отката


3. Записать, что всё сделано без ошибок

Журнал транзакций в сочетании с сегментом отката (область, в которой хранится копия всех изменяемых в ходе транзакции данных) гарантирует целостность данных. В случае сбоя запускается процедура восстановления, которая просматривает отдельные его записи следующим образом:

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


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


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

Firebird вообще не имеет ни журнала изменений, ни сегмента отката, а реализует MVCC, записывая новые версии строк прямо в активное пространство данных. Также поступает MS SQL 2005. Теоретически это даёт максимальную эффективность при параллельной работе с данными, но ценой является необходимость «сборки мусора», то есть удаления старых и уже не нужных версий строк.

Для реализации самой программы мне необходимо было изучить язык программирования Delphi, так как раньше мне не приходилось с ним работать. Я выбрала именно этот язык, потому что считаю, что в настоящее время он очень востребован, и изучить его будет для меня очень полезно. Среда разработки - Borland Developer Studio 2006. Изучением языка я занималась в течение года, и продолжаю этим заниматься до сих пор. Также я изучила такие программы как PowerDesigner, Firebird и IBExpert.

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

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

Во-вторых, программа должна включать реализацию следующих запросов: получение информации по каждому учителю, по каждому классу, по каждому кабинету.

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

Расписание должно создаваться для каждого класса отдельно. Нужно учесть следующие параметры:

- начальная школа не учится по субботам

- максимальное количество уроков в день (начальное звено – 5 уроков, среднее и старшее звено – 6 уроков)

- балловая система предметов

- отсутствие сдвоенных уроков в начальной и средней школе

- чередование предметов точного и гуманитарного характера

- ход дневной и недельной умственной работоспособности

- пожелания учителей, у каждого должен быть методический день

- основная учебная нагрузка должна приходиться на 2,3,4 уроки (по балловой системе)

- необходимо учитывать что в каждом классе на уроках английского, трудов и физкультуры (в старших классах) класс делится на 2 подгруппы

Вид расписания предполагается представить в таком же виде, как показано в приложении 1.

Я планирую реализовать формирование таблиц с расписанием и балловой системой для каждого класса (приложение 6), а также зарисовку соответствующих схем (приложение 7).

2) Следующим шагом в реализации моей программы стала разработка реляционной схемы данных. Для этой цели я использовала программу PowerDesigner.

Спроектированные реляционные таблицы:

Таблица TEACHER – список учителей

Таблица SEX – пол

Таблица METHODIC_DAY – методические дни

Таблица CLASS_GUIDANCE – классное руководство

Таблица SUBJECT – список предметов

Таблица TEACHING_LOAD – преподавательская нагрузка

Таблица CLASS – список классов

Таблица SCHOOL_HALF_YEAR – школьное полугодие

Таблица STUDY_PLAN – учебный план

Таблица SUBJECT_POINTS – баллы предметов

Таблица CLASS_ROOM – кабинеты

Таблица TIME_TABLE – расписание

Схема реляционной базы данных:

3) Следующей моей задачей была разработка самой программы с удобным пользовательским интерфейсом. Для реализации этой задачи решено было использовать среду разработки Borland Developer Studio 2006, язык программирования – Delphi. Раньше мне не приходилось работать в этой среде и писать на этом языке, но я всегда хотела его освоить. Достаточно много времени ушло на изучение Delphi.

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

Выбирая в меню «Предметы», получаем:

Следующая форма появляется при выборе в меню пункта «Учителя»:

При желании возможно добавление нового учителя в список учителей:

Аналогично выглядит форма со списком классов:

По реляционной модели данных видно, что для учителя определяется большое количество параметров, таких как: методический день, классное руководство и нагрузка. Для удобства на форме «Учителя» была создана кнопка «Дополнительно», нажав на которую пользователь получает доступ к вышеуказанным параметрам, например:

По сути, процесс составления расписания – оптимизационная задача, поэтому для её решения я использую метод моделируемого отжига – один из интереснейших методов решения оптимизационных задач. Сейчас моя программа находится на стадии выявления целевой функции и решения оптимизационной задачи методом моделируемого отжига.

4) Ознакомление с программами, подобными моей работе, на мой взгляд, очень важно. Я почерпнула для себя много нового из программы ASCTimetable, пожалуй, самой распространенной, судя по отзывам в интернете. К сожалению, других подобных программ мне не удалось скачать. Вообще, эти программы дорогое удовольствие! ASCTimetable в бесплатном режиме доступна только на ограниченный промежуток времени. Моя школа не в состоянии приобрести подобную программу.

ASCTimetable показалась мне довольно легкой в пользовании, хотя к ней необходимо привыкнуть, ведь она включает в себя очень много параметров, хотя не могу сказать, что среди них есть лишние. Для своей программы я позаимствовала несколько важных условий для создания расписания из ASCTimetable. Мне очень понравился интерфейс программы: очень яркий и наглядный.

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

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

Мне очень понравилась система организации рабочего времени учителя. Хотелось бы взять её на заметку для моей программы.

К сожалению, я не могу просмотреть код ASCTimetable, но меня неприятно удивило составленное этой программой расписание.

Заключение

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

Список используемой литературы

1) В.В.Фараонов, П.В.Шумаков Delphi5 Руководство разработчика баз данных, Москва, «Нолидж», 2001

2) http://zdd.1september.ru/2006/08/5.htm - наука составлять расписание

3) http://ru.wikipedia.org/wiki/Database