Проект по математике · 10–11 класс
Модель школьного расписания без накладок на основе раскраски графа
- Предмет
- Математика
- Тема
- Математика вокруг нас
- Класс
- 10–11 класс
- Вид работы
- Проект
Идея
Представьте уроки как вершины графа, а конфликты (один учитель, один класс) как рёбра. Составьте программу или таблицу, которая раскрашивает граф и распределяет уроки по времени без накладок. Проверьте её на упрощённых данных и сравните число занятых уроками слотов с ручным расписанием.
Создать программу или таблицу, которая составляет расписание для нескольких классов без накладок, используя раскраску графа.
План работы
- Изучите, что такое граф и правильная раскраска, и переведите задачу расписания на этот язык.
- Подготовьте упрощённые данные без имён: 3–5 классов, 6–10 учителей под условными номерами и число уроков в неделю.
- Постройте граф конфликтов и реализуйте жадную раскраску вершин с разным порядком обхода.
- Добавьте хотя бы одно условие: не больше 6 уроков в день или ограничения по кабинетам.
- Сравните число временных слотов при разном порядке вершин и проверьте, нет ли накладок, отдельной функцией.
- Оформите инструмент с описанием входных данных и покажите результат завучу или учителю, запишите замечания.
Что понадобится
Компьютер с Python или электронными таблицами, учебные материалы по теории графов, обезличенные данные о нагрузке классов (с разрешения школы).
Что получится
Рабочая программа или таблица, составляющая расписание, описание математической модели, сравнение порядков обхода по числу слотов и отзыв учителя о том, что модель не учитывает.
Частые ошибки
- Сразу брать всю школу вместо небольшой модели, которую можно проверить вручную
- Не проверять итоговое расписание на накладки отдельной проверкой
- Использовать настоящие имена учителей в опубликованных таблицах
Теги
Тему и план подготовили эксперты фестиваля. Это отправная точка: вопрос, объём опытов и вывод можно менять под себя и вместе с руководителем.