Старт в науке
Научный журнал для школьников ISSN 2542-0186
О журнале Выпуски Правила Олимпиады Учительская Поиск Личный портфель

ЗАДАЧА О РЮКЗАКЕ И АЛГЕБРА ЛОГИКИ В ЗАДАЧЕ СОСТАВЛЕНИЯ ШКОЛЬНОГО РАСПИСАНИЯ

Ковалева Е.А. 1
1 г. Липецк, МАОУ СОШ №59 «Перспектива», 7 класс
Хабибуллина Е.Л. (Липецк, ЛГТУ)
Меньщикова Т.В. (Липецк, МАОУ СОШ №59 «Перспектива»)
1. Информатика. 8 класс: учебник / Л.Л. Босова, А.Ю. Босова. – М.: БИНОМ. Лаборатория знаний.
2. Зепнова Н.Н., Кузьмин О.В. Применение методов дискретной математики при решении логических задач // Омский научный вестник. – 2014. – №2 (130). – С.14–17.
3. Санитарные правила ст. 28 Федерального закона «О санитарно-эпидемиологическом благополучии населения» программы, методики и режимы воспитания и обучения в части гигиенических требований.

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

Цель исследования: проверить, ускорит ли процесс составления расписания, соответствующего нормам СанПиН, использование математических методов. Но, так задача составления расписания относится к NP-сложным задачам, в первый год работы над этой темой было решено решить задачу составления расписания только для одного класса: 7 «А».

Требуется решить следующие задачи:

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

2. Изучение пожеланий учителей для составления расписаний.

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

4. Определение порядка учебных предметов в каждый из дней учебной недели (методы алгебры логики).

5. Анализ получившегося расписания.

Требования к расписанию в школе

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

Работоспособность учащихся в разные дни учебной недели отличается. Уровень работоспособности растет к середине недели и остается низким в понедельник и в пятницу. Распределение учебной нагрузки в течение недели строится так, чтобы наибольший объем приходился на вторник и четверг в 1–7 классах, (среда немного облегченный день). В эти дни в расписание уроков включаются либо наиболее трудные предметы, либо средние и легкие, но в большем количестве.

В 10–12 часов происходит наибольшая эффективность усвоения материала при наименьших психофизических затратах организма.

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

В таблице приведена шкала трудности учебных предметов для учеников седьмых классов по 13-балльной шкале М.И. Степановой, И.Э. Александровой, А.С. Седовой [3], а также – количество часов в неделю.

Суммарная трудоемкость в неделю: 234 единицы.

На рис. 1 приведено наилучшее место предметов в течение учебного дня согласно СанПиН [3].

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

В первую очередь при составлении расписания необходимо распределить предметы по дням.

Шкала трудности учебных предметов, изучаемых в седьмом классе

Предмет

Трудность

Количество часов/неделю

Русский язык

11

4

Литература

4

2

Английский язык

10

5

Алгебра

10

3

Геометрия

12

2

История

6

2

Обществознание

9

1

География

6

2

Биология

7

2

Музыка

1

1

ИЗО

1

1

Физкультура

2

2

Физика

8

2

Технология

2

1

Информатика

4

1

ОБЖ

3

1

kov1.tiff

Место предметов в расписании в течение дня согласно СанПиН

Распределение учебных предметов по дням недели

Для этого рассмотрим эту задачу как аналог задачи о рюкзаке 0–1: учебные предметы – предметы, которые можно положить в рюкзак; их трудность – вес предмета; максимальная разрешенная трудоемкость – вместимость рюкзака (в кг); ценность предметов – одинаковая (нам нужно найти возможные варианты наполнения рюкзака).

Для решения этой задачи воспользуемся методом ветвей и границ: на двумерной плоскости по оси Х откладывается количество предметов, по оси Y – их вес. На первом шаге из начала координат строятся две линии: горизонтальная, соответствующая тому, что первый предмет не был взят, и наклонная, соответствующая взятому первому предмету. Их проекции на ось Y равны весу предмета. На втором шаге опять строятся две линии, горизонтальная (второй предмет не был взят) или наклонная (второй предмет взят). Ограничим прямыми возможный диапазон трудности (от 35 до 60 единиц). В приложении 1 на рисунке 1 представлена сеть, иллюстрирующая наполнение рюкзака. В приложении 1 на рисунке 2 представлена сеть, иллюстрирующая наполнение рюкзака, но без вариантов с суммарной трудностью меньше 35 единиц.

По представленным рисункам можно убедиться, что вариантов распределения по дням достаточно много. Но нам известно, что распределение трудности должно «иметь два горба»: максимальную трудоемкость во вторник и четверг, среда должна быть облегченным днем, а понедельник и пятница – легкими.

Совместно с руководством школы была распределена суммарная трудность по дням недели: понедельник – 40 единиц, вторник – 58 единиц, среда – 42 единиц, четверг – 50 единиц и пятница – 44 единиц.

Для нахождения всех вариантов предметов (без учета порядка уроков) была написана программа «Комбинатор». Программа написана на языке С++ в среде разработки MS Visual Studio 2015. Так как программа пока используется лишь как вспомогательный инструмент, облегчающий задачу распределения предметов по дням, интерфейс для взаимодействия с пользователем не разрабатывался. Всего в 7 «А» 16 учебных предметов; предполагается, что два одинаковых урока в день нежелательно.

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

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

Так как каждый предмет мы можем включить или не включить в расписание, то будем сопоставлять предмету «0» (если не включаем в расписание) или «1» (если включаем расписание).

Тогда задача сводится к перебору всех шестнадцатиразрядных двоичных чисел: от 0000 0000 0000 0000 (соответствует 0 в десятичной системе счисления) до 1111 1111 1111 1111 (соответствует 216–1=65 535 в десятичной системе счисления). Из всех вариантов будем рассматривать только те, где количество единиц равно 6 или 7 (в зависимости от количества уроков в день). Если количество единиц нужное, то проверим суммарную трудоемкость: найдем сумму элементов массива «трудоемкость», соответствующих единицам в проверяемом варианте. Если трудоемкость равна искомой, то выведем текущую комбинацию предметов в файл (выводятся значения элементов массива, соответствующие единицам в проверяемом варианте), иначе перейдем к следующему числу.

При помощи программы «Комбинатор» предметы в расписании (без учета номера урока) были распределены следующим образом.

Понедельник: Литература, Английский язык, Физика, Биология, Изо, Алгебра. Трудность: 40 единиц.

Вторник: Геометрия, Русский язык, Английский язык, Обществознание, История, География, Информатика. Трудность: 58 единиц.

Среда: Физика, Русский язык, Алгебра, Английский язык, Музыка, Физическая культура. Трудность: 42 единиц.

Четверг: Русский язык, Английский язык, География, История, Литература, ОБЖ, Алгебра. Трудность: 50 единиц.

Пятница: Геометрия, Русский язык, Биология, Английский язык, Физическая культура, Технология. Трудность: 44 единиц.

Определение порядка учебных предметов

Для составления распределения предметов по порядку на отдельный день воспользуемся методами алгебры логики[1]. Составим логические формулы, соответствующие заявкам учителей и СанПиН. Индекс переменной обозначает номер урока в расписании. Возможные варианты положения предмета в расписании соединим дизъюнкцией. Формулы для каждого предмета объединим в одну формулу, соответствующую дню, соединим конъюнкцией [2]

Понедельник

В табл. 3 приложения 3 приведены предметы, их обозначения в формуле, пожелания учителя и рекомендации СанПиН.

Формула, соответствующая требованиям к расписанию на понедельник, будет записана следующим образом:

ko1.wmf

Упростим выражения при помощи программы Maxima и оставим только те варианты, где номера уроков разные. Всего получилось 26 вариантов. Некоторые из них приведены ниже:

1. Алгебра; Изо; Английский язык; Биология; Физика; Литература.

2. Изо; Алгебра; Английский язык; Литература; Физика; Биология.

Вторник

В табл. 4 приложения 3 приведены предметы, их обозначения в формуле, пожелания учителя и рекомендации СанПиН.

Формула, соответствующая требованиям к расписанию на вторник, будет записана следующим образом:

ko2.wmf

Было получено 6 вариантов. Некоторые из них приведены ниже:

1. Геометрия; Информатика; Обществознание; Русский язык; Английский язык; История; География.

2. Обществознание; Геометрия; Информатика; Русский язык; Английский язык; История; География.

Среда

В таблице 5 (приложение 3) приведены предметы, их обозначения в формуле, пожелания учителя и рекомендации СанПиН.

Формула, соответствующая требованиям к расписанию на среду, будет записана следующим образом:

ko3.wmf

Было получено 2 варианта. Они приведены ниже:

1. Алгебра; Русский язык; Английский язык; Физика; Физическая культура; Музыка.

2. Алгебра; Русский язык; Физика; Английский язык; Физическая культура; Музыка.

Четверг

В таблице 6 (приложение 3) приведены предметы, их обозначения в формуле, пожелания учителя и рекомендации СанПиН.

Формула, соответствующая требованиям к расписанию на среду, будет записана следующим образом:

ko4.wmf

Было получено 26 вариантов. Некоторые из них приведены ниже:

1. Алгебра; География; Английский язык; Русский язык; История; Литература; ОБЖ.

2. Алгебра; История; Английский язык; Русский язык; Литература; География; ОБЖ.

3.5 Пятница

В таблице 7 (приложение 3) приведены предметы, их обозначения в формуле, пожелания учителя и рекомендации СанПиН.

Формула, соответствующая требованиям к расписанию на среду, будет записана следующим образом:

ko5.wmf

Было получено 10 вариантов. Некоторые из них приведены ниже:

1. Геометрия; Русский язык; Английский язык; Биология; Физическая культура; Технология.

2. Технология; Геометрия; Английский язык; Русский язык; Физическая культура; Биология.

В задаче составления расписания необязательно требуется найти «идеальное решение», достаточно найти «очень хорошее» решение: выберем для каждого дня любой такой вариант, чтобы чередовались предметы естественно-математического профиля с гуманитарными предметами. Таким образом, было составлено расписание для 7 «А» класса.

Пн: Изо; Алгебра; Английский язык; Физика; Литература; Биология.

Вт: Обществознание; Геометрия; Информатика; Русский язык; Английский язык; История; География.

Ср: Алгебра; Русский язык; Физика; Английский язык; Физическая культура; Музыка

Чт: Алгебра; История; Английский язык; Русский язык; Литература; География; ОБЖ.

Пт: Технология; Геометрия; Русский язык; Биология; Английский язык; Физическая культура.

Анализ получившегося расписания

В ходе работы было составлено расписание для 7А класса. Это расписание является подходящим:

+ трудоемкость предметов в течение учебных дней и недели не превышает допустимую норму;

+ в течение дня учебные предметы распределены так, что чередуются предметы естественно-математического профиля с гуманитарными предметами;

+ на 10–12 часов (3–5 урок) приходятся наиболее сложные учебные предметы;

+ наибольшая учебная нагрузка приходится на вторник и четверг, а среда и пятница являются более легкими днями.

Заключение

В рамках исследовательской работы были изучены требования к составлению расписания; написана программа «Комбинатор», помогающая распределять предметы по дням недели; при помощи методов алгебры логики были найдены все возможные варианты порядка предметов с учетом пожеланий учителей и требований СанПиН; приведен пример одного из вариантов расписания для 7 «А» класса.


Библиографическая ссылка

Ковалева Е.А. ЗАДАЧА О РЮКЗАКЕ И АЛГЕБРА ЛОГИКИ В ЗАДАЧЕ СОСТАВЛЕНИЯ ШКОЛЬНОГО РАСПИСАНИЯ // Старт в науке. – 2017. – № 5-2. ;
URL: https://science-start.ru/ru/article/view?id=875 (дата обращения: 06.07.2022).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074