Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

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

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

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

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




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

<== попередня сторінка | наступна сторінка ==>
Центроїд дерева | Поняття і оцінка запасів

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.003 сек.