Математические основы информатики

Кафедра информатики и автоматизации научных исследований

Специальность: Прикладная информатика

Целями освоения дисциплины «Информатика (Математические основы информатики)» являются обучение студентов законам и методам обработки информации, вопросам построения математических моделей для конкретных технических, экономических и физических систем, а так же основным понятиям теории графов, теории информации и кодирования. В курсе изучаются линейные оптимизационные модели, задачи дискретной оптимизации, а так же изучается аппарат теории графов, теории информации и кодирования и другие фундаментальные разделы математических основ информатики. В курс включены основные понятия теории множеств, бинарных отношений, комбинаторного анализа и алгебры логики. В результате освоения дисциплины обучающийся должен: знать основные понятия теории линейных оптимизационных моделей, моделей дискретной оптимизации, теории графов, теории информации и кодирования; уметь доказывать основные теоремы двойственности в линейном программировании, теории графов, теории информации и кодирования; владеть представлениями (навыками) в решении задач линейного программирования (симплекс-метод прямой, двойственный), задач дискретной оптимизации (метод ветвей и границ, динамическое программирование).

Содержание

1. ЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ. Понятие оптимизационных задач. Примеры формальных постановок оптимизационных задач. Общая постановка задачи математического программирования. Задачи линейного программирования. Эквивалентные формы записи задач линейного программирования Геометрический смысл задач линейного программирования. Графическое решение задач линейного программирования. Теорема о выпуклости множества допустимых решений задачи линейного программирования. Теорема о выпуклости множества оптимальных решений задач линейного программирования. Симплекс метод решения задач линейного программирования. Искусственное начальное решение в задаче линейного программирования. Особые случаи применения симплекс-метода. Двойственность. Двойственные задачи линейного программирования для различных форм. Теорема о соотношениях линейных форм. Теорема о равенстве линейных форм. Теорема о взаимодвойственности систем линейных однородных алгебраических уравнений. Основная теорема двойственности. Следствие из основной теоремы двойственности о связи оптимальных решений прямой и двойственной задач линейного программирования. Теорема равновесия. Теорема о дополняющей нежесткости. Интерпретация двойственных оценок. Двойственный симплекс-метод. Обобщенный симплекс метод.
2. ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ ПЕРЕБОРНОГО ТИПА. Задачи целочисленного булева программирования. Каноническая и многомерная задачи о ранце и их интерпретации. Задача коммивояжера и ее интерпретации. Задачи о назначениях и их интерпретации. Метод ветвей и границ. Общая схема метода ветвей и границ. Решение канонической задачи о ранце методом ветвей и границ. Теорема Данцига об оптимальном решении непрерывной задачи о ранце. Решение многомерной задачи о ранце методом ветвей и границ. Решение задачи коммивояжера методом ветвей и границ. Решение задачи целочисленного линейного программирования методом ветвей и границ. Решение задачи о ранце с использованием табличной схемы. Решение задачи о ранце с использованием рекуррентных соотношений динамического программирования. Решение задачи коммивояжера с использованием рекуррентных соотношений динамического программирования. Задача о назначениях. Канонический вид. Простейшая задача о назначениях. Алгоритм Куна решения задачи о назначениях.
3. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ. Понятие простого и ориентированного графа. Подграфы. Операции над графами. N- мерный куб. Задание бинарных отношений графами. Теорема Эйлера о необходимых и достаточных условиях Эйлеровости графа. Алгоритм Флери (с обоснованием) построения в графе Эйлерова цикла. Теорема Рейда "Почти нет Эйлеровых циклов". Гамильтоновы графы. Способы задания графов. Теорема Кенига о двудольности графа. Теорема о цикломатическом числе. Следствие о связи цикломатического числа с количеством различных циклов. Теорема о вариантах определения дерева. Алгоритмы определения остова минимального веса. Теорема Краскала. Кодирование деревьев. Код Прюфера. Восстановление дерева по коду Прюфера. Формула Кэли. Независимые множества. Построение наибольшего независимого множества. Оценки числа независимости графа. Примеры использования независимых множеств. Теорема об оценке числа независимости графа. Внешне устойчивое множество. Прикладные задачи на доминируемость. Поиск наименьшего доминирующего множества. Вершинное покрытие графа. Связь покрытий с независимыми множествами. Клика. Паросочетания. Реберные покрытия графа. Независимость, доминируемость и покрытия. Общая схема. Зависимости характеристик. Планарность. Теорема Эйлера о планарности. Доказательство непланарности графа K5. Доказательство непланарности графа K3,3. Теорема Понтрягина-Куратовского (без доказательства). Примеры планарных и непланарных графов. Теорема об укладке графа в трехмерном пространстве. Вершинная и реберная раскраска графа. Алгоритм последовательной раскраски. Алгоритм укладки графа. Гиперграфы. Реализация гиперграфов. Теорема о реализации гиперграфа в виде дерева. Оптимизационные задачи на графах. Математическая модель построения максимального потока. Теорема Форда-Фалкерсона о максимальном потоке в транспортной сети. Алгоритм Форда-Фалкерсона поиска максимального потока в транспортной сети. Решение простейшей задачи о назначениях алгоритмом Форда-Фалкерсона. 1-оптимальный алгоритм решения задачи коммивояжера. Максиминные и минимаксные задачи выбора. Задачи теории расписаний. Задача о назначениях с индивидуальными предпочтениями. Расчет временных характеристик сетевых моделей
4. ВВЕДЕНИЕ В ТЕОРИЮ ИНФОРМАЦИИ И КОДИРОВАНИЯ. Сообщения. Текстовая модель. Мера количества информации. Теорема Шеннона о величине энтропии. Энтропия сложных событий. Неравенство Мак-Миллана. Теорема о соотношениях между энтропией и коэффициентом сжатия. Алфавитное кодирование. Задача оптимального кодирования. Метод Шеннона-Фано. Метод Хаффмана. Методы повышения надежности передачи информации. Коды, исправляющие ошибки. Коды Хэмминга.

Отчетность

Семестр 2: К/Р Зач Экз
Семестр 3: Экз