A) Для приведенного отношения задайте граф геометрически.

Курсовые работы

По дискретной математике

для студентов факультета «Прикладная информатика»

Краснодар 2015

Темы курсовых работ.

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. Формулы логики предикатов. Классификация формул логики предикатов.

31. Равносильные формулы логики предикатов.

32. Проблема разрешения для общезначимости и выполнимости формул логики предикатов.

33. Основные формализации понятия алгоритма.

34. Машины Тьюринга.

35. Нормальные алгоритмы Маркова.

36. Рекурсивные функции.

Задачи для курсовых работ.

Задача 1. Изобразите геометрически множество истинности двуместного предиката Q(x,y).

0) Q(x, y)=”1/4x2 <2y”, если x, yÎ(-1,6);
1) Q(x, y)=”-4x2<2y”, если x,yÎ(-4, 8];
2) Q(x, y)=”-6x2£ 3y”,если x, y Î [-2, 7];
3) Q(x, y)=”-5x2 £ 2y”, если x, yÎ[-3,7);
4) Q(x, y)=”3x2<-2y”, если x, y Î (-2, 6);
5)Q(x, y)=”- 6x2 >3y”, если x, yÎ (-4, 5];
6) Q(x, y)=”7x2£ -3y”, если x, yÎ [-4, 5];
7) Q(x, y)=”-4x >1/ 2y”, если x, yÎ (-7,1);
8)Q(x, y)=”6x2>- 5y”, если x, y Î [-3, 4]; 9)Q(x, y)=” 8x2£ 1/6y”, если x, yÎ[-3, );

Задача 2.

0)Сколько различных шестизначных чисел можно составить из цифр: 1, 1, 1, 5, 5, 9?

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

2)Сколько всего шестизначных чисел, у каждого из которых цифра 2 встречается два раза, а цифра 3 - четыре раза?

3)Имеется 5 мест на флагштоке и 5 флагов: 2 красных и 3 белых. Сколько можно изобразить различных сигналов, если использовать все флаги одновременно?

4)Сколько различных слов можно получить, переставляя буквы в слове «молоко»? В слове «караоке»? В слове «ингредиент»?

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

6)Сколькими способами можно разделить 40 одинаковых яблок а) между 4 мальчиками; в) чтобы каждый получил, по крайней мере, 3 яблока?

7)Сколькими способами в библиотеке можно расположить на одной полке 6 экземпляров романа «Овод», 7 экземпляров сказки «Золушка» и 8 экземпляров учебника Акимова «Дискретная математика»?

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

9)В магазине ``Все для чая'' продается 7 чашек, 5 блюдец и 6 чайных ложек. Сколькими способами можно распределить посуду с разными названиями?

Задача 3. Составьте таблицу инверсий для перестановки:
0)b={5,7,3,4,2,6,1,10,11,8,9}; 1)b= 7,4,3,1,5,6,2,8,11,10,9}; 2)b= 3,2,1,4,5,10,7,11,9,6,8}; 3)b= 10,11,8,7,5,6,4,3,9,1,2}; 4)b{4,5,3,1,2,8,7,6,9,11,10};	5)b= 11,2,9,8,5,6,7,4,3,10,1}; 6)b={6,10,3,4,5,1,8,7,9,2,11}; 7)b={8,9,5,4,3,6,7,1,2,10,11}; 8)b= 9,7,10,4,11,6,2,8,1,3,5}; 9)b= 4,7,6,9,11,10,5,8,3,1,2}.
Задача 4. Составьте перестановку по заданной таблице инверсий:
0)d = {8,6,7,3,6,4,1,3,0,0,0}; 1)d = {7,7,4,2,2,2,2,0,0,0,0}; 2)d = {5,1,7,6,2,0,2,1,1,0,0}; 3)d = {10,1,7,6,3,3,3,2,1,1,0}; 4)d = {3,3,2,0,0,2,1,0,0,1,0};	5)d = {9,9,7,6,4,4,3,2,2,0,0}; 6)d = {2,1,0,0,0,4,1,3,2,0,0}; 7)d = {3,5,2,1,1,1,0,0,2,1,0}; 8)d = {6,4,2,2,0,0,0,2,2,0,0}; 9)d = {4,2,6,5,1,2,8,9,2,3,0}.

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

Задача 5.

0)В почтовом отделении имеются открытки 3 видов. Сколькими способами можно купить набор из 6 открыток?

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

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

3)Сколько имеется костей в обычной игре "домино"?

4)Сколько вариантов строения ДНК Шубуршунчика обворожительного может быть, если длина цепи 1000 нуклеотидов (нуклеотиды 4 видов: А, Т, Г, Ц)?

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

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

7)Как велико число отличных друг от друга результатов бросаний двух одинаковых кубиков?

8)Сколькими способами можно выбрать 7 крупных апельсинов из 2 имеющихся на рынке сортов?

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

Задача 6. Записать все сочетания из элементов множества А по два элемента без повторений: 0) А = {2,7,9}; 1) A = {x,y,z}; 2) A = {a,b,c}; 3) A = {X,Y,Z}; 4) А = {+,-,×}; 5) А = {!,#,%}; 6) А = {α,β,λ} 7) А = {←,↑,→}; 8) А = {В, П, МР}; 0) A = {Q,W,E}.

Задача 7. Сколько существует N-битовых строк, содержащих А нулей и К единиц, если: 0) N=8; А=3, К=5; 1) N=8; А=2,К=6; 2) N=8; А=4, К=4; 3) N=9; А=2,К=7; 4) N=9; А=3, К=6; 5) N=9; А=4, К=5; 6) N=10; А=3, К=7; 7) N=10; А=4, К=6; 8) N=10; А=2, К=8; 9) N=10; А=5, К=5.

Задача 8.Решите задачи по вычислению валентности вершин графа:

0)В одной компании из 7 человек: Саша дружит с Леной и Алешей, Надя с Колей, Ваня с Сашей и Колей. Какова валентность вершин графа?

1)В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?

2)В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 - по 4 друга, а 10 - по 5 друзей?

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

4)- У меня зазвонил телефон. - Кто говорит? - Слон... А потом позвонил Крокодил... А потом позвонили Зайчатки... А потом позвонили Мартышки... А потом позвонил Медведь... А потом позвонили Цапли... Итак, у Слона, Крокодила, Зайчаток, Мартышек, Медведя, Цапель и у меня установлены телефоны. Каждые два телефонных аппарата соединены проводом. Как сосчитать, сколько для этого понадобилось проводов? Указание: заметьте, каждый провод соединяет два аппарата.

5)У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?

6)Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

7)Джон, приехав из Диснейленда, рассказывал, что там на заколдованном озере имеются 7 островов, с каждого из которых ведет 1, 3 или 5 мостов. Верно ли, что хотя бы один из этих мостов обязательно выходит на берег озера?

8)Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался, ровно с тремя другими?

9)Резидент одной иностранной разведки сообщил в центр о готовящемся подписании ряда двусторонних соглашений между пятнадцатью бывшими республиками СССР. Согласно его донесению, каждая из них заключит договор ровно с тремя другими. Заслуживает ли резидент доверия? Указание: подсчитайте двумя способами число подписей под всеми двусторонними соглашениями. И подумайте, может ли оно быть нечётным?

Задача 9. Граф G(V,E): V={a, b, c, d, e}, задан как алгебраическая система.

a) Для приведенного отношения задайте граф геометрически.