Herramientas de usuario
brainstorm:brainstorm-algoritmos
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
brainstorm:brainstorm-algoritmos [2018/06/21 17:07] santo |
brainstorm:brainstorm-algoritmos [2019/09/08 17:35] (actual) santo |
||
|---|---|---|---|
| Línea 183: | Línea 183: | ||
| * Dualidad intervalo - punto ([A,B] -- (A,B) , complementar intervalos es reflejar por y=x (caso circular)) | * Dualidad intervalo - punto ([A,B] -- (A,B) , complementar intervalos es reflejar por y=x (caso circular)) | ||
| * Truquito de la f lineal que transforma norma 1 en norma infinito (en 2D es "rotar 45") | * Truquito de la f lineal que transforma norma 1 en norma infinito (en 2D es "rotar 45") | ||
| + | * Hay O(NM) rectángulos maximales en una grilla de NxM (Implica O(T^2) para T obstáculos), y cómo enumerarlos (desde cada casilla tirar un rayito para abajo, y de donde pega, expandir para los costados. Eso pasa por todos los maximales y por algunos no maximales [y posiblemente varias veces]) | ||
| * Divide and conquer | * Divide and conquer | ||
| * Par de puntos mas cercano en O(n lg n) | * Par de puntos mas cercano en O(n lg n) | ||
| Línea 188: | Línea 189: | ||
| * Karatsuba | * Karatsuba | ||
| * Armado de fixtures (aunque hay una alternativa constructiva muy elegante y simple) | * Armado de fixtures (aunque hay una alternativa constructiva muy elegante y simple) | ||
| + | * Elemento mayoría (y solución lineal, con O(1) memoria, o alternativamente con 3/2N comparaciones) | ||
| * Meet in the middle | * Meet in the middle | ||
| * BFS (tipo cubo de Rubik) | * BFS (tipo cubo de Rubik) | ||
| Línea 203: | Línea 205: | ||
| * Problemas NP Completos: Maximum independent set, Minimum dominating set, subset sum, etc. | * Problemas NP Completos: Maximum independent set, Minimum dominating set, subset sum, etc. | ||
| * Recursiones y podas de backtracking que mejoran la complejidad (Ejemplo, Max. Ind. Subset en 1.47^N) | * Recursiones y podas de backtracking que mejoran la complejidad (Ejemplo, Max. Ind. Subset en 1.47^N) | ||
| + | * Board hashes (transposition tables, también re útil para BFS/Dijkstra) | ||
| * Teoría de juegos | * Teoría de juegos | ||
| * Cálculo con DP de posiciones ganadoras y perdedoras. Propiedad Universal. | * Cálculo con DP de posiciones ganadoras y perdedoras. Propiedad Universal. | ||
| Línea 216: | Línea 219: | ||
| * Autómatas de KMP y Aho-Corasick | * Autómatas de KMP y Aho-Corasick | ||
| * Parsing Recursivo Descendente predictivo (con "prediccion artesanal") | * Parsing Recursivo Descendente predictivo (con "prediccion artesanal") | ||
| + | * Popurrí | ||
| + | * Detección de ciclo en función (Tortuga de Floyd, Brent) | ||
| + | |||
| + | |||
brainstorm/brainstorm-algoritmos.1529600865.txt.gz · Última modificación: 2018/06/21 17:07 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
