Download Programa de la asignatura con pruebas y Examen

Diseño y Análisis de Algoritmos. (DAA-2014)
Programa de la asignatura Diseño y Análisis de Algoritmos
Dr. Eric Jeltsch F.
TEL: 4-0-2
Requisitos Informales: Se espera que el alumno tenga sólida base en Programación Orientada a
Objetos, así como el manejo para abordar problemas de análisis y desarrollos matemáticos.
Requisitos Formales: Aprobadas las asignaturas de Programación y Fundamentos de
Informática Teórica.
Descripción de la Asignatura:
Es un curso del Ciclo Superior, teórico- práctico, que entrega las herramientas para reconocer,
evaluar, recomendar y diseñar estructuras de datos apropiadas para enfrentar diversas aplicaciones o
requerimientos. Al mismo tiempo en los Laboratorios, se utiliza el lenguaje Java como lenguaje de
programación y la Programación Orientada a Objeto como paradigma para implementar los
diversos algoritmos con la programación genérica. Se llevan a cabo diversas actividades y proyectos
que se derivan de los contenidos.
Objetivos:
Al término del curso el alumno podrá proponer, reconocer y diseñar algoritmos según metodologías
apropiadas, tales como Dividir para Reinar, Heurística Greedy y Programación Dinámica. Podrá
comparar, construir y evaluar algoritmos, esto último, desde el punto de vista de complejidad y
costo asintótico, así como conocer las restricciones de los mismos. Podrá también analizar,
recomendar y aplicar una diversidad de estructuras abstractas de datos y algoritmos en diversos
ámbitos, de acuerdo a parámetros teóricos y prácticos. Además el alumno en los Laboratorios
seguirá desarrollando habilidades en la programación en Java, y en el uso y manejo de librerías, con
las cuales podrá realizar sus propias aplicaciones en el ámbito de los contenidos.
Metodología:
Para cumplir con los objetivos se utiliza una metodología de tipo Teórico - Práctico. La Teoría se
realiza mediante la presentación de los contenidos, fundamentos y algoritmos con ejemplos típicos
de los temas, utilizando transparencias y link apropiados. Se mantendrá un sitio Web con secciones
de ejercicios, problemas y pruebas de años anteriores. Para la sección de Práctica se entrega un
material de apoyo (Libro Guía Web). Las actividades se realizan en forma semanal con una
duración de 1 bloque (2 horas), de las cuales se utilizan para monitorear los estados de avance de
los proyectos. Están programadas 3 evaluaciones, y un Proyecto Final, que debe resumir (o
contener) los temas abordados en los Laboratorios y/o Teoría. La disposición y participación de los
alumnos en clases y laboratorios es fundamental. Por tal motivo, se recomienda que se consideren
12 horas a la semana (extra a las 6 horas correspondientes al TEL), para el estudio y practicas
personales de la asignatura. Suponiendo que un alumno debe realizar en total 40 hrs. a la
semana, como actividad académica.
Exposiciones y Ejercicios:
Otra forma de evaluar el desempeño del alumno es la de exponer o presentar una propuesta en
forma resumida, concisa y clara. Una tarea fundamental es el saber redactar, presentar y preparar un
informe, para luego entregarlo de manera didáctica y clara, frente a sus pares. Al mismo tiempo, por
el material pedagógico y didáctico que se ha ido generando, se entregaran guías de ejercicios y/o
problemas para que los alumnos lo resuelvan y lo expongan. De ahí, la exigencia de exponer
algunos temas y al final del semestre presentar un Portafolio con todas las actividades del semestre
resueltas y mejoradas. En particular, se promoverá la incorporación del editor de texto LATEX en
la presentación y resolución de los ejercicios.
Evaluaciones:
Teoría ( 3 Pruebas, con el mismo valor ) = 50%
_____________________________________________________________________________
Escuela de Ingeniería en Computación, Universidad de La Serena.
1
Diseño y Análisis de Algoritmos. (DAA-2014)
Dr. Eric Jeltsch F.
Laboratorios ( aprox. 3 evaluaciones (o estados de avance) + Proyecto Final, con el mismo valor) =
50%
Fechas de Pruebas y Examen, por fijarse.
Prueba nº 1, 24 de Abril ( Martes )
Prueba nº 2, 29 de Mayo
“
Prueba nº 3, 26 de Junio
“
Examen: 3 de Julio.
TEORIA - Contenidos
CAPITULO 1 - Introducción a la asignatura
Contenidos: Se entrega una introducción al curso y como el programa sustenta otras asignaturas del
plan de estudio de la carrera, así mismo se
aborda el estado del arte de la asignatura, sus
prerrequisitos. Enfatizar en la relevancia y pertinencia de la asignatura en el contexto del plan de
estudio de la carrera y de su futuro profesional.
CAPITULO 2 - Introducción al Análisis de Algoritmos
Contenidos: Introducción al Análisis de Algoritmos. Algoritmos, Análisis de Algoritmos, Diseño de
Algoritmos, Notación Asintótica. Cálculos asintóticos. Repasos fundamentales de Matemática en el
contexto de los temas. Repasos fundamentales de Probabilidades y Estadística en el contexto de los
temas. Enfasis en medir la eficiencia de un algoritmo, ya sea Tiempo y Espacio, considerando peor
caso, mejor caso y caso promedio.
CAPITULO 3 - Métodos de Resolución de Recurrencias
Contenidos: Métodos de Resolución de Recurrencias. Método de Sustitución, Iteración, Arboles
Recursivos, Teorema Maestro. Introducción a la metodología Dividir para Reinar. Enfasis en la
aplicación de los métodos.
CAPITULO 4 – Estructuras de datos
Contenidos: Arboles. Torneos, Arboles ABB, Heap, AVL, Arboles 2-3, 2-3-4, Red-Black, B-tree,
Arboles Splay y otros. Enfasis en transformaciones, rotaciones, buscar, insertar y borrar con sus
costos asociados y aplicaciones.
CAPITULO 5 - Algoritmos de Ordenamiento
Contenidos: Algoritmos de Ordenamiento y su análisis. HeapSort, ShellSort, QuickSort,
StoogeSort y otros. Estabilidad, Ordenamiento en Tiempo Lineal. CountingSort, RadixSort,
BucketSort. Enfasis en saber su funcionamiento y rendimiento según sea el caso con aplicaciones.
Tentativo: Hasta aquí los contenidos para Prueba nº 1.
CAPITULO 6 - Estructuras de Datos Avanzadas
Contenidos: Estructura de Datos Avanzadas. SkipList, Trie, Arboles Sufijo, Arboles Búsqueda
Digital, Arboles Trie y Patricia, Algoritmos de Selección, Arboles Min –Max, y otros. Enfasis en
transformaciones, rotaciones, buscar, insertar y borrar con sus costos asociados y aplicaciones.
CAPITULO 7 - Estructuras de Datos Avanzadas (Heaps)
Contenidos: Heaps. Heaps Binomial, Heaps Fibonacci. Enfasis en transformaciones, rotaciones,
buscar, insertar y borrar con sus costos asociados y aplicaciones.
CAPITULO 8 – Hashing
_____________________________________________________________________________
Escuela de Ingeniería en Computación, Universidad de La Serena.
2
Diseño y Análisis de Algoritmos. (DAA-2014)
Dr. Eric Jeltsch F.
Contenidos: Hashing. Tablas de Hashing, Resolución de Colisiones, Análisis Asintótico con y sin
Probabilidad. Enfasis en la aplicación a diccionarios.
CAPITULO 9 - Programación Dinámica
Contenidos: Fuerza Bruta. Programación Dinámica. Enfasis en ejemplos y aplicaciones, por
ejemplo: Multiplicación Optima de Matrices, Formas de Parentizar, Memoization, Subsecuencia
Común, Arboles de Búsqueda Binaria Optimales, Triangulación del Polígono y otros. Énfasis en la
ejecución y aplicación de los algoritmos en algún contexto.
CAPITULO 10 - Programación Greedy
Contenidos: Programación Greedy. Énfasis en la ejecución y aplicación de los algoritmos en algún
contexto. Por ejemplo: Problema de la Mochila (0-1), Código de Huffman, y otros.
CAPITULO 11 - Programación Dividir para Conquistar
Contenidos: Programación Dividir para Reina. Introducción a otros métodos, tales como Branch
and Bound, Backtracking. Enfasis en ejemplos y aplicaciones, por ejemplo: Skyline, Multiplicación
Rápida de Integer- Matriz, y otros.
Tentativo: Hasta aquí los contenidos para Prueba nº 2.
CAPITULO 12 - Algoritmos de Grafos
Contenidos: Algoritmos de Grafos. Grafos Dirigidos, no-dirigidos, lectura en grafos, por ejemplo:
Búsqueda a lo ancho, Búsqueda en Profundidad, Orden Topológico. Arboles Expandido Minimal,
Algoritmos de Kruskal, Prim y otros. Énfasis en la ejecución y aplicación de los algoritmos en
algún contexto.
CAPITULO 13 - Aplicaciones Varias de los Grafos
Contenidos: Camino Minimal, Algoritmos de Dijkstra, Bellman - Ford, Floyd - Warshall, Flujo
Máximo (Ford Fulkenson), y otros. Énfasis en la ejecución y aplicación de los algoritmos en algún
contexto.
CAPITULO 14 - String Matching
Contenidos: String Matching. Búsqueda de strings: autómata finito, algoritmos de Knuth-MorrisPratt, Boyer-Moore, Rabin-Karp, Shift-Or, y otros. Énfasis en la ejecución y aplicación de los
algoritmos en algún contexto.
CAPITULO 15 - Introducción a la Geometría Computacional
Contenidos: Geometría Computacional. Aplicaciones: Cáscara Convexa, Graham's Scan, y otros.
Aritmética Modular. Criptografía. Énfasis en la ejecución y aplicación de los algoritmos en algún
contexto.
CAPITULO 16 - Computabilidad
Contenidos: Problemas NP- Completo, NP- Hard y otras clasificaciones. Énfasis en la importancia
del tópico en problemas y aplicación de los mismos.
CAPITULO 17 - Y que más.....
Contenidos: Se entrega una visión de futuro en el contexto de la asignatura y como ella sustenta
otras materias. Enfasis en orientar al alumno en otros temas, tales como Bioinformática,
Computación Gráfica, Estructuras de datos Bidimensionales, etc.
Tentativo: Hasta aquí los contenidos para Prueba nº 3.
_____________________________________________________________________________
Escuela de Ingeniería en Computación, Universidad de La Serena.
3
Diseño y Análisis de Algoritmos. (DAA-2014)
Dr. Eric Jeltsch F.
Bibliografía: (*) texto guía, es decir 80% del curso está basado en él.












Aho, Hopcroft, Ullman. "The Design and Analysis of Computer Algorithms", AddisonWesley 1974.
Aho, Hopcroft, Ullman. "Data Structures and Algorithms", Addison-Wesley 1983.
Gonnet, Baeza-Yates "Handbook of Algorithms and Data Structures", Addison_Wesley,
1991.
Shimon Even, "Graph Algorithms", Computer Science Press, Inc.1979.
Horowitz, Sanhi, "Fundamentals of Data Structures", Computer Science Press, Inc.1982.
Robert Kruse, "Estructura de Datos y Diseños de Programas", Prentice Hall, 1988.
(*) Cormen, Leiserson, Rivest, "Introduction to algorithms", McGraw-Hill, 1990 y otros.
Sara Baase, " Computer Algorithms: Introduction to Design and Analysis, 2Ed."
Addison_Wesley, 1988.
Mark Allen Weiss , "Data Structures and Algorithm Analysis (in Java)", Addison_Wesley,
1999.
Standish, "Data Structures, Algorithms, and Software Principles", Addison_Wesley, 1998.
Sedgewick, "Algorithms" , Addison_Wesley, 1996.
Goodrich, Tamassia, "Data Structures and Algorithms in Java", John Wiley & Sons,
Inc.1998.
LABORATORIOS - Contenidos
Objetivo: Continuar profundizando el manejo de alguna plataforma o herramientas de desarrollo,
por ejemplo, Netbeans, Eclipse u otra. (En especial con la que empezó a trabajar en la asignatura de
Programación (Orientada a Objetos). Preparar al alumno en el aprendizaje y aplicación de algunas
API’s de Java, que en el transcurso de la carrera le serán de gran utilidad, por ejemplo Collections,
Generics, y otras. Iniciarse en la programación enfocada a servidor usando la plataforma J2EE (Java
2 Enterprise Edition), JME entre otras. Se concluye el curso con alguna aplicación que convoque la
mayoría de los conceptos que se entregaron en teoría, en especial los algoritmos y estructuras de
datos. El contexto está abierto.
Bibliografía y enlaces Web de utilidad:

http://java.sun.com/downloads/

Horstmann, Cornell, "Core Java Vol I-Fundamentals", JavaSeries, 1999.

Deitel & Deitel, " How to program Java2", 3 Ed., Prentice Hall, 2000.

Bruce Eckel, "Thinking in Java", 2Ed. 2000. (Fuentes)

Mark Allen Weiss , "Data Structures and Algorithm Analysis in Java" Addison_Wesley,
1999.
 Goodrich, Tamassia, "Data Structures and Algorithms in Java", Addison_Wesley, 1998.
_____________________________________________________________________________
Escuela de Ingeniería en Computación, Universidad de La Serena.
4