3. Алгоритмы и их сложность

Содержание

• Конспект лекций по дисциплине “Дискретная математика”
• Санкт Петербург Содержание.
• Раздел I. Множества, функции, отношения. Лекция № 1. Множества и операции над ними.
• 1. Основные понятия теории множеств.
• 2. Операции над множествами и их свойства.
• 3. Векторы и прямые произведения.
• Лекция № 2. Соответствия и функции.
• Соответствия.
• Отображения и функции.
• Лекция № 3. Отношения и их свойства.
• Основные понятия и определения.
• Свойства отношений.
• Лекция № 4. Основные виды отношений.
• Отношения эквивалентности.
• Отношения порядка.
• Лекция № 4. Пересчёт.
• Раздел II. Введение в общую алгебру. Лекция № 6. Элементы общей алгебры.
• 1. Свойства бинарных алгебраических операций.
• 2. Алгебраические структуры.
• Гомоморфизм и изоморфизм.
• Лекция № 7. Различные виды алгебраических структур.
• Полугруппы.
• Группы.
• Поля и кольца.
• Раздел III. Введение в логику. Лекция № 8. Элементы математической логики.
• Булевы функции.
• Лекция № 9. Логические функции.
• Функции алгебры логики.
• Примеры логических функций.
• Суперпозиции и формулы.
• Лекция № 10. Булевы алгебры.
• Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.
• Булева алгебра функций.
• Эквивалентные преобразования.
• Лекция № 11. Булевы алгебры и теория множеств.
• Двойственность.
• Булева алгебра и теория множеств.
• Днф, интервалы и покрытия.
• Лекция № 12. Полнота и замкнутость.
• Функционально полные системы.
• Алгебра Жегалкина и линейные функции.
• Замкнутые классы. Монотонные функции.
• Теоремы о функциональной полноте.
• Лекция № 13. Язык логики предикатов.
• Предикаты.
• Кванторы.
• Истинные формулы и эквивалентные соотношения.
• Доказательства в логике предикатов.
• Лекция № 14. Комбинаторика.
• Правила суммы и произведения.
• Размещения.
• Перестановки.
• Сочетания. Бином Ньютона.
• Раздел IV. Теория графов. Лекция № 15. Графы: основные понятия и операции.
• Графы, их вершины, рёбра и дуги. Изображение графов.
• Матрица инцидентности и список рёбер. Матрица смежности графа.
• Идентификация графов, заданных своими представлениями.
• Лекция № 16. Маршруты, цепи и циклы.
• Основные определения.
• Связные компоненты графов.
• Расстояния. Диаметр, радиус и центр графа. Протяжённости.
• Эйлеровы графы.
• Лекция № 17. Некоторые классы графов и их частей.
• Деревья.
• Ориентированные графы.
• Графы с помеченными вершинами и рёбрами.
• Лекция № 18. Теория алгоритмов Понятие алгоритма
• 1.2.1. Основные требования к алгоритмам
• 1.2.2. Машина Тьюринга
• Универсальная машина Тьюринга
• 1.2.3. Тезис Тьюринга
• 1.3. Граф машина
• 1.3.1. Модель данных
• 1.3.2. Построение моделей алгоритмов в системе graph
• 2. Сложность алгоритмов
• 2.1.Временная и пространственная сложность алгоритма. Классы dtime и dspace
• 2.2. Классы сложности
• 2.2.1. Полиномиальность и эффективность
• 2.2.2. Алгоритмическая сводимость задач
• 3. Алгоритмы и их сложность
• 3.1. Представление абстрактных объектов (последовательностей)
• 3.1.1. Смежное представление последовательностей
• 3.1.2. Связанное представление последовательностей
• Список вопросов для подготовки к экзамену по дисциплине "дискретная математика"