0 к Л6 большинство.pptx - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему 0 к Л6 большинство.pptx. Доклад-сообщение содержит 18 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

ВЕРИФИКАЦИЯ ПРОГРАММ ДВС Лектор - С.А. Ивановский

Слайд 2

Описание слайда:

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

Слайд 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

Слайд 4

Описание слайда:

Пояснения Элемент a в массиве Х [1 .. п] является элементом большинства ттогда, когда a появляется более n / 2 раз в массиве X, то есть, по крайней мере n/2 если n нечётное n/2 + 1 = n/2 + 1 если n чётное Примечания: элемент большинства является элементом с наибольшей частотой, но обратное не верно.

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Вариант рандомизированного алгоритма Случайно выбираем i (равновероятно), а затем проверяем, удовлетворяет ли xi условию большинства. do j = random(n); // Выбор 1

Слайд 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 > ½.

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

«Дерандомизация» Идея: За основу берется рандомизированный алгоритм и случайный выбор заменяется на нерандомизированный (детерминированный) Выбор кандидата Проверка – является ли кандидат элементом большинства

Слайд 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

Слайд 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 “нет”;

Слайд 12

Описание слайда:

Функция Candidate(m) { j = m; c =x[m]; count = 1; While ( (j0)) { j ++; if (x[j]==c) count++; else count--; } if (j==n) return c; else return candidate(j+1); }

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

Не рекурсивная функция Candid3 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; }

Слайд 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 (!)

Слайд 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}