Введение
Дискретная математика занимается изучением конечных свойств объектов, которые возникают как в различных разделах математики, так и в ее технических приложениях. Под конечными свойствами понимаются их ограниченность или перечислимость. Важными отличиями разделов дискретной математики от классических разделов непрерывной математики являются отсутствие понятия непрерывности и предела последовательности.
То, что в разделах дискретной математики рассматриваются конечные свойства объектов, совсем не означает, что при исследовании невстречаются бесконечные совокупности объектов или их конфигураций, однако, как правило, эти бесконечности являются счетными.
Разделы дискретной математики всегда существовали в математике, но стали выделяться в самостоятельную дисциплину в связи с развитием средств связи и появлением компьютеров.
К разделам дискретной математики обычно относят:
математическую логику,
теорию алгоритмов,
булеву алгебру,
теорию конечных автоматов,
теорию дискретных групп,
теорию графов,
комбинаторику.
теорию чисел.
Характерными примерами приложений различных разделов дискретной математики являются:
методы распознавания образов, основанные на теории принятия ре шений,
криптографические протоколы.
теория кодирования информации,
теория сложности алгоритмов и т.д.
В данном методическом пособии рассматриваются только несколько разделов дискретной математики, которые, на мой взгляд, наиболее востребованы для специалистов в области вычислительной техники и систем связи.
Разумеется, существует огромное количество литературы по дискретной математике и при желании всегда можно найти гораздо более обширную информацию по любой из тем, представленных в данном методическом пособии. Однако практическая ценность данной работы состоит в том, что информация, взятая из различных источников, удобно структурирована и излагается в размере, необходимом для получения студентами базовых знаний по предмету.
1. Введение в комбинаторику
Комбинаторика - один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в ВТ, кибернетике, робототехнике. Большинство задач комбинаторики можно сформулировать как задачи теории конечных множеств, поэтому эти две темы - элементы теории множеств и комбинаторика - рассматриваются взаимосвязано.
Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. Например, сколькими способами могли быть распределены золотая, серебряная и бронзовая медали на Олимпийских играх по баскетболу; или сколькими различными способами можно разместить здания на площади? Задачи такого типа называются комбинаторными.
Содержание
Введение 3
1. Введение в комбинаторику 5
1.1. Основные комбинаторные конфигурации 6
1.2. Правила суммы и произведений 10
1.3. Метод включения-исключения 11
1.4. Производящие функции 13
1.5. Контрольные вопросы 16
1.6. Задачи 17
2. Функции округления и бином Ньютона 18
2.1. Целочисленные функции округления 18
2.2.Бином Ньютона 20
2.3. Биномиальные коэффициенты и их свойства 22
2.4. Полиномиальная формула 24
2.5. Контрольные вопросы 25
2.6. Задачи 26
3. Рекуррентные соотношения и асимптоматика 27
3.1. Решение рекуррентных соотношений 27
3.2. Введение в асимптотические методы 33
3.3. Асимптотические методы решения рекуррентных соотношений 35
3.4. Числа Бернулли и формула суммирования Эйлера 42
3.5. Контрольные вопросы 44
3.6. Задачи 45
4. Введение в теорию графов 46
4.1. Основные понятия 46
4.2. Двудольные графы 49
4.3. Изоморфизм графов 50
4.4. Связные графы 51
4.5. Эйлеровы графы 53
4.6.Гамильтоновы графы 56
4.7. Деревья 59
4.8. Планарные графы 64
4.9. Теорема Эйлера 66
4.10. Бесконечные графы и теорема Кенига 67
4.11. Рёберная и вершинная раскраски 69
4.12. Гипотеза о четырёх красках 71
4.13. Контрольные вопросы 73
4.14. Задачи 74
Заключение 76
Список использованной литературы 77
Список использованной литературы
1. С.П.Гаврилов. А.А Сапоженко. Сборник задач по дискретной математике. М.: Наука, 1978.
2. Н. Я. Виленкин, Комбинаторика, Москва, Наука, 1969.
3. Н. Б. Алфутова, А. В. Устинов, Алгебра и теория чисел (сборник задач), Москва, МЦНМО, 2002.
4. А. М. Райгородский, А. В. Савватеев, И. Д. Шкредов, Комбинаторика (методическое пособие для факультета биоинженерии и биоинформатики МГУ), Москва, МАКС-ПРЕСС, 2005.
5. М. Холл, Комбинаторика, Москва, Мир, 1970.
6. Р. Стенли, Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции, Москва, Мир, 2005.
7. Г. М. Фихтенгольц, Курс дифференциального и интегрального исчисления, Москва Ижевск, Физматлит, 2003.
8. А. А. Карацуба, Основы аналитической теории чисел, Москва, Эдиториал УРСС, 2004.
9. Г. Эндрюс, Теория разбиений, Москва, Наука, 1982.
10. Ф. Харари, Теория графов, Москва, Мир, 1973.
11. О. Оре Теория графов. М.: Наука, 1980.
12. Ф. Харари, Э. Палмер, Перечисление графов, осква, Мир, 1977.