Моделі та структури даних (стр. 3 из 3)

Бінарне дерево

Виконати її, створивши бінарне дерево, кількість вузлів якого визначена відповідно до варіанту №15. Навести зображення дерева. Деревоподібна архітектура має найменший діаметр серед всіх існуючих, який дорівнює для бінарного дерева 2lg ( (P+1) /2) - відстань між двома листами, шлях між якими проходить через корінь. Для k-арних дерев діаметр зменшується зі збільшенням k. Недоліком деревоподібних мереж є те, що обмін даними між процесами відбувається за лінійний час, а процес-корінь є вузьким горлом при передачі інформації. Багатопроцесорний комп'ютер з паралельною обробкою інформації називається деревовидною машиною (tree machine) [33], якщо його процесори сполучені зв'язками так, що утворюється топологія повного бінарного дерева. Такий комп'ютер має 2d-1 процесорних елементів для деякого d, які розбиті на d рівнів, пронумерованих від 1 до d. Кожний процесор на рівні j, 1ЈjЈd, зв'язаний з єдиним процесором на рівні j-1 (батьком), та з двома процесорами на рівні j+1 (синами). Зв'язки між процесами розташовані таким чином, що безпосередньо обмінюватися інформацією можуть лише батько з сином. Єдиний процесор на першому рівні називається коренем в топології дерева, а процесори на рівні d - листами. Корінь не має батька, а листи не мають синів. На малюнку 15 зображена топологія деревовидної машини з d=4 рівнями, яка містить 24-1 = 15 процесорних елементів.

Закінчили виконання практичної частини контрольної роботи

Висновок

У виконаній роботі було розглянуто процеси пошуку інформацій та розроблено структури даних для ефективного зберігання та обробки інформації. Як приклад розглянуто бінарне дерево. Це динамічна структура даних, розмір якої обмежується тільки розміром віртуальної пам'яті комп'ютера. Бінарні дерева забезпечують пошук конкретного значення, максимуму, мінімуму, попереднього, наступного, операції вставки та видалення елемента. Розглянуті у роботі бінарні структури широко використовуються у житті, наприклад це різноманітні "ієрархічні структури", які нині широко використовуються в багатьох комп'ютерних завданнях. На даний час також розвивається граматичний аналіз, в основі якого і знаходяться принципи бінарних дерев. Граматичний аналіз на даний час широко використовується у сучасних пошукових алгоритмах.

Список використаної літератури

1. Баррон Д. Рекурсивные методы в программировании, - М.: 1974

2. Дмитриева М.В., Кубенский А.А. Элементы современного программирования, - СПб.: 1991.

3. Барашенков В.В. Анализ и преобразование операторных схем алгоритмов: учебное пособие. - Л.: ЛЭТИ, 1979.

4. Кинг Д. Создание еффективного программного обеспечения. - М.: Мир, 1991.

5. Барашенков В.В. Интерпретация операторных схем алгоритмов. - Л.: ЛЭТИ, 1978.

6. Бентли Дж. Жемчужины творчества программистов. - М.: Мир, 1990.

7. Шауман А.М. Основы машинной арифметики. - 1979.

8. Ахо, Альфред В. и др. Построение и анализ вычислительных алгоритмов. - М.: Мир, 1979

9. Криницкий Н.А. Программирование и алгоритмические языки. - 1975.

10. Прикладные вопросы системного анализа. Межвузовский тематический сборник. Вып.2. Куйбышев, 1976.

11. Автоматическое построение ассоциативного списка со сжатием информации. - К., 1976.

12. Квиттнер П. Задачи, программы, вычисления, результаты. - М.: Мир, 1980.

13. Шауман А.М. Основы машинной арифметики. - 1979.

14. Малоземов В.Н. Певный А.Б. Рекуррентные вычисления. - Л., изд. ун-та, 1976.