Методические указания по выполнению. Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями.






Скачать 97.06 Kb.
НазваниеМетодические указания по выполнению. Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями.
Дата публикации04.12.2014
Размер97.06 Kb.
ТипМетодические указания
top-bal.ru > Информатика > Методические указания

Вариант 1




1

Орграф задан матрицей смежности. Необходимо:
а) нарисовать граф;
б) выделить компоненты сильной связности;
в) заменить все дуги ребрами и в полученном неориентированном графе найти эйлерову цепь (или цикл).

1
1
0
0
0
1

1
0
0
0
0
0

0
0
1
1
0
1

0
0
1
0
1
0

0
0
1
1
0
1

0
0
0
0
0
1

2 Взвешенный граф задан матрицей длин дуг. Нарисовать граф. Найти: а) остовное дерево минимального веса;
б) кратчайшее расстояние от вершины v1 до остальных вершин графа, используя алгоритм Дейкстры.

3 Построить полный двудольный граф K2,3 G(V,E) c V={1,2,3,4,5}. Построить графы G1=G–{1,2}, G2=дополнение к G1, G3= G+(1,2)+(1,3).

4 Логическая функция задана номерами наборов аргументов, на которых она принимает значение единица. Найти СКНФ и СДНФ этой функции по таблице истинности.

5 Для логической функции, заданной в предыдущей задаче, найти минимальную ДНФ двумя способами – методом Квайна-Мак-Класки и по карте Карно. Построить контактную схему.

^ Методические указания по выполнению.

Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями. Контрольная работа может выполняться в электронном виде или быть решена в обычной ученической тетради и прислана по почте.

Первые три задачи относятся к главе № 3 – элементам теории графов.

^ В первой задаче нужно построить ориентированный граф по заданной матрице смежности и определить его компоненты сильной связности, т.е. такие группы вершин, что каждая из них составляет максимальный сильно связный подграф (по материалам главы 3, п. 3.2.3, 3.4.2, 3.5.1). Затем следует заменить все дуги ребрами и в полученном неориентированном графе найти эйлеров цикл или цепь (по материалам главы 3 п. 3.5.4). При этом в случае соединения двух вершин a и b дугами (a,b) и (b,a) в неориентированном графе появятся кратные ребра. Для выяснения возможности построения эйлерова цикла или цепи (согласно определению, это соответственно цикл или цепь, проходящий по всем ребрам графа ровно по одному разу) необходимо определить степени всех вершин (см. лекции, п. 3.2.1). Условие наличия эйлерова цикла – четность степеней всех вершин. Для существования эйлеровой цепи в графе должно быть ровно две вершины с нечетными степенями, причем они являются соответственно началом и концом этой цепи.

^ Во второй задаче для построения остовного подграфа минимального веса следует использовать алгоритм Краскала (согласно п. 3.5.3 лекций) – нужно построить само дерево и вычислить его вес. Что касается второй части задачи, для ее решения необходимо применять алгоритм Дейкстры (согласно п. 3.5.3 лекций). При этом нужно обратить внимание на то, что пометки вершин (см. пример 3.32 из п. 3.5.3) изменяются только в случае, когда найдено более короткое расстояние. При этом поиск минимального расстояния выполняется по всем временным вершинам, а не только по тем, которые входили в множество смежности на последнем шаге.

В третьей задаче необходимо построить полный двудольный граф требуемого вида и затем выполнить над ним заданные операции (по материалам пп. 3.3.2, 3.3.5). Например, пусть нужно построить граф G=K3,3 с вершинами {1,2,3,4,5,6}. Это означает полный двудольный граф, все множество вершин которого разбито на 2 непересекающихся подмножества по три вершины, а ребра соединяют между собой только вершины этих подмножеств. Выглядеть этот граф G может, например, так (поскольку в задаче не задано разбиение множества вершин, нумерация может быть взята произвольно):

П
G
редположим, что в задании требуется выполнить такие действия и построить графы:
G1=G–{1,5}, G2=дополнение к G1, G3= G+(1,2)+(1,4).

Первое действие означает, что из множества вершин надо удалить вершины 1 и 5 (с инцидентными им ребрами). В результате получается граф G1:

В графе G2 сохранены все вершины исходного графа, а ребра представляют собой дополнение множества ребер исходного графа до полного графа. В итоге получается несвязный граф.

При построении графа G3 в исходный граф G просто добавляются указанные ребра. В данном случае это ребра (1,2) и (1,4). На рисунке видно, что в графе G3 появляются кратные ребра за счет добавления ребра, уже существовавшего ранее.

Четвертая и пятая задачи относятся к теме 4 – алгебре логики.

В четвертой задаче логическая функция задана номерами наборов аргументов, на которых она принимает значение единица, и требуется построить СДНФ и СКНФ этой функции (по материалам гл.4, пп 4.1–4.2, пример 4.8). Для решения задачи следует перевести задающие функцию десятичные числа в двоичный вид, вследствие чего будут получены двоичные наборы, являющиеся прообразом единицы. Затем строится таблица истинности данной функции. Для построения СДНФ необходимо выбрать строки, на которых функция равна единице, а для построения СКНФ – наоборот, где она равна нулю.
Например, пусть задана функция


x

y

z

f

0

0

0

1

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

1
Построим таблицу истинности этой функции. Число строк в ней равно 8=23. Переведем все числа 0,3,4,5,7 в двоичный вид – им в таблице будут соответствовать единичные значения функции. Остальным наборам соответствуют нули.

Для построения СДНФ следует выбрать строки, где функция равна единице, и каждому выбранному двоичному набору сопоставить произведение переменных или их отрицаний, составленное так, чтобы оно давало единицу на выбранном наборе. Например, набору 000 будет соответствовать произведение , набору 011 – произведение , и так далее. В итоге получится СДНФ, содержащая 5 слагаемых: . Для построения СКНФ, наоборот, выбираются строки, где функция равна нулю (это строки 001, 010 и 110), и каждому выбранному двоичному набору сопоставляется дизъюнкция переменных или их отрицаний, составленная так, чтобы она давала ноль на выбранном наборе. Тогда набору 001 будет соответствовать , а итоговый вид СКНФ: .

В пятой задаче для той же самой функции требуется найти минимальную ДНФ двумя способами и построить затем контактную схему (по материалам 4.2.3, 4.3, 4.4.1, 4.4.2).

Для примера рассмотрим ту же самую функцию. Сначала минимизируем ее при помощи карты Карно. Карта будет состоять из 8 клеток и иметь следующий вид:

Для выбора покрытий наибольшей размерности следует взять в первую очередь те единицы, для которых такое покрытие единственно. Они выделены на карте жирным шрифтом. Для левой верхней единицы это покрытие состоит из двух клеток и имеет вид , для второй единицы – , после чего останется непокрытой всего одна единица. Ее можно включить в покрытие двумя равноценными способами: или . В итоге один из вариантов минимальной ДНФ: .

Для минимизации методом Квайна-Мак-Класки (см. пример 4.15) необходимо выписать все 0-кубы функции, а затем путем склеиваний получить сокращенную ДНФ, т.е. дизъюнкцию всех простых импликант данной функции.

К0={000,011,100,101,111}. Для упрощения процесса склеивания класс 0-кубов делится на подклассы по числу единиц в них: K00={000}, K01={100}, K02={011,101}, K03 ={111}. Склеивания возможны только между наборами, различающимися одним разрядом, поэтому они выполняются только между наборами соседних подклассов. Так, после склеивания первого и второго подклассов получится набор х00, в котором переменная, по которой производилось склеивание, заменена символом «х». Второй и третий классы склеиваются только один раз и получается набор 10х (наборы 100 и 011 склеить невозможно). И последние два класса при склеивании дают х11 и 1х1. Для удобства склеенные 0-кубы помечают каким-либо образом, например так: K00={000*}, K01={100*}, K02={011*,101*}, K03={111*}. Все 0-кубы участвовали в склеивании, следовательно, ни один из них не является простой импликантой. Полученный класс 1-кубов имеет вид: К1={х00, 10х, х11, 1х1}.

Далее разбиваем К1 на подклассы по положению символа «х» и продолжаем склеивать уже внутри них. В нашем случае это будут К11={х00, х11}, К12={1х1}, К13={10х}. В первом подклассе склеивание невозможно (т.к. количество различий больше одного), в остальных склеивать просто нечего. Следовательно, получена сокращенная ДНФ, состоящая из четырех наборов. Если провести аналогию с картой Карно, то там это все покрытия наибольшей размерности: . Видно, что результаты одинаковы: х00 соответствует , х11 – , и так далее.

Следующий этап – построение и упрощение импликантной таблицы. Строками являются простые импликанты, столбцами – 0-кубы функции.




000

011

100

101

111

Если простая импликанта покрывает 0-куб, то на пересечении строки и столбца ставится пометка. Это означает, что вместо «х» можно подставить любой символ и результат должен совпасть с заголовком столбца.

x00

v




v







10x







v

v




x11




v







v

1x1










v

v

Одна пометка в столбце соответствует существенной импликанте (выделено цветом). Это означает, что только данная импликанта покрывает соответствующий 0-куб (аналогия с картой Карно: единичка – 0-куб – покрывается покрытием наибольшей размерности единственным образом). Такие импликанты должны обязательно войти в ответ, поэтому они выписываются в ответ, а сами строки и покрытые ими столбцы вычеркиваются.




000

011

100

101

111

В таблице показаны вычеркнутые строки и столбцы. В итоге в таблице останутся две одинаковых строки.

x00

v




v







10x







v

v




x11




v







v

1x1










v

v






101

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

10x

v

1x1

v

Оба варианта ответа равнозначны. Таким образом, здесь опять видна аналогия с картой Карно: последнее покрытие на карте также можно было выбрать двумя равноценными способами. При этом покрытию соответствует импликанта 10x, а покрытию – импликанта 1х1.

Один из ответов, полученный с использованием метода Квайна-Мак-Класки: х00, х11, 10х, и минимальная ДНФ функции в этом случае имеет вид: , т.е. совпадает с результатом, полученным по карте Карно.

Контактная схема будет иметь вид:

Добавить документ в свой блог или на сайт

Похожие:

Методические указания по выполнению. Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями. iconКонтрольная работа Методические указания по выполнению
Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями....

Методические указания по выполнению. Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями. iconМетодические указания по выполнению. Контрольная работа должна выполняться...
Доказать равенства, используя свойства операций над множествами и определения операций. Проиллюстрировать при помощи диаграмм Эйлера-Венна...

Методические указания по выполнению. Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями. iconМетодические указания к контрольной работе по дисциплине «Естествознание (химия)»
Изучение учебного материала должно предшествовать выполнению контрольной работы. Следует придерживаться такой последовательности...

Методические указания по выполнению. Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями. iconМетодические указания и задания для выполнения студентами заочного...
Целью контрольной работы является усвоение курса «Макроэкономика», а именно теоретического материала, применения его для решения...

Методические указания по выполнению. Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями. iconМетодические указания для электроэнергетического факультета. 2012
Задания выполняются студентами во внеаудиторное время после прослушивания лекционного материала и решения задач на практических занятиях...

Методические указания по выполнению. Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями. iconМетодические рекомендации по выполнению контрольных работ
Контрольная работа является отчетом студента о самостоятельной работе, показывает объем проделанной им предварительной работы, глубину...

Методические указания по выполнению. Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями. iconМетодические указания по организации самостоятельной работы для студентов...
Методические указания предназначены для самостоятельного изучения курса Теплотехника студентами заочниками специальности 210200,...

Методические указания по выполнению. Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями. iconМетодические указания к решению задач и выполнению контрольных работ...
Номера задач, которые студент должен включить в свою контрольную работу, определяются по таблице вариантов в соответствии с последним...

Методические указания по выполнению. Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями. iconМетодические указания к выполнению лабораторных работ и решению задач...
Приведены ссылки на методические указания, используемые в лабораторном практикуме

Методические указания по выполнению. Контрольная работа должна выполняться после изучения всего теоретического материала. Решения задач следует сопровождать пояснениями. icon2. Решение задач следует сопровождать формулами, развернутыми расчетами, краткими пояснениями
В системе экономических наук важная роль принадлежит статистической науке. Эта роль значительно возрастает в условиях рыночной экономики....



Школьные материалы


При копировании материала укажите ссылку © 2018
контакты
top-bal.ru

Поиск