Herramientas de usuario

Herramientas del sitio


temarios-oia

Diferencias

Muestra las diferencias entre dos versiones de la página.

Enlace a la vista de comparación

Ambos lados, revisión anterior Revisión previa
Próxima revisión
Revisión previa
temarios-oia [2017/01/13 19:01]
santo
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 [No son relevantes los nombres ni la notación, sino las **ideas**] +
-     * Enunciados en primer orden (Diferencia entre existe y para todo) +
-     * Conectivos lógicos (propiedades básicas) +
-     * Modus ponens, modus tollens, y similares deducciones lógicas +
-==== Conocimientos de Ciencias de la Computación:​ ==== +
-  * Programación +
-     * Sintaxis y semántica básicas de un lenguaje de alto nivel permitido +
-     * 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 y pasaje de parámetros +
-     * 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 subcadena) +
-     * Procesamiento y búsqueda secuencial+
  
- +   Los conocimientos que se listanson **orientativos** para los alumnosdocentes, 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 problemaincluso ​en los más difíciles. Por lo tanto
- +        * **No se espera** que los participantes necesariamente conozcan ​dominen ​**todos** los temas del temario. 
-===== Temario OIA Nivel 2 [Tentativo] ===== +        Se espera que los problemas más sencillos requieran únicamente ​de los conocimientos más básicos.
- +
-==== Conocimientos Matemáticos ==== +
-  ​Aritmética y Geometría +
-     * Rectasegmento, á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 [No son relevantes ​los nombres ni la notaciónsino las **ideas**] +
-     * Tablas de verdad +
-  * Técnicas de demostración +
-     * Nociones de implicaciónrecí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 multiplicaciónprogresiones aritméticas ​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érticeslados, 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 ​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.1484334114.txt.gz · Última modificación: 2017/01/13 19:01 por santo