Летние сборы 2005

Булевы функции, способы задания функций
1. ДНФ, СДНФ
2. КНФ, СКНФ
3. Полиномы Жегалкина
Полные системы функций
1. Предполные классы
2. Теорема Поста
3. Базисы
Схемы из функциональных элементов
1. Сложность схем
2. Функция Шеннона
3. Универсальный многополюсник

Задания

1.	Придумать базис из четырех функций
2.	Доказать лемму о нелиненой функции

Тур на различные задачи (5 часов)

A.	Ожерелье
B.	Пожар в лесу
C.	Прямоугольники

День 4 (2005-06-28)

Языки, автоматы, формальные грамматики (3 часа)

Лектор: Станкевич Андрей Сергеевич

План лекции

Языки
1. Алфавит, слово, язык
2. Операция конкатенации, моноид слов
3. Операции над языками
Конечные автоматы
1. Детерминированный конечный автомат
2. Язык, допускаемый автоматом
3. Недетерминированный конечный автомат
4. Реализация конечных автоматов в программе
5. Алгоритм Томпсона детерминизации НКА
6. Автомат с \eps-переходами
Регулярные выражения
1. Два определения регулярных языков
2. Эквивалентность регулярных и автоматных языков
3. Регулярные выражения
4. Лемма о разрастании
Формальные грамматики
1. Формальные грамматики, вывод
2. Контестно-свободные грамматики
3. Формы Бэкуса-Науэра
4. Дерево вывода. Левый и правый вывод
5. Нормальная форма Хомского для КС-грамматик

Задания

3.	Постройте ДКА, который допускает множество слов, в которых есть как 0, так и 1, причем есть 0, который идет перед 1
4.	По НКА допускающему язык слов, заканчивающихся на \alpha, постройте ДКА с минимальным числом состояний, допускающий тот же язык
5.	Докажите, что в НКА всегда можно устранить \eps-переходы, в КС-грамматике можно устранить \eps-продукции и цепные продукции
6.	Докажите, что определения регулярных языков, приведенные на лекции, эквивалентны
7.	Докажите, что регулярные языки замкнуты относительно следующих операций: пересечение, дополнение, разность, обращение всех слов, переход к языку циклических сдвигов
8.	Докажите нерегулярность следующих языков: {0^n1^n}, {\alpha\alpha}, язык палиндромов, язык простых чисел 0^p, язык правильных скобочных последовательностей
9.	Докажите лемму о разрастании для КС-грамматик. Установите что язык 0^n1^n2^n не является КС. Докажите, что КС-языки не замкнуты относительно операции пересечения

Тур на различные задачи (5 часов)

1.	Виртуальная реальность
2.	Угадай, где обман
3.	Эквивалентные состояния

День 5 (2005-06-29)

Языки, автоматы, формальные грамматики II (для группы П) (3 часа)

Лектор: Станкевич Андрей Сергеевич

План лекции

Автоматные грамматики
LL(1)-грамматики
1. Множества FIRST и FOLLOW, алгоритмы их построения
2. Устранение левой рекурсии
3. Левая факторизация
4. Рекурсивный спуск
5. Нерекурсивный разбор LL(1)-грамматик
Автоматы с магазинной памятью
1. Автомат с магазинной памятью
2. Эквивалентность допуска по допускающим состояниям и по пустому стеку
3. Эквивалентность МП-автоматов и КС-грамматик

Задания

10.	Доказать, что любую КС-грамматику можно привести к нормальной форме Грейбах
11.	Постройте автомат с двумя магазинами, допускающий язык 0^n1^n2^n. Укажите минимальное число магазинов для распознавания языка 0^n1^n...k^n. Напишите ФГ для 0^n1^n2^n

Введение в теорию графов (для группы И) (3 часа)

Лектор: Мирзаянов Михаил Расихович

План лекции

Основные определения, способы задания орграфов и неориентированных графов
Деревья поисков на графах из заданной вершины
Поиск в глубину, его свойства
Алгоритм поиска топологической сортировки
Линейный алгоритм нахождения компонент сильной связности в орграфе
Линейный алгоритм нахождения мостов
Линейный алгоритм нахождения точек сочленения
Взвешенные графы
Алгоритм Дейкстры, его свойства

Задания

12.	Доказать корректность алгоритма Флери

Тур на различные задачи (5 часов)

1.	Вычисление выражения
2.	Ожерелье 2
3.	Занимательная игра
4.	Просто добавь запятые

День 6 (2005-06-30)

Тур на различные задачи (4 часа)

A.	Дороги
B.	Поезда
C.	Редукция дерева

День 7 (2005-07-01)

Произодящие функции, хроматические многочлены (1 час)

Лектор: Митричев Петр Игоревич

План лекции

Формальные степенные ряды
1. Операции над рядами, их свойства
2. Условие существования обратного ряда
Производящие функции
1. Определение производящей функции последовательности
2. Последовательность Фибоначчи
  - Вывод уравнения на производящую функцию из реккурентного соотношения
  - Представление решения уравнения в виде суммы производящих функций геометрических прогрессий
  - Формула для n-ого числа Фибоначчи
3. Последовательность чисел Каталана
  - Вывод уравнения на производящую функцию из реккурентного соотношения
  - Представление решения уравнения с использованием ряда (1+s)^a
  - Ряд (1+s)^a: определение, основное свойство
  - Формула для n-ого числа Каталана
4. Последовательность количеств разбиений на слагаемые
  - Представление производящей функции в виде бесконечного произведения
  - Бесконечное произведение (1-s)(1-s^2)(1-s^3)... : комбинаторный смысл последовательности коэффициентов
  - Диаграммы Юнга. Тождество Эйлера, взаимно-однозначное соответствие между разбиениями на чётное и нечётное числа различных слагаемых
  - Пентагональная теорема Эйлера. Вычисление p(n) за время O(n*sqrt(n)).
Хроматические многочлены
1. Определение хроматической функции
2. Подсчёт хроматических функций для простейших графов
3. Теорема о хроматическом многочлене

Задания

13.	Доказать критерий существования частного двух рядов
14.	Доказать: (1+s)^a*(1+s)^b=(1+s)^(a+b)
15.	Найти производящую функцию для последовательности квадратов чисел Фибоначчи
16.	Установить взаимно-однозначное соответствие между всеми диаграммами Юнга с чётным и нечётным количествами строк различной длины, кроме случаев k = d = l и k = d = l-1 (где k - число строк, d - длина диагонали, l - длина нижней строки)
17.	Найти хроматический многочлен для цикла длины n, и его производящую функцию при фиксированном k.
18.	Найти хроматический многочлен для следующих графов:

Динамическое программирование (группа И) (1,5)

Лектор: Лопатин Андрей Сергеевич

План лекции

Простейшие задачи динамического программирования
1. Задача Иосифа
2. Задачи на прямоугольных таблицах
Иллюстрация приемов исключения параметров на задаче про две кучки монеток
1. Функциональная зависимость между параметрами
2. Отказ от хранения истории
3. Поворот пространства состояний
4. Выражение одного из параметров через остальные
5. Случай стабильного сохранения части параметров при переходе
Сложные примеры функциональной зависимости. Задача о взятии чисел
Общие характеристики задач динамического программирования
1. Пространство состояний
2. Граф переходов - ациклический граф
3. Рекурсия с запоминанием как динамическое программирование
Построение порядка во время работы алгоритма

Тур на различные задачи (5 часов)

A.	Ключ
B.	Трактор
C.	Сеть для жюри

День 8 (2005-07-02)

Тур на нестандартные задачи (5 часов)

A.	Просто Филя
B.	Крестики-нолики
C.	XOR-шифрование

Общение с психологами (3 часа)

День 9 (2005-07-03)

Тур на различные задачи (5 часов)

A.	Дели!
B.	Тройки
C.	Разбитое стекло

Теория игр (2 часа)

Лектор: Станкевич Андрей Сергеевич

План лекции

Игры на графах
1. Определение игры на графе
2. Выигрышные и проигрышные позиции
3. Стратегия в игре на графе
4. Критерий выигрышности и проигрышности позиции
5. Решение игры на ациклическом графе
6. Ретро-анализ. Решение игры на произвольном графе
Функция Гранди
1. Определение функции Гранди
2. Функция Гранди прямого произведения игр
3. Теорема Гранди
Игры на матрицах
1. Определение игры на матрице
2. Чистая стратегия в игре на матрице. Значение игры
3. Седловая точка
4. Смешанная стратегия в игре на матрице. Значение игры
5. Теорема Фон-Неймана
6. Условия дополняющей нежесткости для оптимальных смешанных стратегий
7. Метод поиска оптимальной смешанной стратегии в игре на матрице

Задания

19.	Докажите, что в игре на матрице значения игры для игроков совпадают тогда и только тогда, когда в матрице есть седловая точка
20.	Докажите теорему Фон-Неймана

День 10 (2005-07-04)

Тур на графы (5 часов)

A.	Чат
B.	Сочинитель стихов
C.	Путь

Линейная алгебра (3 часа)

Лектор: Станкевич Андрей Сергеевич

План лекции

Поля
1. Определение поля
2. Примеры полей
3. Кольцо полиномов
4. Конечные поля. Построение конечных полей порядка p^k
Векторые пространства
1. Определение векторного пространства
2. Полные и линейно независимые системы векторов
3. Базис
4. Размерность пространства
Линейные операторы
1. Линейный оператор
2. Матрица линейного оператора
3. Операции с матрицами
4. Ядро и образ линейного оператора
5. Система линейных уравнений
6. Операции над уравнениями как операции с базисом
7. Алгоритм Гаусса решения системы линейных уравнений
8. Использование алгоритма Гаусса для поиска обратной матрицы

День 11 (2005-07-05)

Тур на разные задачи (5 часов)

A.	Антиуфология
B.	Путешествие одинокого короля
C.	Построение