Download Diseño y Análisis de Algoritmos

Diseño y Análisis de Algoritmos. (DAA-2008)
Dr. Eric Jeltsch F.
Programa de la asignatura Diseño y Análisis de Algoritmos
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, así como proyectos que se deriven de los contenidos.
Objetivos:
Al término del curso el alumno podrá comparar, 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, realizando aplicaciones
propias 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) que es donde se basan las actividades a realizar durante los
laboratorios. Las actividades se realizan en forma semanal con una duración de 1 bloque (2 horas).
Están programadas en total aprox. 14 sesiones de Laboratorios, frente al PC, además de 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:
Otra forma de evaluar el desempeño del alumno es la de exponer o presentar una idea. Creo que es
una tarea fundamental el saber redactar y preparar un informe, para luego entregarlo de manera
didáctica y clara, frente a sus pares. De ahí, la exigencia de presentar un Portafolio con todas las
actividades del semestre resueltas y mejoradas.
Evaluaciones:
Teoría (3 Pruebas, con el mismo valor ) = 70%
Laboratorios (aprox. 3 evaluaciones + Proyecto Final, con el mismo valor) = 30% .
Observación: Como una forma de retroalimentación y marcar un estándar de lo que se espera de los
alumnos, es que se mantienen las Pautas de Corrección de pruebas anteriores, en la Secretaría de la
Escuela de Ingeniería en Computación.
Fechas de Pruebas y Examen:
_____________________________________________________________________________ 1
Escuela de Ingeniería en Computación, Universidad de La Serena.
Diseño y Análisis de Algoritmos. (DAA-2008)
Dr. Eric Jeltsch F.
Prueba nº1, (Martes) 29 Abril,
Prueba nº2,
“
3 Junio,
Prueba nº3,
“
8 Julio.
Examen 14 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, pertinencia y oportunidad 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, Btree,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.
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
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.
CAPITULO 10 - Programación Greedy
Contenidos: Programación Greedy. Enfasis en ejemplos y aplicaciones, por ejemplo: Problema de la
Mochila (0-1), Código de Huffman, y otros.
CAPITULO 11 - Programación Dividir para Conquistar
_____________________________________________________________________________ 2
Escuela de Ingeniería en Computación, Universidad de La Serena.
Diseño y Análisis de Algoritmos. (DAA-2008)
Dr. Eric Jeltsch F.
Contenidos: Programación Dividir para Reina. Enfasis en ejemplos y aplicaciones, por ejemplo:
Skyline, Multiplicación Rápida de Integer- Matriz, y otros. Introducción a otros métodos, tales
como Branch and Bound, Backtracking.
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. Enfasis en Arboles Expandido
Minimal, Algoritmos de Kruskal, Prim y otros.
CAPITULO 13 - Aplicaciones Varias de los Grafos
Contenidos: Camino Minimal, Algoritmos de Dijkstra, Bellman - Ford, Floyd - Warshall, Flujo
Máximo (Ford Fulkenson), y otros.
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.
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.
CAPITULO 16 - Computabilidad
Contenidos:Problemas NP- Completo, NP- Hard y otras clasificaciones.
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.
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.
_____________________________________________________________________________
Escuela de Ingeniería en Computación, Universidad de La Serena.
3
Diseño y Análisis de Algoritmos. (DAA-2008)
Dr. Eric Jeltsch F.
LABORATORIOS - Contenidos
Objetivo: Manejo de alguna plataforma o herramientas de desarrollo, por ejemplo, Netbeans,
Eclipse u otra. 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. Iniciarse en la programación enfocada a servidor
usando la plataforma J2EE (Java 2 Enterprise Edition), una de las formas de programar en Java más
ampliamente extendida a nivel empresarial.
Cap. 1 Conocer el manejo de IDE (Integrated Development Environment) apropiado para la
asignatura. Por ejemplo, JBuilder, Eclipse, NetBeans IDE entre otros. Entregar un manual de
Usuario con el uso del IDE correspondiente con la construcción de alguna aplicación.
Cap. 2 Estudio de la API Collection. En este tema se estudia un conjunto de clases e interfaces
de Java que forman el Java Collections Framework (JCF) que constituyen un conjunto de
herramientas que aumentan las capacidades del lenguaje a la hora de trabajar con estructuras de
datos. Construir un sistema de software, con la implementación de las herramientas de Collections.
Cap. 3 Estudio de la API Collection/Generics. Generics agrega estabilidad a su código, al hacer
más fácil, detectar los errores en tiempo de compilación. Atención: Este capitulo cubre Java 2 Platform
Standard Edition version 5.0. Visite la J2SE 5.0 download page. Construir un sistema de software, con la
implementación de las herramientas de Collections/Generics.
Cap. 4 Estudio de la API JDBC. JDBC Database Access. JDBC es una API para trabajar la
conectividad entre las aplicaciones Java y un amplio rango de bases de dato y data sources.
Construir un sistema de software, con la implementación de las herramientas de JDBC.
Cap. 5 Swing. Implementación de alguna GUI, en donde aplique las diversas componentes,
además de lo visto hasta ahora. Construir un sistema de software, en donde se incluyan
componentes Swing y bases de datos construidas ya sea en Access, MySQL, o alguna otra, así como
la aplicación de clases genéricas. La propuesta debería incluir la salida de alguna información que
pueda ser impresa a través de algún modulo de impresión para tal efecto.
Cap. 6 Desarrollar una aplicación en el contexto de alguna API, por ejemplo. Java TV
application programming interface provides an ideal development and deployment platform for the
emerging class of interactive television services. http://java.sun.com/products/javatv/index.jsp
TM
_____________________________________________________________________________
Escuela de Ingeniería en Computación, Universidad de La Serena.
4
Diseño y Análisis de Algoritmos. (DAA-2008)
Dr. Eric Jeltsch F.
The Java Telephony API (JTAPI) supports telephony call control. It is an extensible API designed to
scale for use in a range of domains, from first-party call control in a consumer device to third-party
call control in large distributed call centers. http://java.sun.com/products/jtapi/index.jsp
Java Servlet technology provides Web developers with a simple, consistent mechanism for
extending the functionality of a Web server and for accessing existing business systems. A servlet
can almost be thought of as an applet that runs on the server side--without a face. Java servlets
make many Web applications possible. http://java.sun.com/products/servlet/index.jsp
Java™ security technology includes a large set of APIs, tools, and implementations of commonlyused security algorithms, mechanisms, and protocols. The Java security APIs span a wide range of
areas, including cryptography, public key infrastructure, secure communication, authentication,
and access control. Java security technology provides the developer with a comprehensive security
framework for writing applications, and also provides the user or administrator with a a set of tools
to securely manage applications. http://java.sun.com/docs/books/tutorial/security/index.html
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)
•
Chan, Griffith, Iasi, "1001 Tips para programar con Java", McGrawHill, 1998.
•
Naughton, Schildt, "Java Manual de Referencia", McGrawHill, 1998.
•
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.
5