- •Содержание
- •Тема 1. Множества
- •1.1.Основные понятия
- •1.2. Операции над множествами
- •1.3. Геометрическое моделирование множеств. Диаграммы Венна
- •1.4. Алгебра множеств. Основные тождества алгебры множеств
- •Основные тождества алгебры множеств
- •1.5. Эквивалентность множеств
- •1.6. Счетные множества
- •1.7. Множества мощности континуума
- •Контрольные вопросы к теме 1
- •Тема 2. Отношения. Функции
- •2.1. Отношения. Основные понятия и определения
- •2.2. Операции над отношениями
- •2.3. Свойства отношений
- •2.4. Функции. Основные понятия и определения
- •Способы задания функций
- •Контрольные вопросы к теме 2
- •Тема 3. Графы
- •3.1. Основные характеристики графов
- •3.2. Матричные способы задания графов
- •Основные свойства матриц смежности и инцидентности
- •3.3. Изоморфизм графов
- •3.4. Маршруты, циклы в неориентированном графе
- •3.5. Пути, контуры в ориентированном графе
- •3.6. Связность графа
- •3.7. Экстремальные пути в нагруженных ориентированных графах
- •3.8 Алгоритм Форда – Беллмана нахождения минимального пути Предполагается, что ориентированный граф не содержит контуров отрицательной длины.
- •3.9. Алгоритм нахождения максимального пути
- •3.10. Деревья.. Основные определения
- •3.11. Минимальные остовные деревья нагруженных графов
- •Контрольные вопросы к теме 3
- •Тема 4. Булевы функции
- •4.1. Определение булевой функции
- •4.2. Формулы логики булевых функций
- •4.3. Равносильные преобразования формул
- •Основные равносильности булевых формул.
- •Правило равносильных преобразований
- •4.4. Двойственность. Принцип двойственности.
- •4.5. Булева алгебра (алгебра логики). Полные системы булевых функций
- •4.6. Нормальные формы
- •4.7. Разложение булевой функции по переменным
- •4.8. Минимизация формул булевых функций в классе дизъюнктивных нормальных форм
- •4.9. Применение алгебры булевых функций к релейно-контактным схемам
- •Контрольные вопросы к теме 4
- •Ответы на контрольные вопросы
- •Тема 2.
- •Тема 3.
- •Тема 4.
- •Указания к выполнению лабораторных работ
- •Контрольные задания по курсу "Дискретная математика".
- •1. Раздел «Множества»
- •2. Раздел «Отношения. Функции»
- •3. Раздел «Графы»
- •4. Раздел «Булевы функции»
- •Варианты заданий
- •Вопросы к экзамену по дисциплине «Дискретная математика»
- •Список рекомендованной литературы
- •Краткие сведения о математиках
Список рекомендованной литературы
1. Акимов О. Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория Базовых Знаний, 2001.
2. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. – М.: Энергоиздат, 1988.
3. Липский В. Комбинаторика для программистов. – М.: Мир, 1988.
4. Нефедов В. Н., Осипова В. А. Курс дискретной математики. – М.: Издательство МАИ, 1992.
5. Новиков Ф. А. Дискретная математика для программистов. – СПб.: Питер, 2002.
6. Судоплатов С. В., Овчинникова В. В. Элементы дискретной математики. – М.: ИНФРА – М, Новосибирск: Изд-во НГТУ, 2002.
Краткие сведения о математиках
Арнольд Владимир Игоревич – математик, академик Российской Академии наук.
Беллман Ричард – американский математик.
Буль Джордж (1815 – 1864) – английский математик. Основатель математической логики.
Гильберт Давид (1862 – 1943) – немецкий математик. Его исследования оказали большое влияние на развитие многих разделов математики, особенно на развитие логических основ математики.
Дейкстра Эдсгер (1930 – 2002) – голландский ученый, виднейший специалист в области программирования, лауреат премии Тьюринга.
Декарт Рене (1596 – 1650) – французский математик и философ. Впервые ввел понятия переменной, функции, системы координат на плоскости.
Кантор Георг (1845 – 1918) – немецкий математик. Разработал теорию бесконечных множеств. Идеи Кантора оказали большое влияние на развитие математики.
Колмогоров Андрей Николаевич (1903 – 19 ) – советский математик, академике АН СССР. Основополагающее значение имеют работы в области теории вероятностей. Является автором фундаментальных работ по теории множеств, теории меры, конструктивной логике, топологии, механике, теории дифференциальных уравнений, функциональному анализу.
Фибоначчи (Леонардо Пизанский) (1180 – 1240) – итальянский математик. Основные работы – трактаты об арифметике, алгебре и геометрии, которые являются первыми произведениями, содержащими задачи на приложения алгебры и геометрии.
Эйлер Леонард (1707 – 1783) – математик, физик, механик, астроном. Родился в Швейцарии, с 1726 по 1741 г. и с 1776 по 1783 г. работал в России.