Estadística 17/18
Tras la discusión de clase del otro día sobre los problemas básicos, aquí tenéis una lista:
- El problema de la ordenación. Dados n números, ordenarlos en el menor tiempo posible.
- El problema de la suma. Dados n números, encontrar si hay tres cuya suma sea cero.
- El problema de los puntos colineales. Dados n puntos en el plano, encontrar si hay tres sobre la misma recta.
- El problema del agujero en los triángulos. Dados n triángulos, ¿existe un agujero en su unión?
- El problema de la triangulación. Dados n puntos en el plano, construir una triangulación sobre ellos en el menor tiempo posible.
- El problema del hueco mínimo. Dados n números, encontrar la menor distancia entre ellos.
- El problema del hueco máximo. Dados n números, encontrar la mayor distancia entre ellos.
- El problema de la máxima intersección entre intervalos. Dados n intervalos en la recta real, encontrar la intersección no vacía con el número máximo de intervalos.
- El problema de los k vecinos más cercanos. Dados n puntos en el plano y un punto aparte, encontrar los k vecinos más cercanos al punto aparte.
- El problema de la intersección de rectas. Dados n semiplanos, construir su intersección en el menor tiempo posible.
- El problema de la búsqueda de cadenas. Dada una cadena C, determinar si otra cadena S es subcadena de C y si lo es encontrar todas sus ocurrencias en C. Todo ello, claro, en tiempo óptimo.
- El problema de la recta en la pantalla digital. Dada una recta y=ax+b, dibujarla en la pantalla digital (píxeles) de modo que se parezca lo más posible a la recta original. Este problema se puede formular con el círculo también.
- El problema de la mediana. Dados n números, encontrar la mediana en tiempo lineal.
- El problema de la subcadena común más larga. Dadas n cadenas de caracteres, encontrar la subcadena común más larga.
- El problema del camino mínimo en grafos. Dado un grafo con n vértices, encontrar el árbol de camino mínimos entre sus vértices.
- El problema de la intersección de segmentos. Dado un conjunto de n segmentos en el plano, construir su intersección en el menor tiempo posible.
- El problema del hueco máximo. Dados n números, encontrar la mayor distancia entre ellos.
- El problema del par más cercano Dados n puntos en el plano, encontrar los dos puntos más cercanos en el menor tiempo posible.
- El problema de las k medias. Dados n números, encontrar una agrupación en k grupos de modo que las distancias de cada punto a sus vecinos en el grupo sean lo más pequeñas posible.
- El problema de la generación de números aleatorios. Dada una distribución de probabilidad, generar números acorde a esa distribución.
- El problema de la distribución regular. Dados n cajas, distribuir tan regularmente como sea posible k objetos en esas n cajas.
- El problema del máximo común divisor. Dados dos números, hallar su máximo común divisor en el menor tiempo posible.
- El problema del diagrama de Voronoi. Dados n puntos en el plano, construir el conjunto de los puntos más cercanos a cada uno que al resto.
- El problema de la localización. Dado un grafo plano, diseñar un algoritmo óptimo para dado un punto, encontrar la cara en que se encuentra en el grafo.
- El problema de la galería de arte. Dado un polígono simple (la galería), poner guardias de modo que todo punto de la galería esté vigilada.
- El problema de los servicios buenos. Dado un grafo, que representa una ciudad, poner un servicio bueno (hospital, centro comercial) de modo que la máxima distancia desde cada punto del grafo se minimice.
- El problema de los servicios nocivos Dado un grafo, que representa una ciudad, poner un servicio nocivo (planta de residuos, iglesia) de modo que la mínima distancia desde cada punto del grafo se maximice.
- El problema del vomitador. Dado un vomitador, ¿cómo conseguir que deje de serlo?