Главная » Летние и зимние школы » Зимняя школа 2010 » Анонсы курсов и задачи

Анонсы курсов и задачи

Сергей Анисов «Ассорти: задачи на графах»

Для школьника — участника математических олимпиад теория графов — это задачки про рукопожатия, про маршруты из города в город, про двудольные графы и про эйлеровы циклы. Для программиста-практика теория графов — в первую очередь набор инструментов для решения стандартных задач о разбиении на связные компоненты, нахождении расстояний, о поиске в глубину и поиске в ширину. Для программиста-теоретика графы — источник «плохо решаемых», NP-трудных задач.

Теория графов почти бесконечна, и три взгляда на неё, описанные выше, ведут на разные пути её изучения. Если бы эти пути расходились не сразу после основных определений, то и практики, и теоретики, и школьники-олимпиадники узнавали бы факты о графах, которые:|
– с одной стороны, красивы, довольно просты, но всё же слишком «теоретичны», чтобы встретиться в олимпиадной задаче;
– в то же время приводят к эффективным (работающим за полиномиальное время), но не каждый день необходимым алгоритмам.

Этому островку теории графов и посвящён наш курс.

Программа:

– Независимые множества, вершинные покрытия, раскраски, паросочетания.
– Оптимальные каркасы: жадные алгоритмы, матроиды и теорема Радо-Эдмондса
– Теорема о максимальном потоке.


Алексей Яковлевич Белов «Быстрое умножение многозначных чисел, дискретное преобразование Фурье и тензорнный ранг»

Курс посвящен сложности вычислений. Всем известно, как умножать числа в столбик. На первый взгляд кажется, что для умножения $n$-значных чисел нужно $n^2$ элементарных операций. Однако неожиданно в 1960 году А. Карацуба придумал алгоритм делать это за $n^{\log_{2}(3)}$ операций. Позднее Тоом усовершенствовал этот алгоритм.


Виталий Гольдштейн «Амортизационный анализ в примерах»
Наряду с умением придумывать алгоритмы, не менее важным является умение оценивать их время работы.

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

На лекции будут рассмотрены множество примеров более точной оценки времени работы и способов ускорения алгоритмов.

«Теория игр»

Эта лекция для тех, кому уже наскучили обычные игры из-за их медлительности и неторопливости. На лекции мы рассмотрим теорию, позволяющую анализировать игры сразу на нескольких досках. Благодаря теории Шпрага-Гранди (и ее обобщения Смита) стал возможен анализ игр с огромным количеством возможных позиций. Многие слышали про игру Ним; оказывается, что огромный класс этих игр и есть не что иное, как пресловутый Ним.

«Как работают Яндекс.Пробки»
На лекции будет рассказана общая концепция алгоритмов, используемых для определения затруднений на дорогах. Вы узнаете, какие данные для этого используются, какие трудности встречаются при обработке данных. Так же мы подробно рассмотрим актуальный алгоритм привязки точек графа для определения маршрута следования машины. В популярной форме будет рассказан наиболее точный из существующих алгоритмов, предложенный китайскими учеными в ноябре 2009 года.


Дмитрий Ильинский «Диаграммы Юнга»

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


Григорий Анатольевич Кабатянский «О задачах поиска»

Все мы хорошо знаем, как искать одно загаданное число, скажем, от 1 до $2^n$ — разделить область пополам и спросить, в какой половине число, затем ту половину, где находится число, снова поделить пополам, задать вопрос и т.д. Этот алгоритм — адаптивный (или с обучением), т.е. использует информацию, полученную на предыдущих шагах алгоритма. Но можно придумать и неадаптивный алгоритм, когда все n вопросов задаются сразу, не дожидаясь ответов, а по ответам число находится однозначно.
Придумайте такой алгоритм — и вы придумаете известный код Хэмминга!

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


Станислав Кикоть «Логика игр Джапаридзе и другие неклассические логики»

К настоящему времени известно несколько сотен, если не тысяч, разных неклассических логик. Я хочу рассказать, откуда они берутся, как и зачем их строить,
что такое синтаксис и семантика логики, и что такое логика вообще.

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


Виталий Кошелев «Happy Ending Problem»
Сколько точек на плоскости будет достаточно, чтобы среди них всегда можно было найти выпуклый многоугольник на заданном числе вершин?

Этот вопрос был впервые поставлен 75 лет назад группой знаменитых венгерских математиков (и с этим связана отдельная красивая история). Простота постановки задачи привлекала очень большое количество исследователей, но тем не менее, до конца задача не решена до сих пор. Как бы то ни было, за прошедшее время появилось очень много обобщений и близких задач. Я расскажу о текущих достижениях и, в том числе, о совсем новых результатах.


Даниил Мусатов «Чего не могут компьютеры»

Бытует распространённое заблуждение, что «компьютеры могут всё», т.е. с их помощью если не сейчас, то в недалёком будущем можно решить любую задачу. Однако, ещё до создания современной вычислительной техники были установлены пределы её возможностей. Примером неразрешимой задачи является анализ другой программы: нельзя алгоритмически проверить, вычисляет ли данная программа заданную функцию или нет (если, конечно, не накладывать ограничений на время работы; в том числе поэтому в соревнованиях по программированию такое ограничение всегда есть). В ходе курса мы познакомимся со свойствами разрешимых задач и увидим несколько примеров задач неразрешимых, возникающих как внутри теории алгоритмов, так и в других областях математики.


Андрей Михайлович Райгородский «Случайные графы и вероятность в комбинаторике»

В комбинаторике есть огромное количество задач, которые крайне просто формулируются и, тем не менее, с трудом поддаются решению. Зачастую вероятность оказывается единственным средством для штурма таких задач. В рамках курса слушатели познакомятся с базовыми объектами и инструментами теории вероятностей, а также с рядом красивых примеров применения вероятностных методов при решении комбинаторных задач. Отдельное внимание мы уделим понятию «случайного графа». А именно, мы с «вероятностной точки зрения» посмотрим на хорошо всем известные свойства графов, и такой взгляд даст нам принципиально новое понимание теоретико-графовых задач.


Денис Расковалов «Основы машинного обучения»

Человек может решать нестандартные слабоформализованные задачи. Компьютер умеет проделывать миллиарды операций в секунду. Давняя мечта — научить компьютер решать слабоформализованные задачи. Курс будет посвящен теории и практике машинного обучения, которое позволяет компьютерам решать столь слабоформализованные задачи, как оценка релевантности страницы, распознавание рукописного текста, распознавание речи.

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


Михаил Абрамович Ройтберг «Как найти кратчайший путь, или метод динамического программирования»

Вот задача (несложная): найти сумму миллиона слагаемых $а_1b_1 + \ldots + a_{1}b_{1000} + a_2b_1 + \ldots + a_{1000}b_{1000}$ за не более чем 10000 операций.
Решение этой задачи даёт ключ к эффективному алгоритму поиска кратчайшего пути в графе. К этому же алгоритму сводятся многие задачи из различных областей естествознания.

Речь идёт об одном из важнейших методов построения алгоритмов – методе динамического программирования, который был сформулирован Р. Беллманом около пятидесяти лет назад.

Будет рассказан метод динамического программирования и описаны его приложения к задачам биоинформатики и физики (анализа ДНК и белков). Будут рассказано о связи этого метода с высшей алгеброй (понятием полукольца).


Александр Рябченко «Программирование на RAM-машине»

RAM — аббревиатура от Random Access Memory. RAM-машина — формализм математических вычислений, который можно назвать упрощенным ассемблером, и очень близкий к нему по духу.
В ходе курса слушатели напишут несколько программ на эмуляторе RAM-машины, в том числе стековый калькулятор, а также получат представление о том, как осуществляются вычисления на низком уровне в современных компьютерах, и узнают о некоторых идеях алгоритмов работы программ на ассемблере.

Если хватит времени, мы докажем также вычислительную эквивалентность RAM-машины и машины Тьюринга.


Алексей Владимирович Савватеев «Теоретико-игровой подход в лингвистике»


Александр Чуклин «Языки, автоматы и регулярные выражения»

Каждый из вас знает, что такое алфавит, слово, язык. Мы же попробуем придать этим словам математическую строгость, доказать несколько красивых теорем и порешать задачи. Также мы познакомим вас с понятием конечного автомата и расскажем несколько связанных с этим понятием алгоритмов поиска подстроки в строке.


Владимир Шарич «Взгляд на теорию Галуа сквозь замочную скважину»

– Все знают формулу для корней квадратного уравнения; многие слышали про формулу для корней кубического уравнени. А какова формула для корней уравнения пятой степени?

– Все умеют делить угол пополам или на четыре равные части. А на три? Или пять?

– Все умеют решать дифференциальное уравнение $y”+y=0$: решения — это синус, косинус, а также любая функция вида $A\sin(x)+B\cos(x)$. А как насчет уравнения $y”+xy=0$?

Я не расскажу решения ни одной из этих или похожих известных задач.
Я расскажу об идеях, о точке зрения, о наблюдениях, приведших к успеху.

О теории Галуа.
Эварист Галуа (1811-1832) пробыл несколько месяцев в тюрьме за участие в революционном движении и погиб на дуэли, причиной которой была девушка.