Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364141
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8693)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Контрольная работа: Решение практических заданий по дискретной математике

Название: Решение практических заданий по дискретной математике
Раздел: Рефераты по математике
Тип: контрольная работа Добавлен 07:06:01 18 января 2011 Похожие работы
Просмотров: 5783 Комментариев: 3 Оценило: 1 человек Средний балл: 5 Оценка: неизвестно     Скачать

Содержание

Введение

Задание 1

Представить с помощью кругов Эйлера множественное выражение

Используя законы и свойства алгебры множеств, упростить заданное выражение

Задание 2

Заданы множества кортежей

Показать, что эти множества представляют собой соответствия между множествами N1 и N2 , если N1 = N2 = . Дать полную характеристику этих соответствий

Задание 3

Частично упорядоченное множество М задано множеством упорядоченных пар

Построить диаграмму и определить, является ли данное множество решеткой. Если заданное множество является решеткой, то определить, является ли решетка дедекиндовой , дистрибутивной …

Задание 4

Является ли полной система булевых функций ? Если система функций полная ,то выписать все возможные базисы

Задание 5

Минимизировать булеву функцию по методу Квайна – Мак-Класки

Задание 6

Для неориентированного графа , у которого ,

а) вычислить числа ;

б) определить хроматическое число

Задание 7

Для заданной сети :

а) найти величину минимального пути и сам путь от вершины до вершины по алгоритму Дейкстры ;

б) используя алгоритм Форда-Фалкерсона, определить максимальный поток ( v1 – вход , v6 – выход сети ) и указать минимальный разрез, отделяющий v1 от v6 , если задана матрица весов (длин, пропускных способностей) Р…

Литература


Введение

Проблемы, связанные с понятиями бесконечности, дискретности и непрерывности, рассматривались в математике, как и в философии, древнегреческими мыслителями, начиная с 6 века до нашей эры. Под влиянием сочинений Аристотеля они широко обсуждались средневековыми учеными и философами в странах Европы и Азии. Через всю историю математики проходит идея преодоления между актуальной и потенциальной бесконечностью, с одной стороны, между дискретным характером числа и непрерывной природой геометрических величин – с другой. Впервые проблема математической бесконечности и связанных с нею понятий была широко поставлена в наиболее общем виде в теории множеств, основы которой были разработаны в последней четверти 19 века Георгом Кантором.

Цель контрольной работы – ознакомится с основными понятиями и методами решения по дискретной математике, уметь применить полученные знания при решении практического задания.


Задание 1

Представить с помощью кругов Эйлера множественное выражение

.

Используя законы и свойства алгебры множеств, упростить заданное выражение.

Решение:

Используя круги Эйлера и, учитывая, что операция пересечения выполняется раньше операции объединения, получим следующие рисунки:

Объединяя заштрихованные области, получим искомое множество:

Упростим заданное выражение:


=

.


Задание 2

Заданы множества кортежей:

.

Показать, что эти множества представляют собой соответствия между множествами N1 и N2 , если N1 = N2 = . Дать полную характеристику этих соответствий

Решение:

Найдем декартово произведение:

Видно, что заданные множества являются подмножествами этого пря-мого произведения. Следовательно, данные множества есть соответствия.

а) .


Область определения: . Следовательно, соответствие является частично определенным.

Область значений: . Следовательно, соответствие является сюръективным.

Образом элемента являются два элемента . Значит соответствие не является функциональным. Из этого следует, что соответствие не является функцией, отображением.

б) .

Область определения: . Следовательно, соответствие является частично определенным.

Область значений: . Следовательно, соответствие не является сюръективным.

Образом любого элемента из является единственный элемент из . Следовательно, соответствие является функциональным, функци-ей. Соответствие является частично определенным. Это означает, что функция является частично определенной и не является отображением.

в) .


Область определения:.Следовательно, соответствие всюду определено.

Область значений: . Следовательно, соответствие не является сюръективным.

Образом любого элемента из является единственный элемент из . Следовательно, соответствие является функциональным, функцией. Так как соответствие всюду определено, то имеем полностью определенную функцию, т.е. имеем отображение N1 в N2 .

г) .

Область определения: . Значит, соответствие полностью определено.

Область значений: . Значит, соответствие сюръективно.

Образом любого элемента из N1 является единственный элемент из N2 . Следовательно, соответствие является функциональным, функцией.

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

Так как функция полностью определена и соответствие сюръективно, то имеем отображение N1 на N2 .

Так как для любых двух различных элементов из N1 их образы из N2 также различны, то отображение является инъективным.

Так как отображение является одновременно сюръективным и инъективным, то имеем биективное отображение (взаимно однозначное отображение).


Задание 3

Частично упорядоченное множество М задано множеством упорядоченных пар

.

Построить диаграмму и определить, является ли данное множество решеткой. Если заданное множество является решеткой, то определить, является ли решетка дедекиндовой , дистрибутивной.

Решение:

Построим диаграмму:


Построим таблицу:

Пары

элементов

Н.Г. В.Г. Н.Н.Г. Н.В.Г.
1,2 1 2,5 1 2
1,3 1 3,4,5 1 3
1,4 1 4,5 1 4
1,5 1 5 1 5
1,6 1 6,2,5 1 6
2,3 1 5 1 5
2,4 1 5 1 5
2,5 2,6,1 5 2 5
2,6 6,1 2,5 6 2
3,4 3,1 4,5 3 4
3,5 3,1 5 3 5
3,6 1 5 1 5
4,5 4,3,1 5 4 5
4,6 1 5 1 5
5,6 6,1 5 6 5

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

Решетка М является дедекиндовой, когда выполняется равенство:

для таких , что .

Решетка М не является дедекиндовой, т.к. указанное равенство не вы-полняется, например, для элементов 2, 3, 4:


Одним из условий дистрибутивности решетки является ее дедекиндо-вость. Так как решетка М не является дедекиндовой, то она не является дистрибутивной решеткой.


Задание 4

Является ли полной система булевых функций ? Если система функций полная ,то выписать все возможные базисы.

Решение:

Рассмотрим функцию .

1. Принадлежность функции к классу :

.

Следовательно, .

2. Принадлежность функции к классу :

.

Следовательно, .

3. Принадлежность функции к классу .

Предположим, что функция линейная и, следовательно, представима в виде полинома Жегалкина первой степени:

.

Найдем коэффициенты .

Фиксируем набор 000:

,


,

Следовательно, .

Фиксируем набор 100:

,

,

Следовательно, .

Фиксируем набор 010:

,

,

.

Следовательно, .

Фиксируем набор 001:

,

,

, .

Следовательно, функция (по нашему предположению) может быть представлена полиномом вида:


.

Если функция линейная, то на всех остальных наборах ее значение должно равняться 1. Но на наборе 111 . Значит, функция не является линейной, т.е. .

4. Принадлежность функции к классу .

Функция самодвойственная, если на любой паре противоположных наборов (наборов, сумма десятичных эквивалентов которых равна , где п – количество переменных функции) функция принимает противоположные значения.

Вычисляем . Вычисляем значения функции на оставшихся наборах:

Строим таблицу:

(000)

0

(001)

1

(010)

2

(011)

3

(100)

4

(101)

5

(110)

6

(111)

7

1 1 1 1 1 1 1 0

На наборах 1 и 6, 2 и 5, 3 и 4 функция принимает одинаковые значения. Следовательно, .

5. Принадлежность функции к классу .

Из таблицы видно: 000 < 111 , но . Следовательно, .

Рассмотрим функцию .


1. Принадлежность функции к классу :

.

Следовательно, .

2. Принадлежность функции к классу :

.

Следовательно, .

3. Принадлежность функции к классу .

Предполагаем, что

.

Фиксируем набор 000:

,

.

Фиксируем набор 100:

,

.

Фиксируем набор 010:

,

.


Фиксируем набор 001:

,

.

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

.

Это равенство не соблюдается на наборе 011:

,

.

Следовательно, .

4. Принадлежность функции к классу .

Вычислим значения функции на оставшихся наборах:

Строим таблицу :

(000)

0

(001)

1

(010)

2

(011)

3

(100)

4

(101)

5

(110)

6

(111)

7

1 1 1 0 0 0 0 0

Из таблицы видно, что на наборах 3 и 4 функция принимает одинаковые значения. Следовательно, .

5. Принадлежность функции к классу .

Из таблицы видно, что 111 > 000 , но . Следовательно, .

Строим критериальную таблицу:

К0 К1 КЛ КС КМ
f1 - - - - -
f2 - - - - -

В таблице в каждом столбце стоят минусы. Следовательно, система булевых функций

является полной .

Найдем все возможные базисы. По критериальной таблице составим КНФ :

.

Приведем КНФ к ДНФ :

.

По полученной ДНФ выписываем искомые базисы:

.


Задание 5

Минимизировать булеву функцию по методу Квайна – Мак-Класки.

Решение:

1 этап. Определение сокращенной ДНФ.

По десятичным эквивалентам запишем 0-кубы :

Выполним разбиение на подгруппы:

.

Строим -кубы, сравнивая соседние группы (значок (*) указывает на участие данной импликанты в склеивании):

Выполняем разбиение всех -кубов в зависимости от расположения независимой переменной Х :


.

Выполняем сравнение кубов внутри каждой подгруппы с целью построения -кубов (значок (*) указывает на участие данной импликанты в склеивании):

.

Выполняем сравнение кубов внутри каждой подгруппы с целью построения -кубов (значок (*) указывает на участие данной импликанты в склеивании):

или

.

Так как они одинаковы, то .

Запишем сокращенную ДНФ, в которую должны быть включены им-пликанта из К 3 и импликанты, не участвовавшие в склеивании (в нашем случае таких импликант нет) :


.

2 этап. Определение тупиковой ДНФ.

Так как все импликанты участвовали в склеивании, и сокращенная ДНФ состоит из одной простой импликанты, то строить таблицу покрытий нет необходимости, т.е.

.


Задание 6

Для неориентированного графа , у которого ,

а) вычислить числа ;

б) определить хроматическое число .

Решение:

Построим граф:

а) Вычислим числа .

1) :

Используя алгоритм выделения пустых подграфов, построим дерево:

Согласно определению :


.

2) :

Используя алгоритм выделения полных подграфов, построим дерево:

Здесь - полные подграфы. Видно, что мощность носителей всех подграфов равна трем, т.е.

.

3) :


Построим модифицированную матрицу смежности заданного графа G :

1 2 3 4 5 6

.

Находим минимальное число строк, покрывающих все столбцы модифи-цированной матрицы . Таких строк – одна. Следовательно,

.

б) Определим хроматическое число .

Согласно алгоритму минимальной раскраски вершин графа, выделим все пустые подграфы графа G , т.е. построим дерево (оно построено в пункте а) ):


Построим таблицу:

1 2 3 4 5 6

1. {1,4,6} 1 1 1

2. {1,5} 1 1

3. {2,5} 1 1

4. {2,6} 1 1

5. {3} 1

Определяем минимальное число строк, покрывающих все столбцы таблицы. Такими строками могут быть строки 1, 3, 5. Значит,

.

Зададимся красками: для множества вершин - краска синяя (С ), для множества вершин - краска красная ( К ), для множества вершин - краска зеленая ( З ).


Раскрасим вершины графа G :


Задание 7

Для заданной сети :

а) найти величину минимального пути и сам путь от вершины до вершины по алгоритму Дейкстры ;

б) используя алгоритм Форда-Фалкерсона, определить максимальный поток ( v1 – вход , v6 – выход сети ) и указать минимальный разрез, отделяющий v1 от v6 ,

если задана матрица весов (длин, пропускных способностей) Р :

v1 v2 v3 v4 v5 v6

Решение:

Построим сеть:

а) Найдем величину минимального пути и сам путь сети G . Используем для этого алгоритм Дейкстры.

Этап 1. Нахождение длины кратчайшего пути.

.


Шаг 1. Полагаем

1-я итерация.

Шаг 2. Составим множество вершин, непосредственно следующих за с временными метками: . Пересчитываем временные метки этих вершин: ,

.

Шаг 3. Одна из временных меток превращается в постоянную:

Шаг 4. Следовательно, возвращаемся на второй шаг.

2-я итерация.

Шаг 2.

Шаг 3.

Шаг 4. Переход на второй шаг.

3-я итерация.


Шаг 2.

Шаг 3.

Шаг 4.

Переход на второй шаг.

4-я итерация.

Шаг 2.

Шаг 3.

Шаг 4. Переход на второй шаг.

5-я итерация.

Шаг 2.


Шаг 3.

Шаг 4. Конец первого этапа.

Следовательно, длина кратчайшего пути равна .

Этап 2. Построение кратчайшего пути.

1-я итерация.

Шаг 5. Составим множество вершин, непосредственно предшествующих с постоянными метками : Проверим равенство

для этих вершин:

т.е.

т.е.

Включаем дугу в кратчайший путь,

Шаг 6. Возвращаемся на пятый шаг.

2-я итерация.

Шаг 5.


Включаем дугу в кратчайший путь, .

Шаг 6. . Завершение второго этапа.

Следовательно, кратчайший путь построен. Его образует последовательность дуг: .

Окончательно, кратчайший путь от вершины до вершины v6 построен. Его длина (вес) равна . Сам путь образует последовательность дуг:

б) Определим максимальный поток через сеть G. Для этого используем алгоритм Форда-Фалкерсона.

Выбираем произвольно путь из вершины v1 в вершину v6 . Пусть это будет путь . Минимальную пропускную способность на этом пути, равную 10, имеет дуга , т.е. Увеличим на этом пути поток до 10 единиц. Дуга становится насыщенной. Дуга имеет на данный момент пропускную способность, равную 10.

Путь Следовательно, поток на этом пути можно увеличить на 9 единиц. Дуги становятся насыщенными.

Других маршрутов нет (другие маршруты проходят через насыщенные дуги). Поток максимален. Делаем разрез вокруг вершины v1 по насыщенным дугам


и получаем его величину единиц.

8. Используя алгоритм Краскала, построить остов с наименьшим весом для неориентированного взвешенного графа , у которого , если заданы веса (длины) ребер:

□ Построим граф G :

1. Упорядочим ребра в порядке неубывания веса (длины):

2. Возьмем ребро u1 и поместим его в строящийся остов.

Возьмем ребро u2 и поместим его в строящийся остов (т.к. оно не образует с предыдущим ребром цикла).

Берем ребро u3 и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла).

Берем ребро u4 и помещаем его в строящийся остов (т.к. оно не образует с предыдущими ребрами цикла).

Берем ребро u5 и помещаем его в строящийся остов (т.к. оно не образует цикла с предыдущими ребрами).

Ребра не рассматриваем, т.к. они образуют циклы с предыдущими ребрами.

Проверим окончание алгоритма. Число входящих в остов ребер равно 5. Заданный граф имеет п = 6 вершин и . Таким образом, остов содержит все вершины заданного графа G .

Вес (длина) построенного остова

равен .


Литература

1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986. – 311 с.

2. Коршунов Ю.М. Математические основы кибернетики. – М.: Энерго атомиздат, 1987. – 496 с.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. – 480 с.

4. Шапорев С.Д. Дискретная математика. – СПб.: БХВ-Петербург, 2006. - 400 с.

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

6. Хаханов В.И., Чумаченко С.В. Дискретная математика ( конспект теоретического материала). – Харьков: ХНУРЭ, 2003. – 246 с.

7. Богданов А.Е. Курс лекций по дискретной математике.–Северодонецк: СТИ, 2006. – 190 с.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Отличный у Вас сайт, очень помог! Сделай паузу, студент, вот повеселись: На экзамене по физике профессор пытается вытянуть на положительную оценку нерадивого студента: - Вы можете назвать фамилию хотя бы одного выдающегося физика? - Конечно, вы - профессор. Кстати, анекдот взят с chatanekdotov.ru
Лопух01:00:26 08 июля 2017
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:19:26 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
09:37:53 29 ноября 2015

Работы, похожие на Контрольная работа: Решение практических заданий по дискретной математике

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(175422)
Комментарии (2002)
Copyright © 2005-2017 BestReferat.ru bestreferat@gmail.com реклама на сайте

Рейтинг@Mail.ru