Дискретная математика (стр. 3 )

ФИО преподавателя: Д __________________________

3.МетодическиЕ рекомендациИ для студентов

Дисциплина «Дискретная математика» изучается в течение одного семестра.

Основными видами учебной деятельности при изучении данной дисциплины являются: лекции, практические занятия, самостоятельная работа студента.

Таблица 1 дает представление о распределении общей трудоемкости дисциплины по видам учебной деятельности.

Таблица 1.

Дисциплина	Общая трудоемкость	Аудиторные занятия	Самостоятельная работа
Всего	Лекции	Практические
Дискретная математика	130 часов	76 часов	38 часов	38 часов	54 часа

Лекции являются одним из основных видов учебной деятельности в вузе, на которых преподавателем излагается содержание теоретического курса дисциплины. Рекомендуется конспектировать материал лекций. Кроме того, на лекционных занятиях заслушиваются доклады студентов по темам теоретического курса, вынесенных для самостоятельного изучения.

На практических занятиях происходит закрепление изученного теоретического материала и формирование профессиональных умений и навыков. Под руководством преподавателя студенты должны решить ряд задач.

Посещение студентами лекционных и практических занятий является обязательным.

С содержанием лекционных и практических занятий можно познакомиться в Рабочей модульной программе дисциплины.

Как видно из Таблицы 1, не мало времени при изучении дисциплины занимает внеаудиторная самостоятельная работа студента: самостоятельное изучение рекомендованной литературы, подготовка докладов, рефератов, решение задач для самостоятельной работы.

Формы и содержание самостоятельной работы, сроки выполнения, формы ее контроля приведены в технологической карте по дисциплине, которая является планом-графиком самостоятельной работы.

Список основной и дополнительной литературы, рекомендованной для самостоятельного изучения по дисциплине, приведен в Рабочей модульной программе дисциплины и Карте литературного обеспечения дисциплины.

Темы теоретического курса, вынесенные для самостоятельного изучения, и которые могут использоваться для подготовки докладов, приведены в Рабочей модульной программе дисциплины и Перечне вопросов для самостоятельной работы по дисциплине Дискретная математика.

Примерные темы для написания рефератов приведены в Рабочей модульной программе дисциплины и Тематике рефератов по дисциплине Дискретная математика.

В качестве дополнительных учебных материалов к УМКД прилагается два СD-диска, которые можно использовать для самостоятельной подготовки. Мультимедиа ресурсы содержат:

1.  Электронный вариант лекций к основным темам курса.

2.  Теоретические материалы.

3.  Дидактический материал.

4.  Тесты.

Образовательный процесс по дисциплине организован в соответствии с модульно-рейтинговой системой подготовки студентов.

Модульно-рейтинговая система (МРС) – система организации процесса освоения дисциплин, основанная на модульном построении учебного процесса. При этом осуществляется структурирование содержания каждой учебной дисциплины на дисциплинарные модули и проводится регулярная оценка знаний и умений студентов с помощью контроля результатов обучения по каждому дисциплинарному модулю и дисциплине в целом.

Данная дисциплина состоит из четырех дисциплинарных модулей: входного, двух базовых и одного итогового.

Входной модуль - это часть учебной дисциплины, отводимая на проверку «остаточных» знаний по ранее изученным смежным дисциплинам

Базовый модуль – это часть учебной дисциплины, содержащая ряд основных тем или разделов дисциплины. Содержание данной дисциплины разбито на 2 базовых модуля: «Основные понятия комбинаторики и теории графов», «Основные методы дискретной математики».С содержанием учебного материала, изучаемого в каждом базовом модуле, можно познакомиться в Рабочей модульной программе дисциплины.

Итоговый модуль – это часть учебной дисциплины, отводимая на аттестацию в целом по дисциплине.

Результаты всех видов учебной деятельности студентов оцениваются рейтинговыми баллами. Формы текущей работы и рейтинг-контроля в каждом дисциплинарном модуле, количество баллов как по дисциплине в целом, так и по отдельным формам работы и рейтинг-контроля указаны в Технологической карте дисциплины. В каждом модуле определено минимальное и максимальное количество баллов. Сумма максимальных баллов по всем модулям равняется 100%-ному усвоению материала. Минимальное количество баллов в каждом модуле является обязательным и не может быть заменено набором баллов в других модулях, за исключением ситуации, когда минимальное количество баллов по модулю определено как нулевое. В этом случае модуль является необязательным для изучения и общее количество баллов может быть набрано за счет других модулей. Дисциплинарный модуль считается изученным, если студент набрал количество баллов в рамках установленного диапазона. Для получения оценки «зачтено» необходимо набрать не менее 60 баллов, предусмотренных по дисциплине (при условии набора всех обязательных минимальных баллов по каждому дисциплинарному модулю).

Рейтинг по дисциплине – это интегральная оценка результатов всех видов учебной деятельности студента по дисциплине, включающей:

- рейтинг-контроль текущей работы;

- промежуточный рейтинг-контроль;

- итоговый рейтинг-контроль.

Рейтинг-контроль текущей работы выполняется в ходе аудиторных занятий по текущему базовому модулю в следующих формах: сдача задач для аудиторной и самостоятельной работы, практических работ, рефератов, выступление с докладами по темам, изучаемым самостоятельно.

Промежуточный рейтинг-контроль – это проверка полноты знаний по освоенному материалу текущего базового модуля. Он проводится в конце изучения каждого базового модуля в форме контрольных заданий без прерывания учебного процесса по другим дисциплинам.

Итоговый рейтинг-контроль является итоговой аттестацией по дисциплине, которая проводится в рамках итогового модуля в форме экзамена. Для подготовки к экзамену используйте Вопросы к экзамену, которые также приведены в Рабочей модульной программе дисциплины.

Преподаватель имеет право по своему усмотрению добавлять студенту определенное количество баллов (но не более 5 % от общего количества), в каждом дисциплинарном модуле:

- за активность на занятиях;

- за выступление с докладом на научной конференции;

- за научную публикацию;

- за иные учебные или научные достижения.

Студент, не набравший минимального количества баллов по текущей и промежуточной аттестациям в пределах первого базового модуля, допускается к изучению следующего базового модуля. Ему предоставляется возможность добора баллов в течение двух последующих недель (следующих за промежуточным рейтинг-контролем) на ликвидацию задолженностей.

Студентам, которые не смогли набрать промежуточный рейтинг или рейтинг по дисциплине в общеустановленные сроки по болезни или по другим уважительным причинам (документально подтвержденным соответствующим учреждением), декан факультета устанавливает индивидуальные сроки сдачи.

Если после этого срока задолженность по неуважительным причинам сохраняется, то назначается комиссия по приему академических задолженностей с обязательным участием заведующего кафедрой и декана (его заместителя). По решению комиссии неуспевающие студенты по представлению декана отчисляются приказом ректора из университета за невыполнение учебного графика.

В особых случаях декан имеет право установить другие сроки ликвидации студентами академических задолженностей.

Неявка студента на итоговый или промежуточный рейтинг-контроль отмечается в рейтинг-листе записью «не явился». Если неявка произошла по уважительной причине (подтверждена документально), деканат имеет право разрешить прохождение рейтинг-контроля в другие сроки. При неуважительной причине неявки в статистических данных деканата проставляется «0» баллов, и студент считается задолжником по данной дисциплине.

4. Банк тестовых заданий по дисципЛине «Дискретная математика»

Вариант 1

1. Сколькими способами из слова алгоритм можно выбрать две буквы, одна из которых гласная, а другая согласная?

А) 30; Б) 8; В) 15; Г) 16;

2. Найти число способов, которыми можно выписать в один ряд девять троек и шесть пятерок так, чтобы никакие две пятерки не стояли рядом.

А) 28; Б) 210; В)45; Г) 56;

3. Комбинации из n элементов, отличающиеся порядком элементов и содержащие все элементы n − элементного множества, называются

А) перестановками; Б) сочетаниями; В) разбиениями; Г) перестановками с повторениями ;

4. Вычислить (1 −√5)4 .

А)Ö5; Б)Ö5; В)Ö5; ; Г)Ö5;

5. Найти решение рекуррентного соотношения , .

А) -5n + 6n; Б) 7n - 6n; В) -3n + 4n; Г) 5n – 4n;

6. Граф, у которого каждому ребру поставлено в соответствие вещественное число, называется

А) орграфом; Б) двудольным; В) эйлеровым; Г) взвешенным;

7. Формула Эйлера для связных плоских графов имеет вид:

А) m + n – f = 1; Б) n + f − m = 2; В) f + m − n = 2; Г) n + f − m = 0;

8. Взвешенный Граф G(5,7) задан списком ребер: (1,2,1), (1,3,2), (2,4,2), (2,3,2), (3,4,1), (4,5,4), (3,5,5). Вес остова минимального веса равен:

А) 8; Б) 6; В) 7; Г ) 9;

9. Пара конечных множеств G = <V, E>, где V ¹ Æ, а Е содержит одинаковые пары элементов из V, называется

А) орграфом; Б) псевдографом; В) мультиграфом; Г ) гиперграфом;

10. Взвешенный орграф G(5,8) задан списком дуг: (1,2,2), (2,3,1), (1,4,11), (2,4,7), (3,4,4), (3,5,2), (5,4,1), (1,5,6). Кратчайший путь из вершины 1 в вершину 4 состоит из

А) одной дуги; Б) двух дуг; В) трех дуг; Г) четырех дуг;

11. Граф G(5,9) задан списком ребер: (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (3,5), (3,4), (4,5). Какой цвет будет назначен вершине 5 при использовании алгоритма последовательной раскраски?

А) 5; Б) 2; В) 3; Г) 4;

12. Как определяется функция вещественного числа ?

А) Наибольшее целое £ X; Б) Наименьшее целое ³ X; В) {X}− X; Г) X+1

13) Найти значение выражения 12,75 mod 4,2.

А) 0,15; Б) 0,75; В) 4,05; Г ) 0,2;

Вариант 2

1. Комбинации из k различных элементов, отличающиеся порядком или составом элементов, взятых из n − элементного множества, называются

А) перестановками из k элементов; Б) сочетаниями из n элементов по k ; В) разбиениями; Г) размещениями из n элементов по k;

2. Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов?

А) 60; Б) 12; В)120; Г) 36;

3. Найти число способов, которыми можно расставить по кругу семь пятерок и четыре тройки так, чтобы никакие две тройки не стояли рядом.

А) 56; Б) 840; В) 120; Г) 35;

4. Вычислить (2 + √2)5 .

А) 232 + 164Ö2; Б) 196 +164Ö2; В) 232 + 82Ö2; ; Г) 232 +162Ö2;

5. Найти решение рекуррентного соотношения , .

А) (-5)n + 2n; Б) 5n +(– 2)n; В) -5n + 2n; Г) 2n +1n;

6. Связный граф, у которого есть цикл, содержащий все ребра графа, называется

А) орграфом; Б) двудольным; В) эйлеровым; Г) взвешенным;

7. Какое утверждение для графа K5 является неверным:

А) связный; Б) гамильтоновый; В) планарный; Г) полный;

8. Взвешенный Граф G(6,9) задан списком ребер: (1,2,2), (1,3,3), (2,4,2), (2,3,1), (5,4,1), (3,5,3), (2,5,2), (6,5,5), (4,6,4). Вес остова минимального веса равен:

А) 8; Б) 10; В) 9; Г) 11;

9. Пара конечных множеств G = <V, E>, где V ¹ Æ, а Е содержит упорядоченные пары элементов из V, называется

А) орграфом; Б) псевдографом; В) мультиграфом; Г ) гиперграфом;

10. Взвешенный орграф G(5,8) задан списком дуг: (1,2,10), (1,3,1), (1,4,4), (2,5,3), (3,4,2), (3,5,9), (4,5,7), (4,2,1). Кратчайший путь из вершины 1 в вершину 5 имеет длину

А) 6; Б) 5 ; В) 7; Г) 8;

11. Граф G(6,11) задан списком ребер: (1,2), (1,3), (1,4), (1,5), (1,6), (2,3), (2,6), (3,5), (3,4), (4,5), (5,6). Какой цвет будет назначен вершине 6 при использовании алгоритма последовательной раскраски?

А) 4; Б) 6; В) 2; Г) 3;

12. Найти значение выражения 13,9 mod 3,2.

А) 0,1; Б) 1,1; В) 2,1; Г) −2,1;

13. Как определяется функция вещественного числа ?

А) Наибольшее целое £ X; Б) Наименьшее целое ³ X; В) {X}− X; Г) X+1

Вариант 3

1. Сколькими способами из колоды в 36 карт можно выбрать две карты так, чтобы одна из них была картинкой (валет, дама, король), а другая нет?

А) 36; Б) 72; В) 576; Г) 288;

2. Найти число способов, которыми можно расставить 3 белых и 3 черных фигуры на 8 полях первой горизонтали шахматной доски?

А) 560; Б) 28; В) 3136; Г) 66;

3. Вычислить (3 −√2)4 .

А) Ö2; Б) Ö2; В) Ö2; Г) Ö2;

4. Комбинации из k различных элементов, отличающиеся составом элементов, взятых из n − элементного множества, называются

А) перестановками из k элементов; Б) сочетаниями из n элементов по k; В) разбиениями; Г) размещениями из n элементов по k;

5. Найти решение рекуррентного соотношения , .

А) -5n + 4n; Б) 5n +(– 6)n; В) 2n - 3n; Г) 2n + (-3)n;

6. . Связный граф, у которого есть цикл, проходящий через все вершины по одному разу, называется

А) орграфом; Б) двудольным;

В) эйлеровым; Г) гамильтоновым;

7. Какое утверждение для графа K3,3 является неверным:

А) двудольный; Б) эйлеров; В) непланарный; Г) гамильтоновый;

8. Взвешенный Граф G(6,9) задан списком ребер: (1,2,4), (1,6,1), (1,4,1), (1,5,1), (3,2,5), (4,5,1), (3,4,2), (3,5,2), (5,6,1). Вес остова минимального веса равен:

А) 9; Б) 6; В) 7; Г) 8;

9. Пара конечных множеств G = <V, E>, где V ¹ Æ, а Е состоит из произвольных непустых подмножеств множества V, называется

А) орграфом; Б) псевдографом;

В) мультиграфом; Г ) гиперграфом;

10. . Взвешенный орграф G(5,8) задан списком дуг: (1,2,9), (1,3,1), (1,4,4), (2,5,3), (3,4,2), (3,5,8), (4,5,7), (4,2,1). Кратчайший путь из вершины 1 в вершину 5 состоит из

А) одной дуги; Б) двух дуг; В) четырех дуг; Г) трех дуг;

11. Найти значение выражения 17,75 mod 5,3.

А) 3; Б) −3,45; В) 3,3; Г) 1,85;

12. Граф G(6,10) задан списком ребер: (1,2), (1,5), (1,6), (2,3), (2,4), (2,5), (2,6), (3,4), (4,5), (5,6). Какой цвет будет назначен вершине 6 при использовании алгоритма последовательной раскраски?

А) 3; Б) 2; В) 5; Г) 4;

13. Как определяется функция вещественного числа {X}?

А) Наибольшее целое £ X; Б) Наименьшее целое ³ X;

Вариант 4

1. Имеется 6 пар перчаток различных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку и одну − на правую руку так, чтобы эти перчатки были разных размеров?

А) 60; Б) 30; В) 11; Г) 66;

2. В цветочном магазине продаются цветы 5 видов. Сколько различных букетов из 7 цветов может составить продавец?

А) 56; Б) 462; В) 21; Г) 330;

3. Найти решение рекуррентного соотношения ,

А) 3n + (-4)n; Б) 4n +(– 5)n; В) 2n - 3n; Г) 3n - 4n;

4. Вычислить (3 +√2)4.

А) 193 + 120Ö2; Б) 193 +132Ö2; В) 139 + 132Ö2; Г) 183 +122Ö2;

5. Комбинации из k не обязательно различных элементов, отличающиеся порядком элементов, взятых из n − элементного множества, называются

А) перестановками из k элементов; Б) сочетаниями с повторениями из n элементов по k; В) размещениями с повторениями из n элементов по k; Г) перестановками с повторениями из n элементов;

6. Связный граф, у которого любые две вершины соединены единственной цепью, является

А) гамильтоновым; Б) двудольным; В) эйлеровым; Г) деревом.

7. Какое утверждение не следует из теоремы Эйлера о плоских графах:

А) n + f −m=2; Б) m £ 3n−6 при n ³3;

В) K3,3 − двудольный; Г) K5 − не планарный;

8. Взвешенный граф G(6,9) задан списком ребер: (1,2,4), (1,6,2), (3,6,2), (2,6,5), (4,5,7), (3,5,4), (2,5,1), (5,6,3), (3,4,2). Какое ребро будет выбрано на втором шаге алгоритма Прима?

А) (1,6); Б) (3,4); В) (3,6); Г) (5,6);

9. Пара конечных множеств G = <V, E>, где V ¹ Æ, а Е содержит пары одинаковых элементов из V, называется

А) орграфом; Б) псевдографом;

В) мультиграфом; Г ) гиперграфом;

10. Взвешенный орграф G(5,8) задан списком дуг: (1,2,8), (1,3,1), (1,4,5), (2,5,3), (3,4,2), (3,5,10), (4,5,4), (4,2,1). Кратчайший путь из вершины 1 в вершину 5 имеет длину

А) 7; Б) 5 ; В) 6; Г) 8;

11. Граф G(6,10) задан списком ребер: (1,2), (1,5), (1,6), (2,3), (2,5), (3,4), (3,5), (4,5), (4,6), (5,6). Какой цвет будет назначен вершине 6 при использовании алгоритма последовательной раскраски?

А) 2; Б) 5; В) 4; Г) 3;

12. Как определяется функция вещественного числа X mod Y?

А) Наибольшее целое £ X; Б) Наименьшее целое ³ X;

13. Найти значение выражения 14,9 mod 3,3.

А) 1,7; Б) 0,3; В) −1,6; Г) 5;

ТЕСТ

Вариант №1.

1). Всякое подмножество М, состоящее из k элементов, называется

a) Размещением

b) Сочетанием

c) Размещением с повторением

d) Перестановкой

2). Число размещений с повторениями находятся по формуле

a) nm

b)

c)

d) fn + fn-1

3). Сколькими способами из колоды в 36 карт можно выбрать две карты, так, чтобы одна из них была картинкой (валет, дама, король), а другая нет?

a) 36

b) 72

c) 576

d) 288

4). Сколькими способами тренер может отобрать в команду трех мальчиков из семи и двух девочек из пяти?

a) 350

b) 792

c) 112

d) 4200

5). Сколько различных девятизначных чисел можно получить, используя в их записи две двойки, три тройки и четыре четверки?

a) 1260

b) 288

c) 576

d) 362880

6). Найти член разложения ( +)8, который содержит x2.

a) 56/ а2

b) 28/ а4

c) 70а

d) 1/ а8

Вариант №2.

1). Всякое упорядоченное конечное множество или всякая конечная последовательность длины n, все элементы которой различны называется

a) Размещением

b) Сочетанием

c) Размещением с повторением

d) Перестановкой

2). Число сочетаний с повторениями находятся по формуле

a) n!

b)

c)

d)

3). Рота состоит из трех офицеров, 6 сержантов и 60 рядовых. Сколькими способами можно выделить из них отряд, состоящий из одного офицера, одного сержанта и двух рядовых?

a) 31860

b) 64800

c) 63720

d) 2160

4). На окружности выбрано десять точек. Сколько существует треугольников с вершинами в этих точках, если треугольники с разной последовательностью вершин считаются равными?

a) 720

b) 120

c) 80

d) 360

5). В кондитерской имеются пирожные пяти видов. Сколькими способами можно составить набор из трех пирожных?

a) 15

b) 35

c) 10

d) 60

6). Найти член разложения (x + )10, не содержащий x?

a) 32

b) 80

c) -1

d) -40

Вариант №3.

1). Всевозможные расстановки по k предметов в каждой - k-расстановки, называются

a) Размещением

b) Сочетанием

c) Размещением с повторением

d) Перестановкой

2). Число перестановок с повторениями находятся по формуле

a) n!

b)

c)

d)

3). В автомашине 5 мест. Сколькими способами пять человек могут усесться в эту машину, если занять место водителя могут только двое из них?

a) 60

b) 48

c) 120

d) 24

4). Сколькими способами можно распределить 8 книг между тремя учениками, если каждому ученику достанется хотя бы одна книга?

a) 4096

b) 512

c) 336

d) 6561

5). В цветочном магазине продаются цветы пяти видов. Сколько различных букетов из семи цветов может составить продавщица? Букеты, отличающиеся только расположением цветов, считаются одинаковыми.

a) 56

b) 462

c) 21

d) 330

6). Найти член разложения (x + )10, содержащий x?

a) 32

b) 80

c) -1

d) -40

Вариант №4.

1). Всякая упорядоченная часть из k элементов множества, содержащего n элементов, называется?

a) Размещением

b) Сочетанием

c) Размещением с повторением

d) Перестановкой

2). Число перестановок находятся по формуле

a) n!

b)

c)

d)

3). У скольких двузначных чисел первая буква нечетная, а вторая четная? Число нуль считается четным числом.

a) 20

b) 24

c) 26

d) 25

4). Сколькими способами из полной колоды в 36 карт можно вынуть четыре карты разной масти?

a) 39366

b) 6561

c) 262144

d) 26244

5). Сколько можно построить различных прямоугольных параллелепипедов, если длина каждого его ребра может выражаться любым целым числом от 1 до 8?

a) 56

b) 120

c) 336

d) 112

6). Найти член разложения ( +)8, который содержит x.

e) 56/ а2

f) 28/ а4

g) 70а

h) 1/ а8

Второе контрольное занятие нужно провести после изучения методов решения комбинаторных задач.

Контрольная работа.

Вариант №1.

1). В чем заключается метод включения – исключения?

2). Дайте определение рекуррентного соотношения.

3). Найдите частное решение рекуррентного соотношения fn+2 =5 fn-1 - 6fn

, соответствующие начальным членам рекуррентной последовательности: a0 = 0, a1 = 1.

4). n человек сдали свои n шляп гардеробщику; требуется найти число способов, которыми шляпы могут быть розданы обратно, причем каждый получает одну шляпу и ни один не получает свою собственную. Решить задачу о шляпах для n = 6.

5). Найти число разбиений числа 11. Проверить свой результат на компьютере.

Вариант №2.

1). Напишите основные свойства функции p(n). 2). Дайте определение линейного рекуррентного соотношения с постоянными коэффициентами.

3). Решите рекуррентное соотношение fn+2 =3 fn-1 - 2fn

, соответствующие начальным членам рекуррентной последовательности: a0 = 0, a1 = 1.

4). n человек сдали свои n шляп гардеробщику; требуется найти число способов, которыми шляпы могут быть розданы обратно, причем каждый получает одну шляпу и ни один не получает свою собственную. Решить задачу о шляпах для n = 5.

5). Найти число разбиений числа 10. Проверить свой результат на компьютере.

Вариант №3.

1). Напишите основные свойства функции p(n). 2). Напишите общий вид решения линейного рекуррентного соотношения с постоянными коэффициентами, с одинаковыми корнями характеристического уравнения.

3). Решите рекуррентное соотношение fn+2 =14 fn-1 - 48fn

, соответствующие начальным членам рекуррентной последовательности: a0 = 1, a1 = 2.

4). n человек сдали свои n шляп гардеробщику; требуется найти число способов, которыми шляпы могут быть розданы обратно, причем каждый получает одну шляпу и ни один не получает свою собственную. Решить задачу о шляпах для n = 7.

5). Найти число разбиений числа 8. Проверить свой результат на компьютере.

Вариант №4.

1). В чем заключается метод включения – исключения?

2). Напишите общий вид решения линейного рекуррентного соотношения с постоянными коэффициентами, с разными корнями характеристического уравнения.

3). Решите рекуррентное соотношение fn+2 = -fn-1 + 6fn

, соответствующие начальным членам рекуррентной последовательности: a0 = 0, a1 = 1.

4). n человек сдали свои n шляп гардеробщику; требуется найти число способов, которыми шляпы могут быть розданы обратно, причем каждый получает одну шляпу и ни один не получает свою собственную. Решить задачу о шляпах для n = 8.

5). Найти число разбиений числа 9. Проверить свой результат на компьютере.

В конце профильного курса учащиеся проходят тестирование по всему пройденному материалу. Контрольный урок можно повести в виде теста на компьютере.

Итоговый тест.

Вариант №1.

В окошке с правильным ответом поставьте галочку.

1). Всякая упорядоченная часть из k элементов множества, содержащего n элементов, называется:

Размещение

Размещение с повторениями

Сочетание

Сочетание с повторениями

2). Всякая упорядоченная последовательность элементов множества М, в котором a встречается l раз, b - b раз,…, с - g раз, называется

Размещение

Размещение с повторениями

Сочетание

Перестановка с повторениями

3). Линейным рекуррентным соотношением с постоянными коэффициентами называется соотношения вида

Fn+k= a1 Fn+k-1 +a2Fn+k-2+... + akFn

an+k= F(an,an+1, ..., an+k-1, n)

r2 = а1r+ а2

a0, a1, a3,..., an,...

4). Формула бинома Ньютона имеет вид:

(+ +...+)n = å P( , ,..., )* ,

(a + b)n = ∑k=0:n Cn,kakbn−k

p(n) = p(n-1) + p(n-2)- p(n-5)-p(n-7)+...+ *p(n-3* -) + p(n-3* +)+...,

fn+m = fn-1·fm + fn·fm+1

5). Сколько различных трехзначных чисел можно составить, используя цифры 1, 2, 3, 4, 5, если каждую цифру можно использовать только один раз?

24 12

30 10

6). Сколько трехзначных чисел, делящихся на три, можно составить из всех нечетных цифр, если каждую из них использовать не более одного раза?

24

60

4

10

7). У одного человека имеется 8 книг, а у другого - 10. Сколькими способами они могут обменять друг у друга три книги на три книги?

1056

6720

176

241920

8). Сколько различных трехзначных чисел можно записать с помощью начетных цифр?

60

35

10

125

9). Решите рекуррентное соотношение fn+2 =-4 fn-1 - 4fn

, соответствующие начальным членам рекуррентной последовательности: a0 = 0, a1 = 6.

(C1+C2n)(-2)n-1.

C1(-2)n.+C2n(-2)n.

(6+6*2) (-2)n

18(-2)n-1

10). Группа школьников, в составе 25 человек, отправилась в лес. Известно, что 5 человек взяли с собой бутерброды с колбасой, 5 человек – бутерброды с ветчиной, 6 человек – бутерброды с сыром, 4 человека взяли бутерброды с ветчиной и сыром, 3 – с ветчиной и колбасой и 2 – с сыром. Некоторые взяли бутерброды трех сортов. Сколько человек взяли бутерброды трех сортов?

5

2

6

3

Вариант №2.

1). Всякое подмножество М, состоящее из k элементов, называется

Размещением

Сочетанием

Размещением с повторением

Перестановкой

2). Всякое упорядоченное конечное множество или всякая конечная последовательность длины n, все элементы которой различны называется

Размещением

Сочетанием

Размещением с повторением

Перестановкой

3). Каждый член этой последовательности, начиная с третьего, равен сумме двух предыдущих.

Рекуррентное соотношение

Числа Фибоначчи

Линейное рекуррентное соотношение с постоянными коэффициентами

Решение задачи о шляпах

4). Полиномиальная формула имеет вид

(+ +...+)n = å P( , ,..., )* ,

(a + b)n = ∑k=0:n Cn,kakbn−k

p(n) = p(n-1) + p(n-2)- p(n-5)-p(n-7)+...+ *p(n-3* -) + p(n-3* +)+...,

fn+m = fn-1·fm + fn·fm+1

5). Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов и одна из полос должна быть красной, (красный входит в состав данных пяти цветов)?

36

7

72

21

6). Из группы, состоящей из пяти мальчиков и восьми девочек, надо отобрать группу из четырех человек, так, чтобы в ней оказалось не менее трех девочек. Сколькими способами это можно сделать?

131

280

350

1960

7). Сколькими способами можно расставить 3 белых и 3 черных шашки на восьми полях первой горизонтали шахматной доски?

560

28

3136

66

8). Сколько различных «слов» можно составить из слова «Математика» за счет перестановки составляющих его букв?

3628800

24

151200

907200

Решите рекуррентное соотношение fn+2 =6 fn-1 - 9fn

, соответствующие начальным членам рекуррентной последовательности: a0 = 0, a1 = 6.

(C1+C2n)3n-1.

C13n.+C2n3n.

(6+6*2) 3n

18*3n-1

10). Группа школьников, в составе 25 человек, отправилась в лес. Известно, что 5 человек взяли с собой варежки, 5 человек –теплые носки, 6 человек –теплый свитер, 4 человека взяли теплые носки и варежки, 3 – варежки и теплый свитер и 2 – теплый свитер и теплые носки. Некоторые взяли все три вещи. Сколько человек взяли и варежки, и теплые носки, и теплый свитер?

5 2

6 3 5.ПРИМЕРНАЯ ТЕМАТИКА РЕФЕРАТОВ

1.  Комбинаторные суммы и их вычисление.

2.  Метод производящих функций в решении рекуррентных соотношений.

3.  Перманенты и их свойства.

4.  Числа Рамсея.

5.  Методы линейной алгебры в теории графов.

6.  Вероятностные методы в комбинаторике.

7.  Восстановление графов.

8.  Раскраска карт.

9.  Покрытия и упаковки в теории графов.

10.  Применение теории графов в программировании

6.ВОПРОСЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ПО ДИСЦИПЛИНЕ «ДИСКРЕТНАЯ МАТЕМАТИКА»

1.  Линейные рекуррентные соотношения с постоянными коэффициентами. Возвратные последовательности.

2.  Вычисление сумм вида , s = 1, 2, 3, ... .

3.  Целочисленные функции ëxû , éxù , mod.

4.  Формула суммирования Эйлера.

5.  Основные свойства треугольника Паскаля.

6.  Использование многочленов для доказательства комбинаторных тождеств.

7.  Вычисление комбинаторных чисел на ЭВМ.

8.  Верхние и нижние оценки для чисел N (p, q, 2). Теорема Эрдеша.

9.  Некоторые применения теоремы Рамсея.

10.  Графы с цветными ребрами.

11.  Число различных графов с p вершинами.

12.  Число различных деревьев с р вершинами. Теорема Кэли. Соответствие Прюфера.

13.  Формула Эйлера для плоских графов и ее следствия.

14.  Раскрашиваемость вершин планарного графа шестью красками.

7. ВОПРОСЫ К ЭКЗАМЕНУ ПО ДИСЦИПЛИНЕ «ДИСКРЕТНАЯ МАТЕМАТИКА»

1.  Понятие множества. Примеры множеств. Способы задания множеств.

2.  Пустое множество. Равные множества. Подмножества. Примеры.

3.  Универсальное множество. Дополнение подмножества до универсального множества.

4.  Объединение, пересечение и вычитание множеств.

5.  Теоретико-множественные тождества и их применение.

6.  Кортеж. Декартово умножение множеств.

7.  Бинарные отношения между элементами множеств. Граф и график отношения. Способы задания отношений.

8.  Отношения, обратное и противоположное к данному отношению.

9.  Основные свойства отношений на множестве.

10.  Отношения эквивалентности и порядка.

11.  Отображения. Функции. Равномощные множества. Композиция отображений.

12.  Мощность множества. Счетные множества. Мощность континуума.

13.  Комбинаторные правила суммы, произведения, включений и исключений.

14.  Понятие перестановки. Число перестановок n-элементного множества.

15.  Понятие сочетания. Числа всех сочетаний из n элементов по k элементов. Основные свойства сочетаний.

16.  Понятие размещения. Число всех размещений из n элементов по k элементов.

17.  Треугольник Паскаля и его свойства. Бином Ньютона, его свойства и некоторые приложения.

18.  Метод рекуррентных соотношений (Определение и примеры).

19.  Метод последовательного вычисления элементов решения рекуррентного соотношения.

20.  Решение рекуррентных соотношений. Примеры.

21.  Линейные рекуррентные соотношения с постоянными коэффициентами.

22.  Числа Фибоначчи, их свойства и приложения.

23.  Числа Каталана. Числа Стирлинга (1-го и 2-го рода), гармонические числа.

24.  Суммы и рекуррентные соотношения. Преобразования сумм.

25.  Производящие функции.

26.  Целочисленные функции округления.

27.  Иерархия. Асимптотическая аппроксимация.

28.  Формула суммирования Эйлера-Маклорена.

29.  Графы, ориентированные графы, псевдографы, мультиграфы.

30.  Изоморфизм и гомеоморфизм графов, двудольные графы.

31.  Маршруты, пути.

32.  Матричное задание графов.

33.  Операции над графами, подграфы.

34.  Связность, компоненты связности, матрица связности, выделение компонент связности.

35.  Поиск маршрутов в графах.

36.  Деревья, свойства деревьев. Лес.

37.  Остовное дерево, минимальное остовное дерево.

38.  Эйлеровы графы и циклы.

39.  Гамильтоновы графы и циклы.

40.  Планарные графы.

41.  Правильная раскраска вершин графов.

42.  Раскраска планарных графов.

43.  Принцип Дирихле.

44.  Сущность теории Рамсея. Теорема Рамсея. Числа Рамсея.

45.  Приложения теоремы Рамсея. Теорема Ван дер Вардена.

46.  Биномиальные коэффициенты, их комбинаторный смысл.

47.  Полиномиальные коэффициенты, их комбинаторный смысл.

48.  Понятие выборки. Число k-выборок из n-множества.

49.  Понятие размещения. Число k-размещений из n-множества.

50.  Понятие перестановки. Число перестановок n-множества.

51.  Понятие сочетания. Число сочетаний из n по k.

52.  Комбинаторный смысл чисел Стирлинга первого рода.

53.  Комбинаторный смысл чисел Стирлинга второго рода.

54.  Метод включения-исключения.

55.  Формулы обращения

56.  Степень вершины графа. Теорема о сумме степеней вершин графа и ее следствие.

57.  Связные графы. Компоненты связности графа.

58.  Эйлеровы графы. Критерий эйлеровости.

59.  Планарные графы.

60.  Двудольные графы. Теорема Кенига.