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


 

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

79617. ОБ ОБЩИХ ПРИНЦИПАХ ОРГАНИЗАЦИИ МЕСТНОГО САМОУПРАВЛЕНИЯ В РОССИЙСКОЙ ФЕДЕРАЦИИ 78.5 KB
  С момента принятия Федерального закона Об общих принципах организации местного самоуправления РФ прошло уже почти восемь лет наработана определенная практика его применения которая выявила некоторые серьезные проблемы функционирования местного самоуправления.
79618. КОНЦЕПЦИЯ ЧАСТНОПРАВОВОГО РЕГУЛИРОВАНИЯ ОТНОШЕНИЙ ПО ПОВОДУ ПРИРОДНЫХ РЕСУРСОВ 99 KB
  Причиной для написания настоящей статьи послужила непрекращающаяся дискуссия о месте и значении частноправовых средств в регулировании общественных отношений по поводу природы. Особенность природы состоит в том, что она не имеет собственно вещный характер в абсолютном смысле этого слова...
79619. ГЕОГРАФИЯ ПРЕСТУПНОСТИ: ВОПРОСЫ ТЕОРИИ И РЕГИОНАЛЬНЫЕ ПРОБЛЕМЫ СИБИРИ 84.5 KB
  Одной из наиболее актуальных и трудноразрешимых проблем общественной жизни в РФ остается проблема преступности: ее уровня структуры темпов роста. Не случайно подчеркивается что даже при достаточно позитивных изменениях в динамике и структуре преступности криминальная ситуация в России остается сложной.
79620. К ВОПРОСУ О МЕТОДИКЕ ПРЕПОДАВАНИЯ КРИМИНОЛОГИИ: СТУДЕНЧЕСКИЙ ОПЫТ – 3 118.5 KB
  Сегодня мы представляем на ваш суд пример апробирования еще одной из форм преподавания, реализованной в ходе изучения криминологии студентами 4 курсов дневных бюджетного и коммерческого отделений Юридического института ИГУ. Назовем ее условно «Криминологический КВН».
79621. МОГУЩЕСТВО ЮРИДИЧЕСКОЙ НАУКИ РОССИЙСКОЙ ПРИРАСТАТЬ БУДЕТ…СИБИРЬЮ?! 40.5 KB
  Что касается иркутской конференции, то сразу оговоримся, что в рамках данной статьи мы не будем говорить о ней, поскольку сама эта тема заслуживает отдельной статьи. Напомним также, что такие конференции проводятся в Юридическом институте Иркутского государственного университета уже давно...
79622. КРИМИНАЛЬНАЯ КУЛЬТУРОЛОГИЯ. ЧАСТЬ 1. МАСС-МЕДИА 196 KB
  Неоднократно высказывавшееся положение о том что средства массовой информации в результате переноса информации оказывают широкий спектр общего воздействия на ее получателей дают возможность для их подробного криминологического исследования.
79623. К ВОПРОСУ О МЕТОДИКЕ ПРЕПОДАВАНИЯ КРИМИНОЛОГИИ: СТУДЕНЧЕСКИЙ ОПЫТ– 4 117 KB
  Основными участниками игры, как Вы поняли, стали три команды — «соперницы» (с одной стороны, бюджетное отделение, с другой стороны, коммерческое отделение, представленное в этом году сразу двумя командами). Были проведены многочисленные репетиции.
79624. ИСТОРИЧЕСКИЕ И СОЦИАЛЬНЫЕ ПРЕДПОСЫЛКИ ИЗУЧЕНИЯ ПРЕСТУПНОСТИ КРУПНОГО ГОРОДА ВОСТОЧНОЙ СИБИРИ 161.5 KB
  Иркутская область являясь субъектом Российской федерации входит в состав Восточно-Сибирского района. Имея 22 города в том числе 5 городов с населением свыше 100 тысяч человек большое количество поселков городского типа и население численностью 28 млн.
79625. ЗАМЕТКИ О РАЗВИТИИ ПРЕДМЕТНЫХ ДЕЙСТВИЙ В РАННЕМ ДЕТСТВЕ 81 KB
  Исследованию психологических механизмов возникновения предметных действий у детей в истории детской психологии не очень повезло. Несмотря на чрезвычайную теоретическую и практическую значимость этой проблемы, ее изучение только начинается.