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/09/22 03:54]
santo
temarios-oia [2017/09/26 03:16] (actual)
santo
Línea 1: Línea 1:
 ====== Temarios orientativos por nivel para la OIA, Categoría Programación ====== ====== Temarios orientativos por nivel para la OIA, Categoría Programación ======
 +
 +El temario se encuentra publicado en [[http://​www.oia.unsam.edu.ar/​oia-programacion/​|el sitio web de la OIA]].
  
 ===== Aclaraciones ===== ===== Aclaraciones =====
Línea 8: Línea 10:
         * **No se espera** que los participantes necesariamente conozcan y dominen **todos** los temas del temario.         * **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.         * Se espera que los problemas más sencillos requieran únicamente de los conocimientos más básicos.
- 
-===== Temario OIA Nivel 1 ===== 
- 
-==== 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 ===== 
- 
-==== 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 ===== 
- 
-==== 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) =====
temarios-oia.1506052459.txt.gz · Última modificación: 2017/09/22 03:54 por santo