12. Для графа, построенного в задаче 10, найти минимальную по суммарному времени сеть дорог, соединяющую все пункты (кратчайший остов), используя алгоритм Краскала.
13. Для графа, построенного в задаче 10, найти самый короткий (по времени) путь из пункта 0 в каждый пункт (использовать алгоритм Дейкстра).
14. Для приведенных ниже формул булевых функций найти ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований
14.1. 
. 14.2. 
.
14.3. 
. 14.4. 
.
14.5. 
. 14.6. 
.
14.7. 
. 14.8. 
.
14.9. 
. 14.10. 
.
14.11. 
. 14.12. 
.
14.13. 
. 14.14. 
.
14.15. 
. 14.16. 
.
14.17. 
. 14.18. 
.
14.19. 
. 14.20. 
.
15. Для булевых функций задачи 14 найти СДНФ и СКНФ табличным способом.
16. Для булевых функций задачи 14 постройте полином Жегалкина.
17. Укажите существенные и фиктивные переменные булевой функции задачи 14.
18. Получите сокращенную ДНФ задания 14 методом Блейка.
19. Получите сокращенную ДНФ задания 14 из к. н.ф.
20. Получите все тупиковые ДНФ функции f, заданной вектором значений. Выделите из них минимальные.
20.1. f = (1000 1000 0000 1101); 20.2. f = (1000 1000 0100 1100);
20.3. f = (1000 1101 0000 0001); 20.4. f = (1001 1101 0000 0000);
20.5. f = (1100 0100 0000 0101); 20.6. f = (1100 0100 0000 1100);
20.7. f = (1100 0000 0100 0101); 20.8. f = (1100 0000 0100 1100);
20.9. f = (1100 0000 0111 0000); 20.10. f = (1100 0000 0101 0001);
20.11. f = (0011 0010 0001 0001); 20.12. f = (0100 0001 0101 0001);
20.13. f = (0000 0001 1101 0001); 20.14. f = (0000 0001 0011 0001);
20.15. f = (0000 0001 1011 0001); 20.16. f = (0010 0011 0001 0001);
20.17. f = (0000 1011 0001 0001); 20.18. f = (0000 0000 1101 0011);
20.19. f = (0100 0000 0101 0011); 20.20. f = (0010 0010 0001 0011).
21. Постройте структурную схему для любой минимальной ДНФ предыдущей задачи.
РЕШЕНИЕ ТИПОВЫХ ЗАДАЧ
Вариант № 0.
1.0. Используя метод математической индукции, докажите формулу
.
Решение. База индукции: проверим при 
: 
. Формула верна.
Индуктивное предположение. Предположим, что формула верна для : 
: 
.
Шаг индукции. Необходимо доказать, что формула верна для 
. Действительно,
.
Что и требовалось доказать.
2.0. Решить уравнение: 
Решение. Найдем область допустимых значений: 
значит, x ³ 2.
Подставив формулы: 
,
в уравнение, получим: 
Þ 
Þ 
, Þ 
.
Решив это уравнение, найдем корни x1= – 9, x2= 8.
Корень x1= –9 не входит в область допустимых значений, поэтому уравнение имеет единственный корень x = 8.
Ответ: x = 8.
3.0. В разложении 
найти член, содержащий 
.
Решение. 
.
Ответ: 
.
4.0. Контрольная работа состоит из четырех заданий. Известно, что i-е задание сделали 
% студентов, i-е и j-е – 
%, i-е, j-е и k-е – 
%, а все задания 
%. Сколько процентов студентов
а) не сделали ни одного задания;
б) сделали в точности два задания;
в) сделали не менее двух заданий.
A1 | A2 | A3 | A4 | A12 | A13 | A14 | A23 | A24 | A34 | A123 | A124 | A134 | A234 | A1234 |
50 | 60 | 70 | 60 | 50 | 40 | 30 | 50 | 40 | 60 | 40 | 30 | 30 | 40 | 30 |
Решение. Из условия задачи 
, 
,
, 
,
.
Тогда
а) 
;
б) 
;
в) 
.
Ответ: а) 
; б) 
; в) 
.
5.0. Найти решение рекуррентного соотношения, удовлетворяющее данным начальным условиям: 
Решение. Решение этого соотношения можно представить в виде 
, где 
– общее решение соответствующего однородного соотношения, а 
– частное решение данного неоднородного соотношения.
Составим характеристическое уравнение 
и найдем его корни: λ1= 2, λ 2= 3. Тогда 
.
Число λ1= 2 является однократным корнем характеристического уравнения, поэтому частное решение неоднородного уравнения имеет вид: 
, где A и B – неопределенные коэффициенты, которые можно найти, подставив 
в исходное уравнение и приравняв коэффициенты при одинаковых степенях n.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
