МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
|||||||
Десяткове кодуванняДерева є важливим|поважним| видом графів. За допомогою дерев описуються бази даних, дерева моделюють алгоритми і програми, їх використовують в електротехніці, хімії. Одним з актуальних завдань|задач| в епоху комп'ютерних і телекомунікаційних мереж|сітей| є|з'являється,являється| завдання|задача| стиснення|стискування| інформації. Сюди входить і кодування дерев. Компактний запис дерева, що повністю описує його структуру, може істотно|суттєво| спростити як передачу інформації про дерево, так і роботу з|із| ним. Існує безліч способів кодування дерев. Розглянемо|розгледимо| одне з простих кодувань помічених|позначених| дерев з|із| виділеним коренем – десяткову. Кодуючи дерево, дотримуємося наступних|таких| правил. 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. Розбиваючи число на трійки, переводимо|перекладаємо,переказуємо| одержане|отримане| двійкове уявлення|виставу,подання,представлення| у вісімкове. Одержуємо|отримуємо| . Потім переводимо|перекладаємо,переказуємо| це число в десяткове: . Читайте також:
|
||||||||
|