2018-01-08
573
Самокорректирующиеся алгоритмы – это алгоритмы, которые правильно и точно решают задачу даже при наличии сбоев (т.е. ошибок при выполнении)
Задача сортировки массива.
Предположим, что ошибки возможны при сравнении элементов массива. Причем, всего возможно <=k ошибок. N- число элементов в массиве.
Алгоритм:
1. Отсортировать массив с помощью алгоритма слияние. Полученный массив обозначим pi(0)
2. Повторить 2k раз шаги:
2.1 Верификация – последовательный просмотр pi(i) и сравниваем попарно его элементы: a(1) и a(2),a(2) и a(3), т.д. В массиве pi(i) до тех пор пока не найдем пару a(j)>a(j+1). Такая пара (ошибка) называется инверсией.
· Если инверсия найдена, то запоминаем в t номер j и переходим к шагу 2.2
· Если инверсия не найдена, то полагаем pi(i+1)=pi(i) и переходим к следующей итерации
2.2 Если найдена инверсия – исправление. Массив pi(i) разрезается на 2 части в одну a(1)..a(t), а во вторую a(t+1)..a(n). Эти две части сливаются по алгоритму слияния, образуя массив pi(i+1). Переходим на следующий шаг итерации.
3. Получили 2k+1 массив: pi(0) и pi(1), …, pi(2k). Согласно теореме, среди них ищем повторяющийся min k+1 раз массив – он и является ответом.
Пример:
m=(6, 4, 3, 8, 1, 2, 7, 5) k=3
1. 4, 6 3,8 -> 3, 8, 4, 6 (допущена первая ошибка)
1,2 5,7 -> 1, 2, 5, 7
pi(0) = 1, 2, 3, 5, 7, 8, 4, 6
2. 1, 2, 3, 5, 7, 8, 4, 6
pi(1) = 1, 2, 4, 3, 5, 6, 7, 8 (допущена вторая ошибка)
pi(2) = 1, 2, 3, 4, 5, 6, 7, 8 (допущена третья ошибка)
pi(3) = 1, 2, 3, 4, 5, 6, 7, 8
pi(4) = 1, 2, 3, 4, 5, 6, 7, 8
pi(5) = 1, 2, 3, 4, 5, 6, 7, 8
pi(6) = 1, 2, 3, 4, 5, 6, 7, 8
3. Среди 7 массивов 5 одинаковых.
Оценим сложность:
1. O(n*logn)
2. 2k((n-1)+n)=2k(2n-1) - O(nk)
3. O(nk)
t(α)= O(n*log n +nk)
Следствие:
Если k пропорционально log n, то самокорректирующийся алгоритм имеет такой же порядок роста функции сложности как и алгоритм без коррекции.
Для задачи поиска max элемента оптимальным самокорректирующимся алгоритмом является алгоритм тривиального дублирования.
