Государственное образовательное учреждение

высшего профессионального образования Московской области

«Международный университет природы, общества и человека «Дубна»

(Университет «Дубна»)

Институт системного анализа и управления

Кафедра системного анализа и управления

УТВЕРЖДАЮ

проректор по учебной работе С.В. Моржухина «_»_20 г.

ПРОГРАММА ДИСЦИПЛИНЫ

ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ

(наименование дисциплины) по направлению 010400 62 — Информационные технологии (№, наименование направления, специальности) Форма обучения: очная Уровень подготовки: бакалавр Курс (семестр): 1,2 (2,3 семестр) Дубна, Программа дисциплины «Основы дискретной математики»

Автор программы: к.т.н. Т.Б. Прогулова _ (подпись) Кафедра системного анализа и управления Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования и учебным планом по направлению подготовки 010400 62 — Информационные технологии Программа рассмотрена на заседании кафедры _системного анализа и управления (название кафедры) Протокол заседания № _ от «» 200 г.

Заведующий кафедрой /проф. Черемисина Е.Н. /

СОГЛАСОВАНО

Заведующий выпускающей кафедрой /доц. Токарева Н.А. / дата Рецензент: _ (ученая степень, ученое звание, Ф.И.О., место работы, должность)

ОДОБРЕНО

и.о. директора ИСАУ _ /проф. д.т.н. Черемисина Е.Н./ (ученое звание, степень) (подпись) (ФИО) «» _ 20 г.

Руководитель библиотечной системы _ /_Черепанова В.Г./ (подпись) (ФИО) 1) Выписка из временных требований к минимуму содержания и уровню подготовки выпускников по направлению 511900 — Информационные технологии Направление 010400 62 — «Информационные технологии».

Степень (квалификация) — бакалавр информационных технологий.

Индекс Наименование дисциплины и ее основные разделы Всего часов ЕН.Ф.01.01 Основы дискретной математики Логика высказываний, дизъюнктивные нормальные формы, введение в логические основы ЭВМ, синтез логических схем. Введение в логику предикатов. Элементы теории чисел, свойства числовых множеств и методы их доказательств, алгоритм Эвклида. Последовательности и математическая индукция. Введение в теорию множеств, алгебры Буля. Алгебры Буля. Полные системы функций. Полиномы Жегалкина.

Введение в k-значную логику. Комбинаторика. Введение в дискретную теорию вероятностей. Отношения, элементы реляционной алгебры.

Функции, конечные автоматы. Рекурсия. Конечные структуры: графы, сети, деревья, коды. Графы и деревья. O-нотация и эффективность Данная программа предназначена для подготовки бакалавров по направлению «Информационные технологии».

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

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

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

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

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

Перечень курсов, на которых базируется дисциплина Дисциплина «Основы дискретной математики» базируется на дисциплинах:

«Алгебра и геометрия» (1 семестр), «Информатика», тесно взаимосвязана с дисциплинами «Программирование на языке высокого уровня» (1 и 2 семестры), «Методы оптимизации»

(3 семестр), «Теория вероятностей и математическая статистика» (3 семестр), является базовой для дисциплин «Алгоритмы и анализ сложности» (4 семестр), «Теория конечных графов и ее приложения» (5 семестр), «Математическая логика и теория алгоритмов» ( семестр), «Теория автоматов и формальных языков» (6 семестр), «Неклассические логики» (7 семестр).

Методы обучения Обучение на лекционных занятиях предполагает использование мультимедийных средств (презентации, ролики, схемы, иллюстрации, интерактивная доска). Наряду с теоретическими, лекционными занятиями, исключительно важную роль в курсе играют семинарские (практические) занятия, которые проводятся в компьютерных классах группами по 10-12 человек и способствуют активному практическому переосмыслению и усвоению пройденного материала.

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

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

Самостоятельная работа студентов, предусмотренная учебным планом в объеме 72 часа (34 ч — во 2-м семестре и 38 часов в 3-м семестре), выполняется в ходе семестра в форме домашних работ и типовых расчетов (индивидуальных заданий, связанных с программной реализацией алгоритмов дискретной математики). Отдельные темы теоретического курса прорабатываются студентами самостоятельно в соответствии с планом самостоятельной работы и конкретными заданиями преподавателя с учетом индивидуальных особенностей студентов.

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

Форма итогового контроля Зачеты во 2-м и 3-м семестре, экзамен в 3-м семестре по всему курсу.

Методика формирования результирующей оценки Оценка по курсу формируется по итогам работы в семестре (контрольные работы, типовые расчеты, компьютерное тестирование, активность на лекциях и семинарах, индивидуальные творческие задания) — до 60 баллов и результатам сдачи экзамена — до 40 баллов.

Перевод 100-бальной оценки в 5-бальную оценку осуществляется следующим образом:

«удовлетворительно» — 55-69 баллов;

«неудовлетворительно» — менее 55 баллов.

3) Цели и задачи дисциплины Курс «Основы дискретной математики» имеет целью ознакомление студентов с фундаментальными структурами, понятиями, методами и алгоритмическими основами современной дискретной математики, ее применением в математической кибернетике и теории алгоритмов. В процессе обучения прививаются навыки свободного обращения с такими дискретными объектами, как конечные множества, бинарные отношения, функции алгебры логики, автоматные функции, графы и вырабатывается представление о проблематике теории кодирования, синтеза управляющих систем, сложности алгоритмов.

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

4) Требования к уровню освоения содержания дисциплины В результате изучения дисциплины студенты будут:

• знать:

основы теории множеств;

основные положения логик высказывания и предикатов, булевой алгебры;

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

основные положения теории графов;

основные принципы комбинаторного анализа;

основные положения теории формальных грамматик;

основы теории автоматов;

основы теории кодирования.

• уметь:

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

• иметь навыки:

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

5) Объем дисциплины и виды учебной работы (час):

Курсовой проект (работа) 6) Разделы (темы) дисциплины № п/п Раздел (тема) дисциплины, содержание Лекции ПЗ СР Отношения, функции, элементы реляционной алгебры.

Полные системы функций. Полиномы Жегалкина. Введение в k-значную логику. Дизъюнктивные нормальные формы, введение в логические основы ЭВМ, синтез логических схем.

дискретную теорию вероятностей числовых множеств и методы их Последовательности и математическая деревья, коды. Графы и деревья.

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

Элементы теории множеств. Отношения, функции, элементы реляционной алгебры Множества и классы. Антиномии (парадоксы). Антиномия всемогущества, парадокс «деревенский парикмахер». Антиномия Рассела. Класс разбиений множества.

Пустое множество. Универсум. Мощность (кардинальное число, порядок) множества.

Отношение. Кортеж. Бинарное отношение. Отношение принадлежности.

Отношение включения. Подмножество, надмножество, собственное подмножество.

Операции над множествами. Разбиение и покрытие.

Декартово произведение множеств. Соответствие. Пустое соответствие, полное соответствие. Область определения, прообраз (Dom) соответствия. Область значений, образ (Im) соответствия. Всюду определенные и сюръективные соответствия. Образ (im) и прообраз (coim) элемента. Матричное и графовое представление соответствия.

Инволюция (обращение) соответствий. Объединение, пересечение, дополнение, произведение соответствий. Функциональные соответствия, их связь с графиками функций. Соответствие Галуа и его роль в проективном распознавании образов.

Замкнутое подмножество.

Рефлексивное, симметричное, антисимметричное, асимметричное, транзитивное соответствия. Отношение предпорядка, порядка, толерантности, эквивалентности.

Фактормножество множества по отношению.

Бинарная операция и ее основное множество. Способы задания бинарной операции. Таблица Кэли. Операционный квадрат таблицы Кэли. Группоид. Квазигруппа.

Латинский квадрат. Лупа. Полугруппа. Моноид. Группа. Абелева группа. Группа симметрий фигуры. Симметрическая группа (группа подстановок). Иерархия систем с двумя бинарными операциями. Кольцо. Тело. Поле (коммутативное тело). Поле Галуа.

Алгебраическая система (алгебра). Носитель, основное множество алгебры. Сигнатура алгебры. Универсальная алгебра (собственно алгебра) и реляционная система (модель) как разновидности алгебраической системы (алгебры).

Изоморфизм, изоморфное отображение. Автоморфизм. Гомоморфизм.

Эндоморфизм. Эпиморфизм (сюръекция). Мономорфизм (инъекция). Биморфизм (биекция).

Точная верхняя (sup) и точная нижняя (inf) грани подмножеств. Свойства рефлексивности, антирефлексивности, антисимметричности, транзитивности отношений.

Отношение предпорядка, упорядоченности, строгой упорядоченности. Решетка (структура). Решетка как частично упорядоченное множество и как универсальная алгебра. Диаграмма Хассе.

Комбинаторика. Введение в дискретную теорию вероятностей Перестановки, размещения и сочетания. Сочетания с повторениями, их число.

Биномиальные коэффициенты и Бином Ньютона. Комбинаторные задачи.

Булевы бинарные операций. Их выражение через дизъюнкцию, конъюнкцию и отрицание.

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

Формула. Глубина формулы. Суперпозиция функций. Таблицы истинности и таблицы Кэли. Формы записи операций (функций) — инфиксная, префиксная (прямая польская запись), постфиксная (обратная польская запись). ДНФ и СДНФ. Карта Карно.

Некоторые булевы алгебры: дизъюнктивная алгебра, алгебра Вебба, алгебра Шеффера, импликативная алгебра, коимпликативная алгебра, алгебра Жегалкина.

Приложение булевых функций в области анализа и синтеза функциональных схем.

Логика высказываний Логика и доказательство. Высказывание и логика. Предикаты и кванторы.

Методы доказательств (прямое рассуждение, обратное рассуждение, метод «от противного»).

Исчисление высказываний как аксиоматическая теория в дизъюнктивном базисе Буля. Связки, пропозициональные буквы. Формула и аксиомы исчисления высказываний.

Правила вывода: правило подстановки, правило заключения (modus ponens).

Функции k-значной логики и их задание с помощью таблицы истинности и с помощью таблицы Кэли. Конечнозначная функция Вебба и конечнозначная алгебра Вебба. Конечнозначные алгебры Поста, Россера-Тьюкетта.

Введение в логику предикатов Предикат: n-местный (n=0, n>0), тождественно истинный, тождественно ложный, выполнимый. Область истинности предиката. Связь между n-местными предикатами и nместными отношениями. Квантор всеобщности и квантор существования. Предикатная переменная.

Исчисление предикатов. Четыре группы символов формализованного языка логики предикатов: предикатные переменные, предметные переменные, логические символы, вспомогательные символы. Пропозициональные переменные, m-местные переменные. Элементарная формула. Правила построения предикатных формул из элементарных.

Формула, подформула в исчислении предикатов. Область действия квантора.

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

Исчисление высказываний как основа (схема) исчисления предикатов. Три правила вывода исчисления предикатов (modus ponens, -правило и -правило). Вывод формулы в исчислении предикатов.

Элементы теории чисел, свойства числовых множеств и методы их доказательств, алгоритм Эвклида.

Решето Эратосфена. Метод выделения множителей Ферма. Алгоритм Эвклида Элементы теории графов Граф. Вершина, ребро, дуга. Неориентированный граф, ориентированный граф (орграф). Кратные ребра (дуги). Петли. Смежные вершины, смежные дуги. Степень вершины. Инцидентные ребро и вершина, дуга и вершина. Укладка графа. Плоский граф.

Матрица смежности, матрица инцидентности. Задание графа списками.

Изоморфные графы. Подграфы. Маршрут, цепь, простая цепь, (простой) цикл.

Компонента связности. Дерево. Остовные деревья. Графы k-связные (k-реберно-связные).

Обход графа. Длина маршрута, расстояние между вершинами. Одноместные операции: удаление или добавление ребра или вершины, стягивание ребра (отождествление пары смежных вершин), подразбиение ребра. Двуместные операции:

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

Эйлеров путь в графе. Задача о кенигсбергских мостах, головоломки. Эйлеров цикл. Теорема о существовании эйлерова пути. Теорема об эйлеровом пути в связном графе без вершин нечетной степени. Алгоритм нахождения эйлерова цикла. Оценка вычислительной сложности алгоритма. Прикладные задачи теории графов.

Деревья, их свойства и представления.

Критерий существования графа с заданными степенями вершин. Критерий существования обхода всех ребер графа. Необходимое и достаточное условие вложения графа в плоскость. Теорема о наименьшем числе цветов, достаточном для раскраски графа. Теорема о группе автоморфизмов (симметрий) графа. Случайные графы.

Гамильтонов путь в графе, гамильтонов цикл. NP-полные задачи. Алгоритм нахождения всех гамильтоновых циклов в графе.

Вес дуги (ребра). Взвешенные графы и орграфы. Длина пути в обычном и во взвешенном орграфе, расстояние между вершинами. Задача коммивояжера. Алгоритмы поиска субоптимального решения задачи коммивояжера. Алгоритмы Краскала и Прима поиска минимального остовного дерева.

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

Алгоритм Форда-Беллмана нахождения расстояния от источника до всех вершин.

Доказательство правильности алгоритма. Оценка временной сложности алгоритма.

Алгоритм Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Приложения алгоритма Дейкстры для решения задач маршрутизации в сетях.

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

Алгоритм нахождения расстояний от источника до всех вершин в бесконтурном графе (с предварительной перенумерацией вершин). Применение алгоритмов в методах управления выполнением проекта (сети PERT — Project Evaluation and Review Technique или CPM — Critical Path Method).

Нахождение кратчайших путей между всеми парами вершин в ориентированном графе — транзитивное замыкание отношения. Модификация алгоритма Уоршалла.

Алгоритм вычисления расстояний между всеми парами вершин — метод Флойда.

Графы и ориентированные графы: аналогии и отличия. Подграфы, ориентированные подграфы и связность.

Знаковые графы и их практическое применение. Задачи из области социологии малых групп, экономики и политики. Теорема о структуре (теорема Харари о балансе).

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

Сети Петри. Формальное определение сети Петри. Функционирование сети Петри. Конечные разметки сети. Ограниченность. Моделирование на сетях Петри.

Задачи о потоках в сетях. Пропускная способность разреза. Теорема Форда и Фалкерсона о максимальном потоке и минимальном разрезе. Метод увеличивающих цепей. Алгоритм построения максимального потока. Метод Диница для построения максимального потока. Алгоритм построения вспомогательной бесконтурной сети.

Конечные автоматы.

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

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

Формальные грамматики Формальные грамматики. Место теории формальных грамматик в математической лингвистике. Порождающая грамматика. Основной и вспомогательный алфавит (словарь). Терминальные (основные) и нетерминальные (вспомогательные) символы. Начальный символ; конечный набор правил вывода и их вид.

Вывод в порождающей формальной грамматике. Слова языка (основные символы); имена классов слов и словосочетаний (вспомогательные символы); имя класса словосочетаний, являющихся предложениями (начальный символ = символ предложения).

Выводимая цепочка. Предложение. Язык, порожденный грамматикой.

Алгоритмы и рекурсия Рекурсивные функции и алгоритмы. Сложность алгоритмов. О-нотация и эффективность алгоритмов.

Элементы теории кодирования Кодирование и декодирование при передаче информации по каналам связи с «шумом». Математическая модель системы связи. Блочный двоичный (m,n)-код и функции, определяющие схему кодирования и схему декодирования. Функция ошибок.

Коды с обнаружением ошибок и коды с исправлением ошибок.

Аксиомы расстояний и расстояние Хемминга. Вес слова, вес поразрядной суммы.

Теорема о наименьшем расстоянии между кодовыми словами, необходимом для обнаружения ошибок; теорема о наименьшем расстоянии между кодовыми словами, необходимом для исправления ошибок.

Преимущества матричного кодирования. Порождающая матрица кода.

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

Групповые коды Хемминга, исправляющие однократную ошибку. Схема кодирования и схема декодирования Хемминга.

№ п/п № раздела дисциплины Наименование практических занятий (семинаров) 1 Введение 1. Дискретизация, примеры, актуальность дискретного 2 Элементы теории 1. Множества, способы задания, законы алгебры множеств. Отношения, множеств и их применение для доказательства функции, элементы тождеств. Диаграммы Эйлера-Венна.

реляционной алгебры. 2. Отношения, способы задания, свойства отношений и 3 Булевы функции. 1. Булевы функции. Способы задания. Бинарные Алгебры Буля. Полные операции. Свойства бинарных булевых функций.

системы функций. 2. Функционально полные базисы. ДНФ, СДНФ, КНФ, Полиномы Жегалкина. СКНФ, полиномы Жегалкина. Упрощение ДНФ. Карта логику. Дизъюнктивные 3. Анализ и синтез логических схем.

введение в логические 4 Комбинаторика. 1. Перестановки, размещения, сочетания Введение в дискретную 2. Бином Ньютона. Треугольник Паскаля.

теорию вероятностей 3. Комбинаторные задачи 5 Логика высказываний 1. Классификация формул логики высказываний.

6 Введение в логику 1. Язык логики предикатов. Формализация. Множества 7 Элементы теории 1. Свойства числовых множеств и методы их чисел, свойства числовых доказательств множеств и методы их Алгоритм Эвклида.

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

формальные грамматики. 2. Минимизация автоматов.

9 O-нотация и 1. О-нотация. Подходы к анализу эффективности 10 Конечные структуры: 1. Способы задания графов.

графы, сети, деревья, 2. Категории связности графа (алгоритмы) коды. Графы и деревья. 3. Циклы Эйлера Примеры индивидуальных заданий (типовых расчетов) 1. Программный иллюстратор операций над множествами.

2. Программный иллюстратор операций над нечеткими множествами.

3. Компьютерная реализация модели соответствия Галуа.

4. Компьютерная реализация преобразования логических функций, заданных ТИ, к СДНФ, СКНФ, ПНФ.

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

6. Алгоритм определения числа компонент связности графа.

7. Алгоритмы нахождения цикла Эйлера и циклов Гамильтона.

8. Решение задачи коммивояжера.

9. Алгоритмы построения минимального остовного дерева.

10. Алгоритмы нахождения кратчайшего расстояния между двумя вершинами графа (орграфа). Нахождение кратчайших путей между двумя вершинами графа (орграфа).

11. Алгоритм Форда-Фалкерсона определения максимального потока.

12. Знаковые неориентированные графы: проверка сбалансированности и разбиение на классы. Перечисление контуров положительной и отрицательной обратной связи.

7) Учебно-методическое обеспечение дисциплины Рекомендуемая литература Основная:

1.Новиков Ф.А. Дискретная математика для программистов. СПб: Питер, 2004.

2.Яблонский С.В. Введение в дискретную математику: Учебное пособие для вузов.

М.: Высшая школа, 2003.

3.Шапорев С.Д. Дискретная математика: Курс лекций и практических занятий. СПб.: БХВ-Петербург, 2009.

Дополнительная:

1.Мазный Г.Л., Прогулова Т.Б. Дискретная математика: Учебное пособие М.:

Международный университет природы, общества и человека "Дубна", 2004.

2.Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. – M.: Физматлит, 2009.

3.Нефедов В.Н., Осипова В.А. Курс дискретной математики. — М.: Издательство МАИ, 1992.

4.Андерсон Дж.А. Дискретная математика и комбинаторика М.: Вильямс, 2004.

5.Гаврилов Г.П., Сапоженко А. А. Задачи и упражнения по дискретной математике М.: Физматлит, 2006.

8) Материально-техническое обеспечение дисциплины Для проведения практических занятий необходим специализированный компьютерный класс. Для самостоятельной работы используются компьютерные классы с доступам к ресурсу Интернет.

9) Формы контроля, перечень выносимых на экзамен (зачет) вопросов.

Формы контроля: экзамен.

Перечень вопросов, выносимых на экзамен по курсу «Основы дискретной математики»:

1. Множества. Отношение принадлежности. Универсум. Мощность множества.

Пустое множество. Подмножество, надмножество, собственное подмножество.

Семейство множества. Булеан множества. Отношение включения. Способы задания множеств. Парадокс Рассела.

2. Операции над множествами. Круги Эйлера. Покрытия и разбиения. Классы 3. Законы алгебры множеств. Формула включений и исключений.

4. Декартово произведение множеств. Соответствие. Пустое соответствие, полное соответствие. Область определения, прообраз (Dom) соответствия. Область значений, образ (Im) соответствия. Всюду определенные и сюръективные соответствия. Образ (im) и прообраз (coim) элемента.

5. Соответствия. Способы задания соответствий.

6. Инволюция (обращение) соответствий. Объединение, пересечение, дополнение, произведение соответствий. Функциональные соответствия, их связь с графиками 7. Соответствие Галуа и его роль в проективном распознавании образов. Замкнутое подмножество.

8. Отношение. Бинарное отношение. Рефлексивное, симметричное, антисимметричное, асимметричное, транзитивное отношения.

9. Отношение эквивалентности. Фактормножество множества по отношению.

10. Отношение предпорядка, упорядоченности, строгой упорядоченности. Отношение частичного порядка.

11. Замыкание отношений. Рефлексивное, симметричное, транзитивное замыкание 12. Понятие нечеткого множества. Функция принадлежности. Способы формализации нечетких множеств. Наиболее распространенные параметрические функции принадлежности.

13. Основные логические операции над нечеткими множествами и их свойства.

14. Диаграмма Хассе как способ задания отношения частичного порядка на 15. Отображения. Изоморфизм. Автоморфизм. Гомоморфизм. Эпиморфизм.

Эндоморфизм. Мономорфизм. Биморфизм.

16. Бинарная операция и ее основное множество. Способы задания бинарной операции. Таблица Кэли. Операционный квадрат таблицы Кэли.

17. Группоид. Квазигруппа. Латинский квадрат. Лупа. Полугруппа. Моноид. Группа.

Абелева группа.

18. Группа симметрий фигуры. Группа подстановок.

19. Иерархия систем с двумя бинарными операциями. Кольцо. Тело. Поле (коммутативное тело). Поле Галуа.

20. Решетка (структура). Решетка как частично упорядоченное множество. Решетка как универсальная алгебра.

21. Алгебраическая система (алгебра). Носитель, основное множество алгебры.

Сигнатура алгебры. Универсальная алгебра (собственно алгебра) и реляционная система (модель) как разновидности алгебраической системы (алгебры).

22. Алгебра логики. Функции алгебры логики. Существенные и несущественные переменные. Бинарные логические операции. Формула. Суперпозиция функций.

Таблицы истинности и таблицы Кэли.

23. Формы записи операций (функций) — инфиксная, префиксная, постфиксная.

Эквивалентные формулы.

24. Основные схемы логически правильных рассуждений.

25. Тождества (законы), определяющие операции дизъюнкции, конъюнкции и отрицания: идемпотентностей, коммутативностей, ассоциативностей, дистрибутивностей, двойного отрицания, де-Моргана, склеивания, поглощения, нуля (лжи) и единицы (истины). Закон противоречия, закон исключенного третьего.

26. Функционально полные системы (базисы). Булева алгебра логики.

Функциональная полнота системы булевых функций. Примеры других алгебр логики.

27. Выражение через дизъюнкцию, конъюнкцию и отрицание других логических бинарных операций.

28. Двойственность.

29. Булева алгебра логики. СДНФ и ДНФ. Карта Карно. Функциональные схемы как приложение булевых функций.

30. КНФ и СКНФ.

31. Полиномы Жегалкина.

32. Функции k-значной логики и их задание с помощью таблицы истинности и с помощью таблицы Кэли. Примеры k-значных логик.

33. Кодирование и декодирование при передаче информации по каналам связи с «шумом». Математическая модель системы связи. Вектор ошибок.

34. Коды с обнаружением ошибок и коды с исправлением ошибок.

35. Расстояние Хемминга. Вес слова, вес поразрядной суммы.

36. Теорема о наименьшем расстоянии между кодовыми словами, необходимом для обнаружения ошибок.

37. Теорема о наименьшем расстоянии между кодовыми словами, необходимом для исправления ошибок.

38. Коды Хемминга, исправляющие однократную ошибку. Схема кодирования и схема декодирования Хемминга.

39. Граф. Вершина, ребро, дуга. Неориентированный граф, ориентированный граф (орграф). Кратные ребра (дуги). Петли. Смежные вершины, смежные дуги. Степень вершины. Инцидентные ребро и вершина, дуга и вершина.

40. Основные классы графов: обыкновенный, орграф, псевдограф, мультиграф, сеть.

41. Виды графов: двудольные графы, регулярные графы, полные графы, деревья, планарные графы 42. Изоморфизм графов.

43. Способы задания графов.

44. Подграфы. Маршрут, цепь, простая цепь, (простой) цикл. Компонента связности.

Связность в ориентированном графе. Дерево. Остовное дерево. Реберная и вершинная связности графа.

45. Обход графа. Длина маршрута, расстояние между вершинами. Одноместные операции: удаление или добавление ребра или вершины, стягивание ребра (отождествление пары смежных вершин), подразбиение ребра. Двухместные операции.

46. Эйлеров путь в графе. Задача о кенигсбергских мостах. Эйлеров цикл. Теорема о существовании эйлерова цикла.

47. Алгоритм нахождения эйлерова цикла и его вычислительная сложность.

48. Гамильтонов цикл в графе. Алгоритм с возвратом для поиска гамильтонова пути.

Оценки вычислительной сложности алгоритма.

49. Задача коммивояжера. Алгоритм поиска субоптимального решения.

50. Задача построения минимального остовного дерева. Алгоритм Краскала. Алгоритм Прима. Оценка вычислительной сложности этих алгоритмов.

51. Перенумерация вершин графа. Алгоритм топологической сортировки.

52. Вес дуги (ребра). Взвешенные графы и орграфы. Длина пути в обычном и во взвешенном орграфе, расстояние между вершинами. Контур, его длина и ее знак.

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

53. Принцип оптимальности Беллмана. Алгоритм нахождения кратчайшего пути в ориентированном графе и его вычислительная сложность.

54. Алгоритм вычисления расстояний между всеми парами вершин графа. Общий случай.

55. Алгоритм нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг — метод Дейкстры. Оценка вычислительной сложности.

56. Алгоритм топологической сортировки. Алгоритм нахождения расстояния от источника до всех остальных вершин в графе в случае бесконтурного графа.

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

58. Теорема о структуре (теорема Харари о балансе).

59. Знаковые орграфы как модель когнитивных карт. Контуры положительной и отрицательной обратной связи и устойчивость/изменчивость моделей на орграфах.

60. Двудольные графы. Необходимое и достаточное условие двудольности графа.

61. Сети Петри. Функционирование сети Петри. Конечные разметки сети.

62. Сети Петри. Ограниченность, безопасность, сохраняемость, достижимость, живость. Моделирование на сетях Петри.

63. Потоки в сетях. Разделяющие множества. Сеть. Поток в сети. Классификация вершин по воздействию на поток. Величина потока. Разрез и поток через разрез.

Теорема о максимальном потоке. Метод увеличивающих цепей. Алгоритм построения максимального потока.

64. Конечный автомат как математическая модель устройства с конечной памятью и как управляющая система. Способы описания конечных автоматов:

перечислительный; диаграмма состояний; таблица состояний.

65. Конечный автомат. Способы задания конечного автомата. Автоматное отображение 66. Минимальный автомат. Алгоритм Мили минимизации конечного автомата 67. Формальные грамматики.

68. Иерархия Хомского (классификация грамматик и порождаемых ими языков) 69. Правила произведения и суммы в комбинаторике 70. Перестановки без повторений 71. Перестановки с повторениями 72. Размещения без повторений 73. Размещения с повторениями 74. Сочетания без повторений 75. Сочетания с повторениями Пример экзаменационного билета Международный университет природы, общества и человека «Дубна»

Направление 010400 62 — Информационные технологии Курс II (3-й семестр) Дисциплина Основы дискретной математики 1. Операции над множествами. Круги Эйлера. Покрытия и разбиения. Классы разбиения.

2. Гамильтонов цикл в графе. Алгоритм с возвратом для поиска гамильтонова пути.

Оценки вычислительной сложности алгоритма.

3. Перестановки без повторений.