Название: по дискретной математике
Вид работы: контрольная работа
Рубрика: Математика
Размер файла: 284.22 Kb
Скачать файл: referat.me-217879.docx
Краткое описание работы: Контрольная работа по дискретной математике. Задание 1. На рисунке изображен граф. Его дуги обозначены буквами a – p. Обозначить произвольным образом вершины графа. Взяв из таблицы вариантов данные о длине его дуг, определить:
по дискретной математике
Контрольная работа по дискретной математике.
Задание 1.
На рисунке изображен граф. Его дуги обозначены буквами a – p. Обозначить произвольным образом вершины графа. Взяв из таблицы вариантов данные о длине его дуг, определить:
1. Кратчайший путь из начальной вершины в конечную, и длину кратчайшего пути.
2. Критический путь из начальной вершины в конечную, и длину критического пути.
3. Считая этот граф сетевым графиком некоторого процесса, а длины дуг – временем осуществления работ, определить:
- для каждой вершины-события ранний и поздний срок его свершения и его резерв времени,
- для каждой дуги-работы независимый резерв времени.
Варианты:
№ |
a |
b |
c |
d |
e |
f |
g |
h |
i |
j |
k |
l |
m |
n |
o |
p |
1 |
4 |
5 |
3 |
5 |
6 |
4 |
2 |
7 |
4 |
8 |
2 |
8 |
6 |
2 |
1 |
4 |
2 |
3 |
3 |
4 |
2 |
5 |
7 |
4 |
3 |
3 |
5 |
8 |
2 |
2 |
6 |
7 |
3 |
3 |
3 |
4 |
4 |
3 |
2 |
1 |
3 |
5 |
5 |
4 |
3 |
4 |
7 |
1 |
2 |
2 |
4 |
3 |
4 |
4 |
4 |
4 |
4 |
6 |
6 |
7 |
3 |
8 |
5 |
1 |
4 |
1 |
3 |
5 |
3 |
2 |
1 |
4 |
6 |
3 |
1 |
1 |
5 |
3 |
6 |
7 |
8 |
4 |
2 |
6 |
6 |
3 |
2 |
2 |
4 |
5 |
2 |
6 |
9 |
4 |
5 |
2 |
3 |
4 |
2 |
6 |
7 |
7 |
3 |
5 |
5 |
4 |
6 |
7 |
2 |
3 |
4 |
5 |
6 |
3 |
6 |
3 |
2 |
5 |
8 |
3 |
4 |
4 |
4 |
2 |
2 |
3 |
1 |
2 |
3 |
4 |
2 |
3 |
1 |
3 |
3 |
9 |
3 |
6 |
4 |
3 |
5 |
6 |
2 |
5 |
2 |
5 |
6 |
2 |
5 |
3 |
4 |
3 |
10 |
3 |
4 |
1 |
7 |
4 |
7 |
3 |
4 |
2 |
5 |
2 |
5 |
1 |
3 |
7 |
5 |
11 |
3 |
4 |
3 |
5 |
6 |
4 |
2 |
7 |
4 |
8 |
2 |
8 |
6 |
2 |
1 |
4 |
12 |
5 |
3 |
5 |
2 |
5 |
7 |
4 |
3 |
3 |
5 |
8 |
2 |
2 |
6 |
7 |
3 |
13 |
5 |
4 |
4 |
2 |
2 |
1 |
3 |
5 |
5 |
4 |
3 |
4 |
7 |
1 |
2 |
2 |
14 |
4 |
4 |
4 |
4 |
1 |
4 |
6 |
6 |
7 |
3 |
8 |
5 |
1 |
4 |
1 |
3 |
15 |
4 |
2 |
1 |
4 |
6 |
6 |
1 |
1 |
5 |
3 |
6 |
7 |
8 |
4 |
2 |
6 |
16 |
6 |
2 |
2 |
4 |
5 |
2 |
7 |
9 |
4 |
5 |
2 |
3 |
4 |
2 |
6 |
3 |
17 |
5 |
5 |
5 |
4 |
6 |
7 |
2 |
8 |
4 |
5 |
6 |
3 |
6 |
3 |
7 |
5 |
18 |
4 |
4 |
4 |
4 |
2 |
2 |
3 |
1 |
4 |
3 |
4 |
2 |
3 |
6 |
3 |
3 |
19 |
6 |
6 |
4 |
3 |
5 |
6 |
2 |
5 |
2 |
8 |
6 |
2 |
4 |
3 |
4 |
3 |
20 |
7 |
4 |
1 |
7 |
4 |
7 |
3 |
4 |
2 |
5 |
1 |
6 |
1 |
3 |
7 |
5 |
21 |
8 |
5 |
3 |
5 |
6 |
4 |
2 |
7 |
4 |
8 |
2 |
8 |
6 |
2 |
1 |
4 |
22 |
6 |
3 |
4 |
2 |
5 |
7 |
4 |
3 |
3 |
5 |
8 |
2 |
2 |
6 |
7 |
3 |
23 |
7 |
4 |
4 |
3 |
2 |
1 |
3 |
5 |
5 |
4 |
3 |
4 |
7 |
1 |
2 |
2 |
24 |
6 |
4 |
4 |
4 |
4 |
4 |
6 |
6 |
7 |
3 |
8 |
5 |
1 |
4 |
1 |
3 |
25 |
6 |
2 |
1 |
4 |
6 |
3 |
1 |
1 |
5 |
3 |
6 |
7 |
8 |
4 |
2 |
6 |
26 |
6 |
2 |
2 |
4 |
5 |
2 |
6 |
9 |
4 |
5 |
2 |
3 |
4 |
2 |
6 |
7 |
27 |
7 |
5 |
5 |
4 |
6 |
7 |
2 |
3 |
4 |
5 |
6 |
3 |
6 |
3 |
2 |
5 |
28 |
8 |
4 |
4 |
4 |
2 |
2 |
3 |
1 |
2 |
3 |
4 |
2 |
3 |
1 |
3 |
3 |
Задание 2.
Проект состоит из последовательного выполнения работ u1 , u2 , u3 , u4 .
Для каждой работы ui
() определена зависимость ее стоимости si
от времени ее осуществления ti
.
1. Предполагая, что , определить:
a) время осуществления работ , для которых общая стоимость проекта
минимальна при условии, что весь проект должен быть закончен не позднее времени Tmax
. Также найти при этих условиях минимальную стоимость проекта
и стоимость осуществления каждой работы
.
Значения
,
Tmax
для каждого варианта даны в столбцах 2 - 6 таблицы вариантов
б) стоимости работ , для которых общее время осуществления проекта
минимально при условии, что общая стоимость проекта не более Smax
. Также найти при этих условиях минимальное время осуществления проекта
и время осуществления каждой работы
.
Значения
,
Smax
для каждого варианта даны в столбцах 2 – 5 и 7 таблицы вариантов.
2. Предполагая, что зависимость si
от ti
линейная и убывающая, и зная для каждой работы ui
ее минимальное и максимальное время осуществления и
, а также минимальную и максимальную стоимость
и
определить:
a) время осуществления работ , для которых общая стоимость проекта
минимальна при условии, что весь проект должен быть закончен не позднее времени Tmax
. Также найти при этих условиях минимальную стоимость проекта
и стоимость осуществления каждой работы
.
Значения
,
,
,
, Tmax
для каждого варианта даны в столбцах 8 – 15 и 6 таблицы вариантов.
б) стоимости работ , для которых общее время осуществления проекта
минимально при условии, что общая стоимость проекта не более Smax
. Также найти при этих условиях минимальное время осуществления проекта
и время осуществления каждой работы
.
Значения
,
,
,
, Smax
для каждого варианта даны в столбцах 8 – 15 и 7 таблицы вариантов.
Варианты:
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
№ вар-та. |
a1 |
a2 |
a3 |
a4 |
Tmax |
Smax |
|
|
|
|
|
|
|
|
1 |
6 |
5 |
3 |
1 |
10 |
40 |
|
|
|
|
|
|
|
|
2 |
2 |
3 |
4 |
2 |
15 |
70 |
|
|
|
|
|
|
|
|
3 |
3 |
6 |
4 |
2 |
10 |
10 |
|
|
|
|
|
|
|
|
4 |
3 |
4 |
1 |
7 |
10 |
40 |
|
|
|
|
|
|
|
|
5 |
3 |
2 |
1 |
4 |
10 |
30 |
|
|
|
|
|
|
|
|
6 |
3 |
2 |
5 |
4 |
15 |
20 |
|
|
|
|
|
|
|
|
7 |
3 |
5 |
9 |
4 |
20 |
70 |
|
|
|
|
|
|
|
|
8 |
3 |
4 |
2 |
1 |
25 |
20 |
|
|
|
|
|
|
|
|
9 |
3 |
6 |
4 |
1 |
10 |
60 |
|
|
|
|
|
|
|
|
10 |
3 |
4 |
1 |
7 |
10 |
70 |
|
|
|
|
|
|
|
|
11 |
3 |
4 |
8 |
5 |
10 |
40 |
|
|
|
|
|
|
|
|
12 |
5 |
3 |
7 |
2 |
15 |
70 |
|
|
|
|
|
|
|
|
13 |
5 |
4 |
3 |
2 |
20 |
10 |
|
|
|
|
|
|
|
|
14 |
4 |
2 |
1 |
3 |
10 |
40 |
|
|
|
|
|
|
|
|
15 |
4 |
2 |
1 |
3 |
20 |
60 |
|
|
|
|
|
|
|
|
16 |
6 |
1 |
2 |
4 |
25 |
20 |
|
|
|
|
|
|
|
|
17 |
5 |
3 |
2 |
4 |
25 |
70 |
|
|
|
|
|
|
|
|
18 |
4 |
2 |
1 |
5 |
20 |
20 |
|
|
|
|
|
|
|
|
19 |
6 |
2 |
4 |
3 |
10 |
60 |
|
|
|
|
|
|
|
|
20 |
7 |
4 |
1 |
3 |
15 |
70 |
|
|
|
|
|
|
|
|
21 |
8 |
5 |
3 |
9 |
10 |
40 |
|
|
|
|
|
|
|
|
22 |
6 |
3 |
4 |
2 |
20 |
70 |
|
|
|
|
|
|
|
|
23 |
7 |
4 |
9 |
3 |
25 |
10 |
|
|
|
|
|
|
|
|
24 |
6 |
7 |
9 |
5 |
20 |
40 |
|
|
|
|
|
|
|
|
25 |
6 |
2 |
1 |
4 |
20 |
30 |
|
|
|
|
|
|
|
|
26 |
6 |
2 |
3 |
4 |
15 |
20 |
|
|
|
|
|
|
|
|
27 |
7 |
5 |
6 |
4 |
20 |
70 |
|
|
|
|
|
|
|
|
28 |
8 |
1 |
3 |
4 |
20 |
20 |
|
|
|
|
|
|
|
|
Похожие работы
-
Двумерная кластеризая по предельному расстоянию. Дискретная математика
Изучение основных вопросов теории графов и области ее применения на практике. Разработка алгоритма кластеризации по предельному расстоянию и построение минимального остовного дерева каждого кластера. Результаты тестирований работы данного алгоритма.
-
Решение практических заданий по дискретной математике
Представление с помощью кругов Эйлера множественного выражения. Законы и свойства алгебры множеств, упрощение выражений. Система функций, ее возможные базисы. Минимизирование булевой функции. Метод Квайна – Мак-Класки. Определение хроматического числа.
-
Графическое представление графа
Алгоритм перехода к графическому представлению для неориентированного графа. Количество вершин неориентированного графа. Чтение из матрицы смежностей. Связи между вершинами в матрице. Задание координат вершин в зависимости от количества секторов.
-
Построение матрицы достижимости
Понятие матрицы достижимости и связности. Операция удаления вершины из графа. Алгоритм выделения компонент сильной связности. Разработка и листинг программы на языке Turbo Pascal, осуществляющей вычисление матрицы достижимости по заданному алгоритму.
-
Поиск оптимального пути в ненагруженном орграфе
Понятия теории графов. Понятия смежности, инцидентности и степени. Маршруты и пути. Матрицы смежности и инцедентности. Алгоритм поиска минимального пути в ненагруженном ориентированном орграфе на любом языке программирования, алгоритм фронта волны.
-
Моделирование систем
Составление таблицы значений функции алгебры логики и нахождение всех существенных переменных. Связный ориентированный и взвешенный граф. Построение функции полиномом Жегалкина. Текст программы для алгоритма Дейкстры. Определение единиц и нулей функции.
-
Операции на графах
Операции на графах позволяют образовывать новые графы из нескольких более простых. Операции на графах без параллельных ребер. Объединение графов. Свойства операции объединения т, которые следуют из определения операции и свойств операций на множествах.
-
Передаточная функция дискретной системы
Определение связи между выходом и входом для непрерывных систем. Вычисление передаточной функции и основы структурного метода дискретной системы. Расчет передаточной функции дискретной системы с обратной связью. Передаточные функции цифровых алгоритмов.
-
Матрицы графов
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Кафедра информатики РЕФЕРАТ На тему: «Матрицы графов» МИНСК, 2008 В теоретико-множественной и геометрической форм определения (задания) графов, часто используется матричная форма их представления. Существуют различные виды матриц графов, однако все они, как правило, полностью передают основные свойства графов.
-
Графы
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ.