Usted está aquí: Inicio / Actividades / Seminarios / Seminario Preguntón de Matemáticas Discretas / Actividades / Árboles crecientes aleatorios, su uso en el análisis de estructuras de datos

Árboles crecientes aleatorios, su uso en el análisis de estructuras de datos

Ponente: Laura Eslava
Institución: McGill University, Canadá
Tipo de Evento: Investigación

Cuándo 01/09/2015
de 17:00 a 18:00
Dónde Unidad Multidisciplinaria de Docencia e Investigación (UMDI), Aula 1. UNAM Campus Juriquilla, Querétaro
Agregar evento al calendario vCal
iCal
Una secuencia de árboles crecientes (T(n), n en N) consiste de árboles enraizados T(n) con n vértices y tal que T(n) contiene a T(n-1) para todo n en N. De esta manera, una secuencia (T(n), n en N) se puede considerar como la historia de un árbol cuyo número de vértices crece con el tiempo y, por lo tanto, ésta surge naturalmente en algoritmos de estructura de datos. 


En esta plática nos enfocaremos en tres algoritmos que dan lugar a los árboles binarios de búsqueda, árboles recursivos y árboles de estructura de datos para conjuntos disjuntos. Indicaremos cómo es que un enfoque probabilístico ayuda a analizar la eficiencia de dichos algoritmos y cómo es que estas tres clases de árboles están íntimamente relacionadas.