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

ПЕДАГОГИЧЕСКОЕ ОБРАЗОВАНИЕ С. М. Окулов ДИСКРЕТНАЯ МАТЕМАТИКА ТЕОРИЯ И ПРАКТИКА РЕШЕНИЯ ЗАДАЧ ПО ИНФОРМАТИКЕ Учебное пособие 2-е издание (электронное) %¦ Москва БИНОМ. Лаборатория знаний 2 0 12 УДК 519. 85(075) ББК 22. 174я7 0-52 Серия основана в 2007 г. Рецензенты: академик РАО, доктор педагогических наук, профессор А. А. Кузнецов доктор технических наук, профессор В. Н. Комаров Окулов С. М. 0-52 Дискретная математика. Теория и практика решения задач по информатике [Электронный ресурс] : учебное пособие / С. М. Окулов. — 2-е изд. (эл. ). — М. : БИНОМ. Лаборатория знаний, 2012. —422 с. : ил. — (Педагогическое образование). ISBN 978-5-9963-0893-4 В учебном пособии даны ключевые разделы дискретной математики с практической реализацией алгоритмических решений. Книга написана на основе лекционного курса и практических занятий для студентов факультета информатики Вятского государственного гуманитарного университета, а также спецкурса, читаемого автором для школьников, занимающихся информатикой по углубленной программе. Для студентов высших учебных заведений, а также старшеклассников, углубленно изучающих информатику. УДК 519. 85(075) ББК 22. 174я7 По вопросам приобретения обращаться: «БИНОМ. Лаборатория знаний, ISBN 978-5-9963-0893-4 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 Глава 3. Перечисление комбинаторных объектов 52 3. 1. Общая схема генерации комбинаторных объектов ... 52 Интерактивное оглавление v 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.