Содержание
Содержание
Введение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. Введение в комбинаторику
Комбинаторика — один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в ВТ, кибернетике, робототехнике. Большинство задач комбинаторики можно сформулировать как задачи теории конечных множеств, поэтому эти две темы — элементы теории множеств и комбинаторика — рассматриваются взаимосвязано.
Человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. Например, сколькими способами могли быть распределены золотая, серебряная и бронзовая медали на Олимпийских играх по баскетболу; или сколькими различными способами можно разместить здания на площади? Задачи такого типа называются комбинаторными.
Список использованной литературы
Список использованной литературы
1.С.П.Гаврилов. А.А Сапоженко. Сборник задач по дискретной математике. М.: Наука, 1978.
2.Н. Я. Виленкин, Комбинаторика, Москва, Наука, 1969.
3.Н. Б. Алфутова, А. В. Устинов, Алгебра и теория чисел (сборник задач), Москва, МЦНМО, 2002.
4.А. М. Райгородский, А. В. Савватеев, И. Д. Шкредов, Комбинаторика (методическое пособие для факультета биоинженерии и биоинформатики МГУ), Москва, МАКС-ПРЕСС, 2005.
5.М. Холл, Комбинаторика, Москва, Мир, 1970.
6.Р. Стенли, Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции, Москва, Мир, 2005.
7.Г. М. Фихтенгольц, Курс дифференциального и интегрального исчисления, Москва Ижевск, Физматлит, 2003.
8.А. А. Карацуба, Основы аналитической теории чисел, Москва, Эдиториал УРСС, 2004.
9.Г. Эндрюс, Теория разбиений, Москва, Наука, 1982.
10.Ф. Харари, Теория графов, Москва, Мир, 1973.
11.О. Оре Теория графов. М.: Наука, 1980.
12.Ф. Харари, Э. Палмер, Перечисление графов, осква, Мир, 1977.