Алгоритм Уоршала.

Алгоритм Уоршала ефективно обчислює матрицю W^(k) за матрицею W^(k-1). Шлях із a_i в a_j з внутрішніми вершинами в множині {a₁, a₂, …, a_k}. Зазначимо, що W^(k-1). Шлях із a_i в a_j з внутрішніми вершинами в множині {a₁, a₂,.., a_k} існує лише в 2 випадках:

1) Якщо існує шлях із a_i в a_j з внутрішніми вершинами в множині {a₁, a₂, …, a_k-1}.

2) Якщо існує шлях із а_і в а_к та з а_к в а_j і кожний з цих шляхів має внутрішні вершини лише в множині {a₁, a₂, …, a_k}.

Алгоритм Уоршала:

Присвоєння початкових значень.

Крок 1. Виконати W: =M_R, k: =0.

Ітерація.

Крок 2. Виконати k: =k+1.

Крок 3. Для всіх i< > k таких, що w_ik=1 і для всіх j виконати операцію w_ij: =w_ikvw_kj.

Перевірка закінчення.

Крок 4. Якщо k=n, то зупинились. Отримано розв’язок W = M_R*. Інакше – перейти до кроку 2.

Результат роботи алгоритму – матриця M_R* рефлексивного замикання відношення R.

20. Постановка проблеми кодування, її значення в інформатиці. Алфавітне і рівномірне кодування. Достатні умови однозначності алфавітного кодування.

Нехай заданий алфавіт А={a₁,.., a_r}, який складається з скінченної кількості букв. Скінченну послідовність символів алфавіту А: α = називають словом в алфавіті А, а число l – довжиною слова α. Довжину слова α позначають l(α). Множину всіх слів в алфавіті А позначають через А^*. Порожнє слово не містить жодної букви, його позначають λ, λ єА^*, l(λ)=0, λ не належить А.

Якщо α =α ₁α ₂, то α ₁ називають початком, або префіксом слова α, а α ₂ – закінченням, або постфіксом слова α.

Алфавітне кодування.

Алфавітне кодування задають схемою (або таблицею кодів) σ:

а₁ -> β ₁,

a₂ -> β ₂,

…..

a_r -> β _r,

де а_і є А, β _і є В^*, і=1, …, r. Схема σ задає відповідність між буквами алфавіту А і деякими словами в алфавіті В. Вона визначає алфавітне кодування так: кожному слову α = з S ставиться у відповідність слово β = . Це слово β називають кодом слова α. Слова β ₁, …, β _r називають елементарними кодами.

Рівномірне кодування.

Рівномірне кодування з параметрами k та n визначають так. Повідомлення α розбивають на блоки довжини k:

, де s< =k (останній блок може бути коротший, у такому разі спосіб його кодування спеціально обумовлюється), x_iєА, і=1, …, mk+s. Блоки довжини k розглядають як букви деякого алфавіту (таких блоків є, очевидно, r^k, оскільки, алфавіт А складається з r букв) і кодують словами в алфавіті В однакової довжини n за схемою рівномірного кодування σ _{k, n}:

….

Надлишковістю схеми σ _{k, n} на символ повідомлення називають величину R=(n-k)/k=n/k -1.

21. Властивості однозначного алфавітного кодування. Нерівність Крафта-Макміллана.

Розглянемо схему алфавітного кодування σ і різні слова, складені з елементарних кодів. Схему σ називають роздільною, якщо з рівності

випливає, що k=l, i_t=j_t для кожного t=1,.., k, тобто будь-яке слово, складене з елементарних кодів, єдиним способом розкладання на елементарні коди. Очевидно, що алфавітне кодування з роздільною схемою допускає однозначне декодування. Схему σ називають префіксною, якщо для будь-яких i, j (i, j= 1, …, r, i< > j) елементарний код β _і не є префіксом елементарного коду β _j.

Т-ма. Префіксна схема є роздільною.

Т-ма. (Нерівність Макмілана). Якщо схема алфавітного кодування σ роздільна, то

, l_i=l(β _i).

Д-ня. Позначимо L=max{l₁, l₂, …, l_r}. Запишемо r-тий степінь лівої частини нерівності.

^r.

Розкривши дужки, отримаємо суму

, де (i₁, …, i_r) – різні набори номерів елементарних кодів. Позначимо через v(r, m) кількість доданків вигляду 1/2^m, які входять у цю суму, тут m= . Для деяких m може бути v(r, m)=0. Зведемо подібні члени й отримаємо суму

. Кожному доданку вигляду можна однозначно спів ставити код вигляду _. Це слово складається з r елементарних кодів і має довжину m. Отже, v(r, m) – це к-ть деяких слів вигляду , таких, що l()=m. Оскільки схема σ роздільна, то v(r, m)< =2^m. Можемо записати

. Отже, для кожного r виконується нерівність ^r< =rL, звідси

22. Задача оптимального кодування. Метод Фано побудови «економних» кодів.

Нехай заданий алфавіт А={a₁,.., a_r} і розподіл ймовірностей Р=(р₁,.., р_r) появи букв у повідомленні. Тут р_і ймовірність появи букви а_і. Не зменшуючи загальності, можна вважати, що

р₁> =p₂> =…> =p_r> 0,

тобто можна одразу виключити букви, які не можуть з’явитись у повідомленні, і впорядкувати букви за спаданням ймовірностей їхньої появи. Крім того р₁+…+р_r=1.

, називають середньою довжиною кодування σ для розподілу ймовірностей Р.

Алгоритм Фано:

1. Упорядковуємо букви алфавіту А за спаданням ймовірностей їхньої появи в повідомленні.

2. Розбиваємо множину букв, записаних у вказаному порядку, на 2 послідовності так, щоб сумарні ймовірності кожної з них були якомога ближчі одна до одної. Кожній букві з першої частини приписуємо символ 0, другої – 1. Далі так само чинять з кожною частиною, якщо вона містить принаймні 2 букви. Процедуру продовжуємо доти, доки вся множина не буде розбита на окремі букви.

Алгоритм Фано має просту інтерпретацію за допомогою бінарного дерева. Від кореня відходять 2 ребра, одне з яких позначене символом 0, друге – 1. Ці 2 ребра відповідають розбиттю множини всіх букв на 2 майже рівно ймовірні частини, одній з яких спів ставляють символ 0, а другій – 1. Ребра, що виходять із вершин наступного рівня, відповідають розбиттю отриманих частин знову на 2 майже рівно ймовірні послідовні частини. Цей процес продовжують до моменту, коли множина букв буде розбита на окремі букви. Кожний листок дерева відповідає деякому елементарному коді. Щоб записати цей код потрібно пройти простий шлях від кореня до відповідного листка.