Задача о раскрасках. Андрей Райгородский
Можно ли любую карту мира раскрасить в 4 цвета так, чтобы соседние страны были разного цвета? Над этой задачей математики бились 124 года — и решили её только с помощью компьютера. Но история раскрасок на этом не заканчивается: жадные алгоритмы, хроматические числа, вероятностный метод — всё это работает сегодня в оптимизации производства и моделировании интернета. Андрей Райгородский — директор Физтех-школы прикладной математики и информатики МФТИ, лауреат премии Президента РФ в области науки, автор 200+ статей и 20 учебников — рассказывает о задачах, которые находятся в самом центре современной дискретной математики. ⏱️ Таймкоды: 0:00 — Вступление, о конференции 2:15 — Начало лекции 4:53 — Проблема четырёх красок 10:34 — Анклавы и эксклавы: когда 4 цветов не хватит 17:12 — Что такое граф 23:01 — История задачи: от Гатри до Аппеля и Хакена 31:26 — Приложения: интернет, соцсети, оптимизация 38:14 — Хроматическое число 43:48 — Почему задача алгоритмически сложная 47:08 — Жадный алгоритм раскраски 54:46 — Завершение 56:22 — Вопросы зрителей Лекция в рамках благотворительной конференции «Математика добра». Андрей Михайлович выбрал фонд развития математики и информатики в МФТИ: https://fund.mipt.ru/capitals/ck6/ Telegram (анонсы и розыгрыши): https://t.me/mathloversclub28 Подробнее о конференции (расписание и бонусы): https://www.notion.so/mathloversclub/2025-2ce28c0e851781988268f5d5e99fb141 Все записи конференции — в нашем профиле на Stepik: https://stepik.org/users/645988571/teach #теорияграфов #комбинаторика #математика #МФТИ #Райгородский
Можно ли любую карту мира раскрасить в 4 цвета так, чтобы соседние страны были разного цвета? Над этой задачей математики бились 124 года — и решили её только с помощью компьютера. Но история раскрасок на этом не заканчивается: жадные алгоритмы, хроматические числа, вероятностный метод — всё это работает сегодня в оптимизации производства и моделировании интернета. Андрей Райгородский — директор Физтех-школы прикладной математики и информатики МФТИ, лауреат премии Президента РФ в области науки, автор 200+ статей и 20 учебников — рассказывает о задачах, которые находятся в самом центре современной дискретной математики. ⏱️ Таймкоды: 0:00 — Вступление, о конференции 2:15 — Начало лекции 4:53 — Проблема четырёх красок 10:34 — Анклавы и эксклавы: когда 4 цветов не хватит 17:12 — Что такое граф 23:01 — История задачи: от Гатри до Аппеля и Хакена 31:26 — Приложения: интернет, соцсети, оптимизация 38:14 — Хроматическое число 43:48 — Почему задача алгоритмически сложная 47:08 — Жадный алгоритм раскраски 54:46 — Завершение 56:22 — Вопросы зрителей Лекция в рамках благотворительной конференции «Математика добра». Андрей Михайлович выбрал фонд развития математики и информатики в МФТИ: https://fund.mipt.ru/capitals/ck6/ Telegram (анонсы и розыгрыши): https://t.me/mathloversclub28 Подробнее о конференции (расписание и бонусы): https://www.notion.so/mathloversclub/2025-2ce28c0e851781988268f5d5e99fb141 Все записи конференции — в нашем профиле на Stepik: https://stepik.org/users/645988571/teach #теорияграфов #комбинаторика #математика #МФТИ #Райгородский