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/09/14 01:26] santo |
brainstorm:brainstorm-algoritmos [2019/09/08 17:35] (actual) santo |
||
|---|---|---|---|
| Línea 2: | Línea 2: | ||
| - | Brainstorm de ideas de temas algorítmicos para desarrollar, en forma de lista. Varios 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 19: | Línea 19: | ||
| * BFS con cola de dos puntas [Aristas 0 y 1] | * BFS con cola de dos puntas [Aristas 0 y 1] | ||
| * BFS con K+1 bolsas [aristas 0..K] | * BFS con K+1 bolsas [aristas 0..K] | ||
| + | * Truquito "ahorrar aristas": Ajedrez, Alfil | ||
| * DFS | * DFS | ||
| * Back Edges | * Back Edges | ||
| Línea 103: | Línea 104: | ||
| * Estructuras de datos | * Estructuras de datos | ||
| * Arreglos | * Arreglos | ||
| + | * "Truco del arreglo autolimpiante" | ||
| * STL (set, multiset, map, multimap, vector, queue, stack, deque, priority_queue, list, etc) | * STL (set, multiset, map, multimap, vector, queue, stack, deque, priority_queue, list, etc) | ||
| * Listas enlazadas | * Listas enlazadas | ||
| Línea 129: | 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 167: | 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). | ||
| * Capsula convexa en O(n lg n) | * Capsula convexa en O(n lg n) | ||
| * Ancho (mínimo) de conjunto (rotating calipers en la chull) | * Ancho (mínimo) de conjunto (rotating calipers en la chull) | ||
| Línea 177: | 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 182: | 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 197: | 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 210: | 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.1505352374.txt.gz · Última modificación: 2017/09/14 01:26 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
