ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
подмножеств Мощность множества Количество k подмножеств в разбиении 2 3 N 1 2 3 : : n 3. Реализовать алгоритм порождения всех упорядоченных разбиений элементного множества. 4. Написать программу, вычисляющую количество всех упорядоченных разбиений элементного множества. Результат представить в виде таблицы (табл. 2.8 ). 5. Реализовать алгоритм порождения всех разбиений элементного множества на k подмножеств. 6. Написать программу, формирующую таблицу Т (табл. 2.9), в которой строки соответствуют количеству n элементов в множестве, а столбцы — количеству k подмножеств в разбиении. Клетка таблицы 112 Т при k ≤ n должна содержать количество всех разбиений элементного множества на k подмножества при k > n клетка таблицы Т не заполняется. Таблица 2.8 Количество упорядоченных разбиений Мощность множества Количество упорядоченных разбиений 1 2 3 : : n Таблица 2.9 Количество разбиений элементного множества на k подмножеств Мощность множества Количество k подмножеств в разбиении 2 3 N 1 2 3 : : n 7. Реализовать алгоритм порождения всех разбиений элементного множества. 8. Написать программу, вычисляющую количество всех разбиений элементного множества. Результат представить в виде таблицы табл. 2.10). Таблица 2.10 Количество разбиений Мощность множества Количество разбиений 1 2 3 : : n 113 Практическое занятие 2.3 Задачи выбора Цель занятия приобрести практические навыки в использовании алгоритмов порождения комбинаторных объектов при проектировании алгоритмов решения задач выбора. Задания 1. Ознакомиться с задачей (см. варианты заданий. 2. Определить класс комбинаторных объектов, содержащих решение задачи (траекторию задачи. 3. Определить, что в задаче является функционалом и способ его вычисления. Определить способ распознавания решения по значению функционала. Реализовать алгоритм решения задачи. 6. Подготовить тестовые данные и решить задачу. Варианты заданий 1. Имеется конечное множество исполнителей {х 1 ,...,х n }, каждый из которых может выполнять некоторые из работ {у 1 ,...,у n }. Для каждого исполнителя задано множество работ, которые он может выполнять. Нужно распределить исполнителей по работам, те. назначить по одному исполнителю на каждую работу, так, чтобы выполнить все работы. Найти всевозможные распределения исполнителей по работам. 2. Числа из заданного девятиэлементного множества разместить в числовом колесе (рис) так, чтобы одно число было в центре колеса, остальные — у концов каждого диаметра, и чтобы суммы чисел каждого ряда были бы одинаковыми. Рис. Числовое колесо 114 3. Определить, существуют ли решения в заданном элементном множестве X целых чисел следующего уравнения a 1 x 1 + a 2 x 2 + …+ a n x n = b, n, b и a 1 ,a 2 ,…,a n — заданы, x i X. 4. На прямой расположены n равноотстоящих друг от друга узлов. Можно ли в узлах разместить n предметов из элементного множества так, чтобы центр тяжести находился водном из узлов. Вес каждого предмета задан. 5. Задана точка с натуральными координатами (x,y) на целочисленной решетке. Найти монотонную траекторию минимальной стоимости, ведущую изначала координат в заданную точку. На каждом шаге монотонной траектории можно двигаться только вправо или вверх к соседней точке. Стоимость возможных шагов из каждой точки решетки задана. 6. Есть n станков. Каждый из станков делает различные операции какие заданы. При обработке детали необходимо выполнить k заданных операций. Найти минимальное множество станков, требуемых для обработки детали. 7. Заданы n 2 попарно различных целых чисел. Разместить их, если можно, в матрице n n так, чтобы суммы строк, столбцов и диагоналей были одинаковыми. Определить количество таких размещений. 8. Найти все решения уравнения x 1 + x 2 + … + x n = b в натуральных числах, n и b — заданы. 9. Имеется n исполнителей, каждый из которых может выполнять некоторые из n работ. Для каждого исполнителя задано множество работ, которые он может выполнять, и стоимость выполнения каждой работы. Нужно распределить исполнителей по работам, те. назначить по одному исполнителю на каждую работу, так, чтобы выполнить все работы, минимизируя затраты. 10. Задана точка в узле целочисленной решетке размером n n. Расположить всеми возможными способами k точек в узлах решетки так, чтобы расстояние от каждой до заданной было одинаковым. 11. Необходимо перевести n тонн груза. Имеется k самолетов грузоподъемностью тонн, s 1 + s 2 + … + s k > n. Стоимость рейса c 1 , c 2 , …, c k руб. не зависит от массы груза, перевозимого самолетом. Найти оптимальное множество самолетов для перевозки груза. 12. Задано множество предметов. Для каждого предмета известен его вес. Можно ли разделить предметы на две равные повесу части. 13. В матрице n m целых чисел встречаются нули. Можно ли перестановкой строк добиться того, чтобы нули в каждом столбце занимали только самые нижние позиции Получить все такие матрицы. 115 14. Имеется n различных предметов. Известны масса каждого предмета и его стоимость. Определить, какие предметы надо положить в рюкзак, чтобы масса не превышала заданной, а общая стоимость была максимальна. 15. Каждая из n деталей последовательно обрабатывается на m станках (сначала нам, затем нами т.д.). Для каждой детали известно время обработки на каждом станке. Определить, в какой последовательности необходимо обрабатывать детали, чтобы время обработки всех деталей было минимальным. 16. Найти все решения в (числах следующего неравенства a 1 x 1 + a 2 x 2 + …+ a n x n a n+1 x n+1 + a n+2 x n+2 + …+ a m x m , n, m и a 1 , a 2 ,…, a m — заданы. 17. Задана целочисленная матрица размером n m. Выбрать минимальное количество строк матрицы, таких, что сумма элементов каждого столбца была бы больше заданного числа. 18. Имеется n станков и n деталей. Каждую деталь можно обработать на любом станке, но время обработки детали на одном станке может отличаться от времени ее обработки на другом. Нужно разместить детали по станкам так, чтобы суммарное время работы было наименьшим. 19. Заданы множества A и B, причем B = {x | x A}. Подмножество множества B называется покрытием множества A, если объединение всех его элементов равно множеству А. Найти все минимальные по мощности покрытия множества А, составленные из элементов множества. Необходимо перевести n тонн груза. Имеется k самолетов грузоподъемностью тонн, k i i n s 1 . Стоимость перевозки самолетами тонны груза составляет c 1 , c 2 ,…, c k руб. Найти оптимальное множество самолетов для перевозки груза. 116 Контрольные вопросы и задания 1. Что называется комбинаторным объектом 2. В чем заключается правило произведения Для чего, когда и как его применять 3. В чем заключается метод поиска с возвращением 4. Изобразите общий рекурсивный алгоритм поиска с возвращением в виде блок-схемы. 5. Изобразите общий итеративный алгоритм поиска с возвращением в виде блок-схемы. 6. Докажите теорему о количестве подмножеств элементного множества. Опишите алгоритм порождения подмножеств. Можете ли вы предложить другие алгоритмы порождения подмножеств 8. Дайте определение перестановки. 9. Докажите теорему о количестве перестановок элементного множества. Опишите алгоритм порождения перестановок. Предложите итеративный алгоритм порождения перестановок, используя метод поиска с возвращением. 11. Дайте определение размещению. 12. Докажите теорему о количестве размещений элементного множества по k местам. 13. Опишите алгоритм порождения размещений. Предложите итеративный алгоритм порождения размещений, используя метод поиска с возвращением. 14. Дайте определение размещению с повторениями. 15. Докажите теорему о количестве размещений с повторениями элементного множества по k местам. 16. Опишите алгоритм порождения размещений с повторениями. Предложите итеративный алгоритм порождения размещений с повторениями, используя метод поиска с возвращением. 17. Дайте определение сочетанию. 18. Докажите теорему о количестве сочетаний из n по k. 19. Опишите алгоритм порождения сочетаний. Предложите итеративный алгоритм порождения сочетаний, используя метод поиска с возвращением. Предложите алгоритм порождения подмножеств в порядке увеличения (уменьшения) мощности. 21. Дайте определение мультимножеству, мощности мультимножества, кратности элемента. 117 22. Предложите способы хранения мультимножества в памяти ЭВМ. 23. Как реализовать операцию разности мультимножеств? 24. Дайте определение перестановки с повторениями. 25. Докажите теорему о количестве перестановок с повторениями. 26. Опишите алгоритм порождения перестановок с повторениями. 27. Дайте определение сочетания с повторениями. 28. Докажите теорему о количестве сочетаний с повторениями из n элементов по k. 29. Опишите алгоритм порождения сочетаний с повторениями. 30. Предложите алгоритм порождения сочетаний с повторениями исходя из доказательства теоремы о количестве сочетаний с повторениями из n элементов по k. 31. Дайте определение упорядоченному разбиению. 32. Докажите теорему о количестве упорядоченных разбиений элементного множества на k подмножеств с мощностями (n 1 ,n 2 ,…,n k ). 33. Опишите алгоритм порождения упорядоченных разбиений элементного множества на k подмножеств с мощностями (n 1 ,n 2 ,…,n k ). 34. Докажите теорему о количестве упорядоченных разбиений элементного множества на k подмножеств с мощностями {n 1 ,n 2 ,…,n k }. 35. Опишите алгоритм порождения упорядоченных разбиений элементного множества на k подмножеств с мощностями {n 1 ,n 2 ,…,n k }. 36. Дайте определение композиции натурального числа n из k частей с ограничением n i > 0. 37. Докажите теорему о количестве композиций натурального числа n из k частей с ограничением n i > 0. 38. Как можно порождать композиции натурального числа n из k частей с ограничением n i > 0? Приведите алгоритмы порождения. 39. Докажите теорему о количестве всех упорядоченных разбиений элементного множества на k подмножеств. 40. Опишите алгоритм порождения всех упорядоченных разбиений элементного множества на k подмножеств. 41. Докажите теорему о количестве всех упорядоченных разбиений элементного множества. 42. Опишите алгоритм порождения всех упорядоченных разбиений элементного множества. 43. Дайте определение разбиению множества. Чем оно отличается от упорядоченного разбиения 44. Докажите теорему о количестве разбиений элементного множества на k подмножеств с мощностями {n 1 ,n 2 ,…,n k }. 45. Опишите алгоритм порождения разбиений элементного множества на k подмножеств с мощностями {n 1 ,n 2 ,…,n k }. 118 46. Докажите теорему о количестве разбиений элементного множества на k подмножеств. 47. Используя литературу, определите, как можно вычислить количество разбиений элементного множества на k подмножеств, как называется это число 48. Дайте определение разбиению натурального числа n на k частей. 49. Опишите алгоритм порождения разбиений натурального числа n на k частей. 50. Опишите алгоритм порождения всех разбиений элементного множества на k подмножеств. 51. Докажите теорему о количестве всех разбиений элементного множества. 52. Используя литературу, определите, как можно вычислить количество всех разбиений элементного множества, как называется это число 53. Опишите алгоритм порождения всех разбиений элементного множества. 54. Какие задачи относятся к задачам выбора Что характерно для задач выбора 55. Что называют траекториями задачи выбора 56. Что называют функционалом траектории, зачем он нужен 57. В чем заключается проектирование алгоритма решения задачи выбора с использованием алгоритмов порождения комбинаторных объектов. Как преобразовать алгоритм порождения комбинаторных объектов в алгоритм решения задачи выбора 119 3. ОТНОШЕНИЯ 3.1. Основные понятия Двухэлементное множество {a,b}, в котором элементы расположены в определенном порядке (порядок важен) называется упорядоченной парой (a,b). Упорядоченные пары (a,b) и (b,a) неравны (в отличие от множеств {a,b} и {b,a}). Упорядоченные пары равны, если равны их первые элементы и равны их вторые элементы. Допускается равенство первого и второго элементов пары (a,a). Пусть Аи В — два множества. Прямым декартовым произведением двух множеств Аи В называется множество упорядоченных пар, в котором первый элемент каждой пары принадлежит А, а второй принадлежит В A B = {(x,y) | x A и y B}, |A B|=|A| |B|. Любое подмножество P A B называется бинарным соответствием из А в В При этом множество А называется областью отправления, множество В — областью прибытия соответствия Р. Множество {x | (x,y) P и x A и y B} называется областью определения, а множество и x A и y B} — областью значений. Множество {y | (a,y) P и y B} называется образом элемента а при соответствии Р, а множество {x | (x,b) P и x A} — прообразом элемента b при соответствии Р Существует много способов задания соответствия. На рис показано графовое представление соответствия P = {(1,a),(3,a),(3,b),(3,c), (4,c),(4,e)} из множества A = {1,2,3,4} в множество B = {a,b,c,d,e}. Рис. Графовое представление соответствия Областью определения этого соответствия является множество {1,3,4}, областью значений — множество {a,b,c,e}. Образ элемента 1 — множество {a}, образ элемента 3 — множество {a,b,c}, образ элемента 1 2 3 4 a b c d e 120 4 — множество {c,e}. Прообраз элемента a — множество {1,3}, прообраз элемента b — множество {3}, прообраз элемента с — множество {3,4}, прообраз элемента e — множество {4}. Соответствие называется функциональным или функцией, если для каждого элемента из области определения существует одноэлементный образ (однозначное соответствие. Функция, у которой область определения равна области отправления, называется полностью определенной или отображением. Если область значений равна области прибытия, то функция называется сюръективной или сюръекцией. Функция называется инъекцией, если различные элементы из области определения имеют различные образы или, по другому, если прообразом любого элемента из области значений является одноэлементное множество. Отображение, которое и сюръективное и инъективное, называется биективным или взаимно-однозначным отображением На рис приведены различные виды соответствий из А в В. Множества Аи В представлены прямоугольниками, элементы множеств — кружочками, элементы соответствий — стрелочками, направленными от элементов множества А к элементам множества В. Соответствие, ноне функция Инъекция, ноне сюръекция Сюръекция, ноне инъекция Биекция Рис. Различные виды соответствий A B A B A B A B 121 1 2 3 x Степенью множества А называется его прямое произведение самогона себя : А = А, А = А А, А = А А n-1 Бинарным отношением R называется подмножество R A 2 и является отношением на множестве А. Бинарное отношение является частным случаем бинарного соответствия, поэтому оно может быть не функцией, функцией, отображением, сюръекцией, инъекцией, биекцией. Бинарное отношение называется пустым, если R= , тождественным I={(x,x) | x A}, универсальными Далее будем рассматривать только бинарные отношения и слово бинарные будем опускать. Обобщенным понятием отношения является n-арное отношение R — подмножество прямого произведения n множеств R A 1 А 2 … А n ={(a 1 ,a 2 ,…,a n )| a 1 A 1 , a 2 A 2 ,…,a n A n }. |