Лекция Дональда Кнута о рождественской елке 2017

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

По традиции Стэнфордского университета в декабре Дональд Кнут надевает яркий джемпер и читает публичную лекцию, в которой, если это вообще возможно, используется та или иная древовидная структура. Этот год кажется еще одним годом без деревьев, поэтому я полагаю, что это должна быть лекция, не посвященная рождественским деревьям. Это называется «Гипотеза, которая должна была быть верной», но ее настоящая ценность в том, что она дает вам некоторое представление о том, что такое математические исследования.

Рекламное объявление о мероприятии гласит:

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

Проблема очень проста и начинается с разделения прямоугольника на другие меньшие прямоугольники – проблема Мондриана? Например:

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

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

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

Всякий раз, когда вы получаете такую комбинаторную компоновку, всегда возникает вопрос: «Сколько существует возможностей?». В этом случае представляет интерес вопрос «сколько там плотных дорожных покрытий?». Плотное покрытие – это укороченное покрытие с минимальным количеством прямоугольников. Оказывается, что для компоновки n x m наименьшее количество прямоугольников в уменьшенной компоновке равно n + m-1. Таким образом, плотное покрытие – это такое покрытие, в котором используется n + m-1 прямоугольников, но сколько их существует для любого n x m?

Кнут приводит в видео примеры для 2 x 2, 3 x 2, чтобы вы могли понять идею. Конечно, по мере увеличения размера вы должны использовать компьютер, и именно поэтому возникла гипотеза о взаимосвязи между n, m и количеством плотных дорожных покрытий.

А теперь посмотрите видео – это как раз мощь математики.

Если вы знаете, кто такой Дональд Кнут, перейдите к 1:45, чтобы избежать знакомства.

В этом видео так много интересного, но именно медленный прогресс от конкретного к абстрактному очень интересен и показывает, как математическое мышление прекрасно работает.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *