Комбинаторная теория и приложения
Nbsp;
Программа государственного экзамена для магистрантов ИМИТ ОмГУ,
Уч. год
Направление – Прикладная математика и информатика
Магистерская программа «Математическое моделирование»
Раздел: Криптография
Криптосистема с открытым ключом 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.Детерминированные модели сообществ с взаимодействием индивидуумов. Модели Лотки-Вольтерра в дифференциальной форме; свойства решений; конкурентное равновесие; существование предельных циклов; диссипативные по Вольтерра сообщества.
Раздел: Многомерные статистические методы и временные ряды
|
|
|
1. Многомерная генеральная и выборочная совокупности. Векторные случайные величины и признаки. Многомерные распределения. Многомерная нормально распределенная генеральная совокупность. Выборка из генеральной совокупности. Методы отбраковки грубых результатов измерений (наблюдений).
2. Регрессионный анализ. Линейная множественная регрессия.
3. Компонентный и факторный анализ. Проблема снижения размерности вектора изучаемых признаков. Линейная модель метода главных компонент. Матричные операции. Собственные числа и векторы. Дисперсия исследуемых признаков. Компоненты дисперсии в факторном анализе. Матрица факторных нагрузок.
4. Канонические корреляции и канонические величины генеральной совокупности. Канонические корреляции и их интерпретация. Оценка канонических корреляций и канонических величин.
Раздел: Разностные схемы для задач с пограничным слоем
1. Дифференциальное уравнение первого порядка. Построение и обоснование схемы равномерно сходящейся схемы.
2. Уравнение второго порядка с пограничным слоем. Принцип максимума, оценка решения.
3. Уравнение второго порядка с пограничным слоем. Внутренние и внешние разложения решения.
|
|
|
4. Построение схемы Ильина. Формулировка теоремы о равномерной сходимости этой схемы.
Раздел: Метод Монте-Карло в задачах математической физики
1. Моделирование дискретных случайных величин. Стандартный метод моделирования непрерывных случайных величин. Специальные методы моделирования непрерывных случайных величин (геометрическое распределение, распределение Пуассона). Метод исключения. Метод суперпозиции.
2. Приближенное вычисление интегралов. Простейший метод Монте-Карло для вычисления интегралов. Случайные квадратурные формулы. Основные способы уменьшения дисперсии (выделение главной части, метод существенной выборки, выборка по группам, понижение порядка интегрирования).
3. Процесс блуждания по сферам. Определение и простейшие свойства блуждания по сферам.
4. Общая схема решения интегральных уравнений методом Монте-Карло. Построение и обоснование алгоритма блуждания по сферам для решения краевой задачи для уравнения Гельмгольца.
Литература:
Криптография
1. Романьков В.А. Введение в криптографию. Курс лекций. Изд-во ОмГУ, Омск, 2006 г.
Комбинаторная теория и приложения
1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
Ильев В.П. Комбинаторные задачи на графах. Учебное пособие. Изд-во ОмГУ, Омск, 2013 г.
Дата добавления: 2019-02-12; просмотров: 112; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!