OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Brainstorm de Meta-Ideas ======

Brainstorm desordenado de ideas, de las cuales podría salir un artículo.

  * Heurística de conjunto-ordenación
  * Heurística de queries que "dividan parejo" el espacio de opciones [para problemas de teoría de información, golosa "generalmente buena" pero no óptima]
  * "Dar vuelta el sentido de la recursión", si eso ayuda en algo (puede pasar de no salir a salir. También es clave cuando hay que dar el i-ésimo lexicográfico).
  * "Idea china del binomial heap" (transforma un algoritmo para el problema estático, en un algoritmo para el problema dinámico con un overhead logarítmico)
  * Scaling (aplica por ejemplo a muchos algoritmos de grafos, notablemente Dinitz, pero es un principio general)
  * "Eliminación de dominados". [El valor generalmente está en que cuando el conjunto no tiene dominados queda con alguna propiedad buena y útil, como estar ordenado, ser convexo, etc]. Propiedad util generalmente: que borrar un dominado no cambie el conjunto de dominados (de los restantes). Eso hace que eliminar en cualquier orden siempre produzca el mismo conjunto final. Chull puede verse como un ejemplo de borrar dominados, con la def de que alguien está dominado si es combinación convexa de otros elementos del conjunto. Si no hay puntos repetidos se tiene la propiedad anterior. [Nacional OIA 2017, compradores y vendedores. Si uno tiene un mínimo más alto y además un precio más alto, nunca lo voy a querer usar.]
  * Reducciones entre problemas: "Desde el nuestro" (para resolverlo, haciéndolo más fácil que uno conocido) y "Hacia el nuestro" (para pensar cómo encararlo y cómo *no* encararlo, al concluir que es al menos tan difícil como algo conocido. Ejemplo, "este va a necesitar sí o sí un segment tree, o algo más difícil" o bien "Este problema es al menos tan difícil como este otro, que yo ya sé que no me sale")
  * "Subalgorithms": En definitiva es separar en casos el problema, y resolver cada caso con algoritmos bien distintos. Pero la división en casos puede no tener nada que ver con "la respuesta" que es más común, sino con "el tiempo" de ejecución. Los ejemplos típicos son problemas donde ocurre algo de esta pinta: uno tiene que procesar todos los $k$ de $1$ hasta $N$, y para procesar cada uno, existen dos métodos (uno tiene que descubrir todo esto para el problema puntual, obviamente :P): Uno procesa en $O(k)$, y el otro en $O(\frac{N}{k})$. Los dos métodos son lineales en $N$ en peor caso, así que la complejidad total queda cuadrática. Pero si usamos uno para los valores chicos y otro para los grandes, procesar se hace siempre en $O(\sqrt{N})$, y el total del algoritmo pasa a ser $O(N \sqrt{N})$.
  * flujo / corte / conservación / mover cosas de un lado a otro. Ejemplo feliz especial: "en un camino" (Arte Moderno, Toneles, Railroads).
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
