Алексей Яковлевич Белов «Роботы в лабиринтах, конечные автоматы, приспособляемость»
Какую информацию несет утверждение, что 15 июля в центре Сахары дождя не будет? Насколько информативен эксперимент? Какова пропускная способность канала при наличии шума? Мы начнем с олимпиадных задач на взвешивание и кончим обсуждением совершенствования автоматов в средах.
Илья Игоревич Богданов «Связь локального и глобального хроматических чисел графа»
Если мы рассматриваем очень большой граф, обычно его нельзя обозреть целиком; можно обозреть лишь небольшой кусок — окрестность
произвольной вершины. Возникает вопрос: как вязаны свойства этих небольших подграфов со свойствами всего графа?
Мы рассмотрим один аспект этого вопроса — о связи хроматических чисел окрестностей с хроматическим числом всего графа. Вообще говоря, даже если все окрестности ограниченного радиуса двудольны, хроматическое число графа может быть сколь угодно большим; однако для этого требуется, чтобы ф графе было не просто много, а очень много вершин. Оценками этого количества мы и займёмся.
Виталий Гольдштейн «Кратчайшие пути в графе»
На лекциях будут глубоко рассмотрены классические алгоритмы поиска кратчайших путей. Будут рассмотрены различные модификации и обобщения этих алгоритмов. Будет рассмотрены примеры задач, которые могут быть решены несложными модификациями алгоритмов. Будут рассмотрены некоторые интересные свойства деревьев кратчайших путей.
Глеб Геннадьевич Гусев – TBA
Иван Истомин «Центральная догма молекулярной биологии»
Какое событие в жизни наиболее важно для человека?
Рождение? Свадьба? Конечно же, гаструляция!
Из предсмертных мемуаров биолога
Биология стала наукой менее чем сотню лет назад — её предсказательная сила ни в какое сравнение не шла с таковой математики, физики, да пусть даже и химии в те кажущиеся далекими современнику времена! Но когда Уотсон и Крик получили Нобелевскую премию за раскрытие структуры ДНК, все представления ученых кардинально поменялись — сегодня даже школьник может делать реальные эксперименты с этой замечательной молекулой, знания о ней вошли во все школьные учебники и принимаются как само собой разумеющееся. Ведь вы же не станете испытывать эйфорию при решении квадратного уравнения?
Знания в области основных молекулярных механизмов, которыми оперирует клетка, позволяют построить замечательный фундамент для работы в смежных с биологией областях. Из трех важнейших процессов построен весь информационно-смысловой цикл клетки – репликация, трансляция, транскрипция.
Приходите, будет интересно!
Виталий Анатольевич Кошелев «Задача Эрдеша–Секереша о выпуклых многоугольниках на плоскости»
Сколько точек на плоскости будет достаточно, чтобы среди них всегда можно было найти выпуклый многоугольник на заданном числе вершин?
Этот вопрос был впервые поставлен 75 лет назад группой знаменитых венгерских математиков (и с этим связана отдельная красивая история). Простота постановки задачи привлекала очень большое количество исследователей, но, тем не менее, до конца задача не решена до сих пор. Впрочем, за прошедшее время появилось очень много обобщений и близких задач.
Первая лекция будет введением. На второй и третьей лекции будут только новые результаты, которые на предыдущих школах не рассказывались.
Андрей Владимирович Леонидов «Элементы статистической физики: от случайного блуждания до полимеров»
В лекциях обсуждаются основы статистического описания двух центральных задач статистической физики: случайного блуждания (броуновское движение) и системы многих частиц (магнетик). Особое внимание уделяется ключевому понятию энтропии. Рассматривается пример описания свойств полимеров, размер которых определяется свойствами случайной конфигурации цепочки, аналогичной траектории случайного блуждания, а упругие свойства — энтропийной силой.
Даниил Мусатов «Меня доказать нельзя»
На листе бумаги написано утверждение: «Это утверждение невозможно
доказать». Верно оно или нет? Если неверно, то его можно доказать. Но
тогда можно доказать неверное утверждение, а такого не может быть!
Значит, оно верно. Получается, что его невозможно доказать. Но почему
же приведённое рассуждение само по себе не является доказательством?
Это рассуждение было записано на языке арифметики великим математиком
XX века Куртом Гёделем и стало доказательством его знаменитой теоремы
о неполноте формальной арифметики. Эта теорема утверждает, что
некоторое арифметическое суждение невозможно ни доказать, ни
опровергнуть. Основным инструментом доказательства (и открытием
Гёделя) стала запись арифметических утверждений средствами самой
арифметики, своего рода способность к самоанализу.
В мини-курсе мы разберёмся, как формально записывать математические
доказательства, как арифметика может говорить о самой себе, как
формально записать утверждение «Меня доказать нельзя» и почему
рассуждение из первого абзаца не является его доказательством.
Виталий Павленко «Теорема Байеса: спам-фильтр и Акинатор»
Представьте, что мы создаём почтовый сервер, и нам нужно написать для него спам-фильтр. Классификация текстов по видам спам/не-спам — это одна из задач анализа данных. На первом занятии я расскажу про простой способ её решения, который называется наивным байесовским классификатором. В его основе лежат теоретико-вероятностные соображения, поэтому слушатели узнают, что такое независимые события и в чём заключается теорема Байеса.
Второе занятие будет логическим продолжением первого. Акинатор — это интернет-гений, который за пару десятков вопросов угадывает очень многих персонажей российского медийного пространства. Мы разберёмся с тем, как алгоритмически устроен Акинатор, для чего введём понятие информационной энтропии. Также мы научимся писать стратегию для игры в “Быки и коровы”. Если останется время, то мы сможем поговорить про функцию Йенсена–Шеннона.
Андрей Михайлович Райгородский «Системы общих представителей и дефекты решёток»
Михаил Абрамович Ройтберг – TBA
Андрей Ромащенко «Три с половиной определения понятия количества информации»
В современном русском языке слово «информация» стало использоваться
удивительно активно. Поисковая система Яндекс показывает, что это
слово встречается в интернете много чаще таких слов как «масса»,
«энергия» или даже «время». В разных контекстах все эти слова могут
означать совершенно разные понятия. Но среди бытовых значений слов
масса, энергия и время совершенно особое место
занимает “основной”, “научный” смысл этих слов – тот смысл, который
придают этим терминам физики и инженеры. Есть ли точный «научный»
смысл у слова информация? Что такое информация на
самом деле?
Математики, физики и инженеры предложили несколько способов
формализовать наше интуитивное представление об информации. Мы
рассмотрим три основных подхода к математическому определению понятия
информации: комбинаторный подход Хартли, вероятностный подход Шеннона
и алгоритмический подход Колмогорова. Также мы обсудим связь понятия
информации с эпсилон-энтропией и размерностью Хаусдорфа.
Рассказ рассчитан на 2 лекции, предварительных знаний за пределами
школьной программы не требуется.
Алексей Савватеев «Диофантовы уравнения и гауссовы числа»
В курсе, состоящем из трёх лекций, будут решены следующие, на первый
взгляд простейшие, но на проверку весьма нетривиальные проблемы:
– Когда квадрат целого числа отличается от куба целого числа
на единицу? (Знаменитые диофантовы уравнения $y^2 = x^3 \pm 1$);
– Сколькими способами можно представить данное натуральное
число в виде суммы двух квадратов натуральных чисел? Какие простые
числа представляются в виде суммы двух квадратов?
– Когда «квадратное число» является одновременно «треугольным»?
При решении поставленных выше задач мы выйдем за пределы области
обычных целых чисел, рассмотрев так называемые Гауссовы числа, а также
другие сходные с ней системы, являющиеся кольцами. Свойства
делимости во введённых кольцах позволят решить все три задачи.
Михаил Тихомиров «Методы глобальной оптимизации»
Существует множество теоретических и практических задач, требующих подобрать оптимальные параметры для некоторой заданной функции; например, это могут быть затраченное на какое-то действие время или средства, размер или вероятность выигрыша в некоторой игре, и т.д. и т.п. Зачастую заданная функция устроена крайне сложно, и поиск точного глобального оптимума не под силу ни теоретическим, ни практическим методам. Однако в большинстве приложений интерес представляет даже не точный, а приближенный оптимум, т.е. достаточно хорошее решение задачи. Мы поговорим о некоторых классах оптимизационных задач и существующих методах и подходах к нахождению их решений. Также у вас будет возможность применить полученные знания на практике и решить при помощи компьютера несколько интересных задачек.
Данила Черкашин «Спектральная теория графов»
Вообще говоря, не секрет, что наши любимые графы довольно плотно связаны со всякой линейной алгеброй. Об одном из проявлений этой связи, допустим-то, часто читает курс Андрей Михайлович, и некоторые из вас его уже даже слышали, думаю.
Почти все люди, хоть сколько-нибудь сталкивающиеся с графами, знают о матрицах смежности графа. Более-менее и продвинутые ребята знают о ней не только как о форме хранения графа в памяти компьютера, но также осведомлены о некоторых простых свойствах матрицы смежности именно как матрицы. Например, про связь k-ой матрицы и количеств путей в соответствующем графе длины ровно k. Собственно, спектральная теория графов и изучает свойства матриц (не только матрицы смежности) соответствующих графу и позволяет, используя технику матричной теории, нагадать особенности графа по его левой руке.
Я сделаю курс настолько СЛОЖНЫМ/ИНТЕРЕСНЫМ, насколько смогу.
ХОТЯ КУРС ПОСВЯЩЕН ГРАФАМ В ФОРМЕ МАТРИЦ, НИКАКОЙ СВЯЗИ С ПРОГРАММИРОВАНИЕМ ЗДЕСЬ НЕТ!!
Примерный план лекций:
1. Экскурсия в линейную алгебру.
2. Простые утверждения, связь спектра с хроматическим числом, плотностью разреза.
3. Применение подхода к сильно регулярным графам.