41738

Мінімізація функцій за допомогою карт Карно

Лабораторная работа

Информатика, кибернетика и программирование

Мета: навчитися мінімізувати функції за допомогою карт Карно Завдання: Для кожного варіанта задана функція від п'яти змінних номерами відсутніх конституент. Мінімізувати функцію за допомогою карт Карно. Побудована таблиця називається картою Карно.

Украинкский

2013-10-25

48.54 KB

16 чел.

6

Лабораторна робота №2

Тема: Мінімізація функцій за допомогою карт Карно.

Мета: навчитися мінімізувати функції за допомогою карт Карно

Завдання: 

Для кожного варіанта задана функція від п'яти змінних номерами відсутніх конституент. Мінімізувати функцію за допомогою карт Карно. Визначити складність функції до та після мінімізації. Проаналізувати отримані результати. Індивідуальні варіанти завдань представлені в таблицях А.1-А.3 (додаток А).

Теоретичні основи:

Графічний спосіб мінімізації функцій зручний для трьох, у крайньому випадку для чотирьох аргументів. Для того, щоб використовувати сам принцип цього методу для більшої кількості змінних була запропонована його модернізація. Ідея полягає в розгортці куба на площині. Покажемо цю розгортку на малюнку.

                          011                              111

1

100              101                111              110                 100

Виходячи з розгортки куба побудуємо наступну таблицю.

00

01

11

10

0

1

1

1

1

1

Побудована таблиця називається картою Карно. У карті позначено конституенти, присутні у функції. Подібно тому, як відмічені вершини куба поєднувалися в ребра й грані, поєднуються й одиниці карти в так звані інтервали. В інтервали можна поєднувати 2m одиниць, тобто 2,4,8…і т.д. Покажемо об'єднання одиниць і зчитування мінімальної форми на карті Карно.

М3

00

01

11

10

0

1

1

М1

1

1

1

М2

Усього на карті виділено три інтервали. В кожний інтервал входять ті мінітерми, у яких він повністю перебуває. Виходячи з карти, мінімальна форма має вигляд :

                         __                                   __  __

f(М1, M2 , M3) = М1  M3  +  M2  M3 +  М1 M2, M3

Як видно, результат повністю збігається з попереднім. Покажемо, як виглядають карти Карно для чотирьох змінних.

00

01

11

10

00

1

1

01

1

1

11

1

1

10

1

1

Можна скласти карти Карно для п'яти й більше аргументів, однак, з ростом числа аргументів складність роботи з картою зростає швидше, і при цьому процес оптимізації важко алгоритмізувати.

Зміст звіту:

  1.  Титульний лист.
  2.  Мета, індивідуальне завдання.
  3.  Карти Карно з означеними інтервалами.
  4.  Опис інтервалів.
  5.  Визначення складності функції.
  6.  Аналіз результатів.

Контрольні питання.

  1.  Перерахуйте відомі операції над множинами.
  2.  Назвіть закони над операціями для множин.
  3.  Дайте визначення первинного терму.
  4.  Визначите поняття конституенти.
  5.  Як функція від множин представляється графічно?
  6.  Що таке інтервали й максимальні інтервали?
  7.  Дайте визначення нормальної й зробленої нормальної форми Кантора.
  8.  Як проводиться графічна мінімізація функції від множин?
  9.  Як одержати карту Карно для трьох змінних?
  10.  Карти Карно для чотирьох і п'яти змінних.


Додаток А Варіанти завдань

Таблиця А.1 – Варіанти завдань групи а

Номер варіанта

відсутні конституенти

Номер варіанта

відсутні конституенти

1

5, 9, 17, 26

17

7, 10, 11, 13, 29

2

4, 10, 15, 29

18

1, 4, 6, 7, 12, 30

3

7, 12, 13, 16, 26

19

5, 8, 10, 22, 30

4

3, 5, 18, 21

20

1, 4, 7, 12, 16, 27

5

2, 10, 22, 23

21

8, 14, 23, 26, 31

6

6, 9, 14, 20, 21

22

2, 6, 15, 20, 27

7

6, 7, 9, 21, 22

23

5, 15, 21, 27, 29

8

1, 3, 12, 23, 30

24

2, 4, 8, 11, 25, 30

9

5, 10, 11, 13, 28

25

11, 18, 27, 29, 31

10

8, 11, 16, 23

26

9, 13, 16, 20, 29

11

5, 16, 20, 26

27

7, 12, 22, 25, 31

12

6, 7, 22, 24, 30

28

0, 4, 8, 11, 22, 27

13

8, 20, 24, 30

29

13, 17, 24, 27, 28

14

1, 7, 13, 24, 28

30

7, 15, 25, 27, 29

15

2, 6, 12, 15, 26

31

1, 5, 9, 17, 23, 27

16

9, 11, 15, 21, 26

32

11, 16, 23, 25, 29


таблиця А.2 – Варіанти завдань групи б

Номер варіанта

відсутні конституенти

Номер варіанта

відсутні конституенти

1

6, 10, 18, 27

17

8, 11, 12, 14, 30

2

5, 11, 16, 30

18

25, 7, 8, 13, 31

3

8, 13, 14, 17, 27

19

6, 9, 11, 23, 31

4

4, 6, 19, 22

20

2, 5, 8, 13, 17, 28

5

3, 11, 23, 24

21

9, 15, 24, 27, 0

6

7, 10, 15, 21, 22

22

3, 7, 16, 21, 28

7

7, 8, 10, 22, 23

23

6, 16, 22, 28, 30

8

2, 4, 13, 24, 31

24

3, 5, 9, 12, 26, 31

9

6, 11, 12, 14, 29

25

12, 19, 28, 30, 0

10

9, 12, 17, 24

26

10, 14, 17, 21, 30

11

6, 17, 21, 27

27

8, 13, 23, 26, 0

12

7, 8, 23, 25, 31

28

1, 5, 9, 12, 23, 28

13

9, 21, 25, 31

29

14, 18, 25, 28, 29

14

2, 8, 14, 25, 29

30

8, 16, 26, 28, 30

15

3, 7, 13, 16, 27

31

2, 6, 10, 18, 24, 28

16

10, 12, 16, 22, 27

32

12, 17, 24, 26, 30


таблиця А.3 – Варіанти завдань групи в

Номер варіанта

відсутні конституенти

Номер варіанта

відсутні конституенти

1

7, 11, 19, 28

17

9, 12, 13, 15, 31

2

6, 12, 17, 31

18

3, 6, 8, 9, 14, 30

3

9, 14, 15, 18, 28

19

7, 10, 12, 24, 29

4

5, 7, 20, 23

20

3, 6, 9, 14, 18, 29

5

4, 12, 24, 25

21

10, 16, 25, 28, 30

6

7, 11, 16, 22, 23

22

4, 8, 17, 22, 29

7

8, 9, 11, 23, 24

23

7, 17, 23, 29, 31

8

3, 5, 14, 25, 0

24

4, 6, 10, 13, 27

9

7, 12, 13, 15, 30

25

13, 20, 29, 31

10

10, 13, 18, 25

26

11, 15, 18, 22, 31

11

7, 18, 22, 28

27

9, 14, 24, 27, 29

12

8, 9, 24, 26, 0

28

2, 6, 10, 13, 24

13

10, 22, 26, 0

29

15, 19, 26, 29, 30

14

3, 9, 15, 26, 30

30

9, 17, 27, 29, 31

15

4, 8, 14, 17, 28

31

3, 7, 11, 19, 25

16

11, 13, 17, 23, 28

32

13, 18, 25, 27, 31


 

А также другие работы, которые могут Вас заинтересовать

39008. Духовно-нравственное воспитание детей дошкольного возраста 425 KB
  Потаповская âПодарок к праздникуâ Программа развивающего и коррекционного рукоделия для детей дошкольного возраста Для ребенка Светлый Праздник и весна Рождество и зима Спас и спелые плоды Троица и зеленые березки сливаются в одно могучее впечатление свежее и полное жизни. Предлагаемый курс разработан с учетом того что среди дошкольников сегодня чрезвычайно высок процент детей нуждающихся в специальной помощи не только направляющей но и корректирующей развитие: физическое психическое социальное духовное. Отметим что речь идет...
39009. Информационные системы 235.5 KB
  Экономические информационные системы человекомашинные системы которые собирают накапливают сохраняют и выдают по запросу или требованию информацию в виде данных и знаний необходимых для управления экономическим объектом. выполнять свои функции при их изменении и экономическая эффективность улучшение экономических результатов в результате внедрения информационной системы.: 1 выявление существенных характеристик объекта 2 создание математической или...
39010. ИНФОРМАЦИОННЫЕ СИСТЕМЫ. Учебник 364 KB
  Однако при передаче И из одной системы в другую количество И в передающей системе не уменьшается хотя в принимающей обычно увеличивается. ИНФОРМАЦИОННЫЕ СИСТЕМЫ Тема 2. Определение информационной системы ИС.
39011. Информационные системы. Курс лекций 496.5 KB
  «Информационная система — организационно упорядоченная совокупность документов (массивов документов) и информационных технологий, в том числе с использованием средств вычислительной техники и связи, реализующих информационные процессы»
39012. Информационные технологии управления. Курс лекций 266 KB
  Целью изучения данного курса является изучение: методологии проектирования информационных технологий управления ИТУ; принципов выбора инструментальных средств проектирования ИТУ; основных направлений автоматизации управления; основных методов используемых для автоматизации подготовки и принятия управленческих решений; практики применения ИТУ; подходов и методов для оценки экономической эффективности ИТУ. Усвоение курса âИнформационные технологии управленияâ основано на знаниях полученных при изучении теоретических основ информационных...
39013. Информационные системы в управлении 444 KB
  Фактографические системы оперируют фактическими сведениями представленными в виде специальным образом организованных совокупностей формализованных записей данных. Фактографические системы используют не только для реализации справочных функций но и для решения задач обработки данных. Взаимосвязь информационных потоков образованных прямыми и обратными связями средств обработки передачи и хранения данных а также субъектов управления составляет информационную систему экономического объекта. Они предназначены для обработки данных и моделей...
39014. Автоматизированные информационные системы 97.5 KB
  В настоящее время проблема выбора информационной системы ИС из специфической задачи превращается в стандартную процедуру. На российских предприятиях зачастую используют системы первого или второго поколения. Процедура принятия решения о выборе наиболее эффективной компьютерной системы управления нова для большинства отечественных руководителей а ее последствия во многом будут оказывать значительное влияние на предприятие в течение нескольких лет.
39015. Физические системы 34 KB
  Энергию всегда можно представить в виде произведения двух сомножителей один из которых описывает интенсивность расхода или накапливания энергии а второй характеризует количественные результаты этого процесса. Активными элементами служат источники энергии. Пассивные элементы системы служат либо для накопления либо для поглощения энергии. Накопители энергии могут накапливать либо потенциальную либо кинетическую энергию.
39016. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МОДЕЛИРОВАНИЯ 64.5 KB
  Речь идет о том что создаваемая модель должна отражать в первую очередь те свойства реальной системы или явления которые влияют на выбранный показатель эффективности. В ряде случаев моделируемая система имеет в своем составе некоторые относительно изолированные подсистемы характеризующиеся определенным параметром в том числе векторным. Такие подсистемы можно заменять в модели соответствующими числовыми величинами а не описывать процесс их функционирования. При имитационном моделировании используемая математическая модель...