Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
ОС - ВУМ
Содержание
- 1. ОС - ВУМ
- 2. Чтобы найти процессы, конфликтующие по данным, построим граф.Граф конфликтов: вершины – процессы, ребра общие данные.X1X2X3X4X5X6
- 3. Один из подходов к решению задачи –
- 4. Алгоритм Магу(X1+X2) (X2+X3) (X1+X4) (X2+X4) (X2+X5) (X4+X5)
- 5. ВУМX1X2X3X4X5X6X2*X3*X4+ X1*X3*X4*X5+ X1*X2*X3*X5 + X2*X4*X6 + X1*X2*X5*X6M1=
- 6. Раскраска графа – алгоритм ЗыковаM1= X- X2*X3*X4={X1,X5,X6}M2=
- 7. Решение задачиX1X2X3X4X5X6(М1+М4) *М2*(М4+М5) (М3+М5) (М1+М4) (М1+М2+М3)М2*М4*М5М2М4М5
- 8. Скачать презентанцию
Чтобы найти процессы, конфликтующие по данным, построим граф.Граф конфликтов: вершины – процессы, ребра общие данные.X1X2X3X4X5X6
Слайды и текст этой презентации
Слайд 1Пусть существуют несколько процессов, взаимодействующих по данным
Как организовать их одновременную
работу ?
Слайд 2Чтобы найти процессы, конфликтующие по данным, построим граф.
Граф конфликтов: вершины
– процессы, ребра общие данные.
X1
X2
X3
X4
X5
X6
Слайд 3Один из подходов к решению задачи – нахождение внутренне устойчивых
множеств и раскраска графа конфликтов.
X1
X2
X3
X4
X5
X6
Внутренне устойчивое множество (ВУМ) –
подмножество несвязанных
вершин графа (не имеющих общих ребер). Максимальное ВУМ – ВУМ, которое теряет свойство внутренней устойчивости при добавлении любой вершины из оставшихся.
Для нахождения ВУМ воспользуемся алгоритмом Магу.
Запишем логическое выражение: в ВУМ может войти либо одна, либо другая вершина каждого ребра. Минимизируем это выражение. Если полученные множества вершин исключить из множества всех вершин графа, то останется ВУМ.
Слайд 4Алгоритм Магу
(X1+X2) (X2+X3) (X1+X4) (X2+X4) (X2+X5) (X4+X5) (X3+X6)=
(X2+X1*X3*X4*X5)(X4+X1*X5)(X3+X6)=
(X2*X4+X1*X3*X4*X5+X1*X2*X5+ X1*X3*X4*X5)(X3+X6)=
(X2*X4+X1*X3*X4*X5+X1*X2*X5)(X3+X6)=
(X2*X3*X4+ X1*X3*X4*X5+
X1*X2*X3*X5 + X2*X4*X6 + X1*X3*X4*X5*X6 +X1*X2*X5*X6)=
X2*X3*X4+ X1*X3*X4*X5+ X1*X2*X3*X5 + X2*X4*X6
+ X1*X2*X5*X6ПОМОЩЬ: X*X=X, X+X=X, X1+X1*X2=X1,
(X1+X2)(X1+X3)=X1+X2*X3
Слайд 5ВУМ
X1
X2
X3
X4
X5
X6
X2*X3*X4+ X1*X3*X4*X5+ X1*X2*X3*X5 + X2*X4*X6 + X1*X2*X5*X6
M1= X- X2*X3*X4={X1,X5,X6}
M2= X
- X1*X3*X4*X5 ={X2,X6}
M3= X - X1*X2*X3*X5 ={X4,X6}
M4= X - X2*X4*X6={X1,X3,X5}
M5=
X - X1*X2*X5*X6 ={X3,X4}|M1|=|M4|=3 число внутренней устойчивости
1
2
3
4
5
Входящие в ВУМ вершины не конфликтуют по данным!!!
Слайд 6Раскраска графа – алгоритм Зыкова
M1= X- X2*X3*X4={X1,X5,X6}
M2= X - X1*X3*X4*X5
={X2,X6}
M3= X - X1*X2*X3*X5 ={X4,X6}
M4= X - X2*X4*X6={X1,X3,X5}
M5= X -
X1*X2*X5*X6 ={X3,X4}Раскрасить граф – поставить в соответствие каждой вершине графа некоторый цвет так, чтобы смежные вершины были окрашены в разные цвета.
Запишем логическое выражение: каждая вершина может быть окрашена в один из цветов (ВУМ). Минимизируем это выражение. Наименьшее количество цветов – хроматическое число графа.
(М1+М4) *М2*(М4+М5) (М3+М5) (М1+М4) (М1+М2+М3)=
(М1*М2 + М2*М4) * (М5+М3*М4)=
М1*М2*М5+М2*М4*М5+М1*М2*М3*М4+М2*М3*М4*М5=
М1*М2*М5+М2*М4*М5+М1*М2*М3*М4
1
2
3
|C2|=3 (хроматическое число графа)
