Temarios relevantes para la OIA

Temario OIA Nivel 1 [Tentativo]

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

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

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 [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

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)