🗊Презентация Идентификация деревьев

Категория: Математика
Нажмите для полного просмотра!
Идентификация деревьев, слайд №1Идентификация деревьев, слайд №2Идентификация деревьев, слайд №3Идентификация деревьев, слайд №4Идентификация деревьев, слайд №5Идентификация деревьев, слайд №6Идентификация деревьев, слайд №7Идентификация деревьев, слайд №8Идентификация деревьев, слайд №9Идентификация деревьев, слайд №10Идентификация деревьев, слайд №11
Скачать
Вы можете ознакомиться и скачать презентацию на тему Идентификация деревьев. Доклад-сообщение содержит 11 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


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

Слайд 2


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

Слайд 3


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

Слайд 4


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

Слайд 5


Идентификация деревьев, слайд №5
Описание слайда:

Слайд 6


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

Слайд 7


Идентификация деревьев, слайд №7
Описание слайда:

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию