Контрольная работа по дискретной математ

Cрок выполнения : сегодня

Вид работы : Контрольная

Дисциплины:
Математические: Дискретная математика.

Добавлен 23.10.2010 12:21:33

Уникальность:

Доработка:

Подробно: Контрольная работа по дискретной математике. 1. Свойства бинарных отношений. В задачах 1.1. – 1.16. установить свойства отношения (рефлексивность, иррефлексивность, симметричность, строгую/нестрогую антисимметричность, связность, транзитивность) на указанном множестве. Указать, является ли оно отношением эквивалентности, строгого/нестрогого частичного/линейного порядка. 1.1. — четное} на множестве натуральных чисел ; 1.2. — нечетное} на множестве натуральных чисел ; 1.3. } на множестве натуральных чисел ; 1.4. } на множестве натуральных чисел ; 1.5. : и находятся на одинаковом расстоянии от оси } на множестве точек действительной плоскости ; 1.6. : векторы и коллинеарны} на множестве точек действительной плоскости ; 1.7. : векторы и коллинеарны} на множестве точек действительной плоскости без начала координат; 1.8. : } на множестве всех подмножеств множества ; 1.9. : } на множестве всех подмножеств множества ; 1.10. : } на множестве всех подмножеств множества ; 1.11. : } на множестве всех подмножеств множества ; 1.12. : } на множестве всех подмножеств множества ; 1.13. : } на множестве всех подмножеств множества ; 1.14. : } на множестве всех подмножеств множества ; 1.15. : знаком с } на множестве людей; 1.16. : — прямой потомок } на множестве людей. 2. Бинарные отношения и графы. В задачах 1.17. – 1.32. найти матрицу смежности графа транзитивного замыкания отношения на множестве M. 2.1. M = {0,1,2,3,4} и ; 2.2. M = {0,1,2,3,4} и « делится на »; 2.3. M = {2,3,4,5,6} и « делится на »; 2.4. M = {0,1} {0,1} {0,1} и ; 2.5. M = {0,1,2,3,4} и ; 2.6. M = {0,1,2,3,4} и ; 2.7. M = {0,1,2,3,4} и ; 2.8. M = {0,1,2,3,4} и ; 2.9. M = {0,1,2,3,4} и ; 2.10. M = и ; 2.11. M = и «одна из букв , входит в слово , но не входит в слово »; 2.12. M = и «буква входит в слово , но не входит в слово »; 2.13. M = и «каждая буква, которая входит в слово , входит и в слово »; 2.14. M = {0,1} {0,1,2} и ; 2.15. M = {0,1} {0,1,2} и ; 2.16. M = {0,1} {0,1,2} и ; 3. Свойства матрицы смежности графа. В задачах 1.33. – 1. 50., используя теорему об n-ой степени матрицы смежности графа, найти: 3.1. ; 3.2. ; 3.3. ; 3.4. ; 3.5. ; 3.6. ; 3.7. ; 3.8. ; 3.9. ; 3.10. ; 3.11. ; 3.12. ; 3.13. ; 3.14. ; 3.15. ; 3.16. . 4. Элементы комбинаторики. 4.1. Найти количество трехзначных чисел, в десятичной записи которых встречается цифра 1. 4.2. Найти количество чисел от 1 до 100, которые делятся хотя бы на одно из чисел 2, 3 или 5. 4.3. Найти, сколькими способами можно перетасовать колоду из 32 карт. Используя формулу Стирлинга оценить логарифм полученного числа. 4.4. Найти число различных записей, которые можно получить, переставляя элементы последовательности «011222». Указание. Использовать формулу числа перестановок с повторениями типа (n1, n2, …, nk). 4.5. Найти число различных способов выбрать 10 карт из 32 так, чтобы среди выбранных карт было ровно два туза. Указание. Каждому 10-элементному набору карт, содержащему ровно два туза, может быть однозначно сопоставлена пара (x, y), где x – 2-множество тузов, а y – 8-множество «не-тузов» (что позволяет воспользоваться принципом произведения). 4.6. Сколькими способами можно выбрать на шахматной доске (размером 88) две клетки разных цветов? 4.7. Сколькими способами можно выбрать на шахматной доске три клетки так, чтобы любые две из них не лежали на одной вертикали или горизонтали? 4.8. Сколькими способами можно выбрать на шахматной доске три клетки так, чтобы все три из них не лежали на одной вертикали или горизонтали? 4.9. Сколькими способами можно упорядочить предметы a, b, c, d, e, f так, чтобы предмет a непосредственно предшествовал предмету b? 4.10. Сколькими способами можно упорядочить предметы a, b, c, d, e, f так, чтобы предмет a предшествовал (не обязательно непосредственно) предмету b? Указание. Представить множество всех указанных упорядочений в виде объединения множеств упорядочений, в которых a занимает i-ое, а b – j-ое место. 4.11. Сколькими способами можно упорядочить предметы a, b, c, d, e, f так, чтобы между предметами a и b находились ровно два предмета? 4.12. Сколькими способами можно упорядочить предметы a, b, c, d, e, f так, чтобы между предметами a и b находился хотя бы один предмет? 4.13. Сколькими способами из колоды, содержащей 36 карт можно вытащить 9 карт, содержащих ровно 5 карт одной масти? Указание. Воспользоваться тем, что: - каждый набор из 9-и карт содержит не более одного пятиэлементного подмножества карт одной масти, - каждому 9-элементному набору карт, содержащему ровно пять карт фиксированной масти m, может быть однозначно сопоставлена пара (x, y), где x – 5-множество карт масти m, а y – 4-множество карт, масть каждой из которых не равна m (что позволяет воспользоваться принципом произведения). 4.14. Найти число всех последовательностей длины 5 из двух символов «0» и «1», в каждой из которых (а) символ, следующий за символом «0», не может быть символом «1», (б) число символов «0» строго меньше числа символов «1». 4.15. Найти число различных способов раскрасить все элементы 4-множества X в три различных цвета, если (а) один или два цвета могут оказаться незадействованными, (б) в «раскрашенном» множестве X встретится хотя бы один элемент каждого из трех цветов. 4.16. Колода содержит карты четырех различных мастей и тринадцати различных достоинств (всего 52 карты). Сколько существует наборов из 5-и карт (вне зависимости от порядка), в которых три и только три карты имеют одинаковое достоинство? Указание. Воспользоваться тем, что: - каждый набор из 5-и карт содержит не более одного трехэлементного подмножества карт одинакового достоинства, - каждому 5-элементному набору карт, содержащему ровно три карты фиксированного достоинства d, может быть однозначно сопоставлена пара (x, y), где x – 3-множество карт достоинства d, а y – 2-множество карт, достоинство каждой из которых не равно d (что позволяет воспользоваться принципом произведения). 4.17._x_ Используя принцип включения и исключения, вывести формулу для нахождения значения функции Эйлера , если известны все простые делители p1, p2, …, pk числа n. 4.18._x_ Неподвижной точкой функции называется такой элемент множества , что . Пусть множество содержит 4 элемента. Найти количество: (а) функций без неподвижных точек, (б) взаимнооднозначных функций без неподвижных точек, Обобщить задачу (б) на случай n-элементного множества («задача о беспорядках») и найти , где - количество взаимнооднозначных функций без неподвижных точек, а - количество всех взаимнооднозначных функций . Указание. Вначале найти количество функций, содержащих хотя бы одну неподвижную точку. Для этого подсчитать количество функций, имеющих в качестве неподвижной точки фиксированный элемент , затем воспользоваться принципом включения и исключения. 5. Линейные рекуррентные последовательности. В задачах 3.1.-3.32. найти: а) формулу общего члена (т.е. формулу, выражающую значение an в зависимости от n) последовательности (an), заданной рекуррентным соотношением и начальными членами. б) рекуррентное соотношение для последовательности (sn) частичных сумм (sn = a0+a1+…+an) этой рекуррентной последовательности. 5.1. an+2 = 14an+1 – 49an; a0 = 0, a1 = 1; 5.17. an+2 = 6an+1 – 8an; a0 = 0, a1 = 2; 5.2. an+2 = 3an+1 + 4an; a0 = 0, a1 = 1; 5.18. an+2 = –6an+1 – 8an; a0 = -2, a1 = 0; 5.3. an+2 = –3an+1 + 4an; a0 = 1, a1 = 1; 5.19. an+2 = 2an+1 + 8an; a0 = -2, a1 = 2; 5.4. an+2 = 2an+1 + 15an; a0 = –1, a1 = 1; 5.20. an+2 = 9an+1 + 20an; a0 = -2, a1 = 1; 5.5. an+2 = 6an+1 – 9an; a0 = 2, a1 = 1; 5.21. an+2 = an+1 + an; a0 = -1, a1 = 1; 5.6. an+2 = 4an; a0 = 0, a1 = 1; 5.22. an+2 = 8an+1 – 16an; a0 = -3, a1 = 0; 5.7. an+2 = 5an+1 – 4an; a0 = 1, a1 = 3; 5.23. an+2 = 20an+1 – 100an; a0 = 0, a1 = 10; 5.8. an+2 = –an; a0 = –1, a1 = 3; 5.24. an+2 = 2an+1 – an; a0 = -3, a1 = 2; 5.9. an+2 = an+1 + 2an; a0 = 0, a1 = 1; 5.25. an+3 = 3an+2 – 3an+1+аn; a0 = a1=0, a2 = 1; 5.10. an+2 = 4an+1 + 5an; a0 = 0, a1 = 2; 5.26. an+2 = 10an+1 – 21an; a0 = -1, a1 = 4; 5.11. an+2 = 5an+1 + 6an; a0 = 1, a1 = 1; 5.27. an+2 = an+1 + 2an; a0 = 2, a1 = 1; 5.12. an+2 = 12an+1 + 36an; a0 = –1, a1 = 0; 5.28. an+2 = 2an+1 + 15an; a0 = 0, a1 = 2; 5.13. an+2 = 6an+1 – 5an; a0 = –1, a1 = 1; 5.29. an+2 = 7an+1 + 30an; a0 = –1, a1 = 1; 5.14. an+2 = 9an+1 – 14an; a0 = –1, a1 = 0; 5.30. an+2 = –7an+1 + 30an; a0 = 0, a1 = 1; 5.15. an+2 = 10an+1 – 21an; a0 = –2, a1 = 1; 5.31. an+2 = –10an+1 – 25an; a0 = 0, a1 = 2; 5.16. an+2 = 10an+1 – 21an; a0 = 2, a1 = –2; 5.32. an+2 = 8an+1 – 15an; a0 = 0, a1 = 1; 6. Сетевые графики. На рисунке изображен граф. Его дуги обозначены буквами a – p. В задачах 4.1. – 4.32., взяв из таблицы вариантов данные о длине его дуг, определить: 1. Кратчайший путь из начальной вершины в конечную и длину кратчайшего пути. 2. Критический путь из начальной вершины в конечную и длину критического пути. 3. Считая этот граф сетевым графиком некоторого процесса, а длины дуг – временем осуществления работ, определить: - для каждой вершины-события ранний и поздний срок свершения и резерв времени, - для каждой дуги-работы полный и независимый резерв времени. Варианты: № a b c d e f g H i j k l m n o p 6.1 4 5 3 5 6 4 2 7 4 8 2 8 6 2 1 4 6.2 3 3 4 2 5 7 4 3 3 5 8 2 2 6 7 3 6.3 3 4 4 3 2 1 3 5 5 4 3 4 7 1 2 2 6.4 3 4 4 4 4 4 6 6 7 3 8 5 1 4 1 3 6.5 3 2 1 4 6 3 1 1 5 3 6 7 8 4 2 6 6.6 3 2 2 4 5 2 6 9 4 5 2 3 4 2 6 7 6.7 3 5 5 4 6 7 2 3 4 5 6 3 6 3 2 5 6.8 3 4 4 4 2 2 3 1 2 3 4 2 3 1 3 3 6.9 3 6 4 3 5 6 2 5 2 5 6 2 5 3 4 3 6.10 3 4 1 7 4 7 3 4 2 5 2 5 1 3 7 5 6.11 3 4 3 5 6 4 2 7 4 8 2 8 6 2 1 4 6.12 5 3 5 2 5 7 4 3 3 5 8 2 2 6 7 3 6.13 5 4 4 2 2 1 3 5 5 4 3 4 7 1 2 2 6.14 4 4 4 4 1 4 6 6 7 3 8 5 1 4 1 3 6.15 4 2 1 4 6 6 1 1 5 3 6 7 8 4 2 6 6.16 6 2 2 4 5 2 7 9 4 5 2 3 4 2 6 3 6.17 5 5 5 4 6 7 2 8 4 5 6 3 6 3 7 5 6.18 4 4 4 4 2 2 3 1 4 3 4 2 3 6 3 3 6.19 6 6 4 3 5 6 2 5 2 8 6 2 4 3 4 3 6.20 7 4 1 7 4 7 3 4 2 5 1 6 1 3 7 5 6.21 8 5 3 5 6 4 2 7 4 8 2 8 6 2 1 4 6.22 6 3 4 2 5 7 4 3 3 5 8 2 2 6 7 3 6.23 7 4 4 3 2 1 3 5 5 4 3 4 7 1 2 2 6.24 6 4 4 4 4 4 6 6 7 3 8 5 1 4 1 3 6.25 6 2 1 4 6 3 1 1 5 3 6 7 8 4 2 6 6.26 6 2 2 4 5 2 6 9 4 5 2 3 4 2 6 7 6.27 7 5 5 4 6 7 2 3 4 5 6 3 6 3 2 5 6.28 8 4 4 4 2 2 3 1 2 3 4 2 3 1 3 3 6.29 5 3 4 2 5 6 1 6 3 7 2 1 7 2 2 1 6.30 5 8 9 1 4 2 5 2 4 3 3 6 2 3 7 3 6.31 1 4 2 7 2 5 2 6 2 4 8 2 1 6 3 1 6.32 4 1 7 4 3 7 3 6 2 5 7 2 9 1 2 6 7. Биномиальные модели ценообразования активов. Текущая цена актива составляет S0 рублей. За один период цена актива может увеличиться на % или уменьшиться на %. Безрисковая годовая ставка составляет % годовых. В задачах 5.1. – 5.32. определить: 1) количество (м.б. дробное) опционов, обеспечивающее безрисковость портфеля, 2) премию за европейский опцион «колл» на этот актив со сроком исполнения через 1 период и ценой исполнения рублей. 3) рассмотреть данную задачу как многопериодную с числом периодов 360, считая, что - максимальный, а - минимальный возможный процент повышения цены актива за 360 периодов. Найти премию за европейский опцион «колл» на этот актив со сроком исполнения через 360 периодов. Данные взять из таблицы вариантов. Варианты: № S0, руб , % , % , % 7.1 100 10 14 10 105 7.2 100 15 23 10 110 7.3 100 5 12 10 100 7.4 100 25 19 10 95 7.5 100 12 16 10 105 7.6 100 11 17 10 110 7.7 100 13 20 6 105 7.8 1000 16 19 6 1100 7.9 1000 17 21 6 1100 7.10 1000 19 13 6 1100 7.11 1000 18 15 6 1000 7.12 1000 31 31 10 1200 7.13 1000 32 33 10 1200 7.14 200 35 35 10 220 7.15 200 14 16 10 210 7.16 200 4 9 6 205 7.17 200 6 10 6 205 7.18 200 8 11 6 205 7.19 2000 7 9 6 2050 7.20 2000 9 8 6 2010 7.21 2000 16 12 6 2100 7.22 2000 17 18 6 2200 7.23 2000 18 16 6 2200 7.24 2000 20 22 10 2200 7.25 2000 21 25 10 2200 7.26 2000 22 25 10 2200 7.27 2000 23 26 10 2200 7.28 2000 27 28 10 2200 7.29 2000 29 29 10 2300 7.30 2000 13 16 6 2100 7.31 200 9 10 6 210 7.32 200 19 23 6 220 Указания к пункту 3): 1. Безрисковая ставка r0 , повышающий коэффициент и понижающий коэффициент за 1 период могут быть определены исходя из соотношений: , , . 2. По возможности используйте приближенную формулу.

Кратко: Контрольная работа по дискретной математике.