Государственного экзамена для магистрантов имит омгу,

Программа

Государственного экзамена для магистрантов ИМИТ ОмГУ,

Уч. год

Направление – Прикладная математика и информатика

Общая часть

 

Раздел: Криптография

1. Криптосистема с открытым ключом RSA: платформа шифрования, выбор параметров, выбор ключей, алгоритм шифрования, алгоритм дешифровки, математические основы криптостойкости.

2. Дискретный логарифм в мультипликативных группах конечных полей: определение и основные свойства, протоколы Диффи-Хеллмана, Масси-Омуры и ЭльГамаля.

3. Базовая схема ЭльГамаля цифровой подписи. Цифровая подпись на основе RSA.

4. Линейный регистр сдвига с обратной связью (LFSR): определение, связующий многочлен, регистры максимального периода, статистика выпускной последовательности.

5. Электронные платежи: необходимые элементы — цифровая подпись, номер, номинал и их назначение, технология MasterCard.

 

Раздел: Сети и системы телекоммуникаций

1. Понятие сетевых протоколов. Эталонная модель взаимосвязи открытых систем. Основные функции уровней.

2. Сигналы и кодирование двоичной информации. Среды распространения. Сетевая топология. Технологии локальных вычислительных сетей на примере сети Ethernet.

3. Принципы логической адресации. IP- адресация.

4. Установление соединения по протоколу ТСР. Оконное управление в ТСР. Особенности протокола UDP.

5. Служба адресов DNS. Функционирование сети Интернет.

(специальная часть)

Раздел: Математические модели биологических сообществ

1. Биологические сообщества как объект моделирования. Понятие биологических сообществ и индивидуума; их основные характеристики; цели и задачи математического моделирования; основные подходы и этапы к построению моделей.

2. Основные проблемы при построении моделей и интерпретации модельных переменных. Дискретное и непрерывное время; дискретная и непрерывная численность популяций; детерминированный и стохастический подход; уравнения на математические ожидания.

3. Детерминированные модели сообществ с взаимодействием индивидуумов. Модели Лотки-Вольтерра в дифференциальной форме; свойства решений; конкурентное равновесие; существование предельных циклов; диссипативные по Вольтерра сообщества; модели Лотки-Вольтерра в интегральной форме.

4. Стохастические модели сообществ с взаимодействием индивидуумов. Случайный процесс рождения и гибели, ветвящиеся случайные процессы и их применение к описанию динамики популяций; численные методы Монте-Карло моделирования популяционной динамики.

 

Раздел: Многомерные статистические методы и временные ряды

1. Многомерная генеральная и выборочная совокупности. Векторные случайные величины и признаки. Многомерные распределения. Многомерная нормально распределенная генеральная совокупность. Выборка из генеральной совокупности. Методы отбраковки грубых результатов измерений (наблюдений).

2. Регрессионный анализ. Линейная множественная регрессия.

3. Компонентный и факторный анализ. Проблема снижения размерности вектора изучаемых признаков. Линейная модель метода главных компонент. Матричные операции. Собственные числа и векторы. Дисперсия исследуемых признаков. Компоненты дисперсии в факторном анализе. Матрица факторных нагрузок.

4. Канонические корреляции и канонические величины генеральной совокупности. Канонические корреляции и их интерпретация. Оценка канонических корреляций и канонических величин.

5. Дискриминантный анализ. Методы классификации с обучением. Линейный дискриминантный анализ. Случай нормального распределения показателей.

 

Раздел: Разностные схемы для задач с пограничным слоем

1. Дифференциальное уравнение первого порядка. Построение и обоснование схемы равномерно сходящейся схемы.

2. Уравнение второго порядка с пограничным слоем. Принцип максимума, оценка решения.

3. Уравнение второго порядка с пограничным слоем. Внутренние и внешние разложения решения.

4. Построение схемы Ильина. Формулировка теоремы о равномерной сходимости этой схемы.

 

 

Раздел: Метод Монте-Карло в задачах математической физики

1. Моделирование дискретных случайных величин. Стандартный метод моделирования непрерывных случайных величин. Специальные методы моделирования непрерывных случайных величин (геометрическое распределение, распределение Пуассона). Метод исключения. Метод суперпозиции.

2. Приближенное вычисление интегралов. Простейший метод Монте-Карло для вычисления интегралов. Случайные квадратурные формулы. Основные способы уменьшения дисперсии (выделение главной части, метод существенной выборки, выборка по группам, понижение порядка интегрирования).

3. Процесс блуждания по сферам. Определение и простейшие свойства блуждания по сферам.

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

 

Магистерская программа «Исследование операций и системный анализ» (специальная часть)

 

Раздел: Целочисленное программирование

1. Постановки задач целочисленного программирования. Геометрическая интерпретация. Сложность задач.

2. Задача о наименьшем покрытии множества. Задачи об упаковке и разбиении множества.

3. Производственно-транспортные задачи. Транспортная задача с фиксированными доплатами.

4. Задача выполнимости и максимальной выполнимости логической формулы. Модели ЦП и приложения.

5. Метод отсечения. Общая схема алгоритмов, их свойства. Первый алгоритм Гомори, вопросы конечности, построение верхних оценок числа отсечений.

6. Полностью целочисленные алгоритмы отсечения. Прямые алгоритмы отсечения.

7. Метод регулярных разбиений. L-разбиение, примеры других разбиений. L- структура многогранников задачи о рюкзаке, задач о покрытии и упаковке множества.

8. Дробные накрытия задач ЦП. Регулярные отсечения. Глубина отсечений. Верхние и нижние оценки числа итераций.

9. Метод перебора L-классов для решения задач ЦП Алгоритм для задачи целочисленного линейного программирования.

Раздел: Задачи оптимального размещения

1. Постановки задач Вебера, области применения. Классификация задач.

2. Постановка задач оптимального линейного упорядочения (ОЛУ). Полиномиальные алгоритмы решения ОЛУ для корневого дерева и последовательно-параллельного графа.

3. Постановка задачи Вебера на плоскости. Алгоритм решения задачи Вебера с прямоугольной метрикой с помощью построения серии минимальных разрезов в сети.

4. Построение моделей целочисленного программирования для задач размещения на плоскости с запрещенными зонами с минимаксным и минисуммным критериями.

5. Задача о р -центре. Алгоритм Хакими поиска абсолютного о р -центра на сети.

 

Раздел: Эволюционные алгоритмы и оптимизация

1. Стандартная двоичная кодировка и кодировка Грея, свойство смежности.[1,3]

2. Определение схемы, теорема о схемах. [2]

3. Задача оптимальной рекомбинации. [1]

4. Теорема о разнообразии популяции.

5. Классический генетический алгоритм для задачи о максимальном разрезе графа. [1]

 

 

Магистерская программа «Программирование и информационные технологии» (специальная часть)

 

Раздел: Хранение и обработка данных

 

1. Распределенные системы: определение и задачи. Классификация аппаратных и программных решений. Модель "клиент-сервер". Способы масштабирования в распределенных системах.

2. Виды NoSQL баз данных, их особенности и назначение, примеры. Согласованность и доступность данных. Устойчивость систем к отказам. "Теорема" Брюера (CAP-теорема).

3. Синхронизация в распределенных системах. Логические часы: проблематика, алгоритмы решения. Векторные отметки времени.

4. Репликация, проблема согласованности данных. Типы непротиворечивости данных. Протоколы распределения реплик.

 

 

Литература: (Общая часть)

Криптография

1. Романьков В.А. Введение в криптографию. Курс лекций. Изд-во ОмГУ, Омск, 2006 г.

Литература: (специальная часть)

Математическое моделирование

Программа

государственного экзамена для магистрантов ИМИТ ОмГУ,

Уч. год