Викиконспекты - Вклад участника [ru]

Контактная схема

2014-01-08T08:03:05Z

217.118.78.108: /* Задача о минимизации контактной схемы */

Для математического описания электротехнических устройств, состоящих из контактов и промежуточных реле, функционирующих в дискретные моменты времени применяются ''контактные схемы''.

{{Определение
|definition =
'''Контактная схема''' (''англ.'' contact sheme) представляет собой ориентированный ациклический [[Основные определения теории графов|граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами'').
}}

==Принцип работы==
[[Файл:contact.png||right||200px]]
[[Файл:contactnot.png||right||200px]]
Зафиксируем некоторые значения переменным. Тогда '''замкнутыми''' называются ребра, на которых записана 1, ребра, на которых записан 0, называются '''разомкнутыми'''. Зафиксируем две вершины <tex>u</tex> и <tex>v</tex>. Тогда контактная схема вычисляет некоторую функцию <tex>f</tex> между вершинами <tex>u</tex> и <tex>v</tex>, равную 1 на тех наборах переменных, на которых между <tex>u</tex> и <tex>v</tex> есть путь по замкнутым ребрам.

==Построение контактных схем==
Любую булеву функцию можно представить в виде контактной схемы. Для этого необходимо привести её к ДНФ или КНФ, а затем построить, используя комбинации 3 логических элементов:

* '''Конъюнкция''' [[Файл:multiply.png | 200px | right ]]
Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что
последовательное соединение полюсов соответствует операции конъюнкции.

* '''Дизъюнкция''' [[Файл:disjunction.png | 200 px | right]]
Результат дизъюнкции равен 0 только в случае, когда оба операнда равны 0. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению полюсов.

* '''Отрицание'''
Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.

==Задача о минимизации контактной схемы==
{{Определение
|definition =
Две контактные схемы называются '''эквивалентными''', если они реализуют одну и ту же булеву функцию.
}}

{{Определение
|definition =
'''Сложностью''' контактной схемы называется число
ее контактов.
}}
Задача минимизации контактных схем состоит в том, чтобы по данной схеме <tex>S</tex> найти схему <tex>T</tex> , эквивалентную <tex>S</tex> и имеющую наименьшую сложность.
Один из путей решения этой задачи состоит в следующем:
* Осуществляем переход от контактной схемы <tex>S</tex> к её булевой функции <tex>F(S)</tex>.
* Упрощаем <tex>F(S)</tex>, то есть отыскиваем функцию <tex>G</tex> (на том же базисе, что и <tex>F(S)</tex>), равносильную <tex>F(S)</tex> и содержащую меньше вхождений операций дизъюнкции и конъюнкции. Для этого используем основные законы алгебры логики: сочетательный и распределительный закон, правило де Моргана, правило операции переменной с её инверсией и др.
* Строим схему <tex>T</tex>, реализующую функцию <tex>G</tex>.

==Ссылки==
* [http://pgap.chat.ru/zap/zap116.htm Контактные схемы]
* [http://www.encyclopediaofmath.org/index.php/Contact_scheme Encyclopedia of Math {{---}} Contact sheme]

==Литература==
* Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике {{---}} М.:"ФИЗМАТЛИД", 2009 {{---}} стр. 312

QpmtnCmax

2012-06-09T19:01:10Z

217.118.78.108: /* Алгоритм построения расписания */

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>

==Постановка задачи==
Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.

Цель - выполнить все как можно быстрее.

1. Найдем нижнюю границу времени выполнения.

2. Составим оптимальное расписание.

==Алгоритм построения расписания==

<tex> P_i = p_1 + ... + p_i</tex>

<tex> S_j = s_1 + ... + s_j</tex>

Где <tex>i = 1 ... n</tex>; <tex>j = 1 ... m</tex>; <tex> n \ge m</tex>;

Необходимое условие для выполнения всех работ в интервале <tex>[0;T]</tex>:

<tex> P_n = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или <tex>P_n/S_m \le T</tex>

Нижняя граница <tex>C_{max}</tex> :

<tex>w = \max</tex>{<tex>\max\limits_{j=1}^{m-1} P_i/S_j, P_n/S_m</tex>}

Далее построим расписание, которое достигает нашей оценки <tex>w</tex>, с помощью Level-алгоритма.

Level - алгоритм:

<tex>t \leftarrow 0 </tex>
'''WHILE''' существуют работы с положительным level
Assign(t)
<tex>t1 \leftarrow min(s>t |</tex>работа выполненная в момент времени <tex> s)</tex>
<tex>t2 \leftarrow min(s>t | p_i(t)>p_j(t)</tex> && <tex> p_i(s) == p_j(s))</tex>
<tex> t \leftarrow min(t1,t2) </tex>
Построение расписания

Функция <tex>Assign(t)</tex>:

<tex>J = </tex>{<tex>i|p_i(t)>0</tex>}
<tex>M = </tex>{<tex>M_1,...,M_m</tex>}
'''WHILE''' (<tex>J</tex> != 0 && <tex>M</tex> != 0)
Найти множество работ <tex>I</tex> подмножество <tex>J</tex> ,level которых максимальный
<tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|)
Назначаем работы из мн-ва <tex>I</tex> на <tex>r</tex> самых быстрых машин из мн-ва <tex>M</tex>
<tex>J \leftarrow J</tex>\<tex>I</tex>
удаляем из мн-ва <tex>M</tex> <tex>r</tex> самых быстрых машин

==Пример==
[[Файл:qptmncmax.png|400px|thumb|right|Картинка к примеру]]

Пусть у нас есть 5 работ и 4 станка. Покажем работу алгоритма для данного случая.

В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения <tex>J_1-J_4</tex> на станках <tex>M_1-M_4</tex> соответственно. В момент времени <tex>t_1</tex> <tex>lvl</tex> 4-ой работы опускается до времени выполнения 5-ой работы. С этого момента начинаем обрабатывать работы <tex> J_4,J_5</tex> на одном станке: <tex>M_4</tex>. В момент времени <tex>t_2</tex> происходит похожая ситуация. С этого момента времени работы <tex> J_1,J_2</tex> выполняются синхронно на двух станках <tex> M_1,M_2</tex>. Далее работы не пересекаются друг с другом и каждая заканчивается на ранее выделенных им станках.

==Время работы==
Level-алгоритм вызывает функцию Assign(t) в самом худшем случае <tex>O(n)</tex> раз. Функция Assign(t) выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>.

==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8

QpmtnCmax

2012-06-09T08:45:29Z

217.118.78.108: /* Алгоритм построения расписания */

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>

==Постановка задачи==
Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.

Цель - выполнить все как можно быстрее.

1. Найдем нижнюю границу времени выполнения.

2. Составим оптимальное расписание.

==Алгоритм построения расписания==

<tex> P_i = p_1 + ... + p_i</tex>

<tex> S_j = p_1 + ... + p_j</tex>

Где <tex>i = 1 ... n</tex>; <tex>j = 1 ... m</tex>; <tex> n \ge m</tex>;

Необходимое условие для выполнения всех работ в интервале <tex>[0;T]</tex>:

<tex> P_n = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или <tex>P_n/S_m \le T</tex>

Нижняя граница <tex>C_{max}</tex> :

<tex>w = \max</tex>{<tex>\max\limits_{j=1}^{m-1} P_i/S_j, P_n/S_m</tex>}

Далее построим расписание, которое достигает нашей оценки <tex>w</tex>, с помощью Level-алгоритма.

Level - алгоритм:

<tex>t \leftarrow 0 </tex>
'''WHILE''' существуют работы с положительным level
Assign(t)
<tex>t1 \leftarrow min(s>t |</tex>работа выполненная в момент времени <tex> s)</tex>
<tex>t2 \leftarrow min(s>t | p_i(t)>p_j(t)</tex> && <tex> p_i(s) == p_j(s))</tex>
<tex> t \leftarrow min(t1,t2) </tex>
Построение расписания

Функция <tex>Assign(t)</tex>:

<tex>J = </tex>{<tex>i|p_i(t)>0</tex>}
<tex>M = </tex>{<tex>M_1,...,M_m</tex>}
'''WHILE''' (<tex>J</tex> != 0 && <tex>M</tex> != 0)
Найти множество работ <tex>I</tex> подмножество <tex>J</tex> ,level которых максимальный
<tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|)
Назначаем работы из мн-ва <tex>I</tex> на <tex>r</tex> самых быстрых машин из мн-ва <tex>M</tex>
<tex>J \leftarrow J</tex>\<tex>I</tex>
удаляем из мн-ва <tex>M</tex> <tex>r</tex> самых быстрых машин

==Пример==
[[Файл:qptmncmax.png|400px|thumb|right|Картинка к примеру]]

Пусть у нас есть 5 работ и 4 станка. Покажем работу алгоритма для данного случая.

В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения <tex>J_1-J_4</tex> на станках <tex>M_1-M_4</tex> соответственно. В момент времени <tex>t_1</tex> <tex>lvl</tex> 4-ой работы опускается до времени выполнения 5-ой работы. С этого момента начинаем обрабатывать работы <tex> J_4,J_5</tex> на одном станке: <tex>M_4</tex>. В момент времени <tex>t_2</tex> происходит похожая ситуация. С этого момента времени работы <tex> J_1,J_2</tex> выполняются синхронно на двух станках <tex> M_1,M_2</tex>. Далее работы не пересекаются друг с другом и каждая заканчивается на ранее выделенных им станках.

==Время работы==
Level-алгоритм вызывает функцию Assign(t) в самом худшем случае <tex>O(n)</tex> раз. Функция Assign(t) выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>.

==Литература==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8