OIA-Politecnico

Sobre OIA nivel 2

En OIA Nivel 2 se ponen en juego conocimientos de matematica, algoritmia y técnicas de resolucion de problemas. El temario incluye todos los temas de nivel 1, y varios más que se detallan abajo.

El temario es orientativo y no excluye que se puedan tomar temas que no aparecen en él (Por ejemplo, programación dinámica es un tema común en nivel 2, pero aparece recién en el temario de nivel 3.

Al mismo tiempo, no hace falta saber todos los temas para poder participar o incluso para que nos vaya bien.

Temario

Matemática

Grafos y arboles

• Arboles
• Arboles con raiz
• Grafos no dirigidos (nociones de grado, camino, ciclo, conectividad)
• Grafos dirigidos (nociones de grado de entrada, grado de salida, caminos y ciclos dirigidos)
• Arboles generadores
• Grafos con pesos, etiquetas o colores
• Grafos no simples (“multigrafos” con aristas paralelas y bucles)

Logica y demostraciones

• Tablas de verdad
• Negacion, contradiccion
• Implicacion, reciproco, contrarreciproco
• Demostracion directa
• Demostracion por contraejemplo
• Demostracion por absurdo
• Induccion matematica
• Definiciones recursivas

Combinatoria

• Principio de suma y multiplicacion
• Progresiones aritmeticas y geometricas
• Numeros de Fibonacci
• Factorial
• Numeros combinatorios (n tomados de a k / n choose k / nCk)
• Principio del palomar

Funciones, relaciones y conjuntos

• Funciones inyectivas y sobreyectivas
• Funciones inversas
• Composicion de funciones
• Relaciones simetricas y transitivas
• Orden lexicografico
• Conjuntos (nociones de inclusion, complemento y disjuncion)

Geometria

• Recta
• Segmento
• Angulo
• Triangulo
• Rectangulo
• Cuadrado
• Circunferencia
• Teorema de Pitagoras

Computación

Analisis de algoritmos

• Complejidades estandar (O(1), O(log(N)), O(N), O(N lg N), O(N^2), O(N^3), O(k^N))
• Medicion empirica de la eficiencia

Estructuras de datos

• Arreglos multidimensionales
• Structs
• Estructuras enlazadas (listas, arboles binarios, arboles con raiz, etc)
• Representaciones de grafos y arboles
• Pilas y colas
• Heap binario
• Union-Find

Estrategias algoritmicas

• Fuerza bruta / busqueda exhaustiva
• Algoritmos golosos (greedy)

Algoritmos con enteros

• Algoritmo de Euclides (mayor común divisor)
• Criba de Eratostenes (y como usarla para factorizar)
• Manipulacion de enteros arbitrariamente grandes (suma, resta, multiplicacion)

Manipulacion de arreglos

• Redimensionar
• Histogramas
• Bucket / counting sort

Varios

• Busqueda binaria
• Quicksort y quickselect (k-esimo elemento)
• Heapsort
• Mergesort
• Recorridos inorden, preorden y postorden
• Aplicaciones de DFS (toposort)
• Componentes conexas
• Algoritmo de Dijkstra
• Arbol generador minimo (Kruskal o Prim)