Файловый архив студентов. Файловый архив студентов.
1267 вузов, 4649 предметов.
/ Регистрация
FAQ Обратная связь Вопросы и предложения
Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
МИРЭА - Российский технологический университет
Предмет:
[НЕСОРТИРОВАННОЕ]
Файл:

Типовой расчет. Дискретка

.pdf
Скачиваний:
42
Добавлен:
10.05.2015
Размер:
209.77 Кб
Скачать
☆

21

Например, в варианте N = 19 = 24 + 0 ¢ 23 + 0 ¢ 22 + 2 + 1 = (10011)2

к функции f10 применяется подстановка S011 = (3142) и получается

функция f = (0011 0001 1010 1110).

ЗАДАЧА 3. Построить минимальную функциональную схему для функции f из задачи 2 на элементах f_; &; :g.

ЗАДАЧА 4. Построить минимальную контактную схему для той же функции.

ЗАДАЧА 5. Найти кратчайший путь в графе G1.

 

 

 

 

 

 

¡@

 

 

 

 

 

 

¡@

 

 

 

 

 

 

 

 

 

 

 

a13

¡

 

@@a24

 

 

 

 

¡

 

@@ a45

 

 

 

 

 

 

 

¡

 

 

a34 ¡

 

 

 

G1

 

 

 

¡

¡

 

 

@

 

¡

 

 

 

 

@

 

 

 

 

 

 

 

 

a14

 

@@

¡

 

 

a35

 

 

@@

 

 

 

 

 

¡

 

 

¡

 

 

 

 

 

 

 

 

 

 

¡

 

 

 

 

 

 

 

¡

 

 

 

 

 

 

¡¡@@

 

 

a11

 

¡ @

 

 

 

a25

¡ @@

 

 

 

 

 

 

 

 

¡

 

a15@@

 

 

¡

 

@ a41

 

¡

¡a51

@ a54

¡

 

 

 

@

 

 

¡

 

@

 

 

 

 

 

 

 

@

 

¡

 

 

 

 

 

 

¡

 

 

 

 

@

 

 

¡

 

 

 

 

@

¡

 

 

 

 

 

@

 

¡

 

a

 

 

 

 

 

 

 

 

 

 

 

 

 

 

@¡

 

31

 

 

@ ¡

 

 

 

 

 

@

a¡

 

 

 

 

 

 

 

 

 

 

 

@¡

 

 

 

 

 

 

@ b

@

 

 

 

 

 

¡

@

 

 

 

 

 

 

 

 

 

 

 

 

 

¡

@

 

 

 

 

 

 

@

@

 

 

 

 

 

¡ @

@

 

 

 

 

¡

@

 

 

 

 

 

¡

 

 

 

 

¡

¡

 

 

 

 

 

¡

¡

 

 

a

 

¡

 

 

a @

 

 

 

 

 

@

a

 

 

a @

 

21¡

 

 

 

 

¡

a

42

 

 

 

¡

a

55

12

@

 

 

 

 

 

32

@

 

 

 

 

 

 

@ 52

 

 

 

@ ¡¡

 

 

 

 

 

@

 

¡

 

 

 

 

 

 

@@

¡

 

 

 

 

 

 

 

 

 

 

 

 

 

¡

 

 

 

 

 

 

 

¡

 

 

 

 

@

 

 

a22

 

 

@

 

 

a43

 

 

 

 

 

 

 

@

 

 

¡

@

 

 

 

 

¡

 

 

 

 

 

 

 

 

@

 

 

 

 

 

¡

 

@

 

 

 

 

 

 

¡

 

 

 

 

 

 

 

 

 

@

 

 

¡

 

@

 

 

 

 

¡

 

 

 

 

 

 

 

 

a23

@

 

 

¡ a33

 

a44

@

 

 

¡ a53

 

 

 

 

 

 

 

 

 

@

 

¡

 

 

 

 

 

@

 

¡

 

 

 

 

 

 

 

 

 

 

 

@¡

 

 

 

 

 

 

@¡

 

 

 

 

 

 

 

Длины ребер - элементы матрицы A для соответствующего варианта.

N

 

 

 

A

 

 

 

N

 

 

 

A

 

 

 

N

 

 

 

A

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0 1

3

1

5

4 1

 

0

5

2

3

1

2 1

 

0

5

2

3

1

2 1

1

B

1

3

1

5

4

C

2

B

1

3

1

5

4

C

3

B

1

3

1

5

4

C

3

1

4

3

5

3

5

5

1

2

1

4

3

2

5

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

5

2

3

1

2

C

 

B

3

1

4

3

5

C

 

B

2

4

1

4

3

C

 

B

3

5

5

1

2

C

 

B

1

3

1

5

4

C

 

B

3

5

5

1

2

C

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

22

N

 

 

 

A

 

 

 

N

 

 

 

A

 

 

 

N

 

 

 

A

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

5

2

3

1

2

1

 

0

5

2

3

1

2

1

 

0

5

2

3

1

2

1

 

3

1

4

3

5

 

3

1

4

3

5

 

2

4

1

4

3

4

B

3

5

5

1

2

C

5

B

4

3

2

5

1

C

6

B

1

4

3

2

5

C

1

3

1

5

4

3

1

4

3

5

3

5

5

1

2

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

1

3

1

5

4

C

 

B

3

5

5

1

2

C

 

B

1

3

1

5

4

C

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

0

5

2

3

1

2

1

 

0

3

1

4

3

5

1

 

0

3

1

4

3

5

1

 

2

4

1

4

3

 

3

5

5

1

2

 

3

5

5

1

2

7

B

2

5

4

1

3

C

8

B

1

3

1

5

4

C

9

B

5

2

3

1

2

C

1

4

3

2

5

1

3

1

5

4

3

1

4

3

5

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

3

5

5

1

2

C

 

B

5

2

3

1

2

C

 

B

4

3

2

5

1

C

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

0

3

1

4

3

5

1

 

0

3

1

4

3

5

1

 

0

2

4

1

4

3

1

 

4

3

2

5

1

 

4

3

2

5

1

 

1

4

3

2

5

10

B

3

1

4

3

5

C

11

B

2

4

1

4

1

C

12

B

3

5

5

1

2

C

3

5

5

1

2

1

4

3

2

5

1

3

1

5

4

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

5

2

3

1

2

C

 

B

4

3

2

5

1

C

 

B

5

2

3

1

2

C

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

0

2

4

1

4

3

1

 

0

2

4

1

4

3

1

 

0

2

4

1

4

3

1

 

1

4

3

2

5

 

2

5

4

1

3

 

2

5

4

1

3

13

B

4

3

2

5

1

C

14

B

1

4

3

2

5

C

15

B

2

5

4

1

3

C

3

1

4

3

5

3

5

5

1

2

1

4

3

2

5

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

4

3

2

5

1

C

 

B

5

2

3

1

2

C

 

B

4

3

2

5

1

C

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

0

3

5

5

1

2

1

 

0

3

5

5

1

2

1

 

0

3

5

5

1

2

1

 

1

3

1

5

4

 

1

3

1

5

4

 

5

2

3

1

2

16

B

1

3

1

5

4

C

17

B

1

3

1

5

4

C

18

B

3

1

4

3

5

C

5

2

3

1

2

2

4

1

4

3

4

3

2

5

1

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

3

1

4

3

5

C

 

B

1

4

3

2

5

C

 

B

3

1

4

3

5

C

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

0

3

5

5

1

2

1

 

0

4

3

2

5

1

1

 

0

4

3

2

5

1

1

 

5

2

3

1

2

 

3

1

4

3

5

 

3

1

4

3

5

19

B

2

4

1

4

3

C

20

B

3

5

5

1

2

C

21

B

4

3

2

5

1

C

2

5

4

1

3

5

2

3

1

2

2

4

1

4

3

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

1

4

3

2

5

C

 

B

3

1

4

3

5

C

 

B

1

4

3

2

5

C

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

0

4

3

2

5

1

1

 

0

4

3

2

5

1

1

 

0

1

4

3

2

5

1

 

2

4

1

4

3

 

2

4

1

4

3

 

3

5

5

1

2

22

B

1

4

3

2

5

C

23

B

2

5

4

1

3

C

24

B

1

3

1

5

4

C

4

3

2

5

1

2

5

4

1

3

5

2

3

1

2

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

3

1

4

3

5

C

 

B

1

4

3

2

5

C

 

B

2

4

1

4

3

C

 

B

C

 

B

C

 

B

C

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

23

N

 

 

 

A

 

 

 

N

 

 

 

A

 

 

 

N

 

 

 

A

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

1

4

3

2

5

1

 

0

1

4

3

2

5

1

 

0

1

4

3

2

5

1

 

3

5

5

1

2

 

4

3

2

5

1

 

4

3

2

5

1

25

B

5

2

3

1

2

C

26

B

3

1

4

3

5

C

27

B

2

4

1

4

3

C

2

4

1

4

3

4

3

2

5

1

2

5

4

1

3

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

2

5

4

1

3

C

 

B

2

4

1

4

3

C

 

B

2

5

4

1

3

C

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

0

2

5

4

1

3

1

 

0

2

5

4

1

3

1

 

0

2

5

4

1

3

1

 

1

4

3

2

5

 

1

4

3

2

5

 

2

5

4

1

3

28

B

3

5

5

1

2

C

29

B

4

3

2

5

2

C

30

B

1

4

3

2

5

C

5

2

3

1

2

2

4

1

4

3

4

3

2

5

1

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

 

 

 

 

 

C

 

B

2

4

1

4

3

C

 

B

2

5

4

1

3

C

 

B

2

4

1

4

3

C

 

B

C

 

B

C

 

B

C

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

 

@

 

 

 

 

 

A

ЗАДАЧА 6. Найти остов минимальной длины в графе G1 из задачи 5.

ЗАДАЧА 7. Решить задачу об оптимальном назначении с матрицей эффективности A из задачи 5.

ЗАДАЧА 8. Найти максимальный поток в транспортной сети, заданной графом G2. Пропускная способность ребер определяется

элементами aij матрицы A из задачи 5.

 

 

 

 

 

 

 

 

a21©©©©

©©HH

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G2

 

 

 

 

 

a45HHHHa33

 

 

 

 

 

 

 

 

 

 

 

 

 

©©

©©

a22

 

 

 

 

 

 

a34

HH

HH

 

 

 

 

 

 

 

 

 

 

 

 

©

©

©©©HHH

H

H

 

 

 

 

HHH

H

H a

 

 

 

HHH

H

H

 

 

 

 

 

a

 

 

a

 

 

 

 

 

 

 

 

 

 

 

 

a

 

 

a

 

 

 

11©

 

 

a

 

 

 

 

 

 

 

 

35

 

51

 

 

 

 

 

 

 

 

14

 

 

23

H

HH

 

 

 

 

 

 

 

H

 

 

 

 

 

H 53

 

 

©©

a12

 

 

 

 

 

 

HH

 

 

 

a41

HH

HH

 

 

a54

HH

HH

 

a

©©

 

 

 

 

 

a24

 

 

 

 

 

 

 

 

 

 

b

HH

 

 

 

 

 

HH

HHH

 

 

 

 

HH

HHH

 

 

 

 

 

 

 

 

 

©©©

©©

 

HHH

H

 

a15

 

 

 

 

 

 

 

Ha42

 

a52

 

©

 

 

 

a13

 

 

 

a25

H

 

 

 

 

 

 

 

 

 

 

 

 

a55

 

 

 

 

 

 

 

HHHH

 

 

 

a31HHHH

 

 

 

a43

HHHH©©©©

 

 

 

 

 

 

 

 

 

 

 

 

HHH

HH

 

 

 

 

 

 

 

 

 

©©

©©©

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a32

H

H

HH

 

 

©©

©

© a44

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

H©

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

24

ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ К ЭКЗАМЕНУ (ЗАЧЕТУ)

1. Операции над множествами, их свойства. Аксиомы булевой алгебры.

2. Характеристические векторы подмножеств. Алгебра булевых векторов.

3. Элементарные булевы функции. Их выражение через основные. 4. ДНФ и СДНФ. Методы приведения булевой функции к СКНФ и СДНФ.

5. Минимальная ДНФ. Тривиальный алгоритм минимизации.

6. Определение интервала и максимального интервала булевой функции. Сокращенная и ядровая ДНФ.

7. Геометрический метод минимизации булевой функции от трех переменных.

8. Метод Карно для минимизации булевых функций.

9. Метод Квайна для минимизации булевых функций.

10. Двойственная функция. Принцип двойственности.

11. Определение функционально полной системы функций. Основные примеры функционально полных систем.

12. Многочлены Жегалкина. Методы вычисления многочлена Жегалкина для булевой функции.

13. Замкнутый класс функций. Основные замкнутые классы.

14. Леммы о несамодвойственной, о монотонной и о нелинейной функциях.

15. Теорема Поста о функциональной полноте.

16. Понятие графа. Маршруты, циклы, связность. Определение дерева, его свойства.

17. Понятие орграфа. Сумматор n-разрядных двоичных чисел.

18. Планарные графы. Теорема Понтрягина-Куратовского.

19. Алгоритмы отыскания кратчайших путей в графе. Минимальный остов.

20. Паросочетание. Теорема Холла о совершенном паросочетании.

21. Алгоритм отыскания максимального паросочетания.

22. Задача об оптимальном назначении. Алгоритм ее решения.

23. Транспортные сети и потоки. Алгоритм Форда-Фалкерсона.

25

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

III семестр ТИПОВОЙ РАСЧЕТ

Обозначение: ® = a1a2a3a4a5 двоичный код номера студента в списочном составе группы.

ЗАДАЧА 1. Автомат с одним двоичным входом и одним двоичным выходом выда¼т на выходе 0 до тех пор, пока на вход не поступит слово ®. После этого, начиная со следующего такта, автомат посто-

янно выдает 1. Составить диаграмму Мура и автоматную таблицу данного автомата. Минимизировать полученный автомат.

ЗАДАЧА 2. Для минимального автомата из задачи 1 составить канонические уравнения минимальной сложности и диаграмму Мура, дополненную ветвями резервных/фиктивных состояний. Реализовать минимальный автомат из задачи 1 в виде СЛС (синхронной логической сети) минимальной сложности.

ЗАДАЧА 3. Реализовать минимальный автомат из задачи 1 в виде ССА (синхронной сети автоматов) минимальной сложности над полной автоматной системой §a = fRS ¡ триггер; §0 = f:; _; ^gg.

ЗАДАЧА 4. Язык L задан над алфавитом A0 = f0; 1g и состоит из всех слов словаря A¤0, которые имеют конечную длину и содержат (не менее одного раза) слово ®. Составить регулярную формулу и

источник для языка L.

ЗАДАЧА 5. С помощью теоремы (синтеза) Клини построить направленный (инициальный) автомат Мура, порождающий язык L

из задачи 4.

ЗАДАЧА 6. Минимизировать автомат Мура из задачи 5 и проверить (доказательно) полученный минимальный автомат на эквивалентность минимальному автомату из задачи 1.

26

ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ

1.Определение и способы задания автомата Мили. Последовательный двоичный сумматор.

2.Автоматное отображение, его свойства. Автономный автомат. Свойства его автоматного отображения.

3.Эквивалентные состояния и эквивалентные автоматы. Теорема о существовании минимального автомата.

4.Алгоритм минимизации автомата.

5.Комбинационные и логические автоматы. Теорема о реализации логического автомата в виде СЛС.

6.Теорема о реализации произвольного абстрактного автомата в виде СЛС.

7.Автомат Мура, его связь с автоматом Мили (теорема).

8.Параллельное соединение двух автоматов.

9.Последовательное соединение двух автоматов.

10.Соединение автоматов с обратной связью.

11.Автоматно полные системы автоматов. Теорема о достаточном условии автоматной полноты.

12.Триггеры, их автоматные таблицы и диаграммы Мура. Реализация одних триггеров с помощью других.

13.Детерминированные функции. Их связь с A-деревом.

14.Âåñ A-дерева. Ограниченно детерминированные функции. Тео-

рема о необходимом и достаточном условии автоматного отображения.

15. Определение машины Тьюринга. Ее связь с конечным автоматом.

16. Понятие функции, вычислимой по Тьюрингу. Вычислимость суперпозиции и разветвления.

17. Понятие примитивно-рекурсивной, рекурсивной и частично рекурсивной функции. Базовые функции и основные операторы. 18. Теоремы о примитивной рекурсивности констант, перестановки и отождествления переменных.

19. Теоремы о примитивной рекурсивности суммы, произведения и возведения в степень.

20. Теоремы о примитивной рекурсивности урезанного вычитания, модуля, функции сигнум, минимум и максимум, булевых функций.

27

21.Теорема о связи функций, вычислимых по Тьюрингу, с частично рекурсивными функциями. Тезисы Тьюринга и Черча.

22.Микропрограммные автоматы, их реализация.

23.Перечислимые и разрешимые множества. Теорема Райса (без доказательства).

24.Настроенный автомат Мура. Автоматно порожденный язык.

25.Регулярные операции над языками. Определение регулярного языка.

26.Определение источника. Построение источника для регулярного языка.

27.Теорема синтеза Клини (построение автомата Мура для автоматного языка).

28.Алгоритмическая разрешимость задачи тождества регулярных языков.

Вопросы к зачетам и экзаменам могут быть уточнены и дополнены лектором.

ЛИТЕРАТУРА

1.Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988; Кузнецов О.П. Дискретная математика для инженера. СПб: ¾Лань¿, 2007.

2.Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: ФИЗМАТЛИТ, 2005.

ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА

3.Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.

4.Вшивцев А.С., Применко Э.А. Элементы дискретной математики. М.: МИРЭА, 1986.

5.Вшивцев А.С, Применко Э.А. Методы оптимального проектирования сетей и формальные алгоритмы.. М.: МИРЭА, 1988.

СОДЕРЖАНИЕ

 

Математический анализ, 2 семестр . . . . . . . . . . . . . . . . . . . . . .

3

Типовой расчет . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

Календарный план упражнений . . . . . . . . . . . . . . . . . . . . . . .

17

Теоретические вопросы к экзамену . . . . . . . . . . . . . . . . . . . .

17

Основы дискретной математики, 2 семестр . . . . . . . . . . . . .

20

Математическая логика и теория алгоритмов, 3 семестр

25
Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]
Помощь Обратная связь Вопросы и предложения Пользовательское соглашение Политика конфиденциальности