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 [2017/01/13 18:52] santo |
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 ====== |
- | ===== Temario OIA Nivel 1 [Tentativo] ===== | + | ===== 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 ===== | ||
==== Conocimientos Matemáticos ==== | ==== Conocimientos Matemáticos ==== | ||
Línea 11: | Línea 20: | ||
* Fracciones, porcentajes | * Fracciones, porcentajes | ||
* Números primos | * Números primos | ||
- | * Lógica básica [No son relevantes los nombres ni la notación, sino las **ideas**] | + | * Lógica básica |
- | * Enunciados en primer orden (Diferencia entre existe y para todo) | + | * Entender enunciados matemáticos con "existe" y "para todo", y su diferencia |
- | * Conectivos lógicos (propiedades básicas) | + | * Conectivos lógicos (y, o, no, entonces) |
- | * Modus ponens, modus tollens, y similares deducciones lógicas | + | * Uso de razonamientos y deducciones lógicas |
==== Conocimientos de Ciencias de la Computación: ==== | ==== Conocimientos de Ciencias de la Computación: ==== | ||
* Programación | * Programación | ||
- | * Sintaxis y semántica básicas de un lenguaje de alto nivel permitido | + | * Sintaxis y semántica básicas de algún lenguaje permitido en OIA |
* Variables, tipos, expresiones y asignación | * Variables, tipos, expresiones y asignación | ||
* Entrada y salida sencilla (desde y hacia archivos y stdin / stdout) | * Entrada y salida sencilla (desde y hacia archivos y stdin / stdout) | ||
* Estructuras de control selectivas (if) | * Estructuras de control selectivas (if) | ||
* Estructuras de control repetitivas (while / for / repeat) | * Estructuras de control repetitivas (while / for / repeat) | ||
- | * Funciones y pasaje de parámetros | + | * Funciones (subrutinas) y pasaje de parámetros en ambos sentidos |
* Descomposición de problemas (pensamiento top-down) | * Descomposición de problemas (pensamiento top-down) | ||
* Estructuras de datos fundamentales | * Estructuras de datos fundamentales | ||
Línea 43: | Línea 52: | ||
* Mínimo/Máximo | * Mínimo/Máximo | ||
* Sumas parciales | * Sumas parciales | ||
- | * Algoritmos sencillos con cadenas de texto (búsqueda directa de subcadena) | + | * 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 | * Procesamiento y búsqueda secuencial | ||
- | + | ===== Temario OIA Nivel 2 ===== | |
- | + | ||
- | + | ||
- | + | ||
- | ===== Temario OIA Nivel 2 [Tentativo] ===== | + | |
==== Conocimientos Matemáticos ==== | ==== Conocimientos Matemáticos ==== | ||
Línea 61: | Línea 69: | ||
* Orden lexicográfico | * Orden lexicográfico | ||
* Conjuntos (inclusión, complementos, disjuntos) | * Conjuntos (inclusión, complementos, disjuntos) | ||
- | * Lógica básica [No son relevantes los nombres ni la notación, sino las **ideas**] | + | * Lógica básica |
* Tablas de verdad | * Tablas de verdad | ||
* Técnicas de demostración | * Técnicas de demostración | ||
Línea 122: | Línea 130: | ||
- | ===== Temario OIA Nivel 3 [Tentativo] ===== | + | ===== 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]] |