[Кафедра МаТИС]

Понятие автомата
Детерминированные функции
Неотличимость автоматов
Регулярность событий
Абстрактные автоматы
Структурные автоматы
Сложность управляющих систем
Автоматы в лабиринтах

Протоколы аутентификации
Протоколы электронной подписи
Протоколы распределения криптографических ключей
Протоколы электронного голосования
Протоколы электронной коммерции
Примеры уязвимостей протоколов
Методы формального анализа протоколов

Задачи и модели машинного обучения.
Линейно разделимые выборки. Алгоритм обучения Розенблатта. Теорема Новикова.
Метод градиентного спуска. Метод стохастического градиента.
Метод обратного распространения ошибки для обучения нейронных сетей.
Метод опорных векторов. Теорема Каруша-Куна-Таккера.
Построение оптимальной разделяющей гиперплоскости по зашумленной выборке.
Ядерный метод машинного обучения.
Алгоритм вычисления калибруемых прогнозов.
Алгоритм взвешенного большинства. Алгоритм оптимального распределения потерь в
режиме онлайн.
Алгоритм экспоненциального взвешивания экспертных решений.
Агрегирующий алгоритм Вовка.
Игры и прогнозы. Антагонистические игры двух игроков. Достаточное условие
существования седловой точки. Смешанные расширения матричных игр.
Игры на универсальные прогнозы. Рандомизированные калибруемые прогнозы.
Теорема Блекуэлла о достижимости
Калибруемые прогнозы и коррелированное равновесие.

Лабиринты: прямоугольные, мозаичные, шахматные.
Перемещение независимых систем автоматов в лабиринтах.
Возможность обхода конечных мозаичных лабиринтов конечными автоматами.
Теорема Будаха-Подколзина (невозможность обхода конечным автоматом всех мозаичных лабиринтов).
Обход автоматом конечных односвязных шахматных лабиринтов.
Обход конечным автоматом конечных лабиринтов с ограниченными внутренними дырами.
Перемещение в лабиринтах коллективов автоматов.
Периодичность поведения системы автоматов в конечных лабиринтах.
Пример непериодического поведения коллектива автоматов.
Автоматы со счётчиками.
Обход произвольных конечных шахматных лабиринтов автоматом со счётчиком.
Обход произвольных конечных шахматных лабиринтов коллективом автоматов.
Обход коллективом автоматов лабиринтов с одной дырой.
Постановка задачи преследования в шахматных лабиринтах.
Поведение конечного автомата в L0.
Задача преследования независимой системой хищников независимой системы жертв в L0.
Поведение конечного автомата в L1.
Задача преследования независимой системой хищников независимой системы жертв в L1.
Поведение конечного автомата в L2(l).
Задача преследования независимой системой хищников независимой системы жертв в L2(l).
Поведение конечного автомата в L3(l) и L4.
Задача преследования независимой системой хищников независимой системы жертв в L3(l) и L4.
Поимка данной жертвы в L0 коллективом хищников.
Существование универсального коллектива хищников в L0.
Существование универсального коллектива хищников в L1, L2(l), L3(l) и L4.
Задача преследования коллективом хищников независимой системы жертв в L5(l).
Нерешённые лабиринтные задачи.

Теория функций потерь
Работа с распределениями данных
Состязательное обучение
Устойчивость нейросетей
Предельные теоремы

Обработка двумерных цветных изображений
Обработка двумерных полутоновых изображений
Перевод аналоговых изображений к их дискретному цифровому представлению

Постановка основных математических задач в теории сложности алгоритмов и их значение для обработки экономической информации.
Роль оптимизации и сложности алгоритмов в разработке программных продуктов искусственного интеллекта.
Машины произвольного доступа к памяти, машины Тьюринга и их модификации.
Взаимное моделирование моделей вычислений.
Функции сложности алгоритмов и их свойства.
Существование сложных задач.
Теорема Блюма об ускорении.
Труднорешаемость задач.
Классы P и NP и их свойства.
Полиномиальная сводимость задач.
NP-полные задачи. Теорема Кука о NP-полноте проблемы выполнимости формул алгебры высказываний.
Основные NP-полные задачи.
Задачи с числовыми параметрами. Задача о рюкзаке. Сильная NP-полнота.
Бесконечная серия NP-полных задач Шиффера.
Методы построения быстрых алгоритмов.
Структуры данных.
Рекурсия. Типы полиномиальных оценок сложности рекурсивных алгоритмов.
Рекурсивные алгоритмы для задач сортировки массивов чисел, умножения чисел, умножения матриц, преобразования формул алгебры логики.
Быстрое преобразование Фурье и его применения. Сложность умножения многочленов.
Быстрые алгоритмы на графах. Поиск в глубину и в ширину. Кратчайшие пути. Минимальные остовные деревья. Алгоритмы для задачи о паросочетании.
Потоки в сетях и алгоритмы нахождения максимального потока.
Методы решения труднорешаемых задач.
Метод ограничения параметров.
Метод приближенных алгоритмов. Существование приближенных алгоритмов с различными мерами уклонений от точных алгоритмов.
Доказательства не существования приближенных алгоритмов с некоторыми мерами уклонения.
Политика жадности. Примеры оптимальности жадных алгоритмов. Приближенные алгоритмы для задач об упаковке, о коммивояжере, о вершинном покрытии. Матроиды. Характеризация случаев оптимальности жадных алгоритмов. Теорема Радо- Эдмонса.
Оптимизация алгоритмов перебора.
Минимизация среднего числа опробований с учетом вероятности истинного варианта и сложности его опробования.
Метод согласования координат при переборе.
Методы получения нижних оценок сложности
Нижние оценки сложности в наследственных алгоритмах, использующих отношение частичной упорядоченности. Теорема Дилуорса. Лемма Анселя для единичного куба..
Сложность оптимального алгоритма выделения монотонной функции.
Нижние оценки вычисления на машине Тьюринга. Проблема симметрии слов. Теорема Барздинь и доказательство оптимальности.
Заключение. Основные направления исследований в области оценок сложности алгоритмов. Приложения к проблемам защиты банковской информации и электронной коммерции.

Булевы функции и представления. Преобразование Фурье.
Ряды Фурье булевых функций.
Группы инерции булевых функций. Теорема Шеннона.
Выравнивающие свойства булевых функций. Неравенство Шеннона.
Бент-функции.
Области существенных переменных булевых функций.
Запреты булевых функций.
Регистры сдвига. Регулярность. Цикловая структура. Число полноцикловых регистров сдвига. Теорема де Брейна.
Метод склейки-расклейки. Число циклов регистра чистого сдвига.
Счетчики. Условия полноцикловости.
Коммутаторные схемы. Перестраиваемые схемы Клосса.
Узлы замены. Характеристики. Критерий эквивалентности
Переработка периодических последовательностей автоматами.
Условия сокращения периода для счетчиковых элементов.
Линейные автоматы. Свойства графа линейного преобразования. Расчет периодов в линейных автоматах. Линейные регистры сдвига.
Методы решения систем булевых уравнений.
Классы сложности. Легкорешаемые классы булевских уравнений.
Методы сведения к легкорешаемым классам.
Алгоритм DES. Разностные характеристики.
Алгоритм RSA. Рюкзачные системы.
Системы с открытым ключом.
Алгоритм цифровой подписи.
Сложностной подход к оценке стойкости шифров.
Информационный подход к оценке стойкости шифров.
Алгоритм криптографической защиты IDEA.
Стандарты криптографической защиты.