ДИСКРЕТНАЯ МАТЕМАТИКА

20. Постройте коммутационную схему, соответствующую данному булевому выражению. Определить, при каких положениях переключателей ток в сети отсутствует.

40. Для данной булевой функции

а) постройте таблицу истинности, найдите двоичную форму булевой функции, приведите булеву функцию к СДНФ и СКНФ;

б) найдите двумя способами многочлен Жегалкина и ответьте на вопрос, является ли данная булева функция линейной.

60. По заданной матрице весов графа найти величину минимального пути и сам путь от вершины до вершины по алгоритму Дейкстры.

.

160. 1) Определить:

а) число всех размещений из элементов по элементов;

б) число всех перестановок из элементов;

в) число всех сочетаний из элементов по элементов.

2) В почтовом отделении продаются открытки видов. Найти число способов покупки открыток.

3) Найти разложение .

4) Определить, сколько -значных чисел можно составить из цифр.

80. Найти число различных остовов данного графа, используя теорему Кирхгофа.

100. Для графа , заданного матрицей весов, построить минимальный по весу остов с помощью формализованного алгоритма Прима и найти его вес . Выполнить проверку с помощью алгоритма Краскала.

.

120. По данной матрице пропускных способностей дуг найти величину максимального потока по сети и выписать дуги, образующие на сети минимальный разрез.

140.На одном и том же оборудовании предприятие должно выпускать партиями пять видов продукции. Издержки от переналадок оборудования при переходе от производства одного вида продукции к производству другого заданы матрицей , где - затраты на переналадку оборудования при переходе от выпуска

-го вида продукции к выпуску -го вида продукции.

С помощью алгоритма Литтла найти последовательность запуска партий продукции в производство, при которой суммарные потери от переналадок будут минимальными.