Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://www.mccme.ru/dubna/2004/courses/vyalyi.html
Дата изменения: Thu Apr 21 21:10:31 2005 Дата индексирования: Sat Dec 22 15:09:35 2007 Кодировка: koi8-r Поисковые слова: п р п р п р п р п р п р п |
Михаил Николаевич Вялый планирует провести 4 занятия.
Основной задачей, которая будет обсуждаться, является подсчет укладок домино на прямоугольную доску. Для этой задачи есть замечательный ответ, выражающий искомое число укладок через длины диагоналей правильных многоугольников. Для получения этого ответа потребуется интригующая смесь комбинаторики, топологии и линейной алгебры.
Речь пойдет в основном про многочлены, известные как детерминант, пфаффиан и перманент. В качестве побочной темы планируется обсудить сложность вычисления этих многочленов. Будет сделана попытка объяснить, почему вычисление детерминанта — простая задача, а вычисление перманента — сложная. Будет также объяснено, почему подсчет числа паросочетаний в графе значительно упрощается, если граф можно нарисовать на плоскости без самопересечений.
Знание линейной алгебры сильно упрощает понимание этого курса, но не является обязательным для понимания почти всех затрагиваемых в нем вопросов.