- •1.Предмет и задачи дм. Дискр величины.
- •2.Понятие рекурсии. Показ принципа работы рекурсии на схеме.
- •4.Система рекуррентных соотношений
- •5. Приемы и методы решения рекуррентных соотношений.
- •6.Предмет и задачи раздела раздела матем-ки комбинаторика. Правили суммы и правило произведения.
- •7.Комбинаторика. Размещение с повторением и без повторения.
- •8.Комбинаторика. Перестановка с повтор-ем и без повтор-я.
- •9. Комбинаторика. Сочетание с повторением и сочетание без повторения
- •10. Комбинаторные задачи геом-ого содержания. Свойства чисел . Свойства чисел
- •13. Генерация подмножеств. Числа Стирлинга 2-го и 1-го рода.
- •14. Числа Каталана.
- •15. Полиномиальная формула.
- •16. Производящие функции и их применения.
- •17. Принцип включения и исключения.
- •18. Функция Эйлера. Функция Мебиуса.
- •19. Графы. Основные понятия и определения теории графов.
- •20. Матрица смежности. Валентность вершины. Матрица инцидентности.
- •21. Виды графов
- •22. Маршруты, цепи(пути) и циклы в графах.
- •23. Связные графы. Изоморфизм графов. Подграфы.
- •24. Эйлеровы и гамильтоновы графы.(Эйлеров граф).
- •25. Изоморфизм графов.
- •26. Планарные графы. Непланарность графов к5 и к3,3. Теорема Понтрягина-Куротовского.
- •27. Теорема Эйлера и ее следствия.
- •28. Деревья.
- •29. Ориентированные графы. Полный ориентированный граф.
- •30. Графы с цветными ребрами. Свойства графов с цветными ребрами.
- •31. Сетевое планирование и управление. Сетевой график.
- •32. Принципы и правила построения сетевых графиков.
- •33. Критический путь в сетевых графиках.
- •34. О резервах времени в сетевых графиках.
4.Система рекуррентных соотношений
На практике существ. много задач, где при решении исп-ся не одно рекурр соотнош-е, а 2 или более рекурр соотн-я, тогда эти 2 рекурр соотн записыв-ся в виде сист. Множители послед-ти могут зависеть от предыдущих множ=ей, как своей послед-ти так и др послед-ей. Ex: 1!,2!,3!,4!,5! Знач-е ф-ии при |x|≤1 кажд слагаемое аn при n≥1/ Этой сумме по модулю меньше предыдущего. Кроме того > . Поэтому, если прибавить все множ-ли от а1 до аn из таких аn, что |an|>d? При d>0, то получен сумма отличается от sin x не больше чем на d.
n-?, |an|>d |an+1|≤в очевидно, что Sn=Sn-1+an при n>1. S1=a1=x. Это рав-во выражает сумму ч\з предыдущ сумму и очередное слагаемое, т.е. послед-ть значений суммы яв-ся рекуррентной, заметим, что при d<|x| слаг a1 не нужно прибавлять к сумме и резулт-ом должна быть сумма без слагаемых, поэтому к этой послед-ти прибавим S0=0, Sn=Sn-1+an при n>0.
Найдем рекурр соотнош для аn
,
; Sn=Sn-1+an ,(n>1)
S:=0; a:=x; i:=1;
While a>d do
Begin
S:=S+a;
a:=((x*x)*a)/((2*i)*(2*i-1));
i:=i+1;
end;
Реш-е рекурр соотнош в общем виде запис-ся так f(n+k)-F(n,f(n+k-1), fn)) (1). F-некотор ф-я от (к+1) переем-х, число к называют порядком соотнош-я. Реш-е рекурр соотнош (1) наз-ся послед-ть an для котор выполн-ся рав-во a(n+k)=F(n,a(n+k-1),…, a(n)) (2), n=0,1,2,3,..
Вообще говоря произвольное рекурр соотнош-е им ∞ много реш-ий. Ex: (*) а(n+1)=(n+1)f(n), (**)f(n+2)=f(n). Решением рекурр соотнош (* и (**) яв-ся С1n! и C1+C2(-1)n при любом С1 и С2.
5. Приемы и методы решения рекуррентных соотношений.
6.Предмет и задачи раздела раздела матем-ки комбинаторика. Правили суммы и правило произведения.
С камбинаторн вычисл приходится им дело представителям многих специальностей: химику при рассм различн возможных типов связей атомов в молекулах. Биолог при изуч разл возможных послед-ей чередования аминокислот в белковых соед-х, конструктору вычисл машин, агроному- рассм все возможн способы посевов на неск-х участках, диспетчер при составл графиков движения.
Камбинаторика- одна из разделов ДМ, котор приобрел важн значения в связи с использов-ем его в теории вероятности, матем логики, теор чисел, вычислит техники, кибернетики и т.д и т.п. Комбинаторику м\о рассм как часть теории конечн мн-в, любую комбинаторную задачу м\о свести к задаче о конечных множ-вах и их отображениях.
Комбинаторика возникла в 17 веке в связи с появлением азартных игр: карты, кости. В первое время по комбинаторикой понимали задачи связи с азартными играми. В ходе исследов таких задач были выработаны общие методы реш-я, выявления закономерности , были выведены формулы и т.д. и т.п. Комбинаторн задачи в связи с азартными играми решали еще древн арабы, «азар»-трудный. В Европе сильно развив-сь азартные игры и соотв комбинаторн вопросы.
Основ правила комбинаторики:
а) Правило суммы Опр-е: Пусть Эл-т а м\о выбрать k способом, объект b не такой, как а, м\о выбрать m способами, то выбор либо а либо b м\о произвотить (k+m) способами.
б)Правло произведения Опр-е: Если объект а м\о выбрать k сособами объект b не такой как а, то объект b м\о выбрать m способами, то выбор пары (а;b) м\о привеси (k;m).