Основная образовательная программа высшего профессионального образования Направление подготовки

Вид материала

Содержание

Базовая часть
Вариативная часть
Дисциплины по выбору обучающихся
Дисциплины по выбору обучающихся
Дисциплины по выбору обучающихся (научно
Дисциплины по выбору обучающихся (научно
Всего теоретическое обучение
Защита курсовой
Защита магистерской диссертации.
Общая трудоёмкость основной образовательной программы
М.1-Б «Общенаучный цикл – базовая часть»
010400 «Прикладная математика и информатика»
Содержание курсов общенаучного цикла ооп
2. Регулярные множества и автоматы
3. КС-языки и автоматы с магазинной памятью
4. Машины Тьюринга и проблемы разрешимости
5. Классы P и NP
6. Иерархии языков и задач
7. Сети Петри
Дискретная математика
...
Полное содержание

Подобный материал:

1 2 3 4 5 6 7 8

	Прикладная логика	2	72	48	24		2			экзамен
	Теория чисел	1.5	54	36	18			1.5		экзамен

М.3	Профессиональный цикл	31	1116	576	540	12.5	12.5	4	2

	Базовая часть	17	612	324	288	8.5	8.5

	Математические модели и методы принятия решений	4	144	72	72	2	2			экзамен
	Дискретные экстремальные задачи	5	180	108	72	2.5	2.5			экзамен
	Дискретный анализ и комбинаторика	4	144	72	72	2	2			экзамен
	Учебный семинар кафедры	4	144	72	72	2	2			зачет

	Вариативная часть	11	396	252	144	3	3	3.5	1.5

	Дисциплины по выбору обучающихся	2	72	36	36			2		экзамен
	Дискретные задачи принятия решений
	Теория оптимальных процессов
	Экстремальные задачи анализа данных и распознавания образов

	Дисциплины по выбору обучающихся	3	108	72	36	1.5	1.5			экзамен
	Теория графов
	Графы и алгоритмы
	Теория расписаний
	Теория статистических решений


	Дисциплины по выбору обучающихся (научно- исследовательские семинары)	3	108	72	36	1.5	1.5			зачет
	Дискретные экстремальные задачи
	Теория графов
	Теория статистических решений

	Дисциплины по выбору обучающихся (научно- исследовательские семинары)	3	108	72	36			1.5	1.5	зачет
	Дискретные экстремальные задачи
	Теория графов
	Теория статистических решений

	Всего теоретическое обучение
М.4	Практика и научно-исследовательная работа	51	1836							Защита курсовой
М.5	Итоговая государственная аттестация (Подготовка и защита магистерской диссертации)	12	432							Защита магистерской диссертации. Государственный экзамен
	Общая трудоёмкость основной образовательной программы	120	4320

Примечания:

Настоящий примерный учебный план составлен в соответствии с федеральным государственным образовательным стандартом (ФГОС) высшего профессионального образования по направлению подготовки магистров "010400 – Прикладная математика и информатика".

Курсовые работы (проекты), текущая и промежуточная аттестации (зачеты и экзамены) рассматриваются как вид учебной работы по дисциплине и выполняются в пределах трудоемкости, отводимой на ее изучение.

В соответствии с Типовым положением о вузе к видам учебной работы отнесены: лекции, консультации, семинары, практические занятия, лабораторные работы, контрольные работы, коллоквиумы, самостоятельные работы, научно-исследовательская работа, практики, курсовое проектирование (курсовая работа).

ПРИЛОЖЕНИЕ 3.1.

Дополнение к учебному плану подготовки магистров по профилю «Исследование операций и оптимизация»

П3.1. Учебные циклы ООП. Согласно ФГОС ВПО магистратуры по направлению подготовки 010400 «Прикладная математика и информатика» ООП включает следующие учебные циклы и разделы:

– М.1-Б «Общенаучный цикл – базовая часть»;

– М.1-В «Общенаучный цикл – вариативная часть»;

– М.2-Б «Профессиональный цикл – базовая часть»;

– М.2-В «Профессиональный цикл – вариативная часть»;

– М.3 «Практика и научно-исследовательская работа»;

– М.4 «Итоговая государственная аттестация».

Учебный план представлен в Приложении 3.

П3.1.2. Раздел «Общенаучный цикл – базовая часть». Учебный план раздела М.1-Б представлен в Приложении 3. Трудоёмкость цикла включает внеаудиторную (самостоятельную) работу магистранта, а также все виды текущей и промежуточной аттестаций. Коды формируемых компетенций – ОК-1 – ОК-5 и ПК-1 – ПК-7. Согласно ФГОС ВПО магистратуры по направлению подготовки 010400 «Прикладная математика и информатика» проектируемые результаты освоения дисциплин раздела должны быть следующие. Магистрант должен:

знать:

современные концепции естествознания, место естественных наук в выработке научного мировоззрения, историю, современные тенденции развития и достижения прикладной математики и информатики;

уметь:

осуществлять концептуальный анализ и формирование онтологического базиса при решении научных и прикладных задач в области информационных технологий; использовать знание иностранного языка в профессиональной деятельности, профессиональной коммуникации и межличностном общении;

владеть:

основами методологии научного познания и системного подхода при изучении различных уровней организации материи, информации, пространства и времени.

П3.1.3. Раздел «Общенаучный цикл – вариативная часть». Трудоёмкость цикла включает внеаудиторную (самостоятельную) работу магистранта, а также все виды текущей и промежуточной аттестаций. Коды формируемых компетенций – ОК-1-5 и ПК-1-7. В результате прохождения цикла магистрант должен:

знать:

современные концепции базовых математических дисциплин (таких, как теория вычислений, дискретная математика, прикладная логика, линейная алгебра и др.);

уметь:

осуществлять анализ современных фундаментальных математических проблем, разрабатывать алгоритмы соответствующих аналитических и численных решений;

владеть:

методологией разработки и применения аналитических и численных подходов решения математических и прикладных задач.

П3.1.4. Раздел «Профессиональный цикл – базовая часть». Трудоёмкость цикла включает внеаудиторную (самостоятельную) работу магистранта, а также все виды текущей и промежуточной аттестаций. Коды формируемых компетенций – ОК-6-9 и ПК-8-13. Согласно ФГОС ВПО магистратуры по направлению подготовки 010400 «Прикладная математика и информатика» проектируемые результаты освоения дисциплин раздела должны быть следующие. Магистрант должен:

знать:

фундаментальные концепции и профессиональные результаты, системные методологии в профессиональной области; современное состояние и принципиальные возможности теории математического моделирования и методов принятия решений, теории экстремальных задач, языков и систем программирования;

уметь:

использовать новые знания и применять их в профессиональной деятельности; использовать современные теории, методы, системы и средства прикладной математики и информационных технологий для решения научно-исследовательских и прикладных задач.

П3.1..5. Раздел «Профессиональный цикл – вариативная часть». Трудоёмкость цикла включает внеаудиторную (самостоятельную) работу магистранта, а также все виды текущей и промежуточной аттестаций. Коды формируемых компетенций – ОК-6-9 и ПК-8-13. В результате прохождения цикла магистрант должен:

знать:

современные концепции математических и прикладных дисциплин, связанных с выбранным направлением исследований в области математического моделирования и теории экстремальных задач;

уметь:

осуществлять анализ исследуемой прикладной проблемы методами исследования операций, разрабатывать соответствующие математические модели; конструировать алгоритмы аналитического и численного решения требуемых оптимизационных задач;

владеть:

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

П3.1.6. Раздел «Практика и научно-исследовательская работа». Трудоёмкость цикла включает внеаудиторную (самостоятельную) работу магистранта, а также все виды текущей и промежуточной аттестаций. Коды формируемых компетенций – ОК-4-7 и ПК-1-3, ПК-5, ПК-10.

Согласно ФГОС ВПО магистратуры по направлению подготовки 010400 «Прикладная математика и информатика» магистрант должен получить следующие практические навыки:

- навыки использования математического аналитического и численного моделирования, методов оптимизации для решения прикладных задач;

- навыки работы с современными программными и аппаратными средствами информационных технологий для выполнения научных исследований;

- способность проводить научные исследования и получать научные результаты (в том числе, в области математического моделирования и в методах решения экстремальных задач);

- способность публично выступать перед различными аудиториями с докладами/сообщениями о возникающих проблемах и путях их решения;

- способность работать в научно-исследовательском коллективе.

П3.1.7. Раздел «Итоговая государственная аттестация». Трудоёмкость цикла включает самостоятельную работу магистранта, а также все виды текущей и промежуточной аттестаций. Согласно ФГОС ВПО магистратуры по направлению подготовки 010400 «Прикладная математика и информатика» магистрант должен:

уметь:

использовать современные методы для исследования и решения научных и прикладных задач (в том числе, в области математического моделирования и методов оптимизации);

знать и уметь:

применять методы прикладной математики и информатики.

ПРИЛОЖЕНИЕ 4.1

СОДЕРЖАНИЕ КУРСОВ ОБЩЕНАУЧНОГО ЦИКЛА ООП

Наименование курса:

ТЕОРИЯ ВЫЧИСЛЕНИЙ

1. Введение

Цепочки, языки, графы и деревья. Порождающие грамматики и распознаватели, классификация Хомского, свойства КЗ-грамматик.

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

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

3. КС-языки и автоматы с магазинной памятью

Деревья вывода и эквивалентные преобразования КС-грамматик. Однозначность КС-грамматик и языков, приведение КС-грамматики к нормальной форме Хомского. Лемма о разрастании для КС-языков, пример языка, не являющегося КС-языком. Свойства замкнутости и незамкнутости класса КС-языков. Автоматы с магазинной памятью и их связь с КС-языками. Детерминированные КС-языки и их свойства.

4. Машины Тьюринга и проблемы разрешимости

Машины Тьюринга (ТМ) и их связь с порождающими грамматиками. Линейно-ограниченные автоматы и их связь с КЗ-языками. Алгоритмически неразрешимые проблемы, метод сведения, неразрешимые проблемы КС-грамматик и языков.

5. Классы P и NP

Сложность алгоритмов и задач. Недетерминированные ТМ (NTM), их детерминированное моделирование. Классы P и NP, полиномиальная сводимость, NP-полные и NP-трудные языки и задачи, Теорема Кука. NP-полнота задачи о 3-выполнимости и задачи о клике. NP-полнота задачи о вершинном покрытии и точном покрытии 3-множествами. NP-полнота задачи о трехмерном сочетании. Структура класса NP, список задач из NPC и кандидаты в NPI, класс co-NP.

6. Иерархии языков и задач

Многоленточные ТМ и их моделирование. Класс P-SPACE, примеры языков, полных для P-SPACE, и задач, требующих экспоненциальной памяти. Иерархия по емкостной сложности для DTM. Понятие моделирования, теорема об ускорении. Существование сколь угодно сложных задач, теорема Цейтина. RАМ с равномерным и логарифмическим критерием, ее связь с TM. Техника следов и нижняя оценка сложности распознавания симметрии. Альтернирующие машины Тьюринга (ATM) и их свойства. Полиномиальная иерархия, ее связь с ATM. Модели вычислений PTM, RTM и CTM, класс #P, примеры #P-полных задач. Параллельные RAM, их классификация и свойства. Тезисы инвариантности и параллельного выполнения.

7. Сети Петри

Сети Петри, графы разметок, теорема о дополнительных фишках. Моделирование сетями Петри, представление блок-схем, задачи о взаимном исключении, о производителе/потребителе, об обедающих философах, о читателях/писателях. Основные свойства сетей Петри, проблемы R-включения и R-эквивалентности. Покрывающее дерево, алгоритм проверки ограниченности сети. Полное покрывающее дерево и разрешимость проблемы ограниченности места в сети. Алгоритмы проверки t-тупиковости, безопасности, потенциальной живости, получения местом фишки, неограниченности срабатываний перехода. Проблемы достижимости и живости, их взаимосвязь. Языки сетей Петри, разрешимость проблемы принадлежности.

Наименование курса:

ДИСКРЕТНАЯ МАТЕМАТИКА

Выборки. Перестановки, сочетания, перестановки с повторениями, сочетания с повторениями. Биномиальная и полиномиальная теоремы. Разбиения. Числа Стирлинга 1-го и 2-го рода; свойства чисел Стирлинга; обращение Стирлинга. Числа Белла и их свойства. Формулы обращения. Дзета-функция и функция Мёбиуса. Метод включений и исключений. Оценки для числа элементов, не обладающих ни одним из n свойств. Формула для числа элементов, обладающих в точности m свойствами, 0 ≤ m ≤ n. Формула обращения Мёбиуса. Производящие функции. Примеры применения метода производящих функций для решения комбинаторных задач. Линейные рекуррентные соотношения с постоянными коэффициентами. Теорема о решении линейных рекуррентных соотношений. Числа Фибоначчи. Числа Каталана. Экспоненциальные производящие функции. Трансверсаль. Теорема о числе трансверсалей. Задача о гаремах. Латинские прямоугольники. Теорема Рамсея. Теорема Рамсея для графов. Верхние и нижние оценки для чисел Рамсея. Теорема Эрдеша – Секереша. Теорема Ван дер Вардена об арифметических последовательностях.

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

Графы. Основные понятия. Способы представления графов. Перечисление графов на нумерованных вершинах. Верхняя оценка для числа неизоморфных графов с q ребрами. Деревья и их свойства. Оценка числа неизоморфных корневых деревьев с q ребрами. Теорема Кэли о числе помеченных деревьев. Связность. Свойства двусвязных графов. Теорема Менгера. Эйлеровы циклы. Теорема Эйлера. Теорема Эйлера для ориентированных графов, последовательности де Брейна. Гамильтоновы циклы. Теорема Дирака. Гамильтоновы циклы и степенные последовательности. Теорема Хватала. Гамильтоновы циклы и совершенные паросочетания. Теорема Финка. Укладка графа в пространство. Планарный и плоский графы. Формула Эйлера. Теорема Понтрягина-Куратовского. Алгебраические критерии планарности. Правильная раскраска вершин графа. Оценки хроматического числа. Теорема Брукса. Теорема Зыкова. Раскраски планарных графов. Теорема о четырех красках. Совершенные графы. Теорема Ловаца. Совершенность триангулированных графов. Правильная раскраска ребер графа. Хроматический индекс. Теорема Кёнига о хроматическом индексе двудольных графов. Теорема Визинга.

Наименование курса:

ТЕОРИЯ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ

Модель канала связи с шумами, скорость кода, пропускная способность. Теорема Шеннона для двоичного симметричного канала связи с шумом (с доказательством). Вероятность ошибки декодирования. Стандартное расположение. Синдром.

Поле Галуа, его свойства.

Линейные коды. Кодирование и декодирование. Общие свойства линейных кодов. Теорема о связи проверочной и порождающей матриц. Теорема Глаголева.

Границы объема кода: граница Синглтона, граница Хэмминга, граница Варшамова-Гилберта, граница Плоткина. Оценки мощностей кодов, теоремы Джонсона.

Методы построения новых кодов из заданных. Комбинирование кодов. Теорема Плоткина. Каскадная конструкция.

Совершенные коды. Теорема о существовании совершенных кодов. Коды Хемминга над GF(q), способы задания, кодирование, декодирование, единственность. Группа автоморфизмов кода Хэмминга. Конструкции совершенных кодов: свитчинговые (коды Васильева, Моллара, конструкция

-компонент), каскадные (коды Зиновьева, Соловьевой, Фелпса). Оценки числа совершенных кодов. Общие свойства совершенных кодов, теоремы Шапиро и Злотника, группа автоморфизмов совершенных кодов. Связь совершенных кодов с блок схемами, конструкция Ассмуса и Маттсона.

Матрица Адамара. Коды Адамара. Связь кодов Адамара с кодами Хэмминга и блок-схемами.

Коды Рида-Маллера, группа автоморфизмов. Код Голея, его свойства. Код Нордстрома-Робинсона.

Двойственные коды. Весовой энумератор. Дискретное преобразование Фурье. Тождества Мак-Вильямс.

Теория циклических кодов. Кольцо многочленов над полем Галуа. Определение циклического кода. Теорема о необходимом и достаточном условии существования циклического кода с порождающим многочленом g(x). Кодирование и декодирование циклических кодов. Важные классы циклических кодов: коды Хэмминга, коды Боуза-Чоудхури- Хоквингема (БЧХ-коды), коды Рида-Соломона, коды Юстесена, коды Гоппы.

Наименование курса:

МАТЕМАТИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ

1. Введение в криптологию

Введение в криптологию. Секретность и имитостойкость. Основные идеи. Криптография и криптоанализ.

Криптографические системы с секретными ключами. Подстановки.. Перестановки. Полиалфавитные шифры. Шифр с бегущим ключом. Криптографические системы коды. Стандарты шифрования данных DES, AES, GOST. S-блоки, APN-функции, их свойства.

Теорема Шеннона о существовании совершенно секретных шифров.

Криптографические системы с открытыми ключами. Односторонняя функция с лазейкой. “Шарады” Меркля.

Криптосистема Диффи и Хэллмана и проблема вычисления дискретного логарифма.

Криптосистема RSA и проблема разложения числа на простые сомножители.

Криптосистема Меркля-Хэллмана, основанная на задаче об укладке ранца. Криптоанализ системы Меркля-Хэллмана.

Криптосистема Шамира.

Кодирующая система МакЭлиса. Криптосистема МакЭлиса, построенная на коде Рида-Маллера.

Цифровая подпись, применение различных криптосистем для создания цифровой подписи.

Криптосистемы на эллиптических кривых.

Применение теории кодирования в криптографии. Проблема аутентификации. Распределение секретов.

2. Сжатие информации

Разделимые и префиксные коды. Стоимость кодирования. Неравенство Крафта-Макмиллана. Теорема Крафта, теорема Макмиллана.

Оптимальное кодирование. Метод Хаффмена. Метод Фано.

Энтропия, ее свойства. Метод Шеннона для бернуллиевских источников. Теорема Шеннона.

Критерий разделимости побуквенного кодирования. Теоремы Маркова. Алгоритм распознавания разделимости.

Универсальное кодирование, теорема Фитингофа.

Код Левенштейна. Код “стопка книг”.

Адаптивные методы сжатия данных. Методы Лемпела-Зива и их модификации. Адаптивный метод Хаффмена.

Арифметический код.

Наименование курса:

ПРИКЛАДНАЯ ЛОГИКА

Blog

Основная образовательная программа высшего профессионального образования Направление подготовки

Содержание