ТРЕНИНГ УМЕНИЙ
Пример выполнения упражнения тренинга на умение № 1
Задание
Вычислить число (n, k)-размещений и (n, k)-сочетаний с повторениями и без повторений для параметров:
(а) n = 7, k = 3;
(б) n = 3, k = 7.
Решение
| № п/п | Алгоритм | Конкретное соответствие данной ситуации предложенному алгоритму |
| Использовать формулы для пересчета указанных комбинаторных конфигураций | Число (n, k)-размещений с повторениями:  = nk.
Число (n, k)-размещений без повторений:
 = n • (n –1) •... • (n–k +1).
Число (n, k)-сочетаний без повторений:
 =  =  .
Число (n, k)-сочетаний с повторениями:
 =  = [тождество Сnk = Сnn-k ] = 
| |
| Выделить недопустимые наборы параметров для каждого типа конфигураций | (а) n = 7, k = 3: все четыре типа конфигураций допустимы; (б) n = 3, k = 7: в (n, k)-конфигурации без повторений параметр k не может быть больше n; по этой причине A37 = 0 и С37 = 0 | |
| Подставить заданные параметры в соответствующие формулы и вычислить требуемые значения | (а) n = 7, k = 3:
A 73 = 7 • 6 • 5 = 210;
 73 = 73 = 343;
С73 = (7 • 6 • 5) / (1 • 2 • 3) = 35;
 73 = С37+3-1 = С93 = (9 • 8 • 7) / (1 • 2 • 3) = 84;
(б) n = 3, k = 7:
 37 = 37 = 2187;
 37 = С73+7-1 = С97 = С92 = (9 • 8) / (1 • 2) = 36
|
Решите самостоятельно следующие задачи:
Вычислить значения комбинаторных величин Ank, nk, Сnk, nk для значений параметров:
1) n = 7, k = 4;
2) n = 8, k = 5;
3) n = 4, k = 3;
4) n = 9, k = 3;
5) n = 9, k = 6.
Пример выполнения упражнения тренинга на умение № 2
Задание
Цифровой кодовый замок имеет 10 клавиш с цифрами 0, 1,..., 9. Сколько существует различных кодов, если для открывания двери нужно:
(а - замки 1-го типа): одновременно нажать 4 определенные клавиши;
(б - замки 2-го типа): набрать определенное четырехзначное число?
Решение
| № п/п | Алгоритм | Конкретное соответствие данной ситуации предложенному алгоритму |
| По условию задачи определить тип комбинаторных конфигураций | (а) код для замков 1-го типа – сочетание без повторений: все цифры различны и порядок цифр не имеет значения (т.е., например, наборы 2 5 7 8 и 7 8 2 5 при одновременном нажатии клавиш не различаются, набор 2 8 8 5 невозможен); (б) код для замков 2-го типа - размещение с повторениями: цифры набираются последовательно, одна за другой, и могут повторяться; порядок цифр важен (так, наборы 2 5 7 8 и 7 8 2 5 различаются, набор 2 8 8 5 - допустимый) | |
| Подставить заданные параметры в соответствующие формулы и вычислить требуемые значения | (а) число различных кодов равно числу
(10, 4)-сочетаний без повторений:
С 104 = (10 • 9 • 8 • 7) / (1 • 2 • 3 • 4) = 210;
(б) число различных кодов равно числу
(10, 4)-размещений с повторениями:
 = 104 = 10000
|
Решите самостоятельно следующие задачи:
1. Имеется собрание сочинений в 8 томах. Сколькими способами можно расставить их на полке?
2. На книжной полке помещаются только 5 томов. Сколькими способами можно выбрать их из собрания сочинений в 8 томах?
3. Имеется собрание сочинений в 8 томах. На книжной полке помещаются только 5 томов. Сколькими способами можно установить их в определенном порядке?
4. Оптовая база предлагает туфли определенного фасона семи размеров. Сколькими способами магазин может составить заявку на 250 пар?
5. Найти число 7-значных чисел, в десятичной записи которых могут участвовать цифры из множества {3, 5, 8, 9}.
Пример выполнения упражнения тренинга на умение № 3
Задание
Ориентированный граф G с множеством вершин V = {1, 2, 3, 4, 5, 6, 7} задан списком дуг
E = {(1, 6), (2, 1), (2, 2), (2, 6), (2, 6), (3, 4), (4, 6), (5, 2), (5, 4), (5, 4), (5, 5), (6, 2), (6, 5), (7, 1)}.
Построить реализацию графа G.
Построить матрицу соседства вершин графа G.
Решение
| № п/п | Алгоритм | Конкретное соответствие данной ситуации предложенному алгоритму |
| Построить геометрическую реализацию графа | Наметить 7 точек (например, в вершинах выпуклого 7-угольника). Соединить смежные вершины vi и vj ориентированным ребром (vi, vj). Число ребер равно 14
| |
| Построить матрицу соседства вершин | Матрица соседства вершин – квадратная размера 7´7. Каждой дуге (ориентированному ребру) графа (vi, vj) соответствуют элемент матрицы: bij = 1, а для кратных дуг bij равно их числу (здесь - элементы b 26и b 54). Петлям соответствуют диагональные элементы матрицы bii. Остальные элементы матрицы равны 0
|
Решите самостоятельно следующие задачи:
Постройте самостоятельно различные представления ориентированных графов, заданных списком дуг:
1. {(1, 6), (2, 3), (3, 1), (3, 3), (3, 3), (3, 4), (3, 6), (5, 1), (5, 6), (5, 6), (5, 6), (7, 4), (7, 6)};
2. {(1, 2), (1, 4), (1, 5), (2, 4), (3, 2), (3, 4), (3, 4), (4, 2), (4, 5), (5, 5), (5, 7), (7, 1)};
3. {(1, 2), (1, 6), (2, 2), (2, 3), (3, 1), (3, 2), (3, 6), (4, 3), (4, 3), (4, 5), (5, 1), (5, 2), (5, 4), (5, 6)};
4. {(1, 4), (2, 1), (2, 5), (2, 6), (3, 4), (3, 7), (4, 1), (5, 3), (5, 4), (5, 6), (7, 1), (7, 5)};
5. {(2, 1), (2, 5), (2, 6), (2, 7), (3, 5), (3, 5), (4, 1), (4, 3), (4, 5), (6, 1), (6, 2), (6, 5), (6, 7), (7, 3)}.
Пример выполнения упражнения тренинга на умение № 4
Задание
Неориентированный граф G, задан следующим образом: множество вершин
V = { a, b, c, d, e, f, g } соответствует перечисленным ниже интервалам действительных чисел, ребра связывают две различные вершины, если соответствующие числовые интервалы пересекаются.
V = {(7, 18), (3, 10), (15, 20), (19, 25), (2, 5), (8, 12), (13, 22)}.
Построить реализацию графа G.
Построить матрицу соседства вершин графа G.
Построить матрицу инциденций графа G.
Найти расстояние между вершинами d и e.
Решение
| № п/п | Алгоритм | Конкретное соответствие данной ситуации предложенному алгоритму |
| Построить геометрическую реализацию графа | Наметить 7 точек (например, в вершинах выпуклого 7-угольника). Для каждой пары интервалов проверить, имеют ли они общую точку. Нужно проверить  = 7 • 6 / 2 = 21 пару и соединить смежные вершины ребром (vi, vj). Например, ребро (a, c) присутствует, поскольку интервалы a = (7, 18) и c = (15, 20) пересекаются, а ребро (с, f) отсутствует, поскольку интервалы с = (15, 20) и f = (8, 12) не пересекаются. Петли в графе отсутствуют.
В графе 9 ребер: (a, b), (a,c), (a, f), (a, g), (b, e), (b, f), (c, d), (c, g), (d, g)
| |
| Построить матрицу со-седства вершин | Матрица соседства вершин – квадратная размера 7´7. Каждому ребру графа (vi, vj) соответствуют два элемента матрицы, равные 1, симметричные относительно главной диагонали матрицы: bij и bji
|
| № п/п | Алгоритм | Конкретное соответствие данной ситуации предложенному алгоритму |
| Построить матрицу инциденций | Матрица инциденций – прямоугольная размера 7´9. Каждому ребру графа (vi, vj) соответствует столбец матрицы: два элемента этого столбца равны 1 в строках, соответствующих концам ребра vi и vj. Остальные элементы матрицы равны 0.: bij и bji
| |
| Найти расстояние между вершинами d и e | Расстояние – это число ребер в кратчайшей цепи (длины ребер не заданы, поэтому можно считать, что все они равны 1). Вершина e - концевая; поэтому расстояние между вершинами d и e на 1 больше, чем расстояние между b и d. Из d цепь идет либо через c, либо через g; обе они не смежны с b. Поэтому цепь [ dgabe ] (или [ dcabe ]) – кратчайшая; ее длина равна 4. |
Решите самостоятельно следующие задачи:
1. Решить ту же задачу для графа с вершинами V = { a, b, c, d, e, f, g, h }, которые соответствуют интервалам:
а) V = {(3, 13), (20, 31), (10, 27), (50, 65), (30, 54), (6, 15), (36, 59), (23, 41)};
б) V = {(41, 67), (14, 25), (17, 38), (60, 72), (31, 58), (29, 48), (10, 21), (52, 70)}.
2. Решить ту же задачу для графа с вершинами V = { a, b, c, d, e, f, g }, которые соответствуют интервалам:
а) V = {(6, 22), (39, 66), (20, 42), (20, 46), (51, 58), (36, 60), (14, 31)};
б) V = {(9, 35), (57, 60), (41, 64), (27, 50), (4, 23), (44, 71), (20, 49)}.