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

📚 Краткое содержание

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

Освойте логику и структуры, лежащие в основе информатики.

Автор: Ричард Джонсонбау

Благодарности: Рецензентам, включая Венкату Динахави, Мэтью Элси, Кристофера Гирауд-Каррьера, Евгения Ковчегова, Филикса Майша, Тайлера МакМиллена, Кристофера Сторма, Дональда Вестала и Гуанхуа Чжао. Поддержка со стороны сотрудников Pearson: Дердре Линч, Джефф Вейденар, Лорен Морс и другие.

🎯 Цели обучения

1. Выполнять операции над множествами, включая разность и дополнение, и проверять тождества множеств с помощью диаграмм Венна и Теоремы 1.1.22.
2. Строить и оценивать таблицы истинности для высказываний, включающих отрицание, дизъюнкцию и условные утверждения.
3. Применять правила вывода и дедуктивное рассуждение для определения корректности логических аргументов.
4. Определять и применять компоненты математической системы, включая аксиомы, определения и теоремы.
5. Строить прямые доказательства, доказательства от противного и доказательства по случаям для алгебраических и теоретико-множественных утверждений.
6. Использовать принцип математической индукции и сильную индукцию для доказательства тождеств, свойств делимости и корректности алгоритмов.
7. Определять и классифицировать функции (инъективные, сюръективные, биективные) и выполнять операции, такие как композиция и обращение.
8. Применять обозначения последовательностей, конкатенацию строк и рекуррентные правила для моделирования дискретных наборов данных.
9. Анализировать бинарные отношения на свойства, такие как рефлексивность, симметричность и транзитивность, используя как направленные графы, так и матричные представления.
10. Определять алгоритм и проверять его семь основных свойств (входные данные, выходные данные, точность, детерминизм, конечность, корректность и общность).

🔹 Урок 1: Основы логики и теории множеств

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

Результаты обучения:

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

🔹 Урок 2: Методы математических доказательств

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

Результаты обучения:

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

🔹 Урок 3: Функции, последовательности и отношения

Обзор: Этот урок охватывает фундаментальные математические структуры, используемые для моделирования данных и процессов в информатике. Он охватывает определение функций и их различных типов (инъективные, сюръективные, биективные), а также изучение последовательностей, строк и формальных свойств бинарных отношений. Студенты исследуют практические применения, такие как хеш-функции, контрольные цифры ISBN, планирование задач с частичными порядками, а также представление отношений через матрицы и базы данных.

Результаты обучения:

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

🔹 Урок 4: Анализ алгоритмов и сложность

Обзор: Этот урок охватывает фундаментальное определение и свойства алгоритмов, их реализацию в поиске и сортировке (особенно текстовый поиск и сортировка вставками), а также строгие математические рамки для анализа их эффективности. Студенты исследуют асимптотические обозначения, скорости роста функций и механику рекурсивного решения задач, включая стратегии «разделяй и властвуй», такие как раскладка плиток и последовательности, основанные на числах Фибоначчи.

Результаты обучения:

• Определять алгоритм и проверять его семь основных свойств (входные данные, выходные данные, точность, детерминизм, конечность, корректность и общность).
• Применять обозначения О(большое), Ω и Θ для выражения временной и пространственной сложности алгоритмов.
• Анализировать лучшие, худшие и средние случаи с использованием техник, таких как повторное деление пополам и упорядочивание по степеням полиномов.

🔹 Урок 5: Введение в теорию чисел и криптографию

Обзор: Этот урок исследует основополагающие принципы теории чисел, начиная с базовых свойств делителей и простых чисел до сложных алгоритмов, лежащих в основе современной безопасной связи. Студенты освоят математические механизмы наибольшего общего делителя (НОД), преобразования оснований и модульное возведение в степень для понимания и реализации криптосистемы с открытым ключом RSA.

Результаты обучения:

• Определять и применять понятия делимости, простоты и Фундаментальную теорему арифметики.
• Выполнять эффективные преобразования между десятичной, двоичной и шестнадцатеричной системами счисления.
• Выполнять алгоритм Евклида и его расширенную форму для нахождения НОД и линейных комбинаций (sa + tb).

🔹 Урок 6: Методы подсчета и дискретная вероятность

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

Результаты обучения:

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

🔹 Урок 7: Рекуррентные соотношения

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

Результаты обучения:

• Решать рекуррентные соотношения с помощью метода итерации и характеристических уравнений (для различных и равных корней).
• Моделировать и решать классические математические задачи, включая башню Ханой, последовательность Фибоначчи (золотое сечение) и беспорядки.
• Анализировать худший случай времени выполнения рекурсивных алгоритмов с помощью рекуррентных соотношений.

🔹 Урок 8: Теория графов и алгоритмы кратчайших путей

Обзор: Этот урок исследует основополагающие принципы теории графов, начиная с базовых определений простых и взвешенных графов до сложных алгоритмических решений для кратчайших путей и выявления циклов. Студенты изучают структурные свойства, такие как планарность, связность и изоморфизм, применяя эти концепции к классическим задачам, таким как задача о мостах Кёнигсберга, задача коммивояжера (TSP) и головоломка «Немедленное безумие».

Результаты обучения:

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

🔹 Урок 9: Деревья и алгоритмы поиска

Обзор: Этот урок охватывает фундаментальные свойства, характеристики и приложения деревьев в информатике и математике. Студенты изучают корневые и бинарные деревья, алгоритмы остовных деревьев (BFS/DFS), методы оптимизации, такие как алгоритм Прима для минимальных остовных деревьев, а также системы принятия решений, включая обратный откат, сортировку турнирного типа и игровые деревья с процедурой минимакса.

Результаты обучения:

• Определять и идентифицировать корневые деревья, их уровни, высоту и иерархическую структуру в реальных системах.
• Характеризовать деревья по связности, отсутствию циклов и соотношению рёбер к вершинам.
• Реализовывать и прослеживать алгоритмы для остовных деревьев (BFS, DFS), минимальных остовных деревьев (Прима) и построения бинарного дерева поиска.

🔹 Урок 10: Модели сетей и оптимизация потоков

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

Результаты обучения:

• Определять и проверять свойства транспортной сети и допустимых назначений потоков.
• Выполнять алгоритм максимального потока (Алгоритм 10.2.4) для нахождения оптимальной пропускной способности.
• Применять теорему о максимальном потоке — минимальном разрезе для доказательства оптимальности потока с помощью разбиения сети.

🔹 Урок 11: Булева алгебра и логические схемы

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

Результаты обучения:

• Проектировать и анализировать комбинаторные схемы с использованием стандартных логических элементов (И, ИЛИ, НЕ) и коммутационных конфигураций.
• Применять законы булевой алгебры и теорему двойственности для доказательства эквивалентности схем и упрощения выражений.
• Синтезировать булевы функции из таблиц истинности в дизъюнктивную нормальную форму (DNF) и конъюнктивную нормальную форму (CNF).

🔹 Урок 12: Автоматы, грамматики и формальные языки

Обзор: Этот урок исследует математические основы вычислений, начиная с последовательных схем и конечных автоматов, моделирующих внутреннюю память с помощью задержек единичного времени. Он охватывает формальное определение и классификацию фразово-структурных грамматик (Типы 1, 2 и 3), применение формы Бэкуса-Наура (BNF) и специализированное использование грамматик Линдемайера для генерации фракталов. В конце урок устанавливает критически важную связь между детерминированными и недетерминированными конечными автоматами и формальными языками, которые они принимают.

Результаты обучения:

• Анализировать и проектировать конечные автоматы (КМ) и автоматы (КСА/НКСА) с использованием диаграмм переходов и функций состояний.
• Классифицировать грамматики в иерархии Хомского и выводить строки с помощью правил порождения и нотации BNF.
• Моделировать самоподобные структуры, такие как снежинка Коха, с помощью грамматик Линдемайера и правил одновременного замещения.