ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5047
Скачиваний: 25
86
перестановку, используя данные к этой задаче (см.таблицу 3.2). В
примере на некоторых шагах в числе минимальных оказывается не-
сколько элементов из совокупности
1
π
: в таких случаях выбирает-
ся любой из них. Заметим, что если бы в данной задаче среди эле-
ментов набора
{
}
)
,
( j
i
τ
были равные по величине (как в табл.3.2),
то оператор
1
g
имел бы не одну, а несколько неподвижных пере-
становок. Легко проверить, что все эти перестановки эквивалентны с
точки зрения критерия задачи.
И последнее замечание. Представленное решение задачи о
деталях (для 2-х станков) было плучено современным американским
математиком Р.Джонсоном. Решение оказалось настолько изящным,
что за данной задачей прочно укрепилось название – задача Джон-
сона.
Вторая группа
− приближенные методы. Рассмотренные
точные методы решения в применении ко многим практическим
задачам могут быть сложны в реализации из-за ограниченности вы-
числительных ресурсов.
Кроме того, большие затраты на получение точного решения
не всегда оправданы, так как исходные данные для задачи всегда
получены с некоторой погрешностью. В связи с этим важное значе-
ние для практики имеют приближенные методы решения. Многие из
них являются модификациями точных.
1. Приближенные модификации переборных методов.
Приближенный вариант метода разбиения и анализа отлича-
ется от точного только тем, что наряду со способами анализа, гаран-
тирующим исключение допустимых решений, не лучших оптималь-
ного, применяются способы анализа, не дающие такой гарантии.
2.
Приближенные варианты непереборных методов.
Наиболее широко применяется приближенный вариант мето-
да динамического
программирования (называется методом по-
шагового построения) и перестановочного метода (называется ме-
тодом локальной оптимизации).
Метод пошагового построения решения. При реализации
этого метода процесс построения решения разбивается на этапы на
каждом из которого фиксируется одна или несколько компонент
вектора
x
(один или несколько элементов в определенных позициях
выборки
λ
). При этом используются эвристические соображения,
87
иногда подкрепленные оценками.
Метод локальной оптимизации позволяет путем локальных
изменений улучшить некоторое допустимое решение, полученное,
например, уже перечисленными переборными методами. В основе
метода лежит выбор оператора
)
(
γ
g
, действующего на множестве
1
X
. Метод сводится к построению с помощью оператора
)
(
γ
g
монотонно улучшающейся (по значению целевой функции) после-
довательности
{ }
)
(k
x
,
.
)
(
)
(
)
1
(
k
k
k
x
g
x
γ
=
+
Выбор
k
γ
- параметра осуществляется так, чтобы выполня-
лось условие
0
]
[
]
[
0
1
0
>
−
+
k
k
x
f
x
f
.
В методе локальной оптимизации могут быть использованы
одновременнно несколько операторов типа
)
(
γ
g
. Они могут чере-
доваться при формированиии последовательности
{ }
)
(k
x
. Построе-
ние последовательности продолжается до получения допустимого
решения, являющегося локально оптимальным по отношению ко
всем использованным операторам.
3.10
Задачи
и
упражнения
1.
С помощью комбинаторных рассуждений (используя только оп-
ределение числа сочетаний) доказать тождества:
а)
),
1
,
1
(
)
,
1
(
)
,
(
−
−
+
−
=
k
n
C
k
n
C
k
n
C
б)
).
0
,
1
(
...
)
1
,
2
(
)
,
1
(
)
,
(
−
−
+
+
−
−
+
−
=
k
n
C
k
n
C
k
n
C
k
n
C
2.
Доказать тождество
∑
=
−
+
=
+
m
k
k
k
n
C
m
m
n
C
0
).
,
1
(
)
,
(
3.
На диск кодового замка нанесены 12 букв. «Секретное слово»
состоит из пяти букв. Сколько неудачных попыток может сде-
лать человек, не знающий «секретного слова»?
4.
В скольких различных состояний может находиться ЭВМ, если
ее оперативная память состоит из 2048 ячеек, в каждой из кото-
рых 43 двоичных разряда?
88
5.
Из суеверных соображений члены клуба велосипедистов провели
перерегистрацию, при которой исключили все номера билетов,
содержащие цифру 8. Сколько членов было в клубе, если извест-
но, что использованы все трехзначные номера, не содержащие ни
одной «восьмерки» (000 использован)?
6.
В
n
-ичной системе счисления используется
n
цифр. Сколько в
ней натуральных чисел, записываемых ровно
k
знаками?
7.
Сколькими способами можно посадить за круглый стол
n
муж-
чин и
n
женщин так, чтобы никакие два лица одного пола не си-
дели рядом?
8.
Из колоды, содержащей 52 карты, вынули 10 карт. В скольких
случаях окажется, что среди вынутых карт
а) хотя бы один туз;
б) ровно один туз;
в) не менее двух тузов;
г) ровно два туза.
9.
Сколько существует чисел от 0 до 10
n
, в которые не входят две
идущие друг за другом одинаковые цифры?
10.
Сколькими способами можно разложить
n
различных шаров по
m
различным урнам (вместимость урн неограничена)?
11.
Сколькими способами можно выбрать 6 карт из колоды, содер-
жащей 52 карты так, чтобы среди них были карты каждой масти?
12.
Сколькими способами можно разместить
n
одинаковых шаров
по
m
различным урнам?
13.
Решить задачу 12 при условиях:
а) пустых урн нет;
б) во второй урне ровно
k
шаров.
14.
Какова вероятность, купив 1 билет, угадать в спортлото (из 49):
а)
k
номеров
);
6
,...,
2
,
1
=
k
б) хотя бы
k
номеров.
15.
Сколькими способами можно разместить
1
n
белых,
2
n
черных и
3
n
синих шаров по
m
различным урнам?
16.
Генуэзская лотерея. Участники этой лотереи покупают билеты,
на которых стоят числа от 1 до 90. На некоторых билетах стоят
сразу 2, 3, 4 или 5 чисел. В день розыгрыша случайным образом
выбирают 5 жетонов с номерами от 1 до 90. Выигрывают те уча-
стники, у которых все номера на билетах окажутся среди вы-
бранных (сумма выигрыша зависит от количества чисел на биле-
89
те). Какова вероятность выигрыша в случае покупки билета:
а) с одним числом;
б) с
k
числами
?
)
5
1
(
≤
≤ k
17.
Доказать, что
∑
=
+
=
−
⋅
m
i
m
s
r
C
i
m
s
C
i
r
C
0
).
,
(
)
,
(
)
,
(
Указание.
.
)
1
(
)
1
(
)
1
(
s
r
s
r
x
x
x
+
+
=
+
⋅
+
Дать другое доказа-
тельство этого тождества, рассматривая число способов выбора ко-
миссии в составе
m
человек из группы, состоящей из
r
мужчин и
s
женщин.
18.
Сколько существует положительных чисел, меньших чем 10
n
(в
десятичной системе счисления), цифры которых расположены в
неубывающем порядке?
19.
Сколькими способами можно
n
одинаковых подарков раздать
r
детям:
а) без ограничений;
б) если каждый ребенок должен получить хотя бы один подарок?
20.
Из колоды в
n
4
карт, которая содержит четыре различных мас-
ти, в каждой масти по
n
карт
)
5
(
≥
n
, занумерованных числами
,
,...,
1
n
выбраны пять карт. Расположить в порядке возрастания
частоты появления, зависящей от
n
, следующие наборы:
а) пять последовательных карт одной масти;
б) четыре карты из пяти с одинаковым номером;
в) три карты с одним номером и две карты с другим;
г) пять карт одной масти;
д) пять последовательно занумерованных карт;
е) три карты из пяти с одним и тем же номером;
ж) две карты с одним номером и две с другим;
з) две карты из пяти с одним номером.
90
МЕТОДИЧЕСКИЕ
УКАЗАНИЯ
ПО
КУРСУ
«
ДИСКРЕТНАЯ
МАТЕМАТИКА
»
для специальностей 220400 и 071900
Часть
2
Контрольные работы №№ 3,4, выполняемые в третьем семест-
ре, имеют целью закрепить теоретические знания, полученные в
разделах: «Основы математической логики», «Основы теории алго-
ритмов», «Элементы комбинаторного анализа».
Контрольная
работа
№
3
Тема работы – математическая логика. В работе требуется вы-
полнить следующие задания.
1.
Определить, является ли справедливой приведенная формула
алгебры высказываний, не прибегая к составлению таблицы ис-
тинности, а используя только свойства соответствующих опера-
ций.
2.
Для указанной функции трех переменных:
-
составить таблицу истинности;
-
определить, к каким классам булевых функций она отно-
сится;
-
записать совершенные ДНФ и КНФ;
-
найти минимальную ДНФ;
-
для полученной минимальной ДНФ построить логическую
схему в базисах: а) { ٧,
⎯ } (дизъюнкция, отрицание);
б) { ٨,
⎯ } (конъюнкция, отрицание).
3.
Доказать полноту (или неполноту) приведенной системы буле-
вых функций.
При выполнении контрольной работы затруднения может вы-
звать проверка линейности булевой функции.
Для исследования функции на линейность ее следует предста-
вить в общем виде с помощью полинома по модулю два, а затем,
используя значения функции и значения переменных на конкретных
наборах, попытаться определить коэффициенты полинома. Остав-
шиеся неиспользованными наборы используют для проверки пра-
вильности выражения. Полученное хотя бы на одном из наборов