Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Пример выполнения контрольного задания

Читайте также:
  1. A, Б - органические анионы (OA-, в качестве примера на рисунке продемонстрирована PAH-) и
  2. Example of Jumping / Пример сверхсветового прыжка
  3. Gt;Приведите примеры
  4. I. Задания репродуктивного характера
  5. I. Прочитайте текст и выполните нижеследующие задания
  6. I.3.1. Определение номенклатуры и продолжительности выполнения видов (комплексов) работ
  7. II Примерная тематика ознакомительной практики

«Дискретная математика»

Решение контрольных заданий оформляется в обычных ученических 12 листовых тетрадях. На обложке тетради записывается название факультета, название кафедры, уч.группа ФИО студента, номер варианта задания.

Ниже представлен пример выполнения контрольного задания.

 

Вариант №

1.Построить таблицу истинности формулы x 1 ÙØ x 2®(x 1 Ú x 2) ÙØ x 3.

2.Преобразовать формулу так, чтобы она содержала только булевы операции, упростить (x 1 Ú x 3) ÙØ x 2 ~ x 3

3.Из урны, содержащей 6 белых и 4 черных шара, вынимают 4 шара. Найти число неупорядоченных наборов таких, что: 1- все четыре шара черные; 2 – два белых шара и два черных шара. Решить задачу для схемы выбора: а) с возвращением; б) без возвращения.

4. Задана матрица инцидентности графа (цифрами обозначены вершины, буквами – ребра графа). а) восстановить граф по матрице инцидентности; б) выяснить, является ли граф связным; в) построить для данного графа матрицу смежности.

  e1 e2 e3 e4 e5 e6 e7 e8 e9
                   
                   
                   
                   
                   
                   
                   

 

5. A, B, C, D, E, F – населенные пункты, линии –проектируемые участки дорог, цифры – их стоимость. Найти, какие дороги надо построить, чтобы схема дорог позволяла попасть из любого города в любой другой и из всех возможных схем имела наименьшую стоимость.

В 6 C

 
F
1

 
1 3 D

 
2

 

А Е

 

 

Решение задачи1.

 

В начале покажем полный перебор значений переменных. В таблице истинности они дадут заполненные восемь строк трех самых левых столбцов. Будем строить таблицу истинности постепенно, согласно заданного выражения: x 1 ÙØ x 2®(x 1 Ú x 2) ÙØ x 3. Пропуская объяснения промежуточных этапов, получим таблицу истинности (табл. 1).

 

x 1 x 2 x 3 Ø x 2 x 1 ÙØ x 2 x 1 Ú x 2 Ø x 3 (x 1 Ú x 2) ÙØ x 3 x 1 ÙØ x 2®(x 1 Ú x 2) ÙØ x 3
                 
                 
                 
                 
                 
                 
                 
                 

 

 

Решение задачи 2.

 

(x 1 Ú x 3) ÙØ x 2 ~ x 3 = (x 1ÙØ x 2 Ú x 3Ù x 2 ) ~ x 3 =

= (Ø (x 1ÙØ x 2 Ú x 3Ù x 2 ) ÙØ x 3 ) Ú((x 1ÙØ x 2 Ú x 3Ù x 2 ) Ù x 3 )=

= (Ø (x 1ÙØ x 2) ÙØ(Ø x 2Ù x 3)) ÙØ x 3Ú(x 1ÙØ x 2Ù x 3) ÚØ x 2Ù x 3 =

=(Ø x 1Ú x 2) Ù(x 2ÙØ x 3) ÙØ x 3 Ú x 1ÙØ x 2Ù x 3 Ú Ø x 2Ù x 3 =

= (Ø x 1ÙØ x 3 Ú x 2ÙØ x 3) Ù(x 2Ú Ø x 3) Ú x 1ÙØ x 2Ù x 3 Ú Ø x 2Ù x 3 =

= Ø x 1ÙØ x 3 Ú x 2ÙØ x 3 Ú Ø x 1Ù x 2ÙØ x 3 Ú x 2ÙØ x 3 Ú x 1ÙØ x 2Ù x 3 Ú Ø x 2Ù x 3 =

= Ø x 1ÙØ x 3 Ú x 2ÙØ x 3 Ú Ø x 2Ù x 3.

 

Решение задачи 3.

Случай с возвращением:

  1. В урне 4 черных шара и в нашей выборке должно быть 4 черных шара.

По теореме 1 из комбинаторики, число выборок, где все 4 шара черные, равно 44.

  1. В урне 6 белых шаров, из них два можем выбрать (по теореме 1) 62=36

способами. Два черных шара выбираем 42=16 способами. Для каждой фиксированной пары белых шаров можем брать любую пару черных, поэтому число выборок, содержащих два белых и два черных, равно 36∙16.

Случай без возвращения:

1. Из 4 черных шаров при выборе без возвращения можно единственным образом

выбрать 4 черных шара. То есть выборка, где все 4 шара черные, одна.

2. Из белых шаров два можно выбрать С26 способами (по теореме 2), аналогично два черных шара из четырех выбираем С24 способами. Число выборок, состоящих из двух черных и двух белых шаров, равно

 

 

6! 4! 6!

С26 С24 = = = 90.

2!(6-2)! 2!(4-2)! 8

 

Решение задачи 4

a) Рассмотрим первый столбец матрицы инцидентности. В ней элементы (A(G))11 и (A(G))21 равны единице. По определению матрицы инцидентности получим, что ребро e1 соединяет вершину 1 с вершиной 2.

Рассматривая аналогично все остальные столбцы, получим:

ребро e2 соединяет вершину 1 с вершиной 2,

ребро e3 соединяет вершину 3 с вершиной 4,

ребро e4 соединяет вершину 1 с вершиной 4,

ребро e5 соединяет вершину 2 с вершиной 4,

ребро e6 соединяет вершину 5 с вершиной 7,

ребро e7 соединяет вершину 5 с вершиной 6,

ребро e8 соединяет вершину 6 с вершиной 7,

ребро e9 соединяет вершину 6 с вершиной 7.

Чертеж графа имеет следующий вид:

4

e6

e4 e3

e9 e8

1 e5 3

e7

e1 e2

 

 

 

a) Данный граф не является связным, так как, например, невозможно по ребрам попасть из вершины 1 в вершину 5

 

b) Построим для графа матрицу смежности B(G):

По определению матрицы смежности её элемент (B(G))ij равен числу ребер, соединяющих i-ю и j-ю вершины. Рассмотрим поочередно все ребра графа. Ребро e1 соединяет вершину 1 с вершиной 2, поэтому в матрице смежности элементы (B(G))12 и (B(G))21 равны единице. Аналогично получим, что равны единице элементы

(B(G))23 (B(G))32

(B(G))34 (B(G))43

(B(G))14 (B(G))41

(B(G))25 (B(G))42

(B(G))57 (B(G))75

(B(G))56 (B(G))65

 

Рассмотрим теперь ребро e8 . Оно соединяет вершины 6 и 7. Ребро e9 также соединяет вершины 6 и 7 и других ребер, соединяющих вершины 6 и 7 нет, то есть вершины 6 и 7 соединяют два ребра, поэтому элементы (B(G))67 и (B(G))67 равны двум.

Остальные элементы матрицы смежности равны нулю, так как мы рассмотрели все ребра и все вершины, соединенные этими ребрами.

Окончательно получим:

 

               
               
               
               
               
               
               
               

 

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

 

Решение задачи 5.

 

Решение осуществляем по алгоритму Краскала.

 


Дата добавления: 2015-08-13; просмотров: 44 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Расчет холодопроизводительности| Зарождение и развитие ПВО в годы Первой мировой и Гражданской войн

mybiblioteka.su - 2015-2024 год. (0.013 сек.)