Textos:
Thomas H. Cormen, Charles e. Leiserson,
y Ronald L. Rivest, "Introducction to Algorithms",
McGraw-Hill, ISBN 0-07-013143-0. 1990 (Ver copias
en Pañol ELO)
Timothy Budd, "Data Structures in C++ using
the Standard Template Library", 1998, Addison Wesley
Publishing, ISBN 0-201-30879-7 (Ver en biblioteca
USM)
Otros textos de referencia:
Brian W. Kernighan Y Dennis M. Ritchie,
"El Lenguage de Programación C" , Prentice Hall, ISBN
968-880-205-0 (Buena referencia de C)
Alfred V. Aho, John E. Hopcroft,
Jeffey D. Hullman, "Data Structures and Algorithms", Addison
Wesley (mi copia es del año 83, presenta la mayor
parte de los algoritmos, pero no es tan completo como el de
Cormen, Leiserson and Rivest, pero puede estar en
biblioteca)
Contenido
Introducción
Lenguaje de
programación C , C++ ???
Fundamentos Matemáticos requeridos
para la evaluacion de algortihmos
Crecimiento de funciones
(insertion-sort) (pdf )
,
Análisis de Algoritmos
(merge-sort) (pdf )
Algorithmos de ordenamiento :
Definiciones: Conjunto, grafo,
árbol ( pdf ).
Heapsort (pdf
),
Quicksort (pdf ),
Ordenamiento en tiempo
lineal , Mediana y estadisticas de orden ( pdf ).
Estructuras de datos :
Estructuras de datos
elementales: Pilas, colas, Listas
enlazadas, y Árboles ( pdf )
Tablas hash (pdf )
Árboles de
búsqueda binaria ( pdf ) ,
Extensiones a
Estructuras de Datos Básicas ( pdf ), etc.
Algoritmos "Oportunistas" (Greedy
Algorithms) (pdf )
Algoritmos en Grafos:
Algoritmos elementales
( pdf ),
Minimum Spanning Tree
(árbol de expasión de peso mínimo):
Prim y Kruskal (pdf
) ,
Camino más
corto desde una fuente ( pdf )
Redes de Flujo (pdf )
NP_Completitud (pdf )
Biblioteca Estandar de Pantillas de C++ ( C++
Standard Template Library)
Bases
de C++ (pdf )
Clases contenedoras (pdf )
Vectores
(pdf )
Evaluación:
30 % Primer Certamen: 8 de Mayo. El Certamen y su
solución ( .pdf
.doc )
45 % Segundo
Certamen: 28 de Junio El Segundo certamen y su
solución (.pdf .doc )
10 % Tareas
analíticas
TA 1 : (pdf ) Plazo de entrega jueves
18 de abril 12:00 en Pañol de electrónica.
TA 2
: Sólo problemas 1,3,4,7, y 8
(pdf ) Plazo de entrega
Lunes 20 de Mayo 12:00 en pañol de electrónica.
TA 3 : (pdf ) Plazo de entrega 28 de
Junio al inicio del certamen.
15 % Tareas de programación: Procedimiento de entrega
, Evaluación
TP 1: Insertion Sort, Mergesort, y heapsort
. Plazo Lunes 15 de abril 24:00.
TP 2: Hashing Cerrado . Plazo 24 de Mayo
24:00.
TP 3: Algoritmo de Dijkstra . Plazo
12 de Junio a las 24:00
Tanto las tareas analíticas como las de
programación se pueden desarrollar en grupo de
dos integrantes. La primera tarea entregada define el
grupo para las futuras tareas. No hay cambio.
Mejores Soluciones a Tareas de Programación:
Tarea 1: Rodrigo
Tobar/Germán Pizarro y Nicolás
Cheker/Eric DeLaGoublaye
Tarea 2: Christian
Pelissier/Claudio Ramirez y
Nicolás Cheker/Eric DeLaGoublaye
Tarea 3: José
Gardiazabal/Claudio Decizer y Eric De La
Goublaye/Nicolás Cheker
Misceláneos
Ejemplo de uso de
gnuplot
Manual GNU para make (versión html Local)
Compilador C++ GNU