Herramientas de usuario
temarios-oia
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 Próxima revisión Ambos lados, revisión siguiente | ||
|
temarios-oia [2016/12/23 03:20] santo [Temarios para la Olimpíada Internacional de Informática (IOI)] |
temarios-oia [2017/09/26 03:07] santo [Aclaraciones] |
||
|---|---|---|---|
| Línea 1: | Línea 1: | ||
| - | ====== Temarios relevantes para la OIA ====== | + | ====== Temarios orientativos por nivel para la OIA, Categoría Programación ====== |
| + | |||
| + | ===== Aclaraciones ===== | ||
| + | |||
| + | * El temario se encuentra publicado en [[http://www.oia.unsam.edu.ar/oia-programacion/|el sitio web de la OIA]]. | ||
| + | * Los conocimientos que se listan, son **orientativos** para los alumnos, docentes, y entrenadores, y son **no excluyentes** de otros conocimientos que se podrían incorporar ocasionalmente en los problemas de los certámenes. | ||
| + | * Estos conocimientos son acumulativos para los distintos niveles (Se considera que los temas de cada nivel incluyen los temas correspondientes a los niveles anteriores). | ||
| + | * El temario está pensado como una orientación general de los temas que **podrían** aparecer en un problema, incluso en los más difíciles. Por lo tanto: | ||
| + | * **No se espera** que los participantes necesariamente conozcan y dominen **todos** los temas del temario. | ||
| + | * Se espera que los problemas más sencillos requieran únicamente de los conocimientos más básicos. | ||
| ===== Temario OIA Nivel 1 ===== | ===== Temario OIA Nivel 1 ===== | ||
| - | **Pendiente de revisión y actualización** | + | ==== Conocimientos Matemáticos ==== |
| + | * Aritmética y Geometría | ||
| + | * Enteros, operaciones aritméticas, comparación | ||
| + | * Sistemas de numeración, conversión entre ellos | ||
| + | * Propiedades básicas de los enteros (signo, paridad, divisibilidad) | ||
| + | * Aritmética modular básica: suma, resta, multiplicación | ||
| + | * Fracciones, porcentajes | ||
| + | * Números primos | ||
| + | * Lógica básica | ||
| + | * Entender enunciados matemáticos con "existe" y "para todo", y su diferencia | ||
| + | * Conectivos lógicos (y, o, no, entonces) | ||
| + | * Uso de razonamientos y deducciones lógicas | ||
| + | ==== Conocimientos de Ciencias de la Computación: ==== | ||
| + | * Programación | ||
| + | * Sintaxis y semántica básicas de algún lenguaje permitido en OIA | ||
| + | * Variables, tipos, expresiones y asignación | ||
| + | * Entrada y salida sencilla (desde y hacia archivos y stdin / stdout) | ||
| + | * Estructuras de control selectivas (if) | ||
| + | * Estructuras de control repetitivas (while / for / repeat) | ||
| + | * Funciones (subrutinas) y pasaje de parámetros en ambos sentidos | ||
| + | * Descomposición de problemas (pensamiento top-down) | ||
| + | * Estructuras de datos fundamentales | ||
| + | * Tipos primitivos (booleanos, enteros con y sin signo, caracteres) | ||
| + | * Arreglos unidimensionales | ||
| + | * Cadenas y procesamiento básico de cadenas | ||
| + | * Variables globales y locales | ||
| + | * Estrategias algorítmicas | ||
| + | * Iteración | ||
| + | * Algoritmos | ||
| + | * Algoritmos sencillos con enteros: | ||
| + | * Cambio de base | ||
| + | * Test de primalidad (buscar divisores hasta la raíz) | ||
| + | * Factorización (buscando divisores) | ||
| + | * Manipulación de arreglos: | ||
| + | * Llenar | ||
| + | * Desplazar | ||
| + | * Rotar | ||
| + | * Invertir | ||
| + | * Mínimo/Máximo | ||
| + | * Sumas parciales | ||
| + | * Algoritmos sencillos con cadenas de texto | ||
| + | * Búsqueda directa de una subcadena dada | ||
| + | * Invertir una cadena | ||
| + | * Convertir entre mayúsculas y minúsculas | ||
| + | * Procesamiento y búsqueda secuencial | ||
| ===== Temario OIA Nivel 2 ===== | ===== Temario OIA Nivel 2 ===== | ||
| - | **Pendiente de revisión y actualización** | + | ==== Conocimientos Matemáticos ==== |
| + | * Aritmética y Geometría | ||
| + | * Recta, segmento, ángulo, triángulo, rectángulo, cuadrado, circunferencia | ||
| + | * Teorema de pitágoras | ||
| + | * Funciones, relaciones y conjuntos | ||
| + | * Funciones (inyectivas, sobreyectivas, inversas, composición) | ||
| + | * Relaciones (Propiedad de ser simétricas, transitivas) | ||
| + | * Orden lexicográfico | ||
| + | * Conjuntos (inclusión, complementos, disjuntos) | ||
| + | * Lógica básica | ||
| + | * Tablas de verdad | ||
| + | * Técnicas de demostración | ||
| + | * Nociones de implicación, recíproco, contrarrecíproco, negación, contradicción | ||
| + | * Demostraciones directas, por contraejemplo, por absurdo | ||
| + | * Inducción matemática | ||
| + | * Definiciones matemáticas recursivas | ||
| + | * Combinatoria básica | ||
| + | * Argumentos de conteo (principio de suma y multiplicación, progresiones aritméticas y geométricas, números de Fibonacci) | ||
| + | * Factorial, números combinatorios | ||
| + | * Principio del palomar | ||
| + | * Grafos y árboles | ||
| + | * Árboles y sus propiedades básicas, árboles con raíz | ||
| + | * Grafos no dirigidos (grados, camino, ciclo, conectividad) | ||
| + | * Grafos dirigidos (grado de entrada, grado de salida, camino y ciclo dirigido) | ||
| + | * Árboles generadores | ||
| + | * Grafos con pesos, etiquetas, colores | ||
| + | * Multigrafos, grafos con bucles | ||
| + | |||
| + | ==== Conocimientos de Ciencias de la Computación ==== | ||
| + | |||
| + | * Estructuras de datos fundamentales | ||
| + | * Arreglos multidimensionales | ||
| + | * Registros / Tipos de Datos definidos por el usuario | ||
| + | * Estructuras enlazadas (listas, árboles binarios, árboles con raíz, y similares estructuras naturalmente recursivas) | ||
| + | * Estrategias de implementación de grafos y árboles | ||
| + | * Recursión | ||
| + | * Implementación de funciones matemáticas recursivas | ||
| + | * Análisis de algoritmos | ||
| + | * Complejidades estándar (constante, logarítmica, lineal, N lg N, cuadrática, cúbica, exponencial) | ||
| + | * Medición empírica de la eficiencia | ||
| + | * Estrategias algorítmicas | ||
| + | * Algoritmos de fuerza bruta / búsqueda exhaustiva | ||
| + | * Algoritmos golosos | ||
| + | * Algoritmos | ||
| + | * Algoritmos sencillos con enteros: | ||
| + | * Algoritmo de Euclides | ||
| + | * Criba de Eratóstenes | ||
| + | * Factorización (con criba) | ||
| + | * Operaciones sencillas con enteros de precisión arbitraria (suma, resta, multiplicación cuadrática) | ||
| + | * Manipulación de arreglos: | ||
| + | * Redimensionar | ||
| + | * Histogramas | ||
| + | * Bucket / counting sort | ||
| + | * Búsqueda binaria | ||
| + | * Quicksort y Quickselect (k-ésimo elemento) | ||
| + | * Heapsort y Mergesort | ||
| + | * DFS y BFS | ||
| + | * Recorrido Inorder, Preorder, Postorder | ||
| + | * Aplicaciones de DFS (Orden topológico) | ||
| + | * Componentes conexas | ||
| + | * Algoritmo de Dijkstra | ||
| + | * Árbol generador mínimo (Prim / Kruskal) | ||
| + | * Estructuras de datos: | ||
| + | * Pilas y colas | ||
| + | * Representación de grafos (listas de adyacencia, matriz de adyacencia) | ||
| + | * Heap binario | ||
| + | * Estructura de Union-Find (Listas de componentes + Arreglo de representantes) | ||
| + | |||
| ===== Temario OIA Nivel 3 ===== | ===== Temario OIA Nivel 3 ===== | ||
| - | **Pendiente de revisión y actualización** | + | ==== Conocimientos Matemáticos ==== |
| + | * Aritmética y Geometría | ||
| + | * Punto, vector, coordenadas en el plano | ||
| + | * Polígono (vértices, lados, simple, convexo, interior, área) | ||
| + | * Distancia euclídea | ||
| + | * Funciones, relaciones y conjuntos | ||
| + | * Relaciones (de equivalencia, de orden, de orden total) | ||
| + | * Conjuntos (producto cartesiano, conjunto de partes) | ||
| + | * Combinatoria básica | ||
| + | * Principio de inclusión/exclusión | ||
| + | * Grafos y árboles | ||
| + | * Grafos no dirigidos (ciclo y camino Euleriano / Hamiltoniano) | ||
| + | * Grafos dirigidos (camino y ciclo Euleriano / Hamiltoniano dirigido) | ||
| + | * Grafos bipartitos | ||
| + | * Grafos planares (propiedades básicas) | ||
| + | |||
| + | ==== Conocimientos de Ciencias de la Computación ==== | ||
| + | |||
| + | * Estructuras de datos fundamentales | ||
| + | * Uso elemental de números de punto flotante en cómputos numéricamente estables | ||
| + | * Representación de datos en memoria | ||
| + | * Memoria Heap vs Stack | ||
| + | * Implementación de fracciones para cálculos exactos | ||
| + | * Análisis de algoritmos | ||
| + | * Especificación, precondición, poscondición, correctitud, invariantes | ||
| + | * Análisis asintótico de complejidad | ||
| + | * Notación de O grande | ||
| + | * Estrategias algorítmicas | ||
| + | * Divide y vencerás | ||
| + | * Backtracking (recursivo y no recursivo), Branch-and-bound | ||
| + | * Programación dinámica | ||
| + | * Algoritmos | ||
| + | * Exponenciación eficiente (especialmente con aritmética modular) | ||
| + | * Aplicaciones de DFS (encontrar ciclo/camino euleriano) | ||
| + | * Clausura transitiva | ||
| + | * Algoritmos de Bellman Ford, Floyd-Warshall | ||
| + | * Matching máximo bipartito O(VE) | ||
| + | * Biconectividad en grafos no dirigidos (puentes, puntos de articulación) | ||
| + | * Conectividad en grafos dirigidos (componentes fuertemente conexas) | ||
| + | * Estructuras de datos: | ||
| + | * Árboles binarios balanceados estáticos (Fenwick Tree o Segment Tree) | ||
| + | * Árbol binario de búsqueda balanceado (Treap | Splay Tree | AVL u otros) | ||
| + | * Árbol binario de búsqueda aumentado | ||
| + | * Consulta de LCA en tiempo logarítmico | ||
| + | * Estructuras de datos persistentes | ||
| + | * Composición de estructuras de datos (Fenwick Tree en 2 dimensiones) | ||
| + | * Tries | ||
| + | * Algoritmos avanzados | ||
| + | * Nociones básicas de teoría de juegos combinatoria: posiciones perdedoras y ganadoras, minimax para juego óptimo | ||
| + | * Algoritmos Online vs Offline | ||
| + | * Algoritmos probabilísticos | ||
| + | * Algoritmos geométricos | ||
| + | * Representación de puntos, vectores, rectas, segmentos | ||
| + | * Detección de puntos alineados, vectores paralelos / perpendiculares, giros horarios / antihorarios | ||
| + | * Intersección de dos rectas | ||
| + | * Intersección de dos segmentos | ||
| + | * Área de polígono | ||
| + | * Verificación de punto en polígono | ||
| + | * Compresión de coordenadas | ||
| + | * Algoritmos O(N lg N) para cápsula convexa | ||
| + | * Método de Sweep Line | ||
| + | * Teoría de lenguajes | ||
| + | * Gramáticas sencillas en BNF | ||
| ===== Temarios para la Olimpíada Internacional de Informática (IOI) ===== | ===== Temarios para la Olimpíada Internacional de Informática (IOI) ===== | ||
| * [[https://people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus.pdf|Versión actual del Syllabus]] | * [[https://people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus.pdf|Versión actual del Syllabus]] | ||
| + | |||
| + | * [[https://people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus-2018.pdf|Syllabus de IOI de 2018]] | ||
| * [[https://people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus-2017.pdf|Syllabus de IOI de 2017]] | * [[https://people.ksp.sk/~misof/ioi-syllabus/ioi-syllabus-2017.pdf|Syllabus de IOI de 2017]] | ||
temarios-oia.txt · Última modificación: 2017/09/26 03:16 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
