Presentación del grupo 7069 - 2009-2.

Programación avanzada

Objetivo

A quién está dirigido

• ¿Ciencias de la computación? 4to a 6to semestres
• ¿De otra carrera? mínimo: programar bien y curso equivalente a estructuras de datos

• Si programar NO te apasiona, este curso NO es para ti.
• Si programar 10 a 20 horas a la semana es mucho, este curso NO es para ti.
• Si programar NO está entre las cinco cosas que te producen mayor placer en la vida, este curso NO es para ti.
• ¿La contrapositiva de los enunciados anteriores? ¡Bienvenido!

Forma de trabajo

• Discusiones de problemas y temas tres veces a la semana. Lunes, miércoles y viernes.
• Tareas de programación de los problemas que se discutieron y otros similares. Dependiendo de la semana, serán entre 2 y 4 problemas.
• Cuatro concursos de programación, uno por mes. Cada concurso consistirá de 3 o 4 problemas.
• Dos proyectos de programación de 2 meses cada uno. El primero es individual, el segundo por parejas.

Calificación

• Entregar al menos el 90% de todos los programas es requisito para que se calcule tu calificación final de esta manera:
  • Concursos de programación: 40% (10% cada concurso)
  • Proyecto de programación individual: 30%
  • Proyecto de programación por parejas: 30%
• NP sólo si: (1) no entregas nada o (2) a más tardar dos meses después de iniciado el semestre avisas (a los profesores) que no continuarás.
• En cualquier otro caso tu calificación será 5.

Herramientas y bibliografía

• C++ (aunque no es indispensable que sepas C++)
• Programming Challenges. Steven S. Skiena & Miguel A. Revilla, Springer, 2003

Contenido

1. Introducción
   1. Herramientas
   2. Concursos de programación
2. Estructuras de datos
   1. Estructuras de datos básicas
   2. Diseño de programas
   3. Entrada y salida
3. Cadenas
   1. Conjuntos de caracteres
   2. Representación
   3. Patrones
   4. Manipulación de cadenas
   5. Funciones de biblioteca
4. Ordenamiento
   1. Aplicaciones
   2. Algoritmos
5. Aritmética y álgebra
   1. Aritmética de máquina
   2. Bibliotecas de enteros
   3. Enteros de gran precisión
   4. Bases numéricas y conversiones
   5. Números reales
   6. Álgebra
   7. Manipulación de polinomios
   8. Encontrando raíces
6. Combinatoria
   1. Técnicas de cuenta
   2. Relaciones recurrentes
   3. Otras secuencias de cuenta
   4. Recursión e inducción
7. Teoría de números
   1. Números primos
   2. Divisibilidad
   3. Aritmética modular
   4. Congruencias
   5. Bibliotecas de teoría de números
8. Backtracking
   1. Construcción de todos los subconjuntos
   2. Construcción de todas las permutaciones
9. Recorriendo gráficas
   1. Tipos de gráficas
   2. Estructuras de datos y gráficas
   3. Recorrido de gráficas
   4. Ordenamiento topológico
10. Algoritmos en gráficas
    1. Teoría de gráficas
    2. Spanning tree
    3. Rutas más cortas
    4. Flujo en redes y biparticiones
11. Programación dinámica
    1. No seas glotón
    2. Distancia
    3. Reconstrucción de rutas
12. Latices
    1. Latices rectilineales
    2. Latices triangulares y hexagonales
13. Geometría
    1. Líneas
    2. Triángulos y trigonometría
    3. Círculos
14. Geometría computacional
    1. Segmentos de línea e intersecciones
    2. Cómputo de ángulos y polígonos
    3. Cubiertas convexas
    4. Triangulación
    5. Algoritmos para mallas
    6. Bibliotecas de geometría