Наименование дисциплины: Дискретные и вероятностные модели

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

Профильная направленность: Математическая кибернетика

Квалификация (степень) выпускника: магистр

Форма обучения: очная

Автор: д-р физ.-мат. наук, профессор, зав. кафедрой дискретного анализа .

1. Целями освоения дисциплины «Дискретные и вероятностные модели» являются

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

2. Дисциплина «Дискретные и вероятностные модели» - это обязательный курс базовой части профессионального цикла.

Курс содержит основные факты теории Кука – Карпа, содержащей современное представление о сложности и труднорешаемости дискретных задач. Приводятся и характеризуются многочисленные комбинаторные задачи, которые служат основными дискретными моделями прикладной математики; уточняются представления о массовых и индивидуальных задачах. Излагаются факты и методы сводимости задач. Дается классификация задач по сложности. Рассматриваются основные направления исследования и редукции труднорешаемых задач.

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

НЕ нашли? Не то? Что вы ищете?

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

3. В результате освоения дисциплины обучающийся должен:

Знать: основные дискретные модели; эффективные методы дискретного программирования; основные факты современной теории сложности дискретных задач.

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

Владеть: навыками методологически грамотного осмысления конкретно-научных проблем.

4. Общая трудоемкость дисциплины составляет 4 зачетные единицы, 144 часа.

5. Содержание дисциплины:

№ п/п

Раздел дисциплины

1

Примеры эффективных алгоритмов (краткий обзор). Примеры труднорешаемых задач.

2

Индивидуальная и массовая задачи. Задачи распознавания и иные. «Разумное» кодирование задач. Алгоритм, его временная трудоемкость. Полиномиально разрешимая задача.

3

Недетерминированный полиномиальный алгоритм (содержательное и формальное определение). Класс NP. Примеры.

4

Полиномиальная сводимость. Теорема Кука.

5

Шесть основных NP-полных задач.

6

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

Алгоритм Кристофидеса.

7

Задачи с числовыми параметрами. Сильная NP – полнота. Псевдополиномиальная разрешимость задач.

Анализ примеров.

8

Доказательство NP-полноты задач из разных областей прикладной математики – теории графов, математического программирования, теории информации, логики и др.

6. Учебно-методическое и информационное обеспечение дисциплины:

а) основная литература:

1. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

2. Теория графов. М.: Наука, 1980; 4-е изд. М.: ЛКИ/URSS, 2008.

3. Комбинаторная оптимизация: Алгоритмы и сложность. М.: Мир, 1985.

4. Лекции по математике. Т.10: Перебор и эффективные алгоритмы: Учебное пособие. М.: ЛКИ, 2008.

б) дополнительная литература:

1. Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

2. Левин задачи перебора // Проблемы передачи информации. 1973, вып.3. С. 115-116.

3. Cook S. A. The complexity of theorem-proving procedure // Proc. 3-d Annual ACM on the Theory of Computing. Ohio. 1971. P. 151-159.

4. Karp R. M. Reducibility among Combinatorial problems // Complexity of computer computations. Proc. Symp. Math. 1972. P. 85-103.