[Кафедра математической логики и теории алгоритмов]

Логика первого порядка
Теорема Эрбрана
Метод резолюций для логики высказываний
Алгоритм унификации
Метод резолюций для логики предикатов
Уточнения исчисления резолюций
Применения метода резолюций в математической логике

Рекурсивные функции.
Теоремы Геделя о неполноте.
Аксиоматическая теория множеств.
Теорема Цермело.

Классическая логика высказываний.
Интуиционистская логика высказываний.
Логика предикатов.
Теорема Геделя о полноте.

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

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

Кодовые слова, размерность, минимальное расстояние кодов.
Количество исправленных ошибок и стираний. Код Хэмминга [n-1,n,2].
Граница Хэмминга. Граница Гилберта.
Формула для объема шара Хэмминга. Функция Шеннона.
Линейные коды.
Граница Варшамова-Гилберта.
Коды Возенкрафта.
Коды Хэмминга.
Граница Синглтона. Коды Рида-Соломона.
Каскадные коды. Коды Форни. Коды Форни-Юстесена-Возенкрафта
Границы Плоткина и улучшение границы Синглтона.
Коды Адамара.
Код Рида — Маллера.
Коды БЧХ.
Декодирование списком с исправлением ошибок. Общие границы.
Декодирование списком и минимальное расстояние.
Декодирование списком с исправлением n-sqrt{n(n-d)} ошибок для кода Рида-Соломона.
Декодирование списка с (1-eps)/2 ошибками для кода Адамара
Теорема Голдрайха-Левина

Экскурс в логику первого порядка. Теории классов структур. Гёделевская нумерация.
Метод элиминации кванторов и его применения. Разрешимость теории упорядоченных делимых абелевых групп.
Разрешимость теории упорядоченной группы целых чисел по сложению. Определимость в данной группе. Арифметика Пресбургера.
Теорема Тарского–Зайденберга и разрешимость теории упорядоченного поля вещественных чисел.
Интерпретации между структурами. Разрешимость теории поля комплексных чисел и элементарной геометрии.
Алгебраически замкнутые и вещественно замкнутые поля. Применение элиминации кванторов к решению 17-ой проблемы Гильберта.
Интерпретации между классами структур. Интерпретации между теориями.
Существенная и наследственная неразрешимости. Перенос результатов о неразрешимости посредством интерпретаций.
«Минимальная» арифметика и представимость в ней. Существенная неразрешимость теории дискретно упорядоченных колец.
Построение наследственно неразрешимой теорий в сигнатуре арифметики.
Наследственная неразрешимость теории конечных простых графов.
. Наследственная неразрешимость теории конечных симметрических групп (с помощью теории двух эквивалентностей на общем конечном носителе).
Элементарный язык вероятностных пространств. Безатомные пространства. Разрешимость теории безатомных вероятностных пространств.
Наследственная неразрешимость теории конечных вероятностных пространств.
Язык арифметики второго порядка. Монадическая (второпорядковая) определимость в структуре натуральных чисел со сложением. Вычислимая эквивалентность теории дискретных вероятностных пространств и полной арифметики второго порядка.
Обзор результатов, связанных с векторными пространствами, метрическими пространствами и нормированными пространствами.