- •16. Обход n-арного дерева. Алгоритмы обхода n-арного дерева.
- •17.Бинарные деревья – основные определения, свойства и теоремы.
- •18,19.Не рекурсивные алгоритмы обхода бинарного дерева.
- •20.Поиск в упорядоченных таблицах. Последовательный поиск в массиве.
- •21.Поиск в упорядоченных таблицах. Двоичный поиск в массиве. Фибоначчиев поиск. Интерполяционный поиск.
- •22. Поиск в линейном списке.
- •23.Двоичное дерево поиска. Свойства. Основные операции.
- •Iterative_Tree_Search(t,k).
- •24. Добавление элемента в двоичном дереве поиска.
- •25. Удаление элемента в двоичном дереве поиска.
- •26. Абстрактная таблица. Основные операции. Способ реализации.
- •27. Авл – деревья. Свойства. Вращение. Высота авл-дерева (теорема) Определение и свойства авл-дерева
- •Авл - дерево
- •Повороты при балансировке
- •Алгоритм на псевдокоде
- •Алгоритм на псевдокоде
- •29. Удаление вершины в авл – дереве.
- •Алгоритм на псевдокоде
- •30. Красно – черные деревья. Свойства. Вращение. Высота красно – черного дерева.
- •Повороты
- •Операции поворота в бинарном дереве поиска
- •31. Добавление вершины в красно – черном дереве.
- •32. Удаление вершины в красно – черном дереве.
- •33. 2-3 Деревья. Основные свойства. Высота 2-3 дерева.
- •34 Обход 2-3 дерева.
- •35 Добавление элемента в 2 – 3 дерево.
- •36 Удаление элемента в 2 – 3 дереве.
- •37 2 – 3 – 4 Деревья. Основные свойства. Высота 2 – 3 – 4 дерева.
- •38 Добавление элемента в 2 – 3 – 4 дерево.
- •39. Стратегии внутренней сортировки.
- •40. Турнирная сортировка.
- •41. Пирамидальная сортировка.
- •42. Вставка с убывающим шагом.
- •43. Быстрая сортировка.
- •44. Быстрая двоичная сортировка.
- •45. Цифровая сортировка.
- •46. Карманная (блочная) сортировка.
- •47. Сортировка подсчетом
- •48. Сортировка слиянием. Рекурсивный алгоритм
- •49. Нижняя граница вычислительной сложности алгоритмов сортировки.
- •50. Поиск в глубину в графе. Рекурсивный алгоритм.
- •51. Поиск в ширину в графе. Не рекурсивный алгоритм.
- •52. Топологическая сортировка. Алгоритм топологической сортировки.
- •58. Стягивающие деревья. Нахождение стягивающего дерева методом поиска в ширину
- •59. Стягивающие деревья. Нахождение стягивающего дерева методом поиска в глубину.
- •60.Минимальные покрывающие деревья. Алгоритм Прима
- •61.Минимальные покрывающие деревья. Алгоритм Крускала.
- •62. Нахождение кратчайших путей в графе. Алгоритм Форда – Беллмана
- •63 Поиск кратчайших путей в графе. Алгоритм Дэйкстры.
- •64 Пути в бесконтурном графе.
- •65 Алгоритм Флойда поиска кратчайших путей между всеми парами вершин
- •66. Открытое хеширование.
- •67. Хеш-функции (ключи как натуральные числа, деление с остатком, умножение).
- •68. Закрытое хеширование. (Линейная последовательность проб. Квадратичная последовательность проб. Двойное хеширование).
- •69 Алгоритм Кнута-Морриса-Пратта.
- •70 Поиск подстрок. Алгоритм Бойера-Мура.
- •71. Поиск подстрок. Алгоритм Рабина-Карпа
- •72 Равномерный и неравномерный код. Префиксное кодирование.
- •73. Алгоритм Шеннона – Фано
- •74. Сжатие информации. Метод Хаффмана.
- •75. Исчерпывающий перебор. Задачи коммивояжера. Задача о назначениях.
- •77. Метод ветвей и границ. Задача о назначениях. Задача о рюкзаке. Задача коммивояжера.
- •Постановка задачи коммивояжера
- •Алгоритм решения задачи коммивояжера Жадный алгоритм
- •Полный перебор
- •78. Динамическое программирование. Восходящее и нисходящее динамическое программирование
- •79.Задача определения наиболее длинной общей подпоследовательности.
- •80. Перемножение последовательности матриц.
69 Алгоритм Кнута-Морриса-Пратта.
Пусть дан текст в виде массива T[n] и образец (то что ищем) P[1…m]; mn. Символы принадлежат алфавиту в бинарном коде; в текстовом файле.
Р входит в Т со сдвигом S, если T[S+1…S+m]=P[1…m]; S от 0 до n-m, такой сдвиг называется допустимым.
#T=abcabaabc;
P=abaa;
Pabaa, сдвиг S=3.
Пусть дана строка символов X[1…n], тогда для любой пары i, j; 1 определяем подстроку X[i…j]=X[i] X[i+1]…X[j].
Будем говорить, что подстрока X[i…j], начинается с позиции i и её длина равна j-i+1, если величина меньше чем n, то подстрока называется собственной подстрокой строки X.
(сигма) X=
Для произвольного целого j от 0 до n подстрока X[1…j] называется префиксом подстроки.
Если j<n собственный префикс подстроки X.
Для произвольного целого i от 1 до n+1 подстрока X[i…n] называется суффиксом строки X. Если i>1 то подстрока называется собственным суффиксом X.
Например, X=abaab
-префиксы a, ab, aba, abaa, abaab;
-суфиксы b, ab, aab, baab, abaab=X.
Алгоритм поиска образца:
Алгоритм NSM (T[1…n], P[1…m])
for S=0 to n-m do;
if P[1…m]=T[S+1…S+m] then;
printf “подстрока Р входит в Т”.
Вычислительная сложность: O((n-m+1)m).
Алгоритм КМР для поиска:
Префикс функция ассоциирующаяся с образом Р несет информацию, где в Р встречаются префиксы строки, использование этой информации не считывает заведомо не подходящие сдвиги.
#Т=bacbababababcbab
P=ababaca, сдвиг = 4
T[S+1…S+q]=P[1…q]
Некоторые последующие сдвиги будут недостимыми.
CPF(p[1..m])
s[1]←0
for q=2 to m do
k←s[q-1]
while (P[q]≠P[k+1]) and (k>0) do
k←s[k]
if (P[q]≠P[k+1] and (k=0) then s[q] ←0
else s[q] ←k+1
end for
return s
KMP(T[1..n],P[1..m])
s←CPF(P)
q←0
for k=1 to n do
while T[k]≠P
q←s[q]
if T[k]=P[q+1] then
q←q+1
if q=m then
printf “Образец входит со сдвигом”,k-m
q←s[q]
end for
70 Поиск подстрок. Алгоритм Бойера-Мура.
Использование алгоритма Кнута-Морисса-Пратта в большинстве случаев поиска в обычных текстах весьма незначителен. Метод же, предложенный Р. Боуером и Д. Муром в 1975 г., улучшает обработку самого плохого случая.
БМ-поиск основывается на необычном соображении сравнение символов начинается с конца слова, а не с начала. Как и в случае КМП-поиска, слово перед фактическим поиском трансформируется в некоторую таблицу. Пусть для каждого символа x из алфавита величина dx расстояние от самого правого в слове вхождения x до правого конца слова. Представим себе, что обнаружено расхождение между словом и текстом. В этом случае слово сразу же можно сдвинуть вправо на dpM-1 позиций, т.е. на число позиций, скорее всего большее единицы. Если несовпадающий символ текста в слове вообще не встречается, то сдвиг становится даже больше, а именно сдвигать можно на длину всего слова.
Например,
T=ABCABCABFABCABD
P=ABCABD (сравниваем то что подчеркнуто, идем с конца, не совпало D с C, сдвиг =3, чтоб С=С)
ABCABD (не совпало D и F, так как F нет в образце)
ABCABD(полное совпадение слово найдено)
CLOF(p[1..m], sum) sum это значок суммы
for all a sum do
l[a]←0
for k=1 to m do
l[P[k]] ←k
return l
CGSF(p[1..m])
s←CPF(P)
P’ ← обращение строки P
S’ ← CPF(P’)
For j=0 to m do
Y[j] ←m-s[m]
For k=1 to m do
J ← m-s’[k]
Y[j] ← min(y[j],k-s’[k])
End for
Return y
BM(T[1..n],P[1..m])
L ← CLOF(P,m,sum)
Y ← CGSF(p,m)
S ← 0
While S<=n-m do
k←m
while (k>0) and (P[k]=T[S+k]) do
k←k-1
if k=0 then
printf “Образец со сдвигом”,S
s←s+y[0]
else s←s+max(y[k],k-y[T[s+k]])
end while