Проект по математике · 10–11 класс

Модель школьного расписания без накладок на основе раскраски графа

Предмет
Математика
Тема
Математика вокруг нас
Класс
10–11 класс
Вид работы
Проект

Идея

Представьте уроки как вершины графа, а конфликты (один учитель, один класс) как рёбра. Составьте программу или таблицу, которая раскрашивает граф и распределяет уроки по времени без накладок. Проверьте её на упрощённых данных и сравните число занятых уроками слотов с ручным расписанием.

Задача

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

План работы

  1. Изучите, что такое граф и правильная раскраска, и переведите задачу расписания на этот язык.
  2. Подготовьте упрощённые данные без имён: 3–5 классов, 6–10 учителей под условными номерами и число уроков в неделю.
  3. Постройте граф конфликтов и реализуйте жадную раскраску вершин с разным порядком обхода.
  4. Добавьте хотя бы одно условие: не больше 6 уроков в день или ограничения по кабинетам.
  5. Сравните число временных слотов при разном порядке вершин и проверьте, нет ли накладок, отдельной функцией.
  6. Оформите инструмент с описанием входных данных и покажите результат завучу или учителю, запишите замечания.

Что понадобится

Компьютер с Python или электронными таблицами, учебные материалы по теории графов, обезличенные данные о нагрузке классов (с разрешения школы).

Что получится

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

Частые ошибки

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

Теги

Тему и план подготовили эксперты фестиваля. Это отправная точка: вопрос, объём опытов и вывод можно менять под себя и вместе с руководителем.

Пишете работу? Пришлём шаблон в Word: все разделы с подсказками, что писать в каждом, и оформление по положению фестиваля.

Похожие работы участников

Все работы школьников по математике

Ещё темы по математике

10–11 класс Исследование

Математическая модель очереди в столовой

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

10–11 класс Исследование

Насколько правило ближайшей точки уступает лучшему маршруту доставки

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

10–11 класс Исследование

Фракталы: бесконечная геометрия природы

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

Все темы проектов по математике

Сделали работу по этой теме? Пришлите её на фестиваль

Принимаем исследовательские, проектные и научно-творческие работы учащихся 1–11 классов. Эксперты оценят работу, финалисты защищают её онлайн перед жюри.