1. Дискретная математика.
Булева алгебра высказываний. Принцип двойственности и закон двойственности. Нормальные формы алгебры высказываний. Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма.
Полнота системы функций. Базис. Критерии полноты.
Бинарные отношения. Свойства бинарных отношений: рефлексивность, симметричность, антисимметричность, транзитивность. Отношения эквивалентности. Классы эквивалентности.
Понятие графа: вершины, рёбра. Виды графов. Подграфы. Матрицы, ассоциированные с графами. Степени вершин. Маршруты, цепи и циклы. Расстояние между вершинами. Диаметр и радиус графа.
Связность графов. Компоненты связности. Связность ориентированных графов.
Деревья. Деревья минимальной суммарной меры. Ориентированные деревья. Упорядоченные деревья. Бинарные деревья.
Эйлеров цикл, цепь, граф. Критерий эйлеровости графа. Гамильтонов цикл, цепь, графы. Достаточные условия гамильтоновости графа.
Литература
Основная:
Новиков математика для программистов. – СПб.: Питер, 2009.Дополнительная:
Горбатов основы дискретной математики. Информационная математика: Учебник для втузов. – М.: Наука. Физматлит, 2000.2. Теория вероятностей и математическая статистика
Аксиоматическое и геометрическое определение вероятности события, свойства вероятности.
Виды количественного описания поведения случайных величин всех типов.
Случайные величины, их законы распределения и числовые характеристики.
Предельные теоремы теории вероятностей (общая и частная теорема Чебышева, теорема Бернулли, центральная предельная теорема)
Точечное и интервальное оценивание параметров распределений случайных величин.
Законы распределения и характеристики случайных процессов.
Литература
Основная:
Роднищев теории вероятностей и математической статистики. Учебное пособие. Казань, КГТУ, 2007. Гмурман вероятностей и математическая статистика. М., Высшая школа, 2005.Дополнительная:
Вентцель вероятностей. М., Высшая школа, 2005. Кожевников вероятностей и математическая статистика. М., Машиностроение, 2002.3. Теория игр и исследование операций
Транспортная задача линейного программирования.
Постановка задачи оптимизации перевозок. Математическая модель транспортной задачи. Методы решения транспортных задач. Методы улучшения допустимых решений. Различные постановки и модели транспортных задач. Задачи с правильным и неправильным балансом. Транспортная задача по критерию времени. Задача о назначениях. Решение задачи о назначениях
Сетевые задачи принятия решений.
Поиск оптимального маршрута в сети. Алгоритмы Дейкстры и Флойда. Оптимизация потоков в сетях с ограниченными пропускными способностями коммуникаций. Примеры решения сетевых задач. Нахождение сети минимальной длины (остовное дерево).
Дискретное программирование.
Общая постановка задачи дискретного программирования. Особенности методов решения задач.
Задачи оптимального выбора. Задача о рюкзаке (ранце), постановка и эвристический метод решения. Задача оптимального выбора проектов. Примеры решения задач оптимального выбора. Задача коммивояжера. Методы решения задачи коммивояжера.
Принятие решений в конфликтных ситуациях.
Основные типы конфликтных ситуаций. Предмет и методы теории игр. Классификация задач теории игр. Антагонистические игры двух лиц с нулевой суммой. Платежная матрица игры. Примеры постановок игровых задач принятия решений. Принцип минимакса. Чистые и смешанные стратегии. Методы практической реализации смешанных стратегий принятия решений.
Многокритериальные задачи оптимизации решений.
Задачи векторной оптимизации (примеры). Противоречивость критериев. Классификация методов решения многокритериальных задач. Априорные методы решения задач векторной оптимизации: введение линейной свертки, принцип справедливого компромисса, лексикографическая оптимизация, использование контрольных показателей, введение метрики в пространстве критериев.
Свертка критериев. Оптимизация решений по Парето. Методы и примеры построения Парето-оптимальных решений.
Литература
Основная:
, Моисеев теории принятия решений: Учебное пособие. – Казань: изд-во КГТУ, 2002. Черноруцкий принятия решений. – СПб.: БХВ, 2005.Дополнительная:
Новикова игр и исследование операций [Электронное издание], 2007, URL: http://npe. *****/dokumenti/YMK/Posobie/TKI/Teor_igr. rar , , Моисеев принятия решений [Электронное издание], 2007, URL: http://npe. *****/dokumenti/YMK/Posobie/TKI/TPR. rar Вентцель операций. – М.: Высшая школа, 2007. Таха Введение в исследование операций. – М.: Вильямс, 2007. Ширяев операций и численные методы оптимизации. – М.: КомКнига, 2007.4. Базы данных и экспертные системы
Основные понятия систем баз данных. Назначение и основные компоненты систем баз данных: база данных, система управления базами данных (СУБД), программные и языковые средства СУБД, пользователи баз данных, администратор систем баз данных и его функции.
Проектирование баз данных. Основные этапы проектирования БД: системный анализ предметной области. Инфологическое проектирование БД с использованием метода «Сущность-связь». Понятия объект, свойства, отношения объектов, классы объектов, экземпляры объектов, идентификатор экземпляров объектов. Понятия сущность, атрибуты, связи, первичные ключи сущностей. Типы связей. Построение семантической модели взаимосвязи объектов предметной области с помощью диаграмм ER-типа.
Проектирование баз данных. Даталогическое проектирование БД. Выбор модели СУБД. Общие сведения о даталогическом проектировании. Алгоритмы перехода от инфологической модели к реляционной базе данных в виде совокупности взаимосвязанных отношений.
Логическое и физическое проектирование реляционных баз данных. Отношения, атрибуты отношений и их домены, схема отношения. Табличное представление отношений. Проектирование РБД путем декомпозиции отношений. Функциональные зависимости, полнофункциональные зависимости, транзитивные зависимости. Нормальные формы и нормализация отношений путем анализа функциональных зависимостей.
Языки манипулирования данными. Структурированный язык запросов SQL. Простая выборка, выборка с использованием соединения отношений, подзапросы, коррелированные подзапросы. Запросы на обновление отношений. Представления. Внутренние и внешние соединения отношений.
