новая папка 1 / 310590
.pdf5.9.Сколько различных слов можно получить перестановкой слова «логарифм»? Ответьте на данный вопрос при условии, что второе, четвертое и шестое места заняты согласными.
5.10.Сколько различных слов можно получить перестановкой слова «салага»? Ответьте на данный вопрос при условии, что буква «а» идет непосредственно после «с».
Задание 6. Решить задачи, используя формулы комбинаторики:
6.1.В классе 7 человек успешно занимаются математикой. Сколько существует способов выбрать двоих из них для участи в олимпиаде?
6.2.Учащимся дали список из 20 книг, 10 из которых рекомендуется прочитать. Сколькими способами ученик может выбрать книги для чтения?
6.3.Сколькими способами можно выбрать троих дежурных из группы туристов, состоящей из 12 человек?
6.4.Из точки плоскости провели 5 лучей. Сколько углов при этом получилось?
6.5.Сколькими способами можно выбрать 5 карт красной масти из колоды в 36 карт?
6.6.Сколькими способами можно выбрать 3 дамы из колоды в 36 карт?
6.7.Сколькими способами можно выбрать двух валетов из колоды в 36
карт?
6.8.Сколькими способами можно выбрать 3 учебника по математике из 10, имеющихся в библиотеке?
6.9.Сколькими способами можно выбрать четверых делегатов на профсоюзную конференцию из 20 студентов?
6.10. Сколькими способами можно выбрать семь костяшек домино?
Задание 7. Решить задачи, используя формулы комбинаторики:
7.1.На плоскости отметили 9 точек, никакие 3 из которых не лежат на одной прямой. Сколькими способами можно построить 3 треугольника с вершинами в этих точках?
7.2.В отделе, в котором работают 9 сотрудников, надо отправить 3 человека в командировку. Сколькими способами это можно сделать, если а) начальник отдела должен ехать в командировку; б) начальник отдела должен остаться?
7.3.Для игры в боулинг компания из 12 человек должна поделиться на 4
команды. Сколькими способами это можно сделать?
7.4.На окружности отметили 10 точек. Сколькими способами можно построить 2 четырехугольника с вершинами в этих точках при условии, что каждые 4 точки соединяют в порядке следования против часовой стрелки, четырехугольники не имеют общих вершин?
7.5.В проектном бюро работают 10 инженеров и 4 ведущих инженера. В командировку нужно послать четырех человек, двое из которых – ведущих. Сколькими способами это можно сделать?
7.6.В классе 13 мальчиков и 11 девочек. Сколькими способами можно сформировать команду из 4 девочек и 3 мальчиков для дежурства по школе?
7.7.Для игры в боулинг компания из 8 человек должна поделиться на 2 команды. Сколькими способами это можно сделать?
7.8.На окружности отметили 6 точек. Сколькими способами можно построить 2 треугольника с вершинами в этих точках при условии, что треугольники не имеют общих вершин?
7.9. В классе 10 мальчиков и 11 девочек. Сколькими способами можно сформировать команду из 3 девочек и 3 мальчиков для участия в веселых стартах?
7.10. В отделе, в котором работают 9 сотрудников, надо отправить в командировку 3 человека в город А и 2 человека в город В. Сколькими способами это можно сделать?
Задание 8. Используя круги Эйлера решить следующие задачи:
8.1. У фирмы есть 100 предприятий, причем каждое предприятие выпускает хотя бы одну продукцию вида А, В или С. Продукцию всех трех видов выпускают 10 предприятий, продукцию вида А и В- 18 предприятий,
продукцию А и С-15 предприятий, продукцию вида В и С- 21 предприятие.
Число предприятий, выпускающих продукцию вида А, равно числу предприятий, выпускающих продукцию вида В, и равно числу предприятий,
выпускающих продукцию вида С. Найти число предприятий, выпускающих только продукцию вида А.
8.2.В студенческой группе 20 человек. Из них 10 имеют оценку
«девять» по английскому языку, 8- по математике, 7- по физике, 4- по английскому и языку и по математике, 5- по английскому языку и по физике, 4-
по математике и по физике, 3- по английскому языку, по математике и по физике. Сколько студентов в группе не имеют оценок «девять»?
8.3. В классе 20 человек. На экзаменах по истории, математике и литературе 10 учеников не получили ни одной оценки «9», 6 учеников получили «9» по истории, 5- по математике и 4- по литературе, 2- по истории и по математике, 2- по истории и литературе, 1- по математике и литературе.
Сколько учеников получили «9» по всем предметам?
8.4.В спортивном лагере 100 человек, занимающихся плаванием,
легкой атлетикой и лыжами. Из них 10 занимаются и плаванием, и легкой
атлетикой, и лыжами, 18плаванием и легкой атлетикой, 15плаванием и лыжами, 21легкой атлетикой и лыжами. Число спортсменов, занимающихся плаванием, равно числу спортсменов, занимающихся легкой атлетикой, и равно числу спортсменов, занимающихся лыжами. Найти это число.
8.5.Группе студентов предложены спецкурсы по мультимедиа,
искусственному интеллекту и имитационному моделированию. 22 студента записались на спецкурс по мультимедиа, 18на спецкурс по искусственному интеллекту,10на спецкурс по имитационному моделированию, 8- на спецкурсы по мультимедиа и искусственному интеллекту, 15на спецкурс по мультимедиа и имитационному моделированию,7 - на спецкурс по искусственному интеллекту и имитационному моделированию. 5 студентов записались на все три спецкурса. Сколько студентов в группе.
8.6.Во время сессии 24 студента группы должны сдать три зачета:
по физике, математике и программированию. 20 студентов сдали зачет по физике, 10по математике, 5- по программированию, 7- по физике и математике, 3- по физике и по программированию, 2- по математике и программированию. Сколько студентов сдали все три зачета?
8.7.В группе переводчиков 15 человек владеют английским языком, 19французским, 8- немецким. 9 переводчиков владеют английским и французским языками, 7- английским и немецким, 6- французским и немецким. 4 переводчика владеют всеми тремя языками. Сколько переводчиков в группе?
8.8.Опрос группы студентов показал, что 70% из них любят ходить в кино, 60%- в театр, 30%- на концерты. В кино и театр ходят 40%
студентов, в кино и на концерты20%, в театры и концерты10%. Сколько
студентов (в %) ходят в кино, театр и на концерт?
8.9.В группе 20 студентов. После медицинского осмотра 14
студентов были направлены на дополнительное обследование к терапевту, 6- к
окулисту, 5- к ортопеду. К терапевту и окулисту были направлены 3 студента, к
терапевту и ортопеду-3, к окулисту и ортопеду-2. Сколько студентов было направлено к терапевту, окулисту ортопеду?
8.10. При обследовании рынка спроса инспектор указал в опросном листе следующие данные. Из 1000 опрошенных 811 покупают жевательную резинку « Dirol», 752- «Orbit», 418- «Stimorol», 570- « Dirol» и «Orbit», 356- « Dirol» и «Stimorol», 348- «Orbit» и «Stimorol», 297все виды жевательной резинки. Не ошибся ли инспектор?
Задание 9. Нарисовать диаграммы ЭйлераВенна для следующих множеств:
9.1.А U (В∩С);
9.2.А∩ (В U С);
9.3.(А\В)∩С;
9.4.(А\В) U С;
9.5.А U В U (А U В);
9.6В U (С(А U В));
9.7.А∩(В U С );
9.8.А∩В U А∩В;
9.9.С\А U В;
9.10.А U В∩С;
Задание 10. Определить, имеют ли место следующие равносильности построив таблицу истинности и упростив выражения.
10.1.ВvС АvСvАvВv АВ= С А v С В;
10.2.ВСvАВСvАСАВvСvАС= А;
10.3.АВvАВСvАВСАВС vАВС vАВС=АВС;
10.4.АВС v АВС vАВС v АВС=С;
10.5.АВ v АВС v АВС vАС=А;
10.6.Х→Y→Z=X→Z→X→Z;
10.7.А v ВАvСvВАvС=АВ;
10.8.АВvАВСvВСvССvАСvАВС=ВvАС;
10.9.ВvСvАvСvАВ=СаvСВ;
10.10.АВvАВСvВСvС=ВvАС;
Задание 11. Выполнить задания своего варианта из раздела «Основы теории графов».
11.1 – 11.8. а) Задать приведенный в таблице ориентированный граф:
1)матрицей смежности;
2)матрицей инцидентности;
3)списком ребер;
4)структурой смежности;
5)построить матрицу достижимости;
6)построить матрицу контрдостижимости;
7)найти компоненты сильной связности.
б) выполнить задания 1-7 для соответствующего неориентированного
графа
|
11.1 |
|
|
|
11.2 |
|
11.3 |
|
|
11.4 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
v1 |
u1 |
v2 |
|
v1 |
u1 |
v2 |
v1 |
u1 |
v2 |
v1 |
u1 |
v2 |
|
|
|
|
|
u4 |
u2 |
|
|
|
|
|
u5 |
u2 |
|
|
|
u6 |
|
u5 |
|
u2 |
u2 |
u3 |
u4 |
|
|
|
|
|
|
|
|||||||
|
|
|
u4 |
|
|
u3v3 |
|
u4 |
u3 |
|
|
v3 |
v4 |
u3 |
v3 |
|
|
|
|
|
|
u6 |
|||
|
v5 |
u5 |
v4 |
v4 |
|
v3 |
v5 |
|
v4 |
|||
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11.5 |
|
|
|
11.6 |
|
|
11.7 |
|
11.8 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
v1 |
u1 |
v2 |
|
v1 |
u1 |
v2 |
v1 |
u1 |
v2 |
v1 |
u1 |
v2 |
|
|
|
|
|
u4 |
u2 |
|
|
|
|
|
u5 |
u2 |
|
|
|
u6 |
|
u5 |
|
u2 |
u2 |
u3 |
u4 |
|
|
|
|
|
|
|
|||||||
|
|
|
u4 |
|
|
u3v3 |
|
u4 |
u3 |
|
|
v3 |
v4 |
u3 |
v3 |
|
|
|
|
|
|
u6 |
|||
|
v5 |
u5 |
v4 |
v4 |
|
v3 |
v5 |
|
v4 |
|||
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
11.9 – 11.10. а) Ориентированный граф задан матрицей инцидентности.
1)ориентированный граф задать графически;
2)построенный граф задать матрицей смежности;
3)построенный граф задать списком ребер;
4)построенный граф задать структурой смежности;
5)построить матрицу достижимости;
6)построить матрицу контрдостижимости;
7)найти компоненты сильной связности.
б) выполнить задания 1-7 для соответствующего неориентированного
графа |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
11.9 |
|
|
|
|
|
|
|
|
11.10 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
u1 |
u2 |
u3 u4 |
u5 |
u6 |
|
|
|
u1 |
u2 |
u3 |
u4 |
u5 |
||||
v1 |
1 0 |
0 |
1 |
0 |
1 |
v1 |
1 0 |
1 |
0 |
1 |
||||||||
v2 |
|
1 |
|
1 0 |
0 |
0 |
0 |
|
v2 |
|
1 |
1 0 |
1 |
0 |
|
|||
|
|
|
|
|
||||||||||||||
v |
|
0 |
|
1 |
|
1 1 |
0 |
0 |
|
v |
|
0 |
1 |
1 0 |
0 |
|
||
3 |
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
v4 |
0 0 |
|
1 |
0 |
1 |
0 |
|
|
0 |
0 |
0 |
1 |
1 |
|
||||
|
v4 |
|
||||||||||||||||
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
v5 |
0 |
0 |
|
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
|||
Литература
1.Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов/ Ф.А. Новиков. – Спб.: Питер, 2000.-304 с.
2.Капитонова и др. Лекции по дискретной математике. СПб.:БХВПетербург, 2004.- 624 с.
3.Судоплатов С.В. Дискретная математика: Учебник для вузов/ С.В. Судоплатов, Е.В. Овчинникова; 2-е изд., перераб.- М.: Инфра-М, 2007; Новосибирск:НГТУ, 2007.-255 с.