0 к Л6 большинство.pptx

Сентябрь 3, 2022

Главная
Алгебра
0 к Л6 большинство.pptx

Содержание

2. Пример к Лекции 5 Задача о большинстве массива 14.04.2015 О схемах программ
3. Пример: массив с большинством Определение: массив x1, x2, …, xn содержит большинство, если более половины его
4. Пояснения Элемент a в массиве Х [1 .. п] является элементом большинства ттогда, когда a появляется
5. Решения Простой алгоритм: для каждого элемента подсчитывать число вхождений, пока не встретится элемент, образующий большинство. Сложность
6. Вариант рандомизированного алгоритма Случайно выбираем i (равновероятно), а затем проверяем, удовлетворяет ли xi условию большинства. do
7. Сложность рандомизированного алгоритма Фиксируем размер входа n. Множество всех возможных сценариев – множество кортежей (i1, i2,
8. Рекуррентное уравнение Средние затраты t=t(n) есть t = P*n + (1-P)*(t + n), где P -
9. «Дерандомизация» Идея: За основу берется рандомизированный алгоритм и случайный выбор заменяется на нерандомизированный (детерминированный) Выбор кандидата
10. Наблюдения (наводящие соображения) Если два различных элемента удаляются из массива X, то большинство старого массива остается
11. Algorithm: Majority Вход: x[1..n] Выход: Элемент большинства, если большинство существует, иначе ответ «нет». ------------------------------------------------------------------- c =
12. Функция Candidate(m) { j = m; c =x[m]; count = 1; While ( (j 0)) {
13. Не рекурсивная функция Candid1 { count = 1; c = x[1]; for (j = 2; j
14. Не рекурсивная функция Candid2 { count = 0; // c = x[1]; for (j = 1;
15. int Majority(int X[], int n) {// C++, т.е. X[0..n-1] int Candidate; int i = 0; int
16. Примеры x[1..13] = 3131313131313 Count > 0, и имеется большинство x[13]=3 x[1..9] = 123456777 Count >
17. Продолжение x[1..9] = 555551234 55555 {count=5} 555551 {count=4} 5555512 {count=3} 55555123 {count=2} 555551234 {count=1} !!! x[1..9]
19. Скачать презентацию

Слайд 2

Пример к Лекции 5
Задача о большинстве массива
14.04.2015
О схемах программ

Слайд 3

Пример: массив с большинством
Определение: массив x1, x2, …, xn содержит большинство,

если более половины его элементов имеют равные значения.
Например:
1, 2, 1, 2, 1, 2, 1 ;
n = 7, N(1) = 4
2) 7, 2, 7, 9, 7, 7, 7, 8, 5, 7, 1, 7, 7, 6, 7, 7, 4, 4, 7, 3 ;
n = 20, N(7) = 11
Разрешена операция сравнения: = или ≠
Требуется: в массиве, содержащем большинство, найти хотя бы одно i (1<=i<=n), такое, что xi∈большинству значений массива x. [Представитель большинства - xi]
Нахождение элемента большинства = Finding the Majority Element

03.04.2015

Теория вычислительной сложности Лекция 5

Слайд 4

Пояснения
Элемент a в массиве Х [1 .. п] является элементом большинства

ттогда, когда a появляется более ⎣n / 2⎦ раз в массиве X, то есть, по крайней мере
⎡n/2⎤ если n нечётное
⎣n/2⎦ + 1 =
⎡n/2⎤ + 1 если n чётное
Примечания: элемент большинства является элементом с наибольшей частотой, но обратное не верно.

03.04.2015

Теория вычислительной сложности Лекция 5

Слайд 5

Решения
Простой алгоритм: для каждого элемента подсчитывать число вхождений, пока не встретится

элемент, образующий большинство. Сложность O(n2).
Сортировать массив, а затем сосчитать подряд стоящие равные элементы. Это занимает O(n log n). { ! Здесь используются сравнения}.
Найти медиану (⎡n/2⎤-наименьший элемент), которая (-ый) является элементом большинства (если оно есть). Это займет в худшем случае O(n), но с большим постоянным множителем, или в среднем O(n). { ! Здесь используются сравнения}.
?

03.04.2015

Теория вычислительной сложности Лекция 5

Слайд 6

Вариант рандомизированного алгоритма
Случайно выбираем i (равновероятно), а затем проверяем, удовлетворяет ли

xi условию большинства.
do
j = random(n); // Выбор 1<=j<=n
// проверка:
с = x[j];
k = 0;
for (i = 1; i<=n; i++ )
if(x[i]==c) k++;
while (k <= n/2);
Утверждаем, что сложность по числу сравнений < 2n.

03.04.2015

Теория вычислительной сложности Лекция 5

Слайд 7

Сложность рандомизированного алгоритма
Фиксируем размер входа n.
Множество всех возможных сценариев – множество

кортежей (i1, i2, …, ip-1, ip), p>=1 и iq∈1..n,
И при этом x[i1], x[i2], …, x[ip-1] – ∉большинству,
а x[ip] ∈большинству.
Вероятности сценариев:
Два события:
Первая попытка найти нужный индекс j – удачная,
Первая попытка найти нужный индекс j – Неудачная.
Пусть P=N/n, где N –число элементов большинства при входе n.
По условию P > ½.

03.04.2015

Теория вычислительной сложности Лекция 5

Слайд 8

Рекуррентное уравнение
Средние затраты t=t(n) есть
t = Pn + (1-P)(t +

n),
где
P - вероятность удачной попытки; при этом количество действий = n,
(1-P) - вероятность НЕудачной попытки; при этом количество действий = (t + n), т.е. от цикла for - количество действий = n и затем средние затраты t следующих попыток.
След.
t = n/P; и (P > ½) ⇒ t < 2n;

03.04.2015

Теория вычислительной сложности Лекция 5

Слайд 9

«Дерандомизация»
Идея: За основу берется рандомизированный алгоритм и случайный выбор заменяется на

нерандомизированный (детерминированный)
Выбор кандидата
Проверка – является ли кандидат элементом большинства

03.04.2015

Теория вычислительной сложности Лекция 5

Слайд 10

Наблюдения (наводящие соображения)
Если два различных элемента удаляются из массива X,

то большинство старого массива остается большинством и нового. Потому что самое худшее заключается в удалении одного элемента большинства (вместе с элементом меньшинства).
При этом размер большинства ⎣n/2⎦ +1 -1 > ⎣(n-2)/2⎦ .
Если большинство существует, то как минимум в двух позициях подряд находятся элементы большинства или X[n] является элементом большинства.
M D M D M D M D M D M D M D M D M D M D
M D M D M D M D M D M D M D M D M D M D M
M D M D M D M D M D M D M D M D M M D M D

03.04.2015

Теория вычислительной сложности Лекция 5

Слайд 11

Algorithm: Majority
Вход: x[1..n]
Выход: Элемент большинства, если большинство существует, иначе ответ «нет».
-------------------------------------------------------------------
c

= candidate(1); // находим лишь кандидата
int count = 0;
for (j = 1; j < n; j++)
if (x[j]==c) count++;
if (count > ⎣n/2⎦ ) return c;
else return “нет”;

03.04.2015

Теория вычислительной сложности Лекция 5

Слайд 12

Функция Candidate(m)
{
j = m; c =x[m]; count = 1;
While ( (j

&& (count>0)) {
j ++;
if (x[j]==c) count++;
else count--;
}
if (j==n) return c;
else return candidate(j+1);
}

03.04.2015

Теория вычислительной сложности Лекция 5

Слайд 13

Не рекурсивная функция Candid1
{
count = 1; c = x[1];
for (j

= 2; j if (count = 0) {count = 1; c = x[j];}
else if (x[j] == c) count++;
else count--;
}
return c;
}

03.04.2015

Теория вычислительной сложности Лекция 5

Слайд 14

Не рекурсивная функция Candid2
{
count = 0; // c = x[1];
for

(j = 1; j if (count = 0) {count = 1; c = x[j];}
else if (x[j] == c) count++;
else count--;
}
return c;
}

03.04.2015

Теория вычислительной сложности Лекция 5

Слайд 15

int Majority(int X[], int n)
{// C++, т.е. X[0..n-1]
int Candidate;
int i =

0;
int Count = 0;
while (i < n){
if ( Count == 0 ) {
Candidate = X[i];
Count = 1;
}
else if ( Candidate == X[i] ) Count++;
else Count--;
i++;
}
return Candidate;
}

03.04.2015

Теория вычислительной сложности Лекция 5

Не рекурсивная функция Candid3

Слайд 16

Примеры
x[1..13] = 3131313131313
Count > 0, и имеется большинство x[13]=3
x[1..9] = 123456777
Count

> 0 , но большинства нет!
3. x[1..9] = 123455555
12
34
5
55555 ⇒ с=5 count=5 > ⎣9/2⎦ = 4 (!)

03.04.2015

Теория вычислительной сложности Лекция 5

Слайд 17

Продолжение
x[1..9] = 555551234
55555 {count=5}
555551 {count=4}
5555512 {count=3}
55555123 {count=2}
555551234 {count=1} !!!
x[1..9]

= 515253545
51 {count=0}
52 {count=0}
… {count=0}
5 {count=1, j=9, c=5}

03.04.2015

Теория вычислительной сложности Лекция 5

0 к Л6 большинство.pptx

Содержание

Пример к Лекции 5Задача о большинстве массива14.04.2015О схемах программ

Пример: массив с большинствомОпределение: массив x1, x2, …, xn содержит большинство,

Пояснения Элемент a в массиве Х [1 .. п] является элементом большинства

РешенияПростой алгоритм: для каждого элемента подсчитывать число вхождений, пока не встретится

Вариант рандомизированного алгоритмаСлучайно выбираем i (равновероятно), а затем проверяем, удовлетворяет ли

Сложность рандомизированного алгоритмаФиксируем размер входа n.Множество всех возможных сценариев – множество

Рекуррентное уравнениеСредние затраты t=t(n) есть t = P*n + (1-P)*(t +

«Дерандомизация»Идея: За основу берется рандомизированный алгоритм и случайный выбор заменяется на

Наблюдения (наводящие соображения) Если два различных элемента удаляются из массива X,

Algorithm: MajorityВход: x[1..n]Выход: Элемент большинства, если большинство существует, иначе ответ «нет».-------------------------------------------------------------------c

Функция Candidate(m){ j = m; c =x[m]; count = 1; While ( (j

Не рекурсивная функция Candid1{ count = 1; c = x[1]; for (j

Не рекурсивная функция Candid2{ count = 0; // c = x[1]; for

int Majority(int X[], int n){// C++, т.е. X[0..n-1]int Candidate;int i =

Примерыx[1..13] = 3131313131313Count > 0, и имеется большинство x[13]=3x[1..9] = 123456777Count

Продолжение x[1..9] = 555551234 55555 {count=5} 555551 {count=4} 5555512 {count=3} 55555123 {count=2} 555551234 {count=1} !!! x[1..9]

Похожие презентации

Пример к Лекции 5
Задача о большинстве массива
14.04.2015
О схемах программ

Пример: массив с большинством
Определение: массив x1, x2, …, xn содержит большинство,

Пояснения
Элемент a в массиве Х [1 .. п] является элементом большинства

Решения
Простой алгоритм: для каждого элемента подсчитывать число вхождений, пока не встретится

Вариант рандомизированного алгоритма
Случайно выбираем i (равновероятно), а затем проверяем, удовлетворяет ли

Сложность рандомизированного алгоритма
Фиксируем размер входа n.
Множество всех возможных сценариев – множество

Рекуррентное уравнение
Средние затраты t=t(n) есть
t = Pn + (1-P)(t +

«Дерандомизация»
Идея: За основу берется рандомизированный алгоритм и случайный выбор заменяется на

Наблюдения (наводящие соображения)
Если два различных элемента удаляются из массива X,

Algorithm: Majority
Вход: x[1..n]
Выход: Элемент большинства, если большинство существует, иначе ответ «нет».
-------------------------------------------------------------------
c

Функция Candidate(m)
{
j = m; c =x[m]; count = 1;
While ( (j

Не рекурсивная функция Candid1
{
count = 1; c = x[1];
for (j

Не рекурсивная функция Candid2
{
count = 0; // c = x[1];
for

int Majority(int X[], int n)
{// C++, т.е. X[0..n-1]
int Candidate;
int i =

Примеры
x[1..13] = 3131313131313
Count > 0, и имеется большинство x[13]=3
x[1..9] = 123456777
Count

Продолжение
x[1..9] = 555551234
55555 {count=5}
555551 {count=4}
5555512 {count=3}
55555123 {count=2}
555551234 {count=1} !!!
x[1..9]