Дискретная математика

Дискретная математика (видеозапись лекций)

Год выпуска: 2009
Производитель: Росиия
производителя: //intuit
Автор: Профессор, доктор технических наук Кузнецов Олег П
Продолжительность: 19:7:21
Тип раздаваемого материала: Видеоурок
Язык: Русский
Описание: Дискретная математика - одна из важнейших составляющих современной математики. С одной стороны, она включает фундаментальные основы математики - теорию множеств, математическую логику, теорию алгоритмов; с другой стороны, является основным математическим аппаратом информатики и вычислительной техники и потому служит базой для многочисленных приложений в экономике, технике, социальной сфере.
В отличие от традиционной математики (математического анализа, линейной алгебры и др.), методы и конструкции которой имеют в основном числовую интерпретацию, дискретная математика имеет дело с объектами нечисловой природы: множествами, логическими высказываниями, алгоритмами, графами. Благодаря этому обстоятельству дискретная математика впервые позволила распространить математические методы на сферы и задачи, которые ранее были далеки от математики. Примером могут служить методы моделирования различных социальных и экономических процессов. Знание теории множеств, алгебры, математической логики и теории графов совершенно необходимо для четкой формулировки понятий и постановок различных прикладных задач, их формализации и компьютеризации, а также для усвоения и разработки современных информационных технологий. Понятия и методы теории алгоритмов и алгебры логики лежат в основе современной теории и практики программирования. Курс предусматривает изучение: языка дискретной математики, таких ее основных понятий, как множества, функции, отношения; основ комбинаторики, элементов общей алгебры; введения в математическую логику; теории графов.

Содержание
intuit/department/ds/discretemath/1/

1. Лекция: Множества. Операции над множествами
Понятие множества. Примеры множеств. Элемент множества. Подмножество. Мощность конечного множества. Пустое множество. Равенство множеств. Универсальное множество. Операции над множествами: объединение, пересечение, разность, дополнение. Способы задания множеств: с помощью списка, с помощью характеристического свойства, с помощью порождающей процедуры. Система подмножеств множества. Алгебра (под)множеств и ее законы. Изменение мощности множеств при операциях над множествами. Векторы (кортежи), прямое произведение, проекция.

2. Лекция: Множества. Соответствие. Мощность. Примеры. Понятие функции
Понятие множества. Примеры множеств. Понятие соответствия. Образ и прообраз. Область определения и область значения соответствия. Всюду определенное соответствие. Сюръективное соответствие. Однозначное (функциональное) соответствие. Обратное соответствие. Обратимое соответствие. Взаимно однозначное соответствие (1-1-соответствие, биекция). Мощность бесконечного множества. Равномощность бесконечного множества своему подмножеству. Счетные множества. Несчетные множества (континуум). Понятие функции. Область определения и область значения функции. Обратная функция. Функции многих аргументов.

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

4. Лекция: Комбинаторика. Комбинаторные задачи
Основные объекты комбинаторики. Типы комбинаторных задач. Правило суммы и правило произведения. Формула включения и исключения. Размещения с повторениями. Размещения без повторений. Перестановки. Сочетания без повторений. Бином Ньютона, свойства биномиальных коэффициентов, треугольник Паскаля.

5. Лекция: Комбинаторика. Сочетания с повторениями. Задача перечисления. Двумерные выборки
Сочетания с повторениями. Задача перечисления выборок, лексикографический порядок. Двумерные выборки. Таблицы функций. Понятие алгебры. Замкнутые операции. N-арные операции, бинарные операции, арность операции. Тип алгебры, сигнатура. Свойства бинарных операций: ассоциативность, коммутативность, дистрибутивность слева, дистрибутивность справа. Два вида процедур в алгебре: вычисление формул и преобразование формул.

6. Лекция: Изоформизм, гомоформизм. Алгебры
Изоморфизм алгебр. Гомоморфизм алгебр. Полугруппа. Единица полугруппы. Моноид. Группа. Обратный элемент. Способ задания (полу)групп: с помощью бинарной таблицы и с помощью образующих. Решетка. Наименьшая верхняя грань, наибольшая нижняя грань. Единственность максимального и единственность минимального элемента. Единица решетки и нуль решетки. Решетка подмножеств любого множества.

7. Лекция: Математическая логика. Логические функции
Высказывание. Логические связки: конъюнкция, дизъюнкция, отрицание, импликация, разделительное 'или', эквивалентность. Таблицы истинности для логических функций. Логические функции от нуля переменных (константы), от одной переменной, от двух переменных. Применение к переключательным схемам. Алгебра логических функций. Вычисление логических функций.

8. Лекция: Математическая логика. Булева алгебра. Алгебра Жегалкина
Проблема полноты. Функционально полная система функций (в сильном смысле и в слабом смысле). Эквивалентности формул. Алгоритм перехода от таблицы функции к формуле (построение СДНФ). Булева алгебра и ее законы. Изоморфизм булевых алгебр (алгебры множеств и алгебры логических функций). Функциональная полнота некоторых систем функций. Алгебра Жегалкина. Функциональная полнота алгебры Жегалкина. Ортогональные функции. Монотонные функции.

9. Лекция: Классы логических функций. Понятие предиката
Классы логических функций. Монотонные функции. Линейные функции. Отношение двойственности функций. Функции, двойственные самим себе (самодвойственные функции). Функции, сохраняющие нуль. Функции, сохраняющие единицу. Понятие предиката. Кванторы.

10. Лекция: Логика предикатов. Графы, общие определения
Кванторы всеобщности и существования. Связанные переменные. Область действия квантора. Эквивалентные соотношения в логике предикатов. Чистая логика предикатов и прикладные логики предикатов. Понятия графа. Классификация графов: по наличию ориентирования ребер (неориентированный и ориентированный графы), по наличию кратности ребер (простой граф и мультиграф). Отношение смежности между вершинами, матрица смежности. Отношение инцидентности между вершинами и ребрами. Степень вершины. Изолированные вершины, висячие вершины. Пустой граф, полный граф.

11. Лекция: Теория графов. Основные понятия
Матрица смежности, степень вершины. Подграф и часть графа. Звезда вершины графа. Полный граф. Клика. Максимальный и минимальный (относительно некторого свойства) подграф. Изоморфизм графов. Неориентированные графы. Путь, цепь, простая цепь, цикл. Связанные вершины. Связный граф. Компоненты связности. Длина пути. Расстояние между вершинами в связном графе. Аксиомы метрики (расстояния).

12. Лекция: Теория графов. Основные понятия (продолжение)
Радиус графа, центры графа. Эйлеров обход. Задача о кенигсбергских мостах. Алгоритм построения эйлерова цикла. Задача о гамильтоновом обходе (задача коммивояжера). Ориентированные графы (орграфы). Ориентированный путь, ориентированный цикл. Достижимость. Виды связности: сильная связность, односторонняя связность, слабая связность. Компонента сильной связности. Конденсация, граф конденсации. Ациклический граф. Источники и стоки. Топологическая сортировка.

13. Лекция: Деревья. Оптимизационные задачи на графах. Задача о кратчайшем пути
Неориентированные деревья. Ориентированные деревья. Применение деревьев: классификация, представление формул, бинарное дерево поиска. Оптимизационные задачи на графах. Взвешенные (нагруженные) графы. Задача о кратчайшем пути в неориентированном графе без весов. Ранжирование вершин. Задача о кратчайшем пути в взвешенном графе.