Ciencias de la Computación (plan 2013) 2015-1

Optativas, Seminario de Ciencias de la Computación B

Inicio de clases lunes 11 de agosto a la hora y salón de clase.

Página del curso: https://sites.google.com/site/programacioncomp/

OBJETIVO

El concurso de programación ACM ICPC es el concurso más antiguo, grande y de mayor prestigio en el mundo. Cada año, los equipos de las mejores universidades luchan por un lugar para participar en la Final Mundial.

El objetivo de este curso es que los estudiantes pongan en práctica sus conocimientos, ingenio y destrezas, para desarrollar nuevas estrategias, herramientas, y experiencia en la resolución de problemas, programación y trabajo colaborativo, con el fin de participar en concursos tipo ACM.

Si bien se presentan muchos algoritmos durante el curso, el objetivo no es saturar al estudiante de una gran cantidad de información, sino que los utilice acertadamente y eficientemente para resolver problemas.

Por último el curso provee al estudiante conocimientos necesarios para poder aplicar en empresas multinacionales como Google, Apple, Microsoft y Oracle, ya que los problemas que se presentan aquí, son el tipo de problemas en sus entrevistas de trabajo.

Se pretende alentar a la próxima generación de profesionales de la computación a perseguir la excelencia.

TEMARIO

1. Teoría de Números

1.1. Máximo Común Divisor

1.1.1. Algoritmo de Euclides

1.1.2. 1.1.2 Algoritmo de Euclides Extendido

1.2. Mínimo Común Múltiplo

1.2.1. Reducción por MCD

1.3. Potenciación Binaria

1.4. Problemas: MCD, mcm y Potenciación Binaria

1.5. Números Primos

1.5.1. Prueba de Primalidad Determinista

1.5.2. Prueba de Primalidad de Fermat

1.5.3. Criba de Eratóstenes

1.6. Factores Primos y Divisores

1.6.1. Factorización de Primos

1.6.2. Divisores por medio de Factores Primos

1.7. Problemas: Números Primos, Factores Primos y Divisores

1.8. Aritmética Modular

1.8.1. Propiedades del Operador Módulo

1.8.2. Secuencias Circulares

1.9. Números Enormes (Big Nums)

1.10. Problemas: Aritmética Modular y Números Enormes

1.11. Problemas: Unidad

2. Estructuras de Datos Simples

2.1. Pilas

2.2. Colas

2.3. Listas Enlazadas

2.4. Problemas: Pilas, Colas y Listas Enlazadas

2.5. Diccionarios

2.6. Conjuntos

2.7. Mapeos

2.8. Problemas: Diccionarios, Conjuntos y Mapeos.

2.9. Problemas: Unidad 2

3. Ordenamiento y Búsqueda Binaria

3.1. Ordenamiento por Inserción

3.2. Ordenamiento por Selección

3.3. Ordenamiento de Burbuja

3.4. Ordenamiento con Montículo

3.5. Ordenamiento por Mezcla

3.6. Ordenamiento por Cubetas

3.7. Quicksort y Ordenamiento con Librerías Estándar

3.8. Problemas Selectos: Ordenamientos

3.9. Búsqueda Binaria

3.9.1. Encuentro de Elementos

3.9.2. Adivinación o Predicción

3.9.3. Búsqueda Binaria con Números Reales

3.10. Problemas: Búsqueda Binaria

3.11. 11 Problemas: Unidad 3

4. Recursividad Básica

4.1. Conceptos de Recursividad

4.2. Funciones Recursivas Simples

4.3. Serie de Fibonacci

4.4. Divide y Vencerás

4.5. Problemas: Unidad 4

5. Combinatoria

5.1. Técnicas de Conteo

5.1.1. Factorial

5.1.2. Permutaciones

5.1.3. Combinaciones

5.2. Probabilidad

6. Gráficas

6.1. Implementación

6.2. Recorridos en gráficas (BFS,DFS)

6.3. Ruta a mínimo costo. (Dijsktra, Floyd)

6.4. Conectividad

6.5. Árboles

6.6. Problemas: Unidad 6

7. Programación dinámica

7.1. Enfoque Bottom-Up

7.2. Enfoque Top-Down

7.3. Problemas: Unidad 7

8. Simulación de Exámenes

8.1. Prácticas en Equipo

8.2. Temas Selectos para Competencias

8.3. Problemas Selectos: Unidades 1, 2, 3, 4, 5, 6, y problemas adhoc.

BIBLIOGRAFÍA

1. Competitive Programming 3, Steven Halim and Felix Halim, National University of Singapore. Third Edition, Editor lulu.com, 2013.

2. Programming Challenges: The Programming Contest Training Manual, Steven S. Skiena and Miguel A. Revilla, 2003 Springer-Verlag.

3. From Baylor to Baylor, William B. Poucher and Miguel A. Revilla, Editor lulu.com, 2010.

4. Source code library for ACM/ICPC in C++, Hao Fu, School of Computer Science and Technology, University of Science and Technology of China
2010.