18. Задача о рюкзаке

Вход:

1.n видов предметов, которыe имеет веса w₁,…,w_n и стоимости с₁,…c_n;

2.рюкзак размера R.

Нужно унести в рюкзаке предметы наибольшей суммарной стоимости

Пусть– количество предметовi-го вида.

+…+® max

+…+£ R

Будем строить матрицу A размера n´(R+1). A[i][j] – максимальная стоимость предметов

из множества {1,…,i}, которые занимают в рюкзаке объем не более j.

A[n][R] - ?

A[i][0] = 0, A[1][j] = ?

Утверждение.

A[i][j] = max{m_ic_i + A[i-1][j - m_iw_i], где максимум берется по всем 0£m_i£j/w_i

Трудоемкость - О()

Алгоритм неполиномиальный, например если R = (2n+1 – размер входа).

Но в реальности R ограничен, тогда алгоритм полиномиальный. Такие алгоритмы называются псевдополиномиальными.

19. Алгоритм Штрассена умножения матриц Задача: перемножить две матрицы n на n.Стандартное умножение – O(n³).Предположим для простоты, что n – степень двойки

AB = C

C_1,1=A_1,1B_1,1+A_1,2B_2,1

………………………….

C_2,2=A_2,1B_1,2+A_2,2B_2,2

T(n) – трудоемкость алгоритма умножения матриц T(n) = 8T(n/2) + 4*n²/4 . Решение этого рекуррентного уравнения – O(n³). Пусть мы умеем перемножать матрицы 2 на 2 с помощью m умножений и a сложений .

T(n) = mT(n/2) + a*n²/4 Лемма. T(n) = O(n^logm)

Лемма. Умножение двух матриц размера 2 на 2 можно выполнить с помощью 7 умножений и 18 сложений (вычитаний)

Теорема. Умножение двух матриц размера n на n можно выполнить за время O(n^log7)»O(n^2,81)

В наст время сущ алгор с трудоемкост O(n^2,376)

20. Определение. Машина Тьюринга – это семерка (Γ,b,Q,q₀,q_y,q_n,), где Γ – множество символов, bΓ – пустой символ, Q – конечное множество состояний, q₀,q_y,q_nQ – начальное и конечные состояния, : (Q\{q_y,q_n})ΓQΓ{-1,0,1}