ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.03.2024
Просмотров: 202
Скачиваний: 3
18
14.Имеется n различных предметов. Известны масса каждого предмета и его стоимость. Определить, какие предметы надо положить
врюкзак, чтобы масса не превышала заданной, а общая стоимость была максимальна.
15.Каждая из n деталей последовательно обрабатывается на m станках (сначала на 1-м, затем на 2-м и т.д.). Для каждой детали известно время обработки на каждом станке. Определить, в какой последовательности необходимо обрабатывать детали, чтобы время обработки всех деталей было минимальным.
16.Найти все решения в (0,1)-числах следующего неравенства:
a1 x1 + a2 x2 + …+ an xn an+1 xn+1 + an+2 xn+2 + …+ am xm, n, m и a1, a2,…, am — заданы.
17.Задана целочисленная матрица размером n m. Выбрать минимальное количество строк матрицы, таких, что сумма элементов каждого столбца была бы больше заданного числа.
18.Имеется n станков и n деталей. Каждую деталь можно обработать на любом станке, но время обработки детали на одном станке может отличаться от времени ее обработки на другом. Нужно разместить детали по станкам так, чтобы суммарное время работы было наименьшим.
19.Заданы множества A и B, причем B = {x | x A}. Подмножество множества B называется покрытием множества A, если объединение всех его элементов равно множеству А. Найти все минимальные по мощности покрытия множества А, составленные из элементов множества B.
20.Необходимо перевести n тонн груза. Имеется k самолетов гру-
k
зоподъемностью s1, s2,…, sk тонн, si n . Стоимость перевозки самоле-
i 1
тами тонны груза составляет c1, c2,…, ck руб. Найти оптимальное множество самолетов для перевозки груза.
19
Контрольные вопросы
1.Что называется комбинаторным объектом?
2.В чем заключается правило произведения? Для чего, когда и как его применять?
3.В чем заключается метод поиска с возвращением? Изобразите общий рекурсивный алгоритм поиска с возвращением в виде блоксхемы.
4.Докажите теорему о количестве подмножеств n-элементного множества.
5.Опишите алгоритм порождения подмножеств. Можете ли вы предложить другие алгоритмы порождения подмножеств?
6.Дайте определение перестановки. Докажите теорему о количестве перестановок n-элементного множества. Опишите алгоритм порождения перестановок.
7.Дайте определение размещению. Докажите теорему о количестве размещений n-элементного множества по k местам. Опишите алгоритм порождения размещений.
8.Дайте определение размещению с повторениями. Докажите теорему о количестве размещений с повторениями n-элементного множества по k местам. Опишите алгоритм порождения размещений с повторениями.
9.Дайте определение сочетанию. Докажите теорему о количестве сочетаний из n по k. Опишите алгоритм порождения сочетаний.
10.Предложите алгоритм порождения подмножеств в порядке увеличения (уменьшения) мощности.
11.Дайте определение мультимножеству, мощности мультимножества, кратности элемента.
12.Дайте определение перестановки с повторениями. Докажите теорему о количестве перестановок с повторениями. Опишите алгоритм порождения перестановок с повторениями.
13.Дайте определение сочетания с повторениями. Докажите теорему о количестве сочетаний с повторениями из n элементов по k. Опишите алгоритм порождения сочетаний с повторениями.
14.Какие задачи относятся к задачам выбора?
15.Что называют траекториями задачи выбора?
16.Что называют функционалом траектории, зачем он нужен?
17.В чем заключается проектирование алгоритма решения задачи выбора с использованием алгоритмов порождения комбинаторных объектов?
18.Как преобразовать алгоритм порождения комбинаторных объектов в алгоритм решения задачи выбора?
20
3. ОТНОШЕНИЯ
Л а б о р а т о р н а я р а б о т а № 3.1
Отношения и их свойства
Цель занятия: изучить способы задания отношений, операции над от ношениями и свойства отношений, научиться программно реализовывать операции и определять свойства отношений.
Задания
Часть 1. Операции над отношениями
1.1.Представить отношения (см.”Варианты заданий”, п.а) графиком, графом и матрицей.
1.2.Вычислить значение выражения (см.”Варианты заданий”, п.б) при заданных отношениях (см.”Варианты заданий”, п.а).
1.3.Написать программы, формирующие матрицы заданных отношений (см.”Варианты заданий”, п.а).
1.4.Программно реализовать операции над отношениями.
1.5.Написать программу, вычисляющую значение выражения (см. “Варианты заданий”, п.б) и вычислить его при заданных отношениях (см.”Варианты заданий”, п.а).
Часть 2. Свойства отношений
2.1.Определить основные свойства отношений (см. ”Варианты заданий”, п.а).
2.2.Определить, являются ли заданные отношения отношениями толерантности, эквивалентности и порядка.
2.3.Написать программу, определяющую свойства отношения, в том числе толерантности, эквивалентности и порядка, и определить свойства отношений (см. ”Варианты заданий”, п.а).
Варианты заданий
Вариант 1
а) А = {(x,y) | x N и y N и x < 11 и y < 11 и (x и y четные)}
B = {(x,y) | x N и y N и x < 11 и y < 11 и |x– y| < 5}
C = {(x,y) | x N и y N и x < 11 и y < 11 и y2 кратно x} б) D = (A B)-1 C A2
21
Вариант 2
а) А = {(x,y) | x N и y N и x < 11 и y < 11 и x — четно и y > x}
B = {(x,y) | x N и y N и x < 11 и y < 11 и (x – y = 1 или x + y = 11} C = {(x,y) | x N и y N и x < 11 и y < 11 и
(x,y) {2,5,8,9,10} {1,3,5,10}}
б) D = А-1 B
A
– C
Вариант 3
а) А = {(x,y) | x N и y N и x < 11 и y < 11 и (x > y или y > 7)} B = {(x,y) | x N и y N и x < 11 и y < 11 и 10x + y кратно 3}
C = {(x,y) | x N и y N и x < 11 и y < 11 и x — четно и y — нечетно}
б) D = A B C2 A
а) А = {(x,y) | x N и y B = {(x,y) | x N и y C = {(x,y) | x N и y б) D = (A – B)-1 C
Вариант 4
N и x < 11 и y < 11 и x — четно и x + y < 10}
N и x < 11 и y < 11 и x + 2y < 20}
N и x < 11 и y < 11 и (x > 7 или y кратно 3)}
A
Вариант 5
а) А= {(x,y) | x N и y N и x < 11 и y < 11 и x + y — четно} B = {(x,y) | x N и y N и x < 11 и y < 11 и |x – y| > 5}
C = {(x,y) | x N и y N и x < 11 и y < 11 и если x — четно, то y < x,
иначе y > x}
б) D=A B – A B C-1
Вариант 6
а) А = {(x,y) | x N и y N и x < 11 и y < 11 и x + y — четно и x+y > 8} B = {(x,y) | x N и y N и x < 11 и y < 11 и x + 2y > 20}
C = {(x,y) | x N и y N и x < 11 и y < 11 и
(x,y) {1,2,4,8} {3,5,7,10}}
б) D = A B-1 A C B
Вариант 7
а) А = {(x,y) | x N и y N и x < 11 и y < 11 и x + y кратно трем}
B = {(x,y) | x N и y N и x < 11 и y < 11 и (2 < x < 8 или 2 < y < 8)} C = {(x,y) | x N и y N и x < 11 и y < 11 и x2 + y2 < 100}
б) D = A2 – B A-1 C
Вариант 8
а) А = {(x,y) | x N и y N и x < 11 и y < 11 и (y > x + 5 или x > y + 5} B = {(x,y) | x N и y N и x < 11 и y < 11 и (x и y четные)}
22
C = {(x,y) | x N и y N и x < 11 и y < 11 и |x – y| > 5} б) D = A B-1 A – C
Вариант 9
а) А = {(x,y) | x N и y N и x < 11 и y < 11 и y< x + 1 и x 2y}
B = {(x,y) | x N и y N и x < 11 и y < 11 и x — четно и x + y < 10} C = {(x,y) | x N и y N и x < 11 и y < 11 и (x,y) {2,3,8}
{1,4,5,8}}
б) D =
A
A-1 B C
Вариант 10
а) А = {(x,y) | x N и y N и x < 11 и y < 11 и (x < y < (9 – x) или
(9 - x) < y < x)}
B = {(x,y) | x N и y N и x < 11 и y < 11 и x — четно и y — нечетно}
C = {(x,y) | x N и y N и x < 11 и y < 11 и x y кратно трем} б) D = A B2 – C C-1
Вариант 11
а) А = {(x,y) | x N и y N и x < 11 и y < 11 и (y > x + 3 или y < x – 3)} B = {(x,y) | x N и y N и x < 11 и y < 11 и если x < 9,
то y кратно 3}
С = {(x,y) | x N и y N и x < 11 и y < 11 и x + 3y > 25} б) D = A A-1 B C
Вариант 12
а) А = {(x,y) | x N и y N и x < 11 и y < 11 и x + y кратно x}
B = {(x,y) | x N и y N и x < 11 и y < 11 и
(x,y) {2,4,6,8} {1,7,9}}
C = {(x,y) | x N и y N и x < 11 и y < 11 и x+y — четно и x y < 20} б) D = A B C – A-1 C
Вариант 13
а) A = {(x,y) | x N и y N и x < 11 и y < 11 и если x — четно,
то y < x, иначе y > x}
B = {(x,y) | x N и y N и x < 11 и y < 11 и (y < 7 или x кратно 3)} C = {(x,y) | x N и y N и x < 11 и y < 11 и (x2 + y2 > 100 или x = y)}
б) D = A B C2 – B-1
Вариант 14
а) А = {(x,y) | x N и y N и x < 11 и y < 11 и (y – x > 5 или x – y > 5} B = {(x,y) | x N и y N и x < 11 и y < 11 и 10x + 2y + 1 кратно 3}
C = {(x,y) | x N и y N и x < 11 и y < 11 и ((x + 3) < y < (11 – x)
или (9 – x) < y < (x + 1))}
б) D = (A B) ( A – C)-1