|
Курс Дискретная математика |
Дискретная математика: Информация
Автор: Олег Кузнецов
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 102 студентам
Уровень:
Для всех
Длительность:
3:00:00
Студентов:
6005
Выпускников:
1030
Качество курса:
4.66 | 4.45
Дискретная математика - одна из важнейших составляющих современной математики. С одной стороны, она включает фундаментальные основы математики - теорию множеств, математическую логику, теорию алгоритмов; с другой стороны, является основным математическим аппаратом информатики и вычислительной техники и потому служит базой для многочисленных приложений в экономике, технике, социальной сфере.
В отличие от традиционной математики (математического анализа, линейной алгебры и др.), методы и конструкции которой имеют в основном числовую интерпретацию, дискретная математика имеет дело с объектами нечисловой природы: множествами, логическими высказываниями, алгоритмами, графами. Благодаря этому обстоятельству дискретная математика впервые позволила распространить математические методы на сферы и задачи, которые ранее были далеки от математики. Примером могут служить методы моделирования различных социальных и экономических процессов.
Знание теории множеств, алгебры, математической логики и теории графов совершенно необходимо для четкой формулировки понятий и постановок различных прикладных задач, их формализации и компьютеризации, а также для усвоения и разработки современных информационных технологий. Понятия и методы теории алгоритмов и алгебры логики лежат в основе современной теории и практики программирования.
Курс предусматривает изучение: языка дискретной математики, таких ее основных понятий, как множества, функции, отношения; основ комбинаторики, элементов общей алгебры; введения в математическую логику; теории графов.
Специальности: Программист, Математик
План занятий
Занятие
Заголовок <<
Дата изучения
Множества. Операции над множествами
Понятие множества. Примеры множеств. Элемент множества. Подмножество. Мощность конечного множества. Пустое множество. Равенство множеств. Универсальное множество. Операции над множествами: объединение, пересечение, разность, дополнение. Способы задания множеств: с помощью списка, с помощью характеристического свойства, с помощью порождающей процедуры. Система подмножеств множества. Алгебра (под)множеств и ее законы. Изменение мощности множеств при операциях над множествами. Векторы (кортежи), прямое произведение, проекция.
Оглавление
- Введение
- Понятие множества
- Примеры множеств
- Элемент множества
- Подмножество
- Мощность конечного множества
- Пустое множество
- Равенство множеств
- Универсальное множество
- Операции над множествами
- Способы задания множеств
- Система подмножеств множества
- Алгебра (под)множеств и ее законы
- Изменение мощности при операциях над множествами
- Векторы и прямое произведение множеств
-
Множества. Соответствие. Мощность. Примеры. Понятие функции
Понятие множества. Примеры множеств.
Понятие соответствия. Образ и прообраз. Область определения и область значения соответствия.
Всюду определенное соответствие. Сюръективное соответствие.
Однозначное (функциональное) соответствие. Обратное соответствие.
Обратимое соответствие. Взаимно однозначное соответствие (1-1-соответствие, биекция).
Мощность бесконечного множества. Равномощность бесконечного множества своему подмножеству. Счетные множества. Несчетные множества (континуум).
Понятие функции. Область определения и область значения функции. Обратная функция. Функции многих аргументов.
Оглавление
- Введение
- Прямое произведение и проекция (повторение)
- Понятие соответствия
- Образ и прообраз
- Область определения и область значения соответствия
- Всюду определенное соответствие
- Сюръективное соответствие
- Однозначное (функциональное) соответствие
- Обратное соответствие
- Обратимое соответствие
- Взаимно однозначное соответствие
- Мощность бесконечного множества
- Равномощность бесконечного множества своему подмножеству
- Счетные множества
- Несчетные множества (континуум)
- Понятие функции
- Область определения и область значения функции
- Обратная функция
- Функции многих аргументов
-
Функции. Способы задания. Отношения
Тип функции. Суперпозиция функций. Способы задания функции: с помощью формулы, свойством значений, с помощью порождающей процедуры, с помощью таблицы, с помощью программы (конструктивные и неконструктивные функции). Понятие отношения. Бинарные отношения. Свойства отношений: рефлексивность, антирефлексивность,
симметричность, антисимметричность, транзитивность. Транзитивное замыкание отношения. Обратное отношение. Отношение эквивалентности. Класс эквивалентности. Отношение строгого и нестрогого порядка. Отношение линейного и частичного порядка. Лексикографический порядок векторов.
Оглавление
- Введение
- Понятие функции (повторение)
- Тип функции
- Суперпозиция функций
- Способы задания функции
- Понятие отношения
- Бинарные отношения
- Свойства отношений
- Транзитивное замыкание отношения
- Обратное отношение
- Отношение эквивалентности
- Класс эквивалентности
- Отношение порядка
- Лексикографический порядок векторов
-
Комбинаторика. Комбинаторные задачи
Основные объекты комбинаторики. Типы комбинаторных задач. Правило суммы и правило произведения. Формула включения и исключения. Размещения с повторениями. Размещения без повторений. Перестановки. Сочетания без повторений. Бином Ньютона, свойства биномиальных коэффициентов, треугольник Паскаля.
Оглавление
- Введение
- Основные объекты комбинаторики
- Типы комбинаторных задач
- Правила суммы и произведения
- Формула включения и исключения
- Виды линейных выборок
- Размещения с повторениями
- Размещения без повторений
- Сочетания без повторений, перестановки
- Бином Ньютона
- Свойства биномиальных коэффициентов
- Треугольник Паскаля
-
Комбинаторика. Сочетания с повторениями. Задача перечисления. Двумерные выборки
Сочетания с повторениями. Задача перечисления выборок, лексикографический порядок. Двумерные выборки. Таблицы функций. Понятие алгебры. Замкнутые операции. N-арные операции, бинарные операции, арность операции. Тип алгебры, сигнатура.
Свойства бинарных операций: ассоциативность, коммутативность, дистрибутивность слева, дистрибутивность справа. Два вида процедур в алгебре: вычисление формул и преобразование формул.
Оглавление
- Введение
- Основные комбинаторные величины (повторение)
- Сочетания с повторениями
- Задача перечисления выборок, лексикографический порядок
- Двумерные выборки, таблицы функций
- Понятие алгебры
- Замкнутые операции
- N-арные операции, бинарные операции, арность операции
- Тип алгебры, сигнатура
- Свойства бинарных операций
- Два вида процедур в алгебре: вычисление формул и преобразование формул.
-
Изоморфизм, гомоморфизм. Алгебры
Изоморфизм алгебр. Гомоморфизм алгебр. Полугруппа. Единица полугруппы. Моноид. Группа. Обратный элемент. Способ задания (полу)групп: с помощью бинарной таблицы и с помощью образующих. Решетка. Наименьшая верхняя грань, наибольшая нижняя грань. Единственность максимального и единственность минимального элемента. Единица решетки и нуль решетки. Решетка подмножеств любого множества.
-
Математическая логика. Логические функции
Высказывание. Логические связки: конъюнкция, дизъюнкция, отрицание, импликация, разделительное "или", эквивалентность. Таблицы истинности для логических функций. Логические функции от нуля переменных (константы), от одной переменной, от двух переменных. Применение к переключательным схемам. Алгебра логических функций. Вычисление логических функций.
-
Математическая логика. Булева алгебра. Алгебра Жегалкина
Проблема полноты. Функционально полная система функций (в сильном смысле и в слабом смысле). Эквивалентности формул. Алгоритм перехода от таблицы функции к формуле (построение СДНФ). Булева алгебра и ее законы. Изоморфизм булевых алгебр (алгебры множеств и алгебры логических функций). Функциональная полнота некоторых систем функций.
Алгебра Жегалкина. Функциональная полнота алгебры Жегалкина. Ортогональные функции.
Монотонные функции.
Оглавление
- Введение
- Алгебра логических функций, вычисление функций (повторение)
- Проблема полноты
- Функционально полная система функций
- Эквивалентность формул
- Алгоритм перехода от таблицы функции к формуле (построение СДНФ)
- Булева алгебра и ее законы
- Изоморфизм булевых алгебр
- Функциональная полнота некоторых систем функций
- Алгебра Жегалкина
- Функциональная полнота алгебры Жегалкина
- Ортогональные функции
- Монотонные функции
-
Классы логических функций. Понятие предиката
Классы логических функций. Монотонные функции. Линейные функции.
Отношение двойственности функций. Функции, двойственные самим себе (самодвойственные функции). Функции, сохраняющие нуль. Функции, сохраняющие единицу. Понятие предиката. Кванторы.
-
Логика предикатов. Графы, общие определения
Кванторы всеобщности и существования. Связанные переменные. Область действия квантора. Эквивалентные соотношения в логике предикатов. Чистая логика предикатов и прикладные логики предикатов. Понятия графа. Классификация графов: по наличию ориентирования ребер (неориентированный и ориентированный графы), по наличию кратности ребер (простой граф и мультиграф). Отношение смежности между вершинами, матрица смежности.
Отношение инцидентности между вершинами и ребрами. Степень вершины. Изолированные вершины, висячие вершины. Пустой граф, полный граф.
Оглавление
- Введение
- Подходы к описанию логики, предикаты (повторение)
- Кванторы
- Эквивалентные соотношения в логике предикатов
- Чистая логика предикатов и прикладные логики предикатов
- Понятия графа
- Классификация графов
- Отношение смежности между вершинами
- Матрица смежности
- Отношение инцидентности между вершинами и ребрами
- Степень вершины
- Изолированные вершины
- Висячие вершины
- Пустой граф
- Полный граф
-
Теория графов. Основные понятия
Матрица смежности, степень вершины.
Подграф и часть графа. Звезда вершины графа. Полный граф. Клика. Максимальный и минимальный (относительно некторого свойства) подграф. Изоморфизм графов.
Неориентированные графы. Путь, цепь, простая цепь, цикл. Связанные вершины. Связный граф. Компоненты связности. Длина пути. Расстояние между вершинами в связном графе. Аксиомы метрики (расстояния).
Оглавление
- Введение
- Матрица смежности, степень вершины (повторение)
- Подграф и часть графа
- Звезда вершины графа
- Полный граф
- Клика
- Максимальный и минимальный (относительно некоторого свойства) подграф
- Изоморфизм графов
- Неориентированные графы
- Путь
- Цепь
- Простая цепь
- Цикл
- Связанные вершины
- Связный граф
- Компоненты связности
- Длина пути
- Расстояние между вершинами в связном графе
-
Теория графов. Основные понятия (продолжение)
Радиус графа, центры графа. Эйлеров обход. Задача о кенигсбергских мостах.
Алгоритм построения эйлерова цикла. Задача о гамильтоновом обходе (задача коммивояжера).
Ориентированные графы (орграфы). Ориентированный путь, ориентированный цикл. Достижимость. Виды связности: сильная связность, односторонняя связность, слабая связность.
Компонента сильной связности. Конденсация, граф конденсации.
Ациклический граф. Источники и стоки. Топологическая сортировка.
Оглавление
- Введение
- Понятие расстояния, аксиомы метрики (повторение)
- Максимальное удаление вершины
- Радиус графа, центры графа
- Эйлеров обход
- Задача о кенигсбергских мостах
- Алгоритм построения эйлерова обхода
- Задача о гамильтоновом обходе (задача коммивояжера)
- Ориентированные графы (орграфы)
- Ориентированный путь
- Ориентированный цикл
- Достижимость
- Виды связности орграфа
- Компонента сильной связности
- Конденсация, граф конденсации
- Ациклический граф
- Источники и стоки
- Топологическая сортировка
-
Деревья. Оптимизационные задачи на графах. Задача о кратчайшем пути
Неориентированные деревья. Ориентированные деревья.
Применение деревьев: классификация, представление формул, бинарное дерево поиска.
Оптимизационные задачи на графах. Взвешенные (нагруженные) графы. Задача о кратчайшем пути в неориентированном графе без весов. Ранжирование вершин. Задача о кратчайшем пути в взвешенном графе. Алгоритм Дейкстры.
Оглавление
- Введение
- Деревья
- Неориентированные деревья
- Ориентированные деревья
- Применение деревьев
- Оптимизационные задачи на графах
- Взвешенные (нагруженные) графы
- Задача о кратчайшем пути в неориентированном графе без весов
- Алгоритм нахождения кратчайшего пути: ранжирование вершин
- Задача о кратчайшем пути в взвешенном графе
- Алгоритм Дейкстры
-
Оптимизационные задачи на графах. Сетевое планирование. Потоки в сетях
Сетевой график. Задача поиска максимальных путей в графе.
Понятия раннего срока и позднего срока. Критический путь. Виды резерва: полный резерв, свободный резерв, независимый резерв. Потоки в сетях. Понятие потока, величина потока. Закон Кирхгофа. Увеличивающаяся цепь.
-
Оптимизационные задачи на графах. Алгоритм поиска увеличивающей цепи
Алгоритм поиска увеличивающей цепи. Разрезы. Пропускная способность разреза.
-
Матричные методы анализа графов. Графы и бинарные отношения
Матричные методы анализа графов. Степень матрицы смежности графа. Сумма степеней матрицы смежности, достижимость и связность. Транзитивное замыкание. Графы и бинарные отношения. Отношения эквивалентности и отношения порядка в терминах графов. Матричные методы анализа мультиграфов. Двудольные графы. Задача о раскраске графа.
-
Игорь Орещенков
|
По-моему, 4-й тест невозможно пройти без знания метода построения полинома Жегалкина по таблице логической функции. К сожалению, в лекциях этот вопрос не освещён. Вот ссылка на статью "Что нам стоит полином Жегалкина построить…", где этот вопрос освещён кратко и наглядно: https://habrahabr.ru/post/275527/ |