Imre Simon
Sexta-feira, 15 de agosto de 2003, 14:00
Sala 266, Bloco A, IME-USP
Resumo:
Este seminário explorará dois algoritmos sobre sequências cuja eficiência computacional é surpreendente. Um deles encontra o Menor Ancestor Comum em árvores em tempo O(1) (depois de um pré-processamento linear) e o outro encontra, em tempo O(|A|+|x|+|y|), um Separador Mais Curto, ou seja, uma palavra de comprimento mínimo que seja subpalavra de x sse não for subpalavra de y, com x e y palavras dadas sobre o alfabeto A. (Subpalavra aqui significa uma subsequência não necessariamente contígua.)