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

Линейная регрессия
Метод опорных векторов
Методы кластеризации

Неотрицательные матрицы. Перестановочная матрица. Неразложимая матрица. Критерии неразложимости. Сильно связный граф. Определение сильной связности графа через отсутствие собственных замкнутых подграфов. Примитивные матрицы. Связь с графами. Спектр, радиус матрицы. Теорема Перрона-Фробениуса.
Приложения неотрицательных матриц: числа Фибоначчи, популяция, модель Леонтьева, марковский процесс (разбор случая с двумя состояниями), PageRank.
Матрица смежности графа, её свойства. Характеристический многочлен, спектр графа. Быстрый подсчёт числа маршрутов.
Матрица Кирхгофа, её свойства. Кратность нуля спектра, алгебраические дополнения матрицы Кирхгофа.
Матрица инцидентности. Связь с матрицей Кирхгофа.
Число остовных деревьев связного графа. Число связных компонент графа.
Бинарные отношения. Лемма Бёрнсайда. Число неориентируемых графов без петель с заданным числом вершин.
Инварианты графов. Полный инвариант. Полиномиальные инварианты графов. Хроматические многочлен, многочлен Абеля.
Автоморфизмы и эндоморфизмы графов.
Свойства перманента. Теорема Фробениуса об определителе. Теорема Маркуса-Минка.
Алгебра над полем. Алгебра кватернионов: базис, ассоциативность, норма, сопряжение. Формула произведения кватернионов через скалярные и векторные части. Алгоритм вращения при помощи кватернионов.
Квазигруппы, лупы. Изотопность квазигрупп. Алгоритм Дамма. Квазигруппы в криптографии.
Тропическая алгебра. Идемпотентное полукольцо. Maxplus-алгебра: арифметика, матрицы. Построение регулярного расписания. Вычисление собственного значения для тропических неразложимых матриц. Heap-модель.
Некоммутативная криптография. Тропическая криптография. Криптосхема Месси-Омуры. Схема Эль-Гамаля над группой точек эллиптической кривой.
Разложение матрицы в произведение двух симметричных (эрмитовых). Действительнозначная жорданова клетка. Приложения LU-разложения и разложения Холецкого. Псевдообратная матрица. Сингулярное разложение и его приложения.

Структура российского рынка консалтинга.
Единство социально-экономического пространства
Категорная модель предприятия – концептуальный и инструментальный аппарат разработки автоматизированных систем управления.
Основы функционирования предприятия
Экономика предприятия. Технологическая и экономическая модели предприятия
Основы бизнес – анализа и моделирования.
Виды учета и объекты управления. Основы управленческого учета
Информационно - математические основы создания систем управления бизнесом.
Перспективы применения искусственного интеллекта в области управления компаниями.
Проектная деятельность - форма реализации консалтинга
Обзор рынка корпоративного программного обеспечения.
Корпоративная культура предприятия.

Определение формальной грамматики и языка, заданного ей. Примеры. Алфавиты терминалов и нетерминалов (метасимволов). Правила грамматики и выводы. Пример грамматики для ограниченного подмножества естественного языка.
Иерархия Хомского. Грамматики без ограничений. Контекстно зависимые грамматики. Пример контекстно зависимого языка L = {a^n b^n c^n, n ∈ Z}.
Контекстно свободные языки и грамматики. Левые и правые выводы для КС-грамматик и синтаксические деревья. Лемма о разрастании для контекстно свободных языков. Пример контекстно зависимого языка, который не вляется контексно свободным.
Однозначные грамматики. Примеры неоднозначных и однозначных грамматик для одних и тех же языков. Существенно неоднозначные языки, примеры (без доказательства).
Конечное автоматы и автоматные языки. Детерминированные и недетерминированные конечные автоматы. Лемма о разрастании для автоматных языков. Алгоритм построения детерминированного конечного автомата, эквивалентного данному недетерминированному конечному автомату в смысле порождаемого им языка.
Праволинейные и леволинейные грамматики. Совпадение классов автоматных языков, леволинейных языков и праволинейных языков.
Регулярные языки и выражения. Теорема Клини о совпадении классов регулярных и автоматных языков.
Минимальные детерминированные конечные автоматы. Изоморфизм всех минимальных детерминированных конечных автоматов, порождающих данный автоматный (или регулярный) язык. Алгоритм построения минимального детерминированного конечного автомата.
Преобразование контекстно свободных грамматик. Удаление недостижимых и бесполезных символов, избавление от эпсилон-правил. Грамматики в нормальной форме Хомского (квадратичные грамматики).
Операции над контекстно свободными языками, не выводящие за пределы класса КС-языков и выводящие за пределы этого класса. Пример двух контекстно свободных языков, пересечение которых не является КС-языком. Пример КС-языка, дополнение к которому не является КС-языком.
Алгоритмические проблемы теории формальных языков. Положительное решение большинства алгоритмических проблем в классе автоматных (или регулярных) языков.
Алгоритмически разрешимые и неразрешимые проблемы в классе контекстно свободных языков. Разрешимость проблемы принадлежности цепочки языку. Неразрешимость проблемы равенства двух контекстно свободных языков, заданных КС-грамматиками. Неразрешимость проблемы однозначности контекстно свободной грамматики.
Задача разбора для контекстно свободной грамматики как задача, противоположная выводу в грамматике. Общий алгоритм разбора для КС-грамматик, работающий за время O(n^3). Практические методы разбора: 1) алгоритм нисходящего, или рекурсивного, или LL(1)-разбора; 2) алгоритм восходящего, или LR(1) разбора, или разбора с помощью конечного автомата со стеком (с магазинной памятью).
Два этапа разбора: 1) сканер, разбивающий входной поток символов на лексемы, который традиционно реализуется с помощью конечного автомата; 2) парсер, на вход которого подается поток лексем, выполняющий синтаксический разбор и при необходимости перевод на другой язык, вычисление значения формулы, а также другие задачи, связанные с синтаксическим разбором.
Построение сканера с помощью утилиты lex операционной системы Unix или ее свободной версии flex. Входной язык для утилиты flex. Примеры программ, написанных с использованием flex: выделение имен и числовых констант из входного потока, удаление комментариев из программы на C/C++, раскрашивание в разные цвета ключевых слов, констант и других лексем в тексте программы на C++.
Нисходящий, или рекурсивный, или LL(1)-разбор. Примеры КС-грамматик, допускающих и не допускающих LL(1)-разбор. Критерий того, что КС-грамматика допускает LL(1)-разбор. Способ преобразование грамматики, не допускающей LL(1)-разбор, к форме, которая его допускает: удаление непосредственной рекурсии. Пример такого преобразования для грамматики арифметически формул.
Проект "Калькулятор формул", парсер в котором реализован с помощью
LL(1)-разбора, в котором формула преобразуется в обратную польскую запись, позволяющую вычислить ее значение с помощью стекового вычислителя. Использование этого парсера для реализации на Qt программы, рисующей график функции, заданной в виде формулы в текстовом окне.
Идея восходящего, или LR-разбора. Понятие LR-процесса как процесса, противоположного правому выводу предложения языка в КС-грамматике. Действия сдвиг и свертка, неопределенности.
Понятия LR(0)-ситуации и LR(0)-состояния разбора. Алгоритм построения множества LR(0)-состояний разбора. Конфликты типа сдвиг-свертка (shift-reduce) и свертка-свертка. Определение грамматики, допускающей LR(0)-разбор. Примеры грамматик, допускающих и не допускающих LR(0)-разбор. Таблицы разбора, алгоритм работы LR-парсера, семантический стек.
Определения LR(1)-ситуации и LR(1)-состояния разбора. Примеры разрешения конфликтов LR(0)-разбора путем использования алгоритма LR(1)-разбора, учитывающего первый непрочитанный символ аванцепочки. Определение LR(1)-грамматики и детерминированного языка. Алгоритм работы LR(1)-парсера. Использование сематнического стека для решения различных задач, связанных с синтаксическим разбором.
Утилита yacc и ее свободная версия bison, предназначенная для написания парсеров. Связь с утилитой lex (и ее свободной версией flex), предназначенной для написания сканеров. Синтаксис входного языка для утилиты bison. Пример реализации калькулятора формул с помощью утилит flex и bison, испольующих лексический разбор с помошью конечного автомата и восходящий LR(1)-разбор с помощью конечного автомата со стековой памятью. Применение калькулятора формул для реализации на Qt графической программы, рисующей график функции, заданной в виде формулы в текстовом окне.
Модельный язык Delta, компилятор которого реализован с помощью утилит flex и bison. Синтаксис языка: динамическая типизация, напоминающая язык Python, синтаксис ближе к языку C++. Примеры программ на Delta. Промежуточный код для языка Delta как язык команд для стекового вычислителя.
Генерация промежуточного кода по дереву, представляющему выражение. Принципиальная разница между арифметическими и логическими выражениями. Условные переходы в промежуточном языке. Рекурсивный алгоритм генерации промежуточного кода для логических выражений. Пример генерации кода для логических выражений языка C.
Сканер языка Delta, реализованный с помощью flex. Реализация парсера языка Delta с использованием утилиты bison, а также различных классов на языке C++. Генерация промежуточного кода для арифметических и логических выражений через построение на первом этапе дерева выражения и затем генерацию кода по дереву.
Реализация интерпретатора промежуточного кода языка Delta, аналогия с интерпретатором промежуточного кода языка Python.
Задачи, связанные с развитием языка Delta (добавление новых операций, циклов "для каждого", задание списков в стиле языка Haskell, добавление классов и др.).

Задача разбора для контекстно свободной грамматики как задача, противоположная выводу в грамматике. Общий алгоритм разбора для КС-грамматик, работающий за время O(n^3). Практические методы разбора: 1) алгоритм нисходящего, или рекурсивного, или LL(1)-разбора; 2) алгоритм восходящего, или LR(1) разбора, или разбора с помощью конечного автомата со стеком (с магазинной памятью).
Два этапа разбора: 1) сканер, разбивающий входной поток символов на лексемы, который традиционно реализуется с помощью конечного автомата; 2) парсер, на вход которого подается поток лексем, выполняющий синтаксический разбор и при необходимости перевод на другой язык, вычисление значения формулы, а также другие задачи, связанные с синтаксическим разбором.
Построение сканера с помощью утилиты lex операционной системы Unix или ее свободной версии flex. Входной язык для утилиты flex. Примеры программ, написанных с использованием flex: выделение имен и числовых констант из входного потока, удаление комментариев из программы на C/C++, раскрашивание в разные цвета ключевых слов, констант и других лексем в тексте программы на C++.
Нисходящий, или рекурсивный, или LL(1)-разбор. Примеры КС-грамматик, допускающих и не допускающих LL(1)-разбор. Критерий того, что КС-грамматика допускает LL(1)-разбор. Способ преобразование грамматики, не допускающей LL(1)-разбор, к форме, которая его допускает: удаление непосредственной рекурсии. Пример такого преобразования для грамматики арифметически формул.
Проект "Калькулятор формул", парсер в котором реализован с помощью
LL(1)-разбора, в котором формула преобразуется в обратную польскую запись, позволяющую вычислить ее значение с помощью стекового вычислителя. Использование этого парсера для реализации на Qt программы, рисующей график функции, заданной в виде формулы в текстовом окне.
Идея восходящего, или LR-разбора. Понятие LR-процесса как процесса, противоположного правому выводу предложения языка в КС-грамматике. Действия сдвиг и свертка, неопределенности.
Понятия LR(0)-ситуации и LR(0)-состояния разбора. Алгоритм построения множества LR(0)-состояний разбора. Конфликты типа сдвиг-свертка (shift-reduce) и свертка-свертка. Определение грамматики, допускающей LR(0)-разбор. Примеры грамматик, допускающих и не допускающих LR(0)-разбор. Таблицы разбора, алгоритм работы LR-парсера, семантический стек.
Определения LR(1)-ситуации и LR(1)-состояния разбора. Примеры разрешения конфликтов LR(0)-разбора путем использования алгоритма LR(1)-разбора, учитывающего первый непрочитанный символ аванцепочки. Определение LR(1)-грамматики и детерминированного языка. Алгоритм работы LR(1)-парсера. Использование сематнического стека для решения различных задач, связанных с синтаксическим разбором.
Утилита yacc и ее свободная версия bison, предназначенная для написания парсеров. Связь с утилитой lex (и ее свободной версией flex), предназначенной для написания сканеров. Синтаксис входного языка для утилиты bison. Пример реализации калькулятора формул с помощью утилит flex и bison, испольующих лексический разбор с помошью конечного автомата и восходящий LR(1)-разбор с помощью конечного автомата со стековой памятью. Применение калькулятора формул для реализации на Qt графической программы, рисующей график функции, заданной в виде формулы в текстовом окне.
Модельный язык Delta, компилятор которого реализован с помощью утилит flex и bison. Синтаксис языка: динамическая типизация, напоминающая язык Python, синтаксис ближе к языку C++. Примеры программ на Delta. Промежуточный код для языка Delta как язык команд для стекового вычислителя.
Генерация промежуточного кода по дереву, представляющему выражение. Принципиальная разница между арифметическими и логическими выражениями. Условные переходы в промежуточном языке. Рекурсивный алгоритм генерации промежуточного кода для логических выражений. Пример генерации кода для логических выражений языка C.
Сканер языка Delta, реализованный с помощью flex. Реализация парсера языка Delta с использованием утилиты bison, а также различных классов на языке C++. Генерация промежуточного кода для арифметических и логических выражений через построение на первом этапе дерева выражения и затем генерацию кода по дереву.
Реализация интерпретатора промежуточного кода языка Delta, аналогия с интерпретатором промежуточного кода языка Python.
Задачи, связанные с развитием языка Delta (добавления новых типов и операций, циклов "для каждого", задания списков в стиле языка Haskell, добавление классов и др.).

Полигоны над полугруппами (автоматы).
Гомологические вопросы теории полигонов: инъективность, проективность, плоскостность. Инъективные оболочки, проективные накрытия.
Условия конечности в полигонах: артиновость, нётеровость, хопфовость и т.д.
Полигоны с дистрибутивной и модулярной решёткой конгруэнций.
Подпрямые разложения полигонов и подпрямо неразложимые полигоны.
Топологические полигоны.

Представление знаний отношениями, графами. Категории, функторы, структуры.
Размерность данных. Пи теорема.
Теория Кулакова-Михайличенко. Обобщение теории размерности.
Осреднение. Кластеризация. Уравнения гидромеханики.
Метрики. Гиперболические метрики. Принцип причинно-следственности.
Модели пространства-времени.
Дифференциальные формы. Когомологии де Рама. Уравнения электродинамики.

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

Энтропия случайной величины
Кодирование источника данных
Код Хаффмана
Дискретный канал без памяти
Теорема Шеннона о кодировании дискретного канала без памяти