| Profesor: Agustín J. González Horario clases: Miércoles 8:15-9:45 en C-236 y Viernes 17:20-18:50 en C-236 Oficina: B-322 e-mail: agv "arroa" elo.utfsm.cl Fono: 654196 Horario de Oficina |
Ayudantes: Isabel Delgado /
Cristian González email: elo320 en elo.utfsm.cl Lista de correo: lista_elo320 @ elo.utfsm.cl (ver instrucciones de uso aquí ) |
|
Textos: Otros textos de referencia: |
|
Motivación
Fundamentos Matemáticos requeridos para la
evaluación de algoritmos
Crecimiento de
funciones (insertion-sort) y definiciones (animación insertionSort),
Análisis de Algoritmos
(merge-sort) Ver tarea 1
InsertionSort/MergeSort/HeapSort 2002 y alguna solución.,
Algorithmos de ordenamiento :
Definiciones: Conjunto, grafo,
árbol .
Heapsort (animación ordenamiento, animación de colas
de prioridad), Quicksort (Animación) (ver tarea
Quicksort año 2003 Enunciado Solución)
Ordenamiento en tiempo lineal , Mediana y estadisticas de orden.
(animación radixSort)
(Ver tarea 2 año 01,
y solución de Christian
Bravo)
<======
Desde aquí para el certamen final, por mal resultado en pregunta
sobre listas ======>
Estructuras de datos :
Estructuras de datos
elementales: Pilas (stacks), colas (Queues), Listas
enlazadas, y Árboles Vea tarea sobre uso de stack
para evaluar expresiones aritméticas. (Solución)
Tablas hash Animación de hash cerrado
con función de re-hash lineal
<======
Desde aquí la MAYOR PARTE del certamen final ======>
Árboles de búsqueda
binaria,
Extensiones a Estructuras de
Datos Básicas. Ejemplo
de uso. Mejor
solución de la época dada por Carlos Zamora
Algoritmos "Oportunistas" (Greedy
Algorithms)
Algoritmos en Grafos:
Algoritmos elementales:
Breadth-first search (animación)
y Depth-first search (animación):
Orden topológico y componentes fuertemente conexas.,
Minimum Spanning Tree
(árbol de expasión de peso mínimo): Prim (Animación) y
Kruskal (Animación) ,
Camino más corto
desde una fuente. Algoritmos de Dijkstra (Animación 1-fija, Animación 2
-configurable-) y Bellman- Ford
Redes de Flujo Aquí
pueden encontrar un applet que ilustra el resultado de este algoritmo.
NP_Completitud
<======
Hasta aquí para el certamen final ======>
Sobre perfiles de
ejecución y depuración de programas
Biblioteca Estandar de Pantillas de C++ ( C++
Standard Template Library)
Fundamentos de C++
Vectores
Ejemplos sobre uso de STL: vector.cpp list.cpp count.cpp upperBound.cpp
Evaluación:
35 % Primer
Certamen: 30 de Abril. Solución Histograma Otros
años 2003 Histograma 2003,2002 2001
45 % Segundo
Certamen: 23 de Junio. Solución Histograma Otros
años 2003 Histograma 2003, 2002 2001 3er. Certamen 2001
20 %
Tareas Procedimiento de entrega de
programas , Evaluación
de tareas
NOTAS incluye corrección
última tarea
Correlación Notas
tareas-Promedio Certamenes
Correlación Asistencia a
clases - Promedio Certamenes
Misceláneos
Resultados
de las Evaluación Docente 1s2004:
Problemas
de Ingenio: este dato es un aporte de de Orlando Pinto.
Más
problemas de Ingenio: este dato es un aporte de Domingo Devotto.
ELO320 año 2003
Material
complementario sobre directivas del procesador
Revisión
de Lenguaje de programación C.
Introducción
a Makefile
Ejemplo de uso de gnuplot
Sobre
Intervalos de Confianza: entendiendo el concepto , definición
formal y cálculo de intervalos de confianza para el promedio.
Manual GNU para make(versión html Local)
Compilador C++
GNU