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

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

Модели восприятие цвета человеком
Растровое изображение
Фильтры изображения

Задача разбора для контекстно свободной грамматики как задача, противоположная выводу в грамматике. Общий алгоритм разбора для КС-грамматик, работающий за время 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, добавление классов и др.).

Эллиптические кривые в теории чисел и криптографии
Координаты, формулы сложения и умножения на скаляр
Эллиптические кривые над конечными полями.
Вычисление порядка точек и алгоритм факторизации
Криптография на эллиптических кривых

Отношения и их представления.
Физические законы.
Описание диссипации.
Метрики эллиптического и гиперболического типа.
Теория относительности на метрике Бервальда-Моора.

Алгоритм ранжирования Web-страниц PageRank. Терминологический спам. Первое определение PageRank. Ловушки для пауков. Эффективное вычисление PageRank. Эффективное представление матрицы перехода.
PageRank, чувствительный к теме. Анализ спам-фермы. TrustRank. Масса спама. Концентраторы и авторитеты.
Рекомендательные системы. Матрица предпочтений. Рекомендации на основе содержания. Обнаружение особенностей документов. Рекомендация товаров пользователям в зависимости от содержания. Алгоритмы классификации. Кластеризация пользователей и товаров.
Снижение размерности. UV-разложение. Оптимизация произвольного элемента. Сходимость к минимуму. Как избежать переподгонки.
Метод главных компонент. Использование собственных векторов для понижения размерности. Матрица расстояний. Сингулярное разложение. Запросы с использованием концептов. Вычисление сингулярного разложения матрицы. CUR-декомпозиция.
Интеллектуальный анализ процессов. Методы и типы анализа. Моделирование бизнес-процессов. Процессы: модели и экземпляры. Анализ процессов. Cети Петри.
Линейные модели в машинном обучении: теория и практическое применение. Роль линейных моделей как базовых компонентов современных нейронных сетей.

Методы разделяй и властвуй. Быстрое преобразование Фурье.
Структуры данных. Распределённые хеш-таблицы. Фильтр Блума.
Потоки в сетях
Поиск подстроки
Классы P и NP. Сведение задач. NP-полнота

Сложность алгоритмов
Методы разделяй и властвуй
Структуры данных. Деревья поиска.
Алгоритмы на графах
Жадные алгоритмы
Динамическое программирование

Корпоративные приложения: современные требования. Проблемы в аппаратном и программном обеспечении и способы их решения. Характеристики современных корпоративных приложений (OLTP и OLAP системы; хранилища данных; озёра данных; конвейеры данных; компании, управляемые данными).
Словарное кодирование в In-Memory базе данных, понятие энтропии.
Сжатие данных в In-Memory базе данных: префиксное кодирование (Prefix Encoding), разреженное кодирование (Sparse encoding), непрямое кодирование (In-direct encoding), кодирование длин серий (Run-length encoding), кластерное кодирование (Cluster Encoding), дельта-кодирование (Delta encoding).
Методы хранения баз данных: секционирование, мульти-температурное управление данными, фактические и исторические данные.
Операторы манипулирования данными в In-Memory базе данных: вставка, обновление, удаление, "insert only"-подход (представление точки, интервальное представление, хронологические и битемпоральные базы данных).
Построчное и поколоночное размещение данных в In-Memory базе данных: сравнение подходов при реконструкции кортежей. «Компромиссная» модель хранения таблиц PAX (Partition Attributes Across). iHEAP таблицы Postgres. Сравнение подходов при полном сканировании таблицы, шаговом доступе и полном сканировании столбца.
Оператор выборки в In-Memory базе данных: стратегии материализации (возможные стратегии, преимущества и недостатки). Агрегатные функции.
Оператор соединения таблиц Join. Алгоритмы соединения: хешированием, слиянием отсортированных списков, вложенными циклами. Алгоритм многопроходного разделения.
In-Memory СУБД: архитектура, понятие дифференциального буфера и процесс слияния, кеш для агрегатов.
Индексы в In-Memory базе данных, инвертированный индекс, эффективность инвертированного индекса при словарном кодировании.
Логическая и физическая регистрация в In-Memory базах данных. Ведение журнала в случае словарного кодирования. Процесс восстановления.
k-безопасность. Горизонтальное и вертикальное масштабирование. Реплики для рабочей нагрузки. Нетерпеливые и ленивые репликации.
Обработка SQL запросов. In-memory специфичные запросы. Планирование запросов.
Параллелизм на уровне аппаратного обеспечения, параллелизм на уровне программного обеспечения. Распараллеливание SIMD. Законы Амдала и Густавсона-Барсиса. Распараллеливание в In-Memory базах данных.
Управление параллелизмом транзакций. Побочные эффекты параллелизма. Пессимистическая двухфазная блокировка. Мультиверсионное управление параллелизмом. Проблемы архитектуры СУБД: MVCC и внутренний идентификатор (xid) транзакции.
NoSQL: идея NoSQL, модели целостности (BASE vs ACID), теоремы CAP и PACELC. Типы согласованности данных, модель настраиваемой согласованности. Типы хранилищ данных для NoSQL. “Очень быстрый OLTP”.
Базы данных и технология распределенного реестра, блокчейн, дерево Меркла. Блокчейн 2.0. Трилемма масштабируемости.
Подход к разработке БД: «толстая» база данных, база данных как хранилище, база данных как код, платформа бессерверных вычислений. OLTP и большие OLAP. Особенности работы с данными в облаке.
База данных с технологиями ИИ: адаптивное управление, оптимизация запросов, запросы с учетом достоверности. Автономная база данных. Современный стек данных для приложений ИИ.
Векторные базы данных в современных приложениях искусственного интеллекта. Основные аспекты векторных баз данных: метрики, индексирование. Метод инвертированного индексирования файлов (Inverted File Indexing) для оптимизации работы векторных баз данных

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