Главная » 2013»Март»26 » Дискретная математика. Теория и практика решения задач по информатике
19:23
Дискретная математика. Теория и практика решения задач по информатике
В учебном пособии даны ключевые разделы дискретной математики c практической реализацией алгоритмических решений.
Книга написана на основе лекционного курса и практических занятий для студентов факультета информатики Вятского государственного гуманитарного университета, a также спецкурса, читаемого автором для школьников, занимающихся информатикой по углубленной программе. Для студентов высших учебных заведений, a также старшеклассников, углубленно изучающих информатику.
Содержание:
Предисловие Глава 1. Основные методы дискретной математики (счет и перебор) 1.1. Счет и перебор 1.2. Асимптотические обозначения и основная теорема 1.3. Эффект «комбинаторного взрыва» Глава 2. Основные комбинаторные принципы и понятия в примерах 2.1. Принципы сложения и умножения 2.2. Подмножества 2.3. Принцип включения и исключения 2.4. Выборки 2.5. Размещения c повторениями 2.6. Размещения без повторений 2.7. Сочетания без повторений 2.8. Бином Ньютона и полиномиальная формула (комбинаторный смысл) 2.9. Сочетания c повторениями 2.10. Перестановки без повторений 2.11. Перестановки c повторениями 2.12. Задача о размещениях 2.13. Разбиения 2.14. Разбиения на циклы 2.15. Разбиение числа на слагаемые Глава 3. Перечисление комбинаторных объектов 3.1. Общая схема генерации комбинаторных объектов 3.2. Генерация перестановок без повторений 3.3. Генерация сочетаний без повторений 3.4. Генерация размещений без повторений 3.5. Генерация перестановок c повторениями 3.6. Генерация сочетаний c повторениями 3.7. Генерация размещений c повторениями 3.8. Генерация подмножеств 3.9. Генерация разбиений 3.10. Генерация разбиений на циклы 3.11. Генерация разбиений числа на слагаемые Глава 4. Рекуррентные и нерекуррентные формулы 4.1. Простые примеры 4.2. Числа Фибоначчи 4.3. Числа Каталана 4.4. Схема нахождения общего решения линейных рекуррентных уравнений 4.5. Производящие функции 4.6. Ладейные полиномы 4.7. Аддитивность задач, или динамическое программирование Глава 5. Понятие графа, основные методы просмотра вершин графа 5.1. Терминология 5.2. Способы представления графа 5.3. Поиск в глубину 5.4. Поиск в ширину 5.5. Основные понятия Глава 6. Деревья 6.1. Определение дерева 6.2. Перечисление остовных деревьев связного помеченного графа 6.3. Матричная формула Кирхгофа 6.4. Алгоритм представления дерева в виде последовательности чисел 6.5. Остовные деревья минимального веса 6.6. Задача Штейнера Глава 7. Связность 7.1. Вершинная и реберная связность 7.2. Метод нахождения блоков графа 7.3. Теорема Менгера 7.4. Связность в орграфе Глава 8. Циклы 8.1. Эйлеровы графы 8.2. Гамильтоновы графы 8.3. Фундаментальное множество циклов 8.4. Матроиды Глава 9. Покрытия и независимость 9.1. Основные понятия 9.2. Метод генерации всех максимальных независимых множеств вершин графа 9.3. Клики 9.4. Доминирующие множества 9.5. Паросочетания 9.6. Матроиды трансверсалей 9.7. Диаграмма взаимосвязей между задачами Глава 10. Планарные графы 10.1. Основные понятия 10.2. Формула Эйлера 10.3. Алгоритм укладки графа на плоскости Глава 11. Раскраска вершин графа 11.1. Хроматическое число 11.2. Метод правильной раскраски 11.3. Методы поиска минимальной раскраски Глава 12. Кратчайшие пути в графе 12.1. Постановка задачи. Вывод пути 12.2. Алгоритмы поиска кратчайших путей Глава 13. Потоки в сетях 13.1. Основные понятия и постановка задачи 13.2. Алгоритм К. Эдмондса-Р. Карпа 13.3. Введение в метод блокирующих потоков или алгоритм Е. А. Диница 13.4. Модификация алгоритма Е. А. Диница Ответы и решения Задачи для самостоятельного решения Приложение 1. Математические факты и доказательства отдельных теорем Приложение 2. Описание основных элементов языков программирования Паскаль, визуального Бейсика и C++ Литература Предметный указатель
Год выхода: 2012 Автор: Окулов С. М. Издательство: БИНОМ. Лаборатория знаний Серия или Выпуск: Педагогическое образование Страниц: 422 Формат: DJVU ISBN: 978-5-9963-0893-4 Качество: Отличное Размер файла: 3,87 Mb
Скачать: Дискретная математика. Теория и практика решения задач по информатике Скачать бесплатно
