• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Десяткове кодування

Дерева є важливим|поважним| видом графів. За допомогою дерев описуються бази даних, дерева моделюють алгоритми і програми, їх використовують в електротехніці, хімії. Одним з актуальних завдань|задач| в епоху комп'ютерних і телекомунікаційних мереж|сітей| є|з'являється,являється| завдання|задача| стиснення|стискування| інформації. Сюди входить і кодування дерев. Компактний запис дерева, що повністю описує його структуру, може істотно|суттєво| спростити як передачу інформації про дерево, так і роботу з|із| ним.

Існує безліч способів кодування дерев. Розглянемо|розгледимо| одне з простих кодувань помічених|позначених| дерев з|із| виділеним коренем – десяткову.

Кодуючи дерево, дотримуємося наступних|таких| правил.

1. Кодування починається з кореня і закінчується в корені.

2. Кожен крок на одну дугу від кореня кодується одиницею.

3. У вузлі вибираємо напрям|направлення| на вершину з|із| меншим номером.

4. Досягнувши листа|аркуша|, йдемо назад, кодуючи кожен крок нулем.

5. При русі назад у вузлі завжди вибираємо напрям|направлення| на непройдену|минути,спливти| вершину з|із| меншим номером.

Кодування в такій формі виходить достатньо|досить| компактним, проте|однак| воне не несе в собі інформації про номери вершин дерева. Існують аналогічні кодування, де замість одиниць в такому ж порядку|ладі| проставляються номери або назви вершин.

Є дерева, для яких нескладно вивести формулу десяткового кодування. Розглянемо|розгледимо|, наприклад, графи-зірки , що є|з'являються,являються| повними|цілковитими| дводольними графами, одна з доль яких складається з однієї вершини. Інше позначення зірок – .

На мал. 14.2 показані зірки, а також приведені їх двійкові і десяткові кодування. Корінь дерева розташовується в центральній вершині зірки. Легко одержати|отримати| загальну|спільну| формулу:

. (14.1)

Мал. 14.2

Якщо корінь помістити в будь-якій з висячих вершин, то код такого дерева виражатиметься|виказуватиметься,висловлюватиметься| великим числом. Більш того|більше того|, існує залежність . Аналогічно розглядаються|розглядуються| і ланцюги|цепи| (мал. 14.3). Ланцюги|цепи| позначаються|значаться| як .

Мал. 14.3

У зірках тільки|лише| два варіанти розташування кореня з|із| різними десятковими кодуваннями. У ланцюзі|цепі| ж число варіантів кодувань залежно від положення|становища| кореня росте|зростає| із|із| збільшенням n. Розглянемо|розгледимо| найпростіший варіант, розташувавши корінь в кінцевій вершині (листі|аркуші|). Для одержимо|отримаємо| двійкове кодування 10 і десяткову 2, для – 1100 і 12, для – 111000 і 56, для – 11110000 і 240. Загальна|спільна| формула для десяткового кодування ланцюга|цепу| з|із| коренем в кінцевій вершині має вигляд|вид|

. (14.2)

Приклад|зразок| 14.2. Записати десятковий код дерева, зображеного|змальованого| на мал. 14.4, з|із| коренем у вершині 3.

Мал. 14.4

Рішення|розв'язання,вирішення,розв'язування|. На підставі правила кодування, рухаючись|сунучись| по дереву, проставимо в код одиниці і нулі. При русі з|із| кореня 3 до вершини 7 проходимо|минаємо,спливаємо| чотири ребра. У код записуємо|занотовуємо| чотири одиниці: 1111. Повертаючись від вершини 7 до вершини 2 (до найближчої розвилки), проходимо|минаємо,спливаємо| три ребра. Записуємо|занотовуємо| в код три нулі: 000. Від вершини 2 до 5 і далі до 8 (менший номер): 11; від 8 назад до 5 і від 5 до 9: 01; від 9 до кореня 3: 000.

І, нарешті|урешті|, від 3 до 6 і назад: 10. У результаті, збираючи всі разом, одержимо|отримаємо| двійковий код дерева:

1 111 000 110 100 010.

Розбиваючи число на трійки, переводимо|перекладаємо,переказуємо| одержане|отримане| двійкове уявлення|виставу,подання,представлення| у вісімкове. Одержуємо|отримуємо| . Потім переводимо|перекладаємо,переказуємо| це число в десяткове: .

Читайте також:

1. Автоматичне кодування.
2. Алфавітне кодування
3. Аудит розрахунків за відшкодуванням завданих збитків
4. Бюджетне відшкодування ПДВ
5. Види зобов’язань з відшкодування шкоди, що виникають незалежно від вини заподіювача шкоди
6. Вимоги до методів цифрового кодування
7. Відшкодування збитків - це відновлення майнового стану учас­ника господарських правовідносин за рахунок іншого суб'єкта — правопорушника.
8. Відшкодування збитків постраждалим.
9. Відшкодування збитків як вид господарсько-правової відповідальності: поняття, сфера застосування, порядок реєстрації.
10. Відшкодування збитку, завданого з вини працівника
11. Відшкодування моральної шкоди
12. Відшкодування шкоди

Переглядів: 1080