WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 2 | 3 ||

A C D B; B A B D.

AC B;

X Z;

Y W ;

Y X Z ;

12.

X Z W.

W Y Z;

XW XY Z ;

B D A; B D;

13. A CD; C D;

C B D;

A B.

ACD BD;

C D;

C B D;

14.

A B A C.

A C D;

A C B;

YZ W ;

X Z Z W ;

XY YZW ;

15. YZ W ;

X Z W ;

Y Z.

Z Y ;

A C D;

A C;

AB D;

16. A B;

B A C;

D.

C D;

AC BC D; A D;

17. A B C D; A B;

B C; C D.

X Z W ;

X Y ;

X ZW YW ;

18. Y Z;

Y X Z;

W.

W Z;

A B C;

A B;

AD C;

19. A D;

D A B;

A C.

B C;

X Z Y W ;

X Y ;

20. XY Z W YW ;

Z W.

Z W ;

W X ;

Y Z ;

Y X W ;

21.

X Z W.

Z Y X ;

ZW YXW ;

C D B A D;

A D;

A C D;

22.

B C B A.

AD B;

C B A;

D B A;

D B;

A DC;

23. D C;

C D B;

A.

B A;

ZW X X Y ;

ZXW YW ;

24. Y Z ;

Y X Z ;

W.

W Z;

Y Z X W ;

Y W ;

25. YW XZ XW ;

X Z.

Y W ;

D C A;

D C;

DB A;

26. D B;

B D C;

A.

C A;

Y Z W ;

X Y ;

Y ZW XW ;

27. Z X ;

X Y Z ;

W.

W Z;

Y Z ;

X W ;

X Y Z ;

28.

Y Z W.

W X Z ;

YW XY Z;

BCD AD;

C D;

C A D;

29.

B A B C.

B C D;

B C A;

X Z Y W ;

X Y ;

30. XY Z W YW ;

Z W.

Z W ;

5.2. Контрольная работа по комбинаторике Задача 1. Дано множество U из n элементов. Каким числом способов в нем можно выбрать три подмножества A, B, C так, чтобы выполнялись заданные условия:

1) n 7, | A B | 1, | B ( A C) | 4;

2) n 9, | ( A B) C | 2, | A (B C) | 5 ;

3) n 8, | A B | 6, | A (B C) | 5 ;

4) n 7, | A B C | 5, | A B | 4;

5) n 6, | A B | 3, | B ( AC) | 2;

6) n 7, | A (B C) | 2, | (B C) A|1;

7) n 9, | ( A B) C | 8, | A (B C) |1;

8) n 7, | A B | 2, | C ( A B) |1;

9) n 9, | A (B C) | 6,| C ( A B) | 2;

10) n 8, | ( A B) C | 6, | C ( A B) | 4 ;

11) n 8, | A B | 2, | A B C | 4 ;

12) n 7, | ( A B) C |1, | B ( AC) | 3;

13) n 7, | A B | 5, | A B C | 3 ;

14) n 8, | A B | 6, | (B C) A|1;

15) n 5, | ( A B) C | 3, | C ( A B) |1;

16) n 6, | A B | 4, | ( A B) C |1;

17) n 8, | A (B C) | 5, | (B C) A|1;

18) n 7, | ( A B) C | 4, | C ( A B) |1;

19) n 9, | A B | 3, | (B C) A| 5;

20) n 6, | A B | 3, | B ( A C) | 2 ;

21) n 7, | ( A B) C | 6, | C ( A B) | 3;

22) n 8, | A (B C) | 5, | B ( A C) | 2 ;

23) n 7, | ( A B) C | 6, | A (B C) | 3;

24) n 9, | A B | 4, | A (B C) | 4 ;

25) n 7, | A B | 5, | ( A C) B |1;

26) n 6, | ( A B) C | 4, | ( AC) B | 2 ;

27) n 8, | A B C | 4, | ( A B) C |1;

28) n 8, | A B | 5, | C ( A B) | 2 ;

29) n 8, | ( A B) C | 7, | C B | 6;

30) n 7, | A B C | 3, | A (B C) | 2 Задача 2. На одной из кафедр университета работают S человек, среди которых T человек не знают ни одного иностранного языка. A человек знают английский, N – немецкий, F – французский. AN знают английский и немецкий, AF – английский и французский, NF – немецкий и французский, ANF знают все три языка. По заданным в таблице условиям восстановить недостающую информацию.

№ S A N F AN AF NF ANF T 1. 17 11 6 5 4 3 2 1 2. 16 9 7 4 4 5 2 3. 17 8 10 6 4 4 3 4. 20 11 8 5 7 3 4 5. 10 7 4 5 4 3 3 6. 17 12 9 7 8 5 4 7. 21 11 6 6 5 3 2 8. 26 14 11 5 4 3 2 9. 19 13 9 5 5 3 3 1 10. 17 9 6 6 4 4 2 11. 16 12 9 6 4 3 3 12. 17 13 6 4 6 3 2 13. 14 9 7 7 5 3 2 14. 18 15 8 6 7 4 3 15. 20 12 8 5 5 3 1 16. 23 14 8 7 4 4 2 17. 23 15 8 9 3 4 5 2 18. 14 7 8 4 5 4 3 19. 20 9 6 4 3 2 1 20. 25 11 14 10 6 4 2 21. 27 17 13 9 6 5 4 22. 30 18 14 9 9 5 4 23. 26 15 13 11 8 5 3 24. 28 17 10 11 5 7 4 25. 30 19 16 12 8 7 5 26. 35 20 16 15 10 8 9 6 27. 20 17 13 8 5 4 1 28. 39 17 13 8 5 6 2 29. 37 22 16 8 5 4 3 30. 33 19 18 11 9 7 2 Задача 3. Рассматриваются слова в алфавите a1,a2,,aq. Через ni обозначается число вхождений буквы ai в слово. Требуется подсчитать число слов длины n, удовлетворяющих данным условиям.

1. q 3, n 9, n1 6 ;

2. q 4, n 7, n1 2n2 ;

3. q 4, n 7, n1 n2 n3 n4 ;

4. q 5, n 8, n1 n2 n3 n4 ;

5. q 3, n 9, n1 2, n2 n3 ;

6. q 5, n 7, n1 n2 3, n3 2 ;

7. q 3, n 7, n1 n2 ;

8. q 3, n 10, n1 n2 n3 ;

9. q 3, n 7, n1 n2 n3 ;

10. q 4, n 6, n1 n2 n3 ;

11. q 4, n 5, n1 n2 ;

12. q 3, n 8, n1 n2 6 ;

13. q 3, n 8, 2 n1 6 ;

14. q 3, n 6, n1 n2 n3 ;

15. q 4, n 7, n1 2, n2 n3 4 ;

16. q 5, n 8, n1 4, n2 3;

17. q 4, n 6, n1 n2 n3 n4;

18. q 4, n 8, n1 n2 3, n3 2;

19. q 4, n 9, n1 n2 2;

20. q 5, n 6, n1 n2 ;

21. q 5, n 6, n1 n2 n3 n4 ;

22. q 4, n 8, n1 2, n2 3;

23. q 5, n 7, n1 2, n2 n3 n4 3;

24. q 4, n 8, n1 n2 4, n3 1;

25. q 5, n 7, n1 n2 n3 ;

26. q 4, n 7, n1 n2 4 ;

27. q 5, n 6, n1 n2 n3 n4 n5 ;

28. q 5, n 7, n1 n2 n3 n4 4;

29. q 4, n 8, 2n1 n2 6 ;

30. q 3, n 9, n1 n2 n3.

Задача 4. Сколькими способами можно переставить буквы слова:

1. «здание», чтобы гласные шли в алфавитном порядке;

2. «перешеек», чтобы четыре буквы «е» не шли подряд;

3. «ежевика», чтобы «и» шла непосредственно после «к»;

4. «тарантас», чтобы две буквы «а» не шли подряд;

5. «каракули», чтобы никакие две гласные не стояли рядом;

6. «группоид», чтобы не менялся порядок гласных букв;

7. «перемена», чтобы три буквы «е» не шли подряд;

8. «столовая», чтобы никакие две гласные не стояли рядом;

9. «фигура», чтобы согласные шли в алфавитном порядке;

10. «баобаб», чтобы три буквы «б» не шли подряд;

11. «тетрадь», чтобы «ь» шла непосредственно после «р»;

12. «колокола», чтобы две буквы «о» не шли подряд;

13. «симфония», чтобы никакие две согласные не стояли рядом;

14. «симметрия», чтобы не менялся порядок гласных букв;

15. «кукуруза», чтобы две буквы «у» не шли подряд;

16. «алгебра», чтобы «р» шла непосредственно после «а»;

17. «автобус», чтобы гласные шли в алфавитном порядке;

18. «карандаш», чтобы две буквы «а» не шли подряд;

19. «решение», чтобы «е» шла непосредственно после «н»;

20. «множество», чтобы согласные шли в алфавитном порядке;

21. «апелляция», чтобы «я» шла непосредственно после «л»;

22. «гиппопотам», чтобы гласные шли в алфавитном порядке;

23. «баллада», чтобы две буквы «а» не шли подряд;

24. «интеллект», чтобы «л» шла непосредственно после «е»;

25. «идиллия», чтобы три буквы «и» не шли подряд;

26. «пассажир», чтобы согласные шли в алфавитном порядке;

27. «диаграмма», чтобы «м» шла непосредственно после «а»;

28. «оперетта», чтобы не менялся порядок гласных букв;

29. «гипербола», чтобы гласные шли в алфавитном порядке;

30. «баррикада», чтобы две буквы «а» не шли подряд Литература 1. Алексеев В.Е., Киселева Л.Г., Смирнова Т.Г. Сборник задач по дискретной математике. - Методическая разработка, Нижний Новгород, 2007. - 48 с.

2. Андерсон Д.А. Дискретная математика и комбинаторика. : Пер. с англ. - Издательский дом "Вильямс", 2004. - 960 с.

3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. - М.: ФИЗМАТЛИТ, 2006. - 416 с.

4. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, 1990. - 384 с.

5. Яблонский С.В. Введение в дискретную математику. - М.: Наука, 2000. - 384 с.

Оглавление 1. Множества и операции над ними……………………………………………..2. Бинарные отношения…………………………………………………………..3. Элементы комбинаторики…………………………………………………….4. Теория графов………………………………………………………………….5. Контрольные задания……… ……………………………………………….5.1. Контрольная работа по теории множеств……………...……………5.2. Контрольная работа по комбинаторике……………...……………...Литература………………………………………………………….……………..Владимир Евгеньевич Алексеев Лариса Георгиевна Киселева Татьяна Геннадьевна Смирнова СБОРНИК ЗАДАЧ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ Задачник Государственное образовательное учреждение высшего профессионального образования «Нижегородский государственный университет им. Н.И. Лобачевского» 603950, Нижний Новгород, пр. Гагарина, 23.

Подписано в печать Формат 60 84 1/16.

Бумага офсетная. Печать офсетная. Гарнитура Таймс.

Усл.-печ. л. Уч.-изд. л.

Заказ № Тираж 500 экз.

Отпечатано в типографии Нижегородского госуниверситета им. Н.И. Лобачевского 603600, г. Нижний Новгород, ул. Большая Покровская, Лицензия ПД № 18-0099 от 14.05.

Pages:     | 1 |   ...   | 2 | 3 ||










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.