Применение дискретной в информатикеРефераты >> Кибернетика >> Применение дискретной в информатике
Таблица 4 – Значение производной (5)
|
f(x,y) |
f( |
f(x,y) |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
0 |
0 |
0 |
|
1 |
0 |
1 |
Найдем производную по x,y
- (6)
- (7)
Для нахождения дифференциала функции (1) сначала построим таблицу истинности для функции (7) (таблица 8) и окончательным результатом будет таблица 9 для функции 6.
Таблица 5 - Таблица Истинности для функции (7)
| x | y | x&y |
|
|
|
|
|
| 0 | 0 | 0 | 1 | 1 |
0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 | 0 |
0 |
Таблица 6 – Значение производной 
|
f(x,y) |
f( |
f(x,y)Å f( |
|
0 |
1 |
1 |
|
0 |
0 |
0 |
|
0 |
0 |
0 |
|
1 |
0 |
1 |
2 ГРАФЫ
2.1 Алгоритм Дейкстра
Рассмотрим экономическую задачу: одна крупная компания решила поощрить своих работников и устроить всем работникам отдых в городе С. Для того чтобы приехать в город С необходимо проехать несколько промежуточных городов. Перед экспертами компании была поставлена задача найти оптимальный путь. Они определили расстояния между городами и построили неориентированный граф.
Если задачу перевести на язык математики, то получится, имеется n вершин и число ребер не меньше n-1. Если две вершины соединены, то они соединены только одним ребром.
Рисунок 2 – Исходный граф
Вершине A присваиваем постоянный ярлык 0. Далее приписываем вершинам смежные к A (B и I) временные ярлыки. Bременный ярлык вершины B равен 5; временный ярлык вершины I равен 4. Выбираем наименьший – это будет I, и делаем его постоянным. На рисунке он выделяется жирным шрифтом.
 |
Рисунок 3 – Нахождения первого присоединенного ребра
L(w)=4 далее назначаем временные ярлыки H и F и они соответственно будут равны 11 и 10, выбираем минимальный – это будет F, выделяем его и делаем его постоянным и так далее, пока не дойдем до G .
Рисунок 4-Резулитирующий граф
В результате получается, что кратчайший путь будет равен 13 и будет пролегать через A, I, F, G.
2.2 Жадный алгоритм
Было найдено новое месторождение нефти. Для разработки и соединения месторождения с нефтеперерабатывающими заводами был составлен примерный маршрут. Перед экономистами была поставлена задача определить максимальную загруженность линий. Если всю задачу перевести на графы, то получим, что имеется неориентированный помеченный граф.
Решить – эту задачу можно с помощью Жадного алгоритма.
Решением задачи будет следующий алгоритм. /6/
a. находится ребро с максимальным весом, из него составляется подграф. Ясно, что таковым является ребро с весом равным 14, соединяющее вершины D и E.
б. дальнейшим шагом находится следующее ребро с максимальным весом. Это ребро, соединяющее E и F (с весом 13)
в. присоединяется ребро, связывающее E и C (с весом 12)
г. присоединяется ребро, связывающее E и G (с весом 11)
д. присоединяется ребро, связывающее I и H (с весом 8)
е. присоединяется ребро, связывающее I и F (с весом 8)
ж. присоединяется ребро, связывающее A и B (с весом 6)
В результате получаем граф, изображенный на рисунке 5, который и будет примером применения жадного алгоритма.
 |
Скачать реферат
