Идентификация деревьев - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Идентификация деревьев. Доклад-сообщение содержит 11 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Идентификация деревьев Выполнили студенты 2 курса Высшей Школы ИТИС группы 11-401 Бобринская Екатерина, Анисимова Юлия, Татарских Роман

Слайд 2

Описание слайда:

Содержание Какой граф является деревом? Постановка задачи Представление деревьев По корневому признаку Алгоритмы проверки деревьев на изоморфизм Алгоритм Эдмондса Алгоритм сравнения. Графическое представление работы двух алгоритмов Заключение

Слайд 3

Описание слайда:

Какой граф является деревом? Дерево представляет собой граф, который является связным и не имеет циклов

Слайд 4

Описание слайда:

Постановка задачи Задача идентификации графов, а в частности деревьев, является одной из основных задач теории графов. Одна из целей – выявить алгоритм, сложность которого не будет превышать степенную функцию, который бы определял, являются ли два конечных графа одинаковыми(в абстрактном смысле), то есть изоморфными

Слайд 5

Описание слайда:

Слайд 6

Описание слайда:

Представление деревьев В виде матрицы смежности

Слайд 7

Описание слайда:

Слайд 8

Описание слайда:

Алгоритм Эдмондса Данный алгоритм идентификации деревьев опирается на теорему Эдмондса, которая гласит, что два дерева являются изоморфными тогда и только тогда, когда совпадают их центральные кортежи. Итак, алгоритм состоит в следующем: деревья кортежируются с помощью процедуры если центральные кортежи совпадают, то деревья изоморфны. В противном случае, они не изоморфны.

Слайд 9

Описание слайда:

Алгоритм сравнения Задача алгоритма сравнения состоит в том, чтобы суметь “увидеть” структуру деревьев и сравнивать именно её, а не конкретные значения вершин. Каждой вершине в соответствие ставится ряд чисел {x,y,{a1,a2,a3,…,an}}, где x - уровень вершины по высоте; y - ее “отцовый” уровень, т.е. длина максимальной линии потомков; {a1,…,an} - ряд “отцовых” уровней её сыновей. Важно учесть: 1. при сравнении этих массивов не важен порядковый номер элемента, т.е. элементу 2 одного массива может соответствовать элемент 3 второго массива; 2. не важен порядок элементов ряда «отцовых» уровней сыновей

Слайд 10

Описание слайда:

Графическое представление работы двух алгоритмов

Слайд 11

Описание слайда:

Заключение Из данных, приведенных на графике можно сделать вывод, что по времени работы алгоритм сравнения значительно опережает алгоритм Эдмондса. Однако на небольшом числе вершин графа (до 600-700) алгоритмы работают примерно одинаково. Это можно объяснить погрешностью, вызванной различными системными процессами.

Теги Идентификация деревьев

Похожие презентации