Source: http://cic.javerianacali.edu.co/wiki/doku.php?id=materias:analisisdisenoalgoritmos
Timestamp: 2018-08-21 00:48:04+00:00

Document:
DECC Wiki [materias:analisisdisenoalgoritmos]
Traza: • analisisdisenoalgoritmos
Análisis y Diseño de Algoritmos (300CIG004)
Horas de trabajo acompañado: 5 / semana (3 horas de clase, 2 de taller)
Pre-requisitos: Árboles y Grafos, Computabilidad y Lenguajes Formales, Probabilidad Discreta
Tipo de curso: Núcleo de Formación Fundamental
El curso estudia técnicas para diseñar algoritmos como, por ejemplo, dividir y conquistar, programación dinámica, programación voraz/avara y reintento. A los algoritmos desarrollados mediante estas técnicas se les aplican los dos tipos de análisis fundamentales en algoritmia: el de corrección y el de eficiencia. El curso también aborda técnicas de diseño de algoritmos aleatorizados y de algoritmos de aproximación, al igual que explora técnicas en la teoría de números computacional y en la computación geométrica. En la última parte del curso se introducen modelos de computación en paralelo.
Usar técnicas de diseño algorítmico para resolver problemas de decisión, optimización y búsqueda computacional.
Diseñar algoritmos basándose en los principios de dividir y conquistar, programación avara/voraz y reintento.
Describir las ventajas y desventajas de algoritmos aleatorizados y de aproximación.
Aplicar técnicas para optimización de recursos en el diseño de una solución algorítmica.
Demostrar y argumentar la corrección y eficiencia de un algoritmo.
Plantear contratos (i.e., precondición, poscondición, invariantes) para algoritmos iterativos y recurrentes.
Demostrar que un algoritmo es correcto con respecto a su especificación; en particular, justificar por qué una fórmula es invariante de un ciclo.
Calcular las complejidades temporal y espacial de una algoritmo en el peor de los casos.
Implementar correcta y eficientemente soluciones algorítmicas en un lenguaje de programación.
Escribir programas en un lenguaje de programación con base en el diseño algorítmico de una solución.
Conocer las ventajas y desventajas de los lenguajes de programación utilizados para implementar un diseño algorítmico.
Identificar técnicas de aproximación algorítmica para resolver problemas intratables (i.e., computacionalmente difíciles).
Entender la programación lineal como un método general para resolver problemas de optimización.
Usar la aproximación lineal para obtener algoritmos de aproximación para problemas algorítmicos combinatorios.
Comprender las diferencias entre los modelos de computación secuenciales y los modelos de computación en paralelo.
Distinguir entre modelos de computación secuencial y modelos de computación en paralelo.
Conocer las limitaciones prácticas de los modelos de computación en paralelo.
Se desarrollan competencias en
El uso de un lenguaje de programación imperativo.
La implementación de algoritmos correctos y eficientes en un lenguaje de programación.
La estimación de complejidades algorítmicas para el peor de los casos.
El diseño de casos de prueba para validar el comportamiento de los algoritmos diseñados.
1-2 3 2 Introducción y repaso. Inducción matemática. Diseño algorítmico. Notación asintótica. Algoritmos cuadráticos de ordenamiento. Uso [1 caps 1,2] [2 cap 2][3 cap 0, app 1][5 cap 1]
Total de Horas: 5.
1-2 4 Tareas semanales, resolución de problemas en temas vistos [1,cap 1,2][2 cap 2][3 cap 0, app 1][5 cap 1]
Total de Horas: 4.
Capítulo 2: Dividir y conquistar
3-6 6 4 Dividir, conquistar y combinar. Relación con inducción matemática. MergeSort. HeapSort. Bisección y búsqueda binaria. Teorema Maestro. Evaluación [1 cap 4][2 cap 5][3 cap 1][5 cap 2]
Total de Horas: 10.
3-6 8 Tareas semanales, resolución de problemas en temas vistos [1 cap 4][2 cap 5][3 cap 1][5 cap 2]
Total de Horas: 8.
Capítulo 3: Técnicas de diseño algorítmico
7-11 7 5.5 Programación dinámica. Memorización (top-down). Tabulación (bottom-up). Técnicas de ahorro de memoria. Evaluación [1 cap 15][2 cap 6][3 caps 5,6][5 cap 3]
12-15 6 4 Algoritmos avaros/voraces. Óptimos locales. Técnicas de demostración de optimalidad. Evaluación [1 cap 16][2 cap 4][3 cap 7][5 cap 4]
16-18 5 2.5 Reintento (backtracking). Búsqueda exhaustiva. Heurísticas. Evaluación [3 cap 3][5 caps 5,6]
Total de Horas: 30.
7-18 24 Tareas semanales, resolución de problemas en temas vistos [1 caps 15,16][2 caps 4,6][3 caps 3,5-7][5 caps 3-6]
Total de Horas: 24.
Capítulo 4: Temas seleccionados
19-21 4 3.5 Teoría de números computacional. El algoritmo de Euclides. Criba de Eratóstenes. Test de primalidad. Factorización de números. Funciones multiplicativas. Aritmética de precisión arbitraria. Ciframiento. Evaluación [1 cap 31][4 cap 5][5 cap 10]
22-24 4 3.5 Geometría computacional. Representación de puntos, líneas, segmentos, polígonos. Intersección de segmentos, polígonos. Envolvimiento convexo. Evaluación [1 cap 33][4 cap 7]
Total de Horas: 15.
19-24 12 Tareas semanales, resolución de problemas en temas vistos [1 caps 31,33][4 caps 5,7][5 cap 10]
Total de Horas: 12.
Capítulo 5: Otras técnicas algorítmicas
25-26 3 2 Algoritmos aleatorizados. Quicksort. El algoritmo de Rabin y Karp. Uso [1 cap 7][3 cap 13]
27-29 5 2.5 Algoritmos de aproximación. Programación lineal entera. El algoritmo Simplex. Eliminación Gaussiana. Rounding. Cubrimiento de vértices. Uso [1 cap 29,35][3 caps 26]
Total de Horas: 12.5.
25-29 10 Tareas semanales, resolución de problemas en temas vistos [1 caps 7,29,35][3 caps 13,26]
Capítulo 7: Modelos de computación en paralelo
30-32 5 2.5 Modelos formales de programación en paralelo. Computación secuencial vs. en paralelo. Parallel programming vs. concurrent programming. La ley de Amdahl Uso [5 cap 11]
Total de Horas: 7.5.
30-32 6 Tareas semanales, resolución de problemas en temas vistos [5 cap 11]
Total de Horas: 6.
Relevancia 3 2 3 0 0 2 0 0 0 5 3
(1) baja relevancia - (5) alta relevancia
El curso es presencial y con participación y trabajo en clase. Se asigna trabajos, ejercicios y lecturas. Durante la sesión se expondrán los conceptos acompañados de ejemplos, se fomentará la participación de los estudiantes. Se realizan talleres semanal o bisemanales en los cuales se aplican los fundamentos teóricos.
(A) Aplicación de Conocimientos (A1) Identificar los fundamentos científicos y los principios de ingeniería que rigen un proceso o sistema. (Conocimiento) (A2) Resolver problemas relacionados con la disciplina y otras áreas por medio de la utilización de conocimientos, modelos y formalismos de las ciencias de la computación, las matemáticas y la ingeniería. (Aplicación) (A4) Interpretar modelos matemáticos para estimar su precisión y confiabilidad. (Comprensión) Todos Exposiciones del profesor, talleres, tareas y lecturas Exámenes, Talleres, proyecto
(B) Análisis de problemas y requerimientos (B1) Describir procesos de manera declarativa ignorando los detalles de su implementación. (Comprensión). (B2) Utilizar el lenguaje propio de las matemáticas, la lógica y la ingeniería para especificar requerimientos funcionales y no funcionales de un sistema o proceso. (Aplicación). (B3) Sintetizar la información, evidencias y hechos necesarios para analizar un problema. (Análisis - Síntesis). (B4) Formular hipótesis. Todos Exposiciones del profesor, talleres, tareas y lecturas Exámenes, Talleres, proyecto
(C) Diseño (C1) Utilizar estándares de codificación en la implementación de componentes de software. (Aplicación). (C2) Identificar componentes, interacciones, relaciones e interfaces entre componentes. (Análisis). (C3) Diseñar procesos y componentes de software haciendo uso de la notación, técnicas y herramientas adecuadas. (Síntesis). (C4) Evaluar un componente de software de acuerdo a su complejidad temporal y espacial. (Evaluación). Todos Exposiciones del profesor, talleres, tareas y lecturas Exámenes, Talleres, proyecto
(F) Comunicación efectiva (F2) Comunicarse de manera efectiva de acuerdo al público objetivo haciendo uso correcto del lenguaje, estilo, tiempo y expresión corporal. (Aplicación). (F4) Defender ideas con precisión y claridad. (Evaluación). Todos Ejercicios de demostración, presentación oral y escrita de talleres Exámenes y proyecto
(J) Modelamiento y diseño de sistemas computacionales (J1) Reconocer la importancia del modelamiento cuando se resuelve un problema. (Compresión). (J2) Relacionar conceptos y principios teóricos para la resolución efectiva de un problema. (Síntesis). (J4) Evaluar decisiones de diseño basándose en principios matemáticos y de computación. (Evaluación). Todos Exposiciones del profesor, talleres, tareas y proyectos Exámenes, Talleres, proyecto
(K) Desarrollo de software (K3) Establecer invariantes y propiedades de componentes de software. (Análisis). Todos Exposiciones del profesor, talleres, tareas y proyectos Exámenes, Talleres, proyecto
Contribución al Desarrollo de Competencias (CNA)
La tabla muestra que aspectos de las competencias de Comunicación Escrita, Lectura Crítica y Razonamiento Cuantitativo son evaluados a través de los factores ABET correspondientes. Por otra parte, la competencias de Inglés se favorece gracias a la metodología del curso y también, gracias al factor ABET correspondientes.
Comunicación escrita E E E E E E
Lectura crítica E E E
Inglés U U U U U U
Razonamiento cuantitativo E E E E E
Ejercitar la práctica de la Ingeniería de Sistemas y Computación profesionalmente.
Diseñar y operar sistemas de computación que contribuyen a la solución de problemas relacionados a la disciplina, otra área de la ciencia y la ingeniería u otras disciplinas.
Contribuir al bienestar de las comunidades desde posiciones prominentes en la industria, academia, sector público o como un emprendedor.
Ser distinguido por su bases sólidas en computación, su sentido de ciudadanía responsable, su profesionalismo y liderazgo.
Continuar su desarrollo profesional o involucrarse en estudios de posgrado.
Objetivo 1 X X X X X
Objetivo 2 X X X X X X
Objetivo 3 X
Objetivo 4 X X X X X
Objetivo 5 X X X X X X
Recomendaciones del Director del Programa
Parcial 1	 20 % 17 % 10 % 15 % 11 % 30 % 17 %
Parcial 2	 20 % 17 % 10 % 15 % 11 % 30 % 17 %
Examen final	 20 % 17 % 10 % 15 % 11 % 30 % 17 %
Proyecto 20 % 17 % 15 % 10 % 6 % 30 % 22 %
Talleres y quices 20 % 17 % 5 % 20 % 16 % 30 % 12 %
No está permitido el uso de material en los exámenes, ni el uso de computadores personales ni teléfonos celulares.
Es obligatoria.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. Third Edition. MIT Press, Cambridge, MA, USA, 2009.
J. Kleinberg, É. Tardos. Algorithm Design. Pearson, 2005.
J. Erickson. Algorithms. Urbana, USA, 2015. Available online: http://web.engr.illinois.edu/~jeffe/teaching/algorithms/
S. Halim, F. Halim. Competitive Programming 3: The new lower bound of programming contests. Lulu, 2013.
R. Neapolitan, K. Naimipour. Foundations of Algorithms. 4th Edition. Jones and Barlett Publishers, 2011.
Material de este semestre
Material adicional del curso
materias/analisisdisenoalgoritmos.txt · Última modificación: 2016/09/02 11:38 por camilo.rocha

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución