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 [2017/11/02 19:34] santo |
brainstorm:brainstorm-algoritmos [2019/09/08 17:35] (actual) santo |
||
|---|---|---|---|
| Línea 4: | Línea 4: | ||
| Brainstorm de ideas de temas algorítmicos para desarrollar, en forma de lista. Muchísimos de estos temas exceden el nivel usual de la IOI / competencias de nivel secundario, siendo más avanzados y adecuados para nivel universitario, ya que esta lista se inició a partir de una ya existente lista de temas apuntada a la competencia de programación universitaria ACM-ICPC. | Brainstorm de ideas de temas algorítmicos para desarrollar, en forma de lista. Muchísimos de estos temas exceden el nivel usual de la IOI / competencias de nivel secundario, siendo más avanzados y adecuados para nivel universitario, ya que esta lista se inició a partir de una ya existente lista de temas apuntada a la competencia de programación universitaria ACM-ICPC. | ||
| - | Algunos no son necesariamente más avanzados pero están al momento de escribir estas líneas "explicitely excluded" en el Syllabus de IOI. | + | Algunos no son necesariamente más avanzados pero están al momento de escribir estas líneas "explicitly excluded" en el Syllabus de IOI. |
| No obstante, como lista ideas, con temas existentes posibles para desarrollar, no deja de ser una lista valiosa para generar material apuntado a OIA y competencias de nivel secundario. | No obstante, como lista ideas, con temas existentes posibles para desarrollar, no deja de ser una lista valiosa para generar material apuntado a OIA y competencias de nivel secundario. | ||
| Línea 131: | Línea 131: | ||
| * Suffix Array (Algoritmo de Larsson y Sadakane), LCP | * Suffix Array (Algoritmo de Larsson y Sadakane), LCP | ||
| * BWT (Mismo algoritmo Suffix Array) / BWT inversa en O(N) | * BWT (Mismo algoritmo Suffix Array) / BWT inversa en O(N) | ||
| + | * Compresión de coordenadas | ||
| * Programacion Dinamica | * Programacion Dinamica | ||
| * Maxima subsecuencia creciente (En O(n^2), y su variante en O(n lg n)) | * Maxima subsecuencia creciente (En O(n^2), y su variante en O(n lg n)) | ||
| Línea 169: | Línea 170: | ||
| * Chequear si un punto esta en un poligono / en un segmento / en una recta / en un plano | * Chequear si un punto esta en un poligono / en un segmento / en una recta / en un plano | ||
| * Teorema de Pick | * Teorema de Pick | ||
| + | * Triangulación de polígono (árbol de triángulos, demuestra que piso(n/3) guardias bastan) | ||
| * Par de puntos mas cercano en O(n lg n) | * Par de puntos mas cercano en O(n lg n) | ||
| * Truquito de que v --> (w*v, w^v) es rotohomotecia de razon ||w|| que rota llevando w al eje x positivo (permite "restar angulos en enteros", demuestra que un angulo es posible entre puntos enteros si y solo si su tangente es racional). | * Truquito de que v --> (w*v, w^v) es rotohomotecia de razon ||w|| que rota llevando w al eje x positivo (permite "restar angulos en enteros", demuestra que un angulo es posible entre puntos enteros si y solo si su tangente es racional). | ||
| Línea 180: | Línea 182: | ||
| * Idea de eliminación de dominados / Convex hull trick | * Idea de eliminación de dominados / Convex hull trick | ||
| * 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") | ||
| + | * 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 185: | 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 200: | 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 213: | 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.1509651287.txt.gz · Última modificación: 2017/11/02 19:34 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
