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

QpmtnCmax

2012-06-09T19:38:14Z

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

<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> p_i</tex> - вес i-ой работы ;<tex> s_j</tex> - скорость работы j-oй машины ; <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>}

Будем назвать Level-ом работы <tex> lvl(p_i(t)) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </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-09T19:30:33Z

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

<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> p_i</tex> - вес i-ой работы ;<tex> s_j</tex> - скорость работы j-oй машины ; <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:42:01Z

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

<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''' существуют работы с положительным lvl
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> ,lvl которых максимальный
<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

Теорема Бейкера — Гилла — Соловэя

2012-06-04T13:49:35Z

217.118.78.115: /* Следствия */

==Теорема==
{{ Теорема
| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.
| proof =
'''Существование оракула <tex>A</tex>'''

Рассмотрим [[PS-полнота языка верных булевых формул с кванторами (TQBF) | PS-полный язык <tex>\mathrm{TQBF}</tex>]].

<tex>
\mathrm{P^{TQBF}} \overset{(1)}{\subseteq}
\mathrm{NP^{TQBF}} \overset{(2)}{\subseteq}
\mathrm{NPS^{TQBF}} \overset{(3)}{=}
\mathrm{PS^{TQBF}} \overset{(4)}{=}
\mathrm{PS} \overset{(5)}{\subseteq}
\mathrm{P^{TQBF}}
\Rightarrow
</tex><br/>
<tex>\Rightarrow \mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>.

# <tex> \mathrm{P} \subseteq \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subseteq \mathrm{NP^{TQBF}} </tex>.
# Так как <tex>S(p,x) \le T(p, x)</tex>, то <tex> \mathrm{NP} \subseteq \mathrm{NPS} \Rightarrow \mathrm{NP^{TQBF}} \subseteq \mathrm{NPS^{TQBF}} </tex>.
# По [[ Класс PS. Теорема Сэвича. Совпадение классов NPS и PS | теореме Сэвича]] <tex> \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} </tex>.
# <tex> \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = \mathrm{PS} </tex>.
# <tex> \mathrm{TQBF} \in \mathrm{PSC} \Rightarrow \mathrm{PS} \subseteq \mathrm{P^{TQBF}} </tex>.

Следовательно, <tex>\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>

----

'''Существование оракула <tex>B</tex>'''

Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n \bigm| \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B</tex> выполнено <tex>U_B \in \mathrm{NP}^B</tex> (сертификатом будет слово нужной длины из <tex>B</tex>). Построим такое множество <tex>B</tex>, что <tex>U_B \not\in \mathrm{P}^B</tex>.

Пронумеруем некоторым образом все машины Тьюринга, работающие за полиномиальное время и имеющие доступ к оракулу языка <tex>B</tex>, и рассмотрим последовательность <tex>M_i</tex>, в которой каждая машина Тьюринга встречается бесконечное число раз. Очевидно, это можно сделать в силу счетности множества машин Тьюринга. Построение множества <tex>B</tex> разделим на счетное число стадий. Будем строить <tex>B</tex> так, чтобы на <tex>i</tex>-й стадии было выполнено: существует слово <tex>x</tex>, что <tex>T(M_i, x) \ge 2^{n-1}</tex>. Это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P}^B</tex>, так как <tex>2^n</tex> растет быстрее любого полинома.
* 0-я стадия: <tex>B \leftarrow \emptyset </tex>.
* <tex>i</tex>-я стадия. Стадии с 0-й по <tex>(i-1)</tex>-ю пройдены, <tex>B</tex> — конечное множество слов. Пусть самое длинное из них состоит из <tex>(n-1)</tex>-го символа. Запустим машину <tex>M_i</tex> на входе <tex>1^n</tex> на <tex>2^{n-1}</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, будем определять принадлежность этого слова к <tex>B</tex> следующим образом:
** если принадлежность <tex>x</tex> множеству <tex>B</tex> была определена на одной из предыдущих стадий, то она сохраняется;
** если принадлежность <tex>x</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in B</tex>.

Но <tex>M_i</tex> могла остановится раньше, чем за <tex>2^{n-1}</tex> шагов и вернуть какое-либо значение. Так как <tex>B</tex> строится с условием, что для выбранного <tex>x = 1^n</tex> выполнено: <tex>T(M_i,x) \ge 2^{n-1}</tex>, то решение машины о принадлежности слова должно быть неверным:
* если <tex>M_i</tex> приняла слово, то исключим из <tex>B</tex> все слова вида <tex>\{0,1\}^n</tex>;
* Если <tex>M_i</tex> отклонила слово, то выберем слово <tex>x</tex> длины <tex>n</tex>, принадлежность которого <tex>B</tex> еще не определено. Добавим <tex>x</tex> в <tex>B</tex>. Такое слово всегда найдется, так как на предыдущий шагах мы могли сделать не более, чем <tex>2^n-1</tex> запросов к оракулу (то есть определить принадлежность <tex>B</tex> не более <tex>2^n-1</tex> слов длины <tex>n</tex>), а всего слов длины n <tex>2^n</tex>.

Во множестве <tex>B</tex> на каждой стадии содержится конечное число элементов, так как на каждой стадии в <tex>B</tex> может быть добавлено не более чем <tex>2^{n-1}+1</tex> слов.

Из построения получаем, что для любой машины Тьюринга <tex>M</tex> существует бесконечно много слов из <tex>U_B</tex>, для которых <tex>M</tex> не может принять верное решение о принадлежности слова <tex>U_B</tex> за время, меньшее <tex>2^{n-1}</tex>. Следовательно, <tex>U_B \not\in \mathrm{P}^B</tex>.

}}

==Следствие==

{{ Утверждение
| statement = Если существует решение вопроса равенства <tex>\mathrm{P}</tex> и <tex> \mathrm{NP}</tex>, то оно не должно "релятивизоваться".
}}

Для доказательства строгого включения классов часто используется метод диагонализации. Однако утверждения полученные при помощи данной техники могут быть "релятивизованы". То есть при "разрешении" машине Тьюринга доступа к оракулу некоторого языка доказанное соотношение классов сохраняется. Однако соотношение <tex>\mathrm{P}</tex> и <tex>\mathrm{NP}</tex> не должно "релятивизоваться" по теореме Бейкера-Гилла-Соловэя, следовательно, метод диагонализации не применим для решения этого вопроса.

[[Категория: Теория сложности]]

Теорема Бейкера — Гилла — Соловэя

2012-04-15T09:13:03Z

217.118.78.115: Новая страница: «{{ Теорема | statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <t...»

{{ Теорема
| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>
}}