Me voy a dar una conferencia sobre Alon y Schieber Tech Informe de la computación semigroup productos (Óptimo de Preprocesamiento para Responder a un Producto On-Line de Consultas). Básicamente, dada una lista de elementos $a_1,\ldots,a_n$ y un atado $k$, muestran cómo el preprocesar los elementos, de forma que más tarde es posible de manera eficiente calcular el producto de cualquier sublista $a_i\cdot\ldots\cdot a_j$ mediante la realización de sólo $k$ de los productos.
Para motivar este algoritmo estoy buscando ejemplos de semigroups donde: 1. Es plausible que uno tiene una lista de elementos y se desea calcular productos de sublistas. 2. El semigroup no es un grupo (ya que el problema es trivial para los grupos). 3. El espacio de la complejidad del producto no abrumar a la vez la complejidad de la computación directamente (por ejemplo, en la concatenación de cadenas, solo copiar el resultado a la salida toma el mismo tiempo de computación que incluso sin preprocesamiento).
Hasta ahora sólo tengo $\min$ $\max$ y la multiplicación de la matriz como ejemplos. Estoy buscando algo más "sexy", preferiblemente relacionados con Ciencias de la computación (tal vez algo que ver con los gráficos o los árboles). También, para $\min$ $\max$ existe un algoritmo mejor, así que realmente no puedo usarlas para motivar este algoritmo.
