Содержание
Введение 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.
Введение
Дискретная математика занимается изучением конечных свойств объектов, которые возникают как в различных разделах математики, так и в ее технических при