Portal de Programas de Pós-Graduação (UFABC)

SIGAA - Sistema Integrado de Gestão de Atividades Acadêmicas

PPGCCM PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO FUNDAÇÃO UNIVERSIDADE FEDERAL DO ABC Phone: 11 4996-8337 E-mail: poscomp@ufabc.edu.br http://propg.ufabc.edu.br/ppgccm

Banca de DEFESA: FERNANDO HENRIQUE SANCHES

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : FERNANDO HENRIQUE SANCHES
DATA : 08/02/2019
HORA: 14:00
LOCAL: Sala 301, 3º andar do Bloco B, campus Santo André
TÍTULO:

Analysis of Decomposition Algorithms for the Tree Edit Distance Problem

PÁGINAS: 98
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Teoria da Computação
ESPECIALIDADE: Análise de Algoritmos e Complexidade de Computação
RESUMO:

The Tree Edit Distance (TED) problem is a generalization of the Levenshtein Distance (String Edit Distance). In the TED we are given two rooted, labelled trees A and B, and we want to know the minimum cost of a sequence of operations that transforms A

into B by inserting, deleting or relabelling nodes. In this work we analyze some algorithms of the family of Decomposition Algorithms: Zhang-Shasha’s, Klein’s, and Demaine’s. We revisit the proofs of some of their lemmas, aiming to bring a clearer version when possible. We also present a working implementation of Klein’s algorithm operating over Euler strings, as described in his original work.

MEMBROS DA BANCA:
Presidente - 1760938 - DANIEL MORGATO MARTIN
Interno - 1934625 - JESUS PASCUAL MENA CHALCO
Externo à Instituição - DANIEL DE ANGELIS CORDEIRO - USP

Notícia cadastrada em: 08/01/2019 09:54