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 | ||
temarios-oia [2017/03/18 19:51] santo [Conocimientos de Ciencias de la Computación:] |
temarios-oia [2017/09/26 03:16] (actual) santo |
||
---|---|---|---|
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] ===== | + | El temario se encuentra publicado en [[http://www.oia.unsam.edu.ar/oia-programacion/|el sitio web de la OIA]]. |
- | ==== Conocimientos Matemáticos ==== | + | ===== Aclaraciones ===== |
- | * 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 [Tentativo] ===== | + | * 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). | |
- | ==== Conocimientos Matemáticos ==== | + | * 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: |
- | * Aritmética y Geometría | + | * **No se espera** que los participantes necesariamente conozcan y dominen **todos** los temas del temario. |
- | * Recta, segmento, ángulo, triángulo, rectángulo, cuadrado, circunferencia | + | * Se espera que los problemas más sencillos requieran únicamente de los conocimientos más básicos. |
- | * 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 [No son relevantes los nombres ni la notación, sino las **ideas**] | + | |
- | * 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 [Tentativo] ===== | + | |
- | + | ||
- | ==== 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 | + | |
- | * Recursión | + | |
- | * Estrategias de divide y vencerás | + | |
- | * Backtracking recursivo | + | |
- | * 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 | + | |
- | * Algoritmos sencillos con enteros: | + | |
- | * 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]] |