Раздел: Эволюционные алгоритмы и оптимизация
Программа государственного экзамена для магистрантов ИМИТ ОмГУ,
Уч. год
Направление – Прикладная математика и информатика
Магистерская программа «Исследование операций и системный анализ»
Раздел: Криптография
Криптосистема с открытым ключом RSA: платформа шифрования, выбор параметров, выбор ключей, алгоритм шифрования, алгоритм дешифровки, математические основы криптостойкости.
2. Дискретный логарифм в мультипликативных группах конечных полей: определение и основные свойства, протоколы Диффи-Хеллмана, Масси-Омуры и ЭльГамаля.
3.Базовая схема ЭльГамаля цифровой подписи. Цифровая подпись на основе RSA.
4.Линейный регистр сдвига с обратной связью (LFSR): определение, связующий многочлен, регистры максимального периода, статистика выпускной последовательности.
5.Электронные платежи: необходимые элементы — цифровая подпись, номер, номинал и их назначение, технология MasterCard.
Раздел: Комбинаторная теория и приложения
Комбинаторные задачи. Массовая и индивидуальная задача. Трудоемкость алгоритма. Полиномиальные и экспоненциальные алгоритмы. Задачи распознавания. Недетерминированные алгоритмы. Классы P и NP. Проблема “P vs NP”.
2. Полиномиальная сводимость и NP-полные задачи распознавания. Свойства полиномиальной сводимости. Теорема о сложности NP-полных задач. Теорема Кука (без доказательства).
3. Сводимость по Тьюрингу и NP-трудные оптимизационные задачи. Примеры NP-трудных задач (задача о наименьшем вершинном покрытии, о наибольшем независимом множестве, о покрытии множества).
|
|
|
4. Приближенные алгоритмы. Понятие r( n)-приближенного алгоритма. Приближенные алгоритмы для задач о наименьшем вершинном покрытии, о наибольшем независимом множестве, о покрытии множества. Аппроксимационные классы.
Раздел: Целочисленное программирование
1. Постановки задач целочисленного программирования. Геометрическая интерпретация. Сложность задач.
2. Задача о наименьшем покрытии множества. Задачи об упаковке и разбиении множества.
3. Производственно-транспортные задачи. Транспортная задача с фиксированными доплатами.
4. Задача выполнимости и максимальной выполнимости логической формулы. Модели ЦП и приложения.
5. Метод отсечения. Общая схема алгоритмов, их свойства. Первый алгоритм Гомори, вопросы конечности, построение верхних оценок числа отсечений.
6. Полностью целочисленные алгоритмы отсечения. Прямые алгоритмы отсечения.
7. Метод регулярных разбиений. L-разбиение, примеры других разбиений. L- структура многогранников задачи о рюкзаке, задач о покрытии и упаковке множества.
|
|
|
8. Дробные накрытия задач ЦП. Регулярные отсечения. Глубина отсечений. Верхние и нижние оценки числа итераций.
9. Метод перебора L-классов для решения задач ЦП. Алгоритм для задачи целочисленного линейного программирования.
Раздел: Задачи оптимального размещения
1. Постановки задач Вебера, области применения. Классификация задач.
2. Постановка задач оптимального линейного упорядочения (ОЛУ). Полиномиальные алгоритмы решения ОЛУ для корневого дерева и последовательно-параллельного графа.
3. Постановка задачи Вебера на плоскости. Алгоритм решения задачи Вебера с прямоугольной метрикой с помощью построения серии минимальных разрезов в сети.
4. Построение моделей целочисленного программирования для задач размещения на плоскости с запрещенными зонами с минимаксным и минисуммным критериями.
5. Задача о р-центре. Алгоритм Хакими поиска абсолютного о р-центра на сети.
Раздел: Некооперативные и кооперативные игры
1. Позиционные игры (игры в развернутой форме). Теорема о существовании ситуации равновесия в конечной игре с полной информацией.
2. Некооперативные игры двух лиц в нормальной форме. Антагонистические игры. Ситуации равновесия в антагонистической игре. Решение антагонистической игры. Принцип максимина.
|
|
|
3. Биматричные игры. Чистые и смешанные стратегии. Лемма о гарантированных выигрышах. Графический метод отыскания максиминных смешанных стратегий в биматричной игре.
4. Равновесие и квазиравновесие в биматричной игре. Стационарные стратегии с памятью на один ход. Обоснование выбора стратегий «Око за око» при многократном повторении игры «Дилемма заключенного».
5. Некооперативные игры n лиц в нормальной форме. Теорема Нэша о существовании ситуации равновесия.
6. Кооперативные игры двух лиц в нормальной форме. Решение кооперативной игры двух лиц по фон Нейману-Моргенштерну. Задача о сделках (модель торга по Нэшу). Теорема Нэша.
7. Кооперативные игры n лиц. Характеристическая функция. Кооперативные игры с произвольной и постоянной суммой. Стратегическая эквивалентность и изоморфизм кооперативных игр. Теорема об изоморфизме (достаточное условие изоморфизма).
8. Ядро как решение кооперативной игры. Теорема о характеризации ядра. Примеры (Ядро игры двух лиц и игры трех лиц с постоянной суммой). Теорема о ядре игры с постоянной суммой.
9. Решения по фон Нейману-Моргенштерну (NM-решения). Свойства NM-решений. Симметричное и дискриминативные NM-решения игры трех лиц с постоянной суммой. Теорема фон Неймана-Моргенштерна о решениях кооперативной игры трех лиц с постоянной суммой.
|
|
|
10. Вектор-функция Шепли. Аксиомы Шепли. Теорема Шепли (без доказательства). Содержательная интерпретация вектора Шепли. Вектор Шепли как дележ. Примеры.
Раздел: Эволюционные алгоритмы и оптимизация
1. Стандартная двоичная кодировка и кодировка Грея, свойство смежности.[1,3]
2. Определение схемы, теорема о схемах. [2]
3. Задача оптимальной рекомбинации. [1]
4. Теорема о разнообразии популяции.
5. Классический генетический алгоритм для задачи о максимальном разрезе графа. [1]
Литература:
Криптография
1. Романьков В.А. Введение в криптографию. Курс лекций. Изд-во ОмГУ, Омск, 2006 г.
Дата добавления: 2019-02-12; просмотров: 191; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!