1. Иванов Б.н. Дискретная Математика. Алгоритмы И Программы
2. Иванов Дискретная Математика Скачать
3. Иванов Дискретная Математика

Дискретная математика. Алгоритмы и программы: Учеб.

Дискретная математика область математики, занимающаяся изучением дискретных структур. Читать книгу Иванов Б.Н. Дискретная математика. Алгоритмы и программы онлайн - бесплатно и без регистрации.

– серия “Технический университет” Теоретические основы курса сопровождаются практически значимыми алгоритмами, реализованными в конкретных компьютерных программах. Книгу можно рассматривать в качестве хорошего справочника методов и алгоритмов дискретной математики, широко применяемых в практическом программировании. Пособие рассчитано в первую очередь на математиков-прикладников, а также программистов, занятых разработкой прикладного программного обеспечения. Содержание Предисловие.6 Глава 1. Комбинаторные схемы.8 1.1.

Правило суммы8 1.2. Правило прямого произведения.9 1.3. Размещения с повторениями.9 1.4. Размещения без повторений.10 1.5. Перестановки11 1.6. Сочетания.11 1.7. Сочетания с повторениями.12 1.8.

Перестановки с повторениями, мультимножества14 1.9. Упорядоченные разбиения множества15 1.10. Неупорядоченные разбиения множества.16 1.11. Полиномиальная формула.18 1.12. Бином Ньютона.19 1.13. Инверсии.20 1.14. Обратные перестановки.21 Глава 2.

Представление абстрактных объектов24 2.1. Представление последовательностей.24 2.1.1. Смежное представление.24 2.1.2. Характеристические векторы.25 2.1.3. Связанное размещение.26 2.2.

Представление деревьев.31 2.2.1. Представление деревьев на связанной памяти32 2.2.2. Представление деревьев на смежной памяти33 2.3. Представление множеств37 Глава 3. Методы подсчета и оценивания39 3.1.

Производящие функции.39 3.1.1. Линейные операции.41 3.1.2. Сдвиг начала вправо.41 3.1.3. Сдвиг начала влево.42 3.1.4. Частичные суммы.42 3.1.5. Дополнительные частичные суммы.42 3.1.6. Изменение масштаба43 3.1.7.

Свертка.44 3.2. Линейные рекуррентные соотношения.49 3.3. Неоднородные линейные рекуррентные соотношения. Обобщенное правило произведения.53 3.5. Принцип включения и исключения.56 3.6.

Ладейные многочлены и многочлены попаданий59 3.6.1. Ладейные многочлены60 3.6.2. Многочлены попаданий.63 Глава 4. Генерация комбинаторных объектов66 4.1. Поиск с возвращением.66 4.2. Перестановки различных элементов.68 4.3.

Эффективное порождение перестановок.71 4.4. Порождение подмножеств множества76 4.5. Генерация размещений с повторениями.79 4.6. Порождение сочетаний.80 4.7. Порождение композиций и разбиений83 4.8. Генерация случайных перестановок.89 Глава 5. Сортировка и поиск.91 5.1.

Сортировка вставками.92 5.2. Пузырьковая сортировка.93 5.3. Сортировка перечислением.94 5.4. Сортировка всплытием Флойда95 5.5. Последовательный поиск102 5.6. Логарифмический поиск104 5.7. Сортировка с вычисляемыми адресами.106 Глава 6.

Введение в теорию графов. Алгоритмы на графах110.

Основные понятия и определения.110 6.2. Представления графов.114 6.2.1.

Матрица смежности графа114 6.2.2. Матрица инцидентности графа.115 6.2.3. Матрица весов графа116 6.2.4.

Иванов Б.н. Дискретная Математика. Алгоритмы И Программы

Список ребер графа116 6.2.5. Структура смежности графа.117 6.3. Метод поиска в глубину117 6.4.

Отношение эквивалентности.124 6.5. Связные компоненты.125 6.6. Выделение компонент связности.126 6.7. Эйлеровы графы.130 6.8. Остовные деревья.137 6.8.1. Жадный алгоритм построения минимального остовного дерева.139 6.8.2. Алгоритм ближайшего соседа построения остовного дерева.145 6.9.

Кратчайшие пути на графе.151 6.10. Потоки в сетях.156 6.11. Клики, независимые множества.160 6.12. Циклы, фундаментальные множества циклов.172 6.13. Листы и блоки.177 6.13.1. Листы.178 6.13.2.

Блоки.180 6.13.3. Поиск блоков в глубину.182 6.14.

Двудольные графы185 6.14.1. Условия существования двудольных графов185 6.14.2. Паросочетания.186 6.14.3. Алгоритм определения максимального паросочетания.186 6.14.4. Системы различных представителей189 6.14.5. Связь системы различных представителей и двудольных графов.189 6.14.6. Задача о назначениях.190 6.15.

Хроматические графы.194 6.16. Диаметр, радиус и центры графа.196 Глава 7.

Введение в теорию групп. Приложения.197 7.1. Определение группы.197 7.2. Гомоморфизм групп.198 7.3.

Смежные классы.199 7.4. Строение коммутативных (абелевых) групп203 7.5. Строение некоммутативных групп.207 7.6. Симметрическая группа подстановок208 7.7. Действие групп на множестве.212 7.8.

Цикловой индекс группы217 7.9. Теория перечисления Пойа.218 7.10. Цикловая структура групп подстановок.223 7.10.1. Цикловой индекс группы, действующей на себе.

Цикловой индекс циклической группы.224 7.10.3. Цикловой индекс симметрической группы225 Глава 8. Элементы теории чисел227 8.1. Наибольший общий делитель.227 8.2. Наименьшее общее кратное.228 8.3.

Простые числа.228 8.4. Сравнения, свойства сравнений.232 8.5. Полная система вычетов233 8.6.

Приведенная система вычетов234 8.7. Функция Эйлера.234 8.8. Функция Мёбиуса.

Формула обращения Мёбиуса.238 Задачи и упражнения.240 Ответы281 Литература.285 Предметный указатель.286 Your browser does not seem to support iframes. Click here to read this PDF.

Если задано универсальное множество, то может быть введена операция дополнения:. Указанные операции обладают рядом интересных свойств (см.

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

Иванов Дискретная Математика Скачать

метод эквивалентных преобразований. Операции над множествами могут быть проиллюстрированы на диаграммах Венна. Например, пересечение множеств может быть представлено как тёмная область на рисунке. 5: Пример соответствия, не функционального по 2-ой компоненте Отображение из в (функция) - это соответствие из в, которое всюду определено и функционально по второй компоненте. Соответствие - это множество упорядоченных пар, поэтому все операции над множествами к ним применимы. Для соответствий вводятся две новые операции: композиция и обратное соответствие. Композиция соответствий и - новое соответствие, равное.

Для конечных соответствий удобно пользоваться графовым представлений соответствий - тогда для получения композиции достаточно пройти по ребрам графа. Пример композиции соответствий представлен на рисунке и иллюстрирует композицию соответствий оценок, полученных студентами, ( ) и соответствия оценки получаемой стипендии. Результат композиции в этом случае - соответствие студентов и выплаты стипендии. Задания для самоподготовки.

Иванов Дискретная Математика

На множестве задано отношение. Найти квадрат этого отношения.

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

Отношение называют иррефлексивным,. Отношение иррефлексивно тогда и только тогда, когда диагональ полностью не принадлежит ему.

Если отношение не рефлексивно и не иррефлексивно, его называют нерефлексивным. Иррефлексивным отношением является. Отношение называют симметричным,. При этом график отношения симметричен относительно диагонали, при этом отношение совпадает с обратным к нему.

Примером такого отношения является равенство треугольников. Отношение называют антисимметричным,. Если отношение не симметрично и не антисимметрично, его называют несимметричным. На графике отношения все симметричные относительно диагонали точки будут лежать на самой диагонали.

Пример такого отношения -. Отношение называют транзитивным,. При этом квадрат отношения включается в него самого. На рисунке показаны примеры отношений с перечисленными свойствами.