Download 1. Objetivos Generales de la asignatura 2. Objetivos

FACULTAD REGIONAL RESISTENCIA - DEPARTAMENTO DE INGENIERÍA EN SISTEMAS DE INFORMACIÓN
Carrera: Ingeniería en Sistemas de Información Plan: 2008
Área: ELECTIVAS
Asignatura: PROGRAMACIÓN COMPETITIVA
Régimen de Cursado: Cuatrimestral Horas/Semana: 8 Horas/Semana Anuales: 4
Nivel de Implementación: Tercero Horas/Año: 128
Correlativas:
Para cursar:
Tener Regularizadas: Paradigmas de Programación
Tener Aprobadas: Algoritmos y Estructuras de Datos
Para rendir:
Tener Aprobadas: Paradigmas de Programación
1. Objetivos Generales de la asignatura

Esta asignatura tiene por objetivo lograr en los alumnos un entendimiento concreto de las
estructuras de datos y las técnicas algorítmicas comúnmente utilizadas para solucionar
problemas de las áreas de conocimiento abordadas en las competencias de programación.
2. Objetivos específicos:









Revisar conceptos de abstracción de datos y P.O.O. e introducir su implementación en
JAVA.
Presentar las estructuras de datos avanzadas (listas, pilas, colas, colas con dos extremos,
mapas, conjuntos), y utilizarlas desde una librería concreta: Collections de JAVA.
Presentar las nociones básicas de complejidad de algoritmos y evaluar la misma en forma
práctica.
Reutilizar –intensivamente- software desarrollado por otros programadores en la solución a
problemas conocidos.
Conocer y utilizar recursos específicamente desarrollados para aumentar la productividad
de los programadores “competitivos”.
Introducir técnicas de programación específicas como backtracking y programación
dinámica.
Presentar las estructuras de datos y algoritmos básicos utilizados para el manejo de
grafos.
Introducir algoritmos avanzados sobre grafos: árboles de cobertura mínimos, caminos mas
cortos, flujo en redes.
Revisar conceptos de matemáticas (combinatoria, teoría de números, probabilidad, etc.)
FACULTAD REGIONAL RESISTENCIA - DEPARTAMENTO DE INGENIERÍA EN SISTEMAS DE INFORMACIÓN
3. Programa Analítico:
CONTENIDOS
UNIDAD 1: Introducción a la Programación Competitiva (6 hs. Cátedra)
Conocer las relaciones intrínsecas entre el cómputo matemático y los lenguajes de programación.
Consolidar el conocimiento puntual sobre JAVA y su uso en los distintos jueces en línea.
 Competencias y programación JAVA.
 Competencias de programación. Los sistemas de Jueces en Línea en la web. Mensajes y
significados.
 Entorno de programación JAVA. Tipos de datos. Clases. E/S por teclado y por archivo. Toma
de tiempos.
UNIDAD 2: La librería Collections. (12 hs. Cátedra)
Entender la importancia de las librerías de los lenguajes de programación por sobre la base de un
lenguaje dado. Comprender los distintos tipos de datos aportados por la librería Collections a
JAVA.
 Contenedores secuenciales y asociativos. Iteradores. Algoritmos. Presentación TP1.
UNIDAD 3: Introducción al Análisis de algoritmos y nociones de complejidad. (12 hs.
Cátedra)
Identificar la complejidad de un algoritmo dada su complejidad. Entender el concepto de
complejidad y las tecnicas para reducir la misma.
 Conceptos de análisis de algoritmos. La notación O. Corrección y eficiencia. Complejidad
mejor, peor y promedio. Comprobación del análisis de un algoritmo. Presentación TP2.
UNIDAD 4: Técnica de programación: Backtracking (12 hs. cátedra)
Conocer la relevancia de la recursividad en los procesos de programacion competitiva.
 Definición, casos de uso. Búsqueda con poda.
UNIDAD 5: Grafos:
Aprender sobre los diferentes usos de un grafo en problemas competitivos. Diferenciarlos de las
listas y demas estructuras de datos complejas.
 Estructuras de datos y algoritmos para su implementación. (9 hs. cátedra)
 Tipos de grafos. Estructuras para su implementación. Recorridos de grafos: en anchura, en
profundidad.
UNIDAD 6: Grafos: Algoritmos avanzados. (15 hs. cátedra)
Conocer los principales escenarios donde aplicar grafos y los algoritmos mas comunes para los
mismos. Entender las diferencias entre cada escenario en particular.
 Conectividad, ciclos eulerianos y hamiltonianos, árboles de cobertura mínimos (Prim y
Kruskal), caminos más cortos (Dijkstra y Floyd).
UNIDAD 7: Técnica de programación: Programación Dinámica. (12 hs. Cátedra)
Interpretar situaciones problematicas donde aplicar DP. Verificar escenarios y optimizarlos.
FACULTAD REGIONAL RESISTENCIA - DEPARTAMENTO DE INGENIERÍA EN SISTEMAS DE INFORMACIÓN
 Subestructuras óptimas, subproblemas superpuestos, principio de optimalidad.
- Evaluaciones Parciales (12 hs. cátedra)
 2 evaluaciones teórico-prácticas y 1 en forma de simulación de
competencia.
- Coloquios TP Final (6 hs. cátedra)
 Coloquios grupales de defensa del TP Final.
3. Bibliografía
Básica:
o Halim, Steven – Halim, Félix. “Competitive Programming 3”. 2013 www.lulu.com
o Mark Weiss. “Data Structures and Problem solving with C++”. Addisson Wesley. ISBN
0321205006. 2nd. Edition. 2003
o Información disponible en www.spoj.com. Fecha último acceso: 01/10/2015
o Información disponible en www.urionlinejudge.com.br. Fecha último acceso: 01/10/2015
Complementaria:
o Comern, Lesiserson-Rivest, Strein. “Introduction to Algorithm”. MIT Press.
ISBN 0262039237. Edición 2001.
o Información disponible en uva.onlinejudge.org. Fecha último acceso: 01/10/2015
4. Fundamentación de la asignatura
Durante los últimos años han tomado creciente importancia las competencias de programación.
Suelen tener modalidades y niveles muy diferentes pero todas apuntan a desarrollar y fortalecer
actitudes y procedimientos deseables en los estudiantes de ISI. A modo de ejemplo:
- Análisis, comprensión y búsqueda de soluciones a problemas.
- Selección y diseño de estructuras de datos y algoritmos adecuados con restricciones de contexto.
- Predisposición para trabajar en equipo.
- Habilidad para clasificar problemas según áreas de conocimiento y poder resolverlos en un
tiempo mínimo.
- Facilidad para el reuso de librerías de software ya implementadas.
- Conocimiento y uso adecuado de las herramientas de debugging que brindan los compiladores, y
generación de casos de prueba representativos para el testeo del programa desarrollado.
Los resultados de competencias como la ACM/ICPC, son tomados como una medida de la calidad
en el desarrollo de software de los participantes una vez egresados.
Asignaturas o conocimientos con que se vincula la materia:
La coordinación para esta asignatura electiva es vertical con las asignaturas del área
Programación: “Algoritmos y Estructuras de Datos”, “Sintaxis y Semántica de Lenguajes“ y
“Paradigmas de Programación” que aportan conceptos, métodos y habilidades.
A nivel transversal se vincula con materias de otras áreas (“Análisis Matemático I”, “Álgebra y
Geometría Analítica”, “Análisis Matemático II”, “Cálculo Numérico” ), ya que se abordan para su
solución problemas estudiados en dichas asignaturas.
FACULTAD REGIONAL RESISTENCIA - DEPARTAMENTO DE INGENIERÍA EN SISTEMAS DE INFORMACIÓN
5. Metodología
Estrategias de enseñanza:
Se desarrolla 1 clase semanal (intercaladas: una de teoría, una de práctica) de acuerdo a los
temas del programa y al avance de los trabajos propuestos.
Durante las clases:
- Se realizan presentaciones explicativas de los distintos puntos del temario.
- Se trabaja en la solución a problemas reales de competencias de programación que afiancen los
conceptos y estrategias explicadas.
- Se hace uso de los sitios web de jueces en línea.
- Se orienta para la realización de los trabajos prácticos.
- Se realizan talleres en laboratorio.
- Se realizan instancias de evaluación: parciales y coloquios.
- Se realizan seminarios que aportan a la formación integral en el uso de la librería Collections.
- La modalidad de trabajo es de amplia interacción entre docentes y alumnos, con planteo de
inquietudes que llevan al tratamiento de temas de interés. Se pondrá énfasis en el afianzamiento
de procedimientos y actitudes fundamentales para la programación competitiva.
Modalidad de agrupamientos:
En las clases y actividades de seguimiento se trabajará en pequeños grupos, conformados de
acuerdo a los fines de cada actividad.
Los trabajos prácticos son realizados por grupos de tres alumnos, en forma colaborativa,
combinando actividades de comprensión de problemas, clasificación, búsqueda y análisis de
soluciones, codificación de algoritmos, debugging y testeo de los programas.
Consultas:
El profesor y el auxiliar tienen un espacio de consulta semanal de una hora prefijada, en el Grupo
de Programación Competitiva; además de la atención de consultas vía e-mail y foro de la cátedra
en el Campus Virtual.
Organización de espacios dentro y fuera del ámbito universitario (aulas, talleres, laboratorios,
visitas, empresas, otros):
Se realizan actividades en el Grupo de Programación donde se resuelven problemas de
competencias anteriores de ACM, en lenguaje JAVA, C y C++, haciendo uso de la librería
Collections y STL respectivamente.
Organización de espacios dentro y fuera del ámbito universitario:
El profesor realiza también una actividad de investigación/extensión, a través de la coordinación
anual de un Grupo de Programación, como actividad extracurricular, conformado por alumnos
interesados en profundizar sobre cuestiones de Algoritmos – Estructuras de Datos – Programas –
Lenguajes de Programación, participar en análisis y discusiones grupales de soluciones
alternativas y publicar resultados como medio de compartir con la comunidad interesada en estas
temáticas.