Читать онлайн «Дискретная математика. Теория и практика решения задач по информатике. Учебное пособие»

ПЕДАГОГИЧЕСКОЕ ОБРАЗОВАНИЕ С. М. Окулов ДИСКРЕТНАЯ МАТЕМАТИКА ТЕОРИЯ И ПРАКТИКА РЕШЕНИЯ ЗАДАЧ ПО ИНФОРМАТИКЕ х. Б\гШ ПЕДАГОГИЧЕСКОЕ ОБРАЗОВАНИЕ С. М. Окулов ДИСКРЕТНАЯ МАТЕМАТИКА ТЕОРИЯ И ПРАКТИКА РЕШЕНИЯ ЗАДАЧ ПО ИНФОРМАТИКЕ Учебное пособие %. Москва БИНОМ. Лаборатория знаний 2011 УДК 519. 85(075) ЬБК 22. 174я7 0-52 Рецензенты: академик РАО, доктор педагогических наук, профессор А. А. Кузнецов доктор технических наук, профессор В. Н. Комаров Окулов С. М. 0-52 Дискретная математика. Теория и практика решения задач по информатике : учебное пособие / С. М. Окулов. — М. БИНОМ. Лаборатория знаний, 2011. —422 с. ил. — (Педагогическое образование). ISBN 978-5-94774-498-9 В учебном пособии даны ключевые разделы дискретной математики с практической реализацией алгоритмических решений. Книга написана на основе лекционного курса и практических занятий для студентов факультета информатики Вятского государственного гуманитарного университета, а также спецкурса, читаемого автором для школьников, занимающихся информатикой по углубленной программе. Для студентов высших учебных заведений, а также старшеклассников, углубленно изучающих информатику. УДК 519. 85(075) ББК 22. 174я7 По вопросам приобретения обращаться: БИНОМ. М. , 2008 ISBN 978-5-94774-498-9 © БИНОМ. Лаборатория знаний, 2008 ОГЛАВЛЕНИЕ Предисловие 7 Гпава 1. Основные методы дискретной математики (счет и перебор) 10 1. 1. Счет и перебор 10 1. 2. Асимптотические обозначения и основная теорема . . 17 1. 3. Эффект «комбинаторного взрыва» 20 Упражнения и задачи 22 Комментарии 24 Гпава 2. Основные комбинаторные принципы и понятия в примерах 25 2. 1. Принципы сложения и умножения 25 2. 2. Подмножества 25 2. 3. Принцип включения и исключения 26 2. 4. Выборки 28 2. 5. Размещения с повторениями 28 2. 6. Размещения без повторений 29 2. 7. Сочетания без повторений 30 2. 8. Бином Ньютона и полиномиальная формула (комбинаторный смысл) 32 2. 9. Сочетания с повторениями 33 2. 10. Перестановки без повторений 33 2. 11. Перестановки с повторениями 38 2. 12. Задача о размещениях 39 2. 13. Разбиения 42 2. 14. Разбиения на циклы 43 2. 15. Разбиение числа на слагаемые 45 Упражнения и задачи 46 Комментарии 51 4 Глава 3. Перечисление комбинаторных объектов 52 3. 1. Общая схема генерации комбинаторных объектов 52 3. 2. Генерация перестановок без повторений 53 3. 3. Генерация сочетаний без повторений 54 3. 4. Генерация размещений без повторений 55 3. 5. Генерация перестановок с повторениями 57 3. 6. Генерация сочетаний с повторениями 57 3. 7. Генерация размещений с повторениями 57 3. 8. Генерация подмножеств 58 3. 9. Генерация разбиений 60 3. 10. Генерация разбиений на циклы 66 3. 11. Генерация разбиений числа на слагаемые ... ... 73 Упражнения и задачи 74 Комментарии 75 Глава 4. Рекуррентные и нерекуррентные формулы 76 4. 1. Простые примеры 76 4. 2. Числа Фибоначчи 77 4. 3. Числа Каталана 82 4. 4. Схема нахождения общего решения линейных рекуррентных уравнений 86 4. 5.