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

Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция

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

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

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

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

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. Відшкодування шкоди

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