Algoritmos y Estructuras de Datos
Curso impartido en la UNAM
en la Facultad de Ciencias y en el Posgrado
en Ciencia e Ingeniería de la Computación .
Profesor: Sergio
Rajsbaum
Presentacion del curso
(convertida de Powerpoint a html, optimizada para Internet Explorer).
Semestres en que se ha impartido el curso:
Contenido de esta página
Citas:
"The study of algorithms offers much to the
practicing programmer. A course on the subject equips students with
functions for important tasks and techniques for attacking new
problems. We'll see in later columns how advanced algorithmic
tools sometimes have substantial influence on software systems, both in
reduced development time and in faster execution speed."
Jon Bentley, Programming Pearls, 2000 (2nd Ed,
column 2)
"La
mayoría de los programadores profesionales que me he encontrado,
no están bien preparados para atacar problemas de diseño
de algoritmos. Esto es una lástima, ya que las técnicas
de diseño de algoritmos son una de las tecnologías
prácticas medulares de ciencias de la computación."
"El diseño de algoritmos correctos, eficientes, e implementables
para problemas del mundo real es un asunto delicado, debido a que el
diseñador exitoso de algoritmos requiere de acceso a dos
cuerpos de conocimiento distintos:
- Técnicas - Buenos
diseñadores de algoritmos comprenden varias técnicas
fundamentales de diseño de algoritmos, incluyendo estructuras de
datos, programación dinámica, DFS, backtracking, y
heurísticas. Quizás la técnicas de diseño
más importante sea la de modelar,
el arte de abstraer una aplicación del mundo real poco definida
y convertirla en un problema limpio adecuado para ser atacado
algorítmicamente.
- Recursos - Los buenos
diseñadores de algoritmos se paran sobre los hombros de
gigantes. En lugar de batallar de cero para producir un nuevo algoritmo
para cada tarea, saben como hallar lo que se sabe de un problema
particular. En lugar de reimplementar algoritmos populares desde cero,
saben donde buscar implementaciones existentes que funciones como un
punto de partida. Están familiarizados con un conjunto grande de
problemas algorítmicos básicos, que abarca material
fuente suficiente para modelar casi cualquier aplicación.
Steven S. Skiena, The Algorithm Design Manual, 1997
(Prefacio)
"Two ideas
lie gleaming on the jeweler's velvet.
The first is the calculus,
the second, the algorithm. The calculus and the rich body of
mathematical analysis to which it gave rise made modern science
possible; but it has been the algorithm that has made possible the
modern world."
David Berlinski, The Advent of the
Algorithm, 2000
"A person
well-trained in computer science knows how to deal with algorithms: how
to construct them, manipulate them, understand them, analyze them. This
knowledge is preparation for much more than writing good computer
programs; it is a general-purpose mental tool that will be a definite
aid to the understanding of other subjects, whether they be chemistry,
linguistics, or music, etc. ... An attempt to formalize things as
algorithms leads to a much deeper understanding than if we simply try
to comprehend things in the traditional way."
Donald Knuth, Selected
Papers on Computer Science, Cambridge U. Press, 1996
"Algorithmics is more than a branch of
computer science. It is the core of computer science, and in all
fairness, can be said to be relevant to most of science, business, and
technology."
"People have been known to ask: 'What really is computer science? Why don't we
have submarine science, dishwasher science or telephone science?' ...
It is hoped [] this book will implicitely convey something of the
uniqueness and universality of algorithmics."
"Terming the field 'computer science,' someone once said, is like
referring to surgery as 'knife science.' ... It is generally agreed
that the term 'computer science' is misleading, and that something like
'information science,' 'process science,' or 'the science of the
discrete' might be better."
"We only claim that algorithmics forms the underpinnings of computer
science, not that it replaces it."
David Harel, Algorithmics the Spirit of Computing,
1992
"You think you know when you learn, are
more sure when you can write, even more when you can teach, but certain
when you can program."
Alan
J. Perlis, SIGPAN Notices, 1982
Introducir al alumno al análisis y diseño de algoritmos.
Concentrándose en
algoritmos en gráficas, permite llegar a un mayor nivel de
profundad, y proveer de conocimientos fundamentales para toda
computación.
Fortalecer su formación en teoría de computación y
solución de problemas de
computación.
Se logran estos objetivos mediante un programa intenso de tareas con
ejercicios y lecturas donde el alumno no solo repasa el material visto
en clase, sino que es motivado a que encuentre soluciones por si mismo,
a que desarrolle su creatividad, curiosidad y su capacidad de resolver
problemas complicados, y a que entienda los temas mas a fondo.
"Lo que debemos aprender a hacer lo
aprendemos haciéndolo".
Aristóteles, Ethica Nicomachea II (325 A.C.)
Temas:
- Introducción: Algoritmos, problemas,
codificación. Complejidad y notación asintótica.
Gráficas, y su representación en la computadora.
Invariantes, inducción.
- Paradigmas fundamentales:
Divide-y-vencerás, Programación dinámica.
- Algoritmos de Exploración: Algoritmo de Euler y
aplicaciones (e.g. secuencias deBruijn). BFS y
aplicaciones (e.g. árboles, distancias). DFS y aplicaciones
(e.g. conexidad).
- Árboles Generadores Mínimos: Fundamentos.
Prim y Kruskal.
- Distancias: Fundamentos. Dijkstra. Ford. Floyd.
- Flujo en Redes: Ford-Fulkerson. Edmond-Karp. Variantes y
aplicaciones.
Bilbiografía
Textos:
- Éva
Tardos, Jon
Kleinberg, Algorithm
Design, Addison Wesley, 2005.
- Shimon Even
, "Graph Algorithms", Computer Science Press, 1979
- Thomas H. Cormen
, Charles E. Leiserson
,
y Ronald L. Rivest ,
"Introduction to
Algorithms" , publicado por MIT
Press y McGraw-Hill,
primera edición 1990.
- Robert Tarjan ,
"Data Structures and Network Algorithms", Vol 44 de
Regional Conference Series in Applied Math, SIAM, 1983
- Dexter C. Kozen ,
"The Design and Analysis of Algorithms", Texts and
Monographs in Computer Science, Springer Verlag, 1991
- Steven S. Skiena,
"The Algorithm Design
Manual," Telos-Springer, 1997. (Versión
en línea)
Libros Recomendados:
- Donald E. Knuth, "Stable
Marriage and its Relation to Other Combinatorial Problems,"
American Mathematical Society, volume 10, series CRM Proceedings and
Lecture Notes, 1996.
- Jon Bentley, "Programming Pearls," 2a.
edición, Addison-Wesley, 2000.
- J. van Leeuwen, "Graph Algorithms", en Handbook of
Theoretical
Computer Science: Algorithms and Complexity Vol. A, 525-631, J. van
Leeuwen (ed), MIT Press, 1990
- Donald E. Knuth, "The Stanford Graphbase : A Platform for
Combinatorial Computing," Addison-Wesley, 1993
- David Harel, "Algorithmics : The Spirit of Computing," 2a.
edición, Addison-Wesley 1992
- Aho, Hopcroft y Ullman, "The Design and Analysis of Algorithms,"
Ed. Addison-Wesley, 1979
- Dennis Shasha y Cathy Lazere, "Out of
their Minds," Copernicus, 1998.
- David Berlinski, "The
Advent of the Algorithm," Harcourt, New York, 2000.
Aquí se podrán visitar sitios de interés y
relevancia para el curso.
- Theoretical
Computer Science On The Web : Ligas a páginas de
interés general sobre Teoría de la Computación,
problemas de caminos Hamiltonianos y otros relacionados.
- Páginas
sobre Geometría Computacional
- Teoría-Algoritmos-Complejidad
: Ligas relacionadas a Gráficas
- Analysis
of Algorithms Home Page : Análisis probabilístico y
en el caso promedio.
- Artículo Morphology of
Proof, an introduction to rigorous
proof techniques escrito por Craig
Silverstein , describe la forma de hacer una
demostración o prueba matemática así como varias
técnicas para hacer demostraciones y los casos en que se aplican
- A Computing Research
Repository : Un repositorio de mas de 20,000
articulos y otros documentos de computacion apoyado por ACM, Los Alamos
e-Print archive y NCSTRL (Networked Computer Science Technical
Reference Library), incluyendo la ACM Digital Library
- Artículo How to write a
Proof escrito por Leslie
Lamport . Presenta una metodología para escribir
pruebas matemáticas y garantizar su correctez.
- Congresos sobre Temas Relacionados:
- Programación
- Cursos Similares o Relacionados en otras universidades
- Computer
Science 528: Data Structures and Graph Algorithms , por Robert Tarjan ,
Computer Science Department, Princeton University
- CS
170: Efficient Algorithms and Intractable Problems, Spring 1999,
Professor
Umesh Vazirani with
Christos Papadimitriou, UC Berkeley.
- Advanced
Algorithms, Fall 2003 , por David Karger , MIT
- Computer
Science 311: Design and Analysis of Algorithms , por Soma
Chaudhuri, Department of Computer Science, Iowa State University
Autor original: Miguel Angel Rodríguez
Última modificación: agosto 24, 2004