String matching with finite automata

Finite automata

A finite automaton M is a 5-tuple (Q, q ₀, A, Σ, δ), where

· Q is a finite set of states,

· q ₀ ∈ Q is the start state,

· A ⊆ Q is a distinguished set of accepting states,

· Σ is a finite input alphabet,

· δ is a function from Q × Σ into Q, called the transition function of M.

δ(q,a)

Рис 4

final- state function φ (w) – состояние, в которое перейдет автомат прочитав строку w.

φ (ε)	=	q 0,
φ (wa)	=	δ (φ (w), a)

 

String-matching automata

Рис 5

σ (x) = max { k: P_k ⊐ x }.

FINITE-AUTOMATON-MATCHER(T, δ, m)1 n ← length [ T ]2 q ← 03 for i ← 1 to n 4 do q ← δ (q, T [ i ])5    if q = m 6       then print "Pattern occurs with shift" i - m

 

O(n)

 

COMPUTE-TRANSITION-FUNCTION(P, Σ)1 m ← length [ P ]2 for q ← 0 to m 3 do for each character a ∈ Σ4       do k ← min(m + 1, q + 2)5          repeat k ← k - 16            until P_k ⊐ P_qa 7          δ (q, a) ← k 8 return δ

O (m ³ |Σ|)

 

The Knuth-Morris-Pratt algorithm

Рис 6

Префикс-функция

k=π[ q ] = max {k: k < q and P_k ⊐ P_q }.

KMP-MATCHER(T, P) 1 n ← length [ T ] 2 m ← length [ P ] 3 π ← COMPUTE-PREFIX-FUNCTION(P) 4 q ← 0                     ▹Number of characters matched. 5 for i ← 1 to n             ▹Scan the text from left to right. 6 do while q > 0 and P [ q + 1] ≠ T [ i ] 7        do q ← π[ q ] ▹Next character does not match. 8    if P [ q + 1] = T [ i ] 9       then q ← q + 1 ▹Next character matches.10    if q = m                ▹Is all of P matched?11       then print "Pattern occurs with shift" i - m 12            q ← π[ q ] ▹Look for the next match.

O(n+m)

 

 

COMPUTE-PREFIX-FUNCTION(P) 1 m ← length [ P ] 2 π[1] ← 0 3 k ← 0 4 for q ← 2 to m 5 do while k > 0 and P [ k + 1] ≠ P [ q ] 6        do k ← π[ k ] 7     if P [ k + 1] = P [ q ] 8       then k ← k + 1 9    π[ q ] ← k 10 return π

 

 

Жадные алгоритмы

Задача о выборе процессов

c[ i,j] — количество процессов в подмножестве мак cмаксимального размера, состоящем из взаимно совместимых процессов в задаче S_ij.

 

Сортировки за линейное время

Сортировка подсчетом

COUNTING-SORT(A, B, k) 1 for i ← 0 to k 2 do C [ i ] ← 0 3 for j ← 1 to length [ A ] 4 do C [ A [ j ]] ← C [ A [ j ]] + 1 5 ▹ C [ i ] now contains the number of elements equal to i. 6 for i ← 1 to k 7 do C [ i ] ← C [ i ] + C [ i - 1] 8 ▹ C [ i ] now contains the number of elements less than or equal to i. 9 for j ← length [ A ] downto 110 do B [ C [ A [ j ]]] ← A [ j ]11   C [ A [ j ]] ← C [ A [ j ]] - 1

Цифровая сортировка

RADIX-SORT(A, d)1 for i ← 1 to d 2 do use a stable sort to sort array A on digit i

Сортировка вычерпыванием

BUCKET-SORT(A)1 n ← length [ A ]2 for i ← 1 to n 3 do insert A [ i ] into list B [⌊ n A [ i ]⌋]4 for i ← 0 to n - 15 do sort list B [ i ] with insertion sort6 concatenate the lists B [0], B [1],..., B [ n - 1] together in order

12 Быстрое преобразование Фурье (FFT)

 

Дескретное преобразование Фурье:

 

, k = 0…n-1

e^iu = cos(u) + i sin(u).

y = (y ₀, y ₁,..., y_{n -1}), a = (a ₀, a ₁,..., a_{n -1})

                                      (1)

A ^[0](x) = a ₀ + a ₂ x + a ₄ x ² + ··· + a_{n -2} x^{n /2-1},                    (2)

A ^[1](x) = a ₁ + a ₃ x + a ₅ x ² + ··· + a_{n -1} x^{n /2-1}.                     (3)

                                             (4)

,      (5)

,              (6)

,                       (7)

RECURSIVE-FFT(a)

 1 n ← length [ a ] ▹ n is a power of 2.

 2 if n = 1

 3   then return a

 4 w_n ← e ^{π i / n}

 5 w ← 1

 6 a ^[0] ← (a ₀, a ₂,..., a_{n -2})

 7 a ^[1] ← (a ₁, a ₃,..., a_{n -1})

 8 y ^[0] ← RECURSIVE-FFT(a ^[0])

 9 y ^[1] ← RECURSIVE-FFT(a ^[1])

10 for k ← 0 to n /2 - 1

11  do

12   

                   

13     w ← w w_n

14 return y

 

Без рекурсии:

 

 

 

 

ITERATIVE-FFT (a) 1 BIT-REVERSE-COPY (a, A) 2 n ← length [ a ] ▹ n is a power of 2. 3 for s ← 1 to lg n 4  do m ← 2 ^s 5    ω _m ← e ^{2 π i / m} 6    for k ← 0 to n - 1 by m 7         do ω ← 1 8              for j ← 0 to m /2 - 1 9                 do t ← ω A [ k + j + m /2]10                    u ← A [ k + j ]11                    A [ k + j ] ← u + t 12                    A [ k + j + m /2] ← u - t 13                    ω ← ω ω_m

 

 

Вопросы к экзамену 2010

 

1. Обратная польская запись. Построение и вычисление.
2. Управление динамической памятью.
3. Растеризация невыпуклого многоугольника
4. Топологическая сортировка.
5. Задача о “Ханойской башне”. Вывод формулы сложности.
6. Синтаксический анализ арифметического выражения
7. Перебор
8. Перестановки
9. Сокращение перебора. N ферзей.
10. Сокращение перебора. Задача о ходах коня.

11. Сокращение перебора. Задача о коммивояжере.12. Сокращение перебора. Раскраска карты.13. Сокращение перебора. Распространение ограничений и изменение порядка перебора14. Сокращение перебора. Укладка рюкзака.

1. Алгоритмы обхода бинарных деревьев, включая обход в ширину.
2. Сильноветвящиеся деревья и графы
3. Деревья двоичного поиска
4. Деревья с дополнительной информацией (Добавление с поддержкой числа узлов)
5. Деревья с дополнительной информацией (К-й наименьший и порядковый номер)
6. Динамическое программирование. Конвейер.
7. Динамическое программирование. Наименьшая сумма чисел на пути
8. Динамическое программирование. Умножение матриц
9. Динамическое программирование. Самая длинная общая подпоследовательность
10. АВЛ дерево
11. Красно-черное дерево
12. Treaps
13. Скошенные деревья
14. 2-3 дерево
15. 2-3+ дерево
16. В – деревья
17. Кучи (поддержка свойств и построение)
18. Очередь с приоритетами
19. Huffman коды
20. Кучи на 2-3+ деревьях
21. Биномиальные кучи (определение)
22. Биномиальные кучи (объединение, забрать min ключ, удаление)
23. Фибоначевы кучи
24. Структуры данных для непересекающихся множеств
25. Хеш-таблицы
26. CRC алгоритм
27. Табличный CRC алгоритм
28. Поиск подстроки. Алгоритм Рабина-Карпа.
29. Поиск подстроки с конечным автоматом.
30. Поиск подстроки. Алгритм Кнута-Мориса-Прата.
31. Быстрое преобразование Фурье

 

 

Перебор с возвратом

Вариант алгоритма перебора, на котором мы остановились в подразделе 2.1, называется перебором с возвратом. Слово ``возврат'' выражает то, что есл происходит возврат к последнему выбранному элементу и выбирается для него следующее значение.