Análisis de Estructuras de Sufijos de Strings | Defensa de Trabajo Especial

Director: Luis FERRONI

Link de Google Meet: meet.google.com/nzp-rfdc-pyh

Resumen: El problema de desarrollar algoritmos que decidan si un cierto patrón o palabra aparece o no en un determinado texto es fundamental en ciencias de la computación. Diversos algoritmos se han desarrollado en las últimas décadas para resolver este problema (y sus múltiples variantes). Un análisis detallado de las complejidades temporales y espaciales de dichos algoritmos revela que, en la práctica, teniendo en cuenta el volumen de información y la potencia de los procesadores al día de la fecha, algoritmos de fuerza bruta no son viables en la mayoría de los casos. En particular, dos algoritmos fundacionales en esta área, los llamados suffix tree y suffix array, proveen soluciones que sobrepasan con creces la performance de otros algoritmos más básicos. Durante el desarrollo de este trabajo, se realizó un estudio detallado de los algoritmos de "suffix array" y "longest common prefix array" propuestos en 1993 por Manber y Myers, analizando a nivel teórico su complejidad temporal y espacial, y presentando modificaciones de los mismos que mejoran su performance. Luego, se utilizaron los mismos para proveer soluciones a problemas del área que tienen considerable impacto en la vida real, realizando comparaciones de rendimiento contra algoritmos de fuerza bruta.