Ciencias de la Computación (plan 1994) 2012-2

Quinto Semestre, Análisis de Algoritmos I

Profesora: María de Luz Gasca Soto

Ayudante: Mauricio D. Garza R

Laboratorio: Víctor Miguel Peralta S.

Objetivos Generales. En este curso se estudian los conceptos de complejidad: justificación, análisis y diseño de algoritmos. Para desarrollar estos temas se revisan algoritmos de búsqueda, ordenamiento y aquellos que involucran gráficas. Se discuten clases de complejidad, revisando con detalle la Clase de los Problemas NP-Completos.Al final se presenta un tópico avanzado de algoritmos

T E M A R I O

I. Conceptos Básicos

II. Justificación de Algoritmos

1. Inducción Matemática.

2. Algoritmos Iterativos.

3. Algoritmos Recursivos

III. Diseño de Algoritmos usandoInducción Matemática

IV. Secuencias

1. Búsquedas (Binaria, Exponencial, por Interpolación)

2. Ordenamientos (MergeSort, QuickSort, HeapSort... )

3. Árboles Binarios

V. Algoritmos que Involucran Gráficas

1. Recorrido en árboles (BFS,DFS, TopologicalSort)

2. Árboles Generadores de peso mínimo

3. Ruta más Corta

4.Teoría de Redes *

VI. Problemas NP-Completos

1. Introducción

2. Algoritmos Deterministicos y No-Deterministicos

3. Teoría de los Problemas NP-Completos

4. Técnicas para determinar problemas NP-Completos

5. Algoritmos de Aproximación

VII. Tópicos Avanzados

1. Geometría Computacional

2. Algoritmos que involucran números

Calificación

50% Tareas-Examen

20%Examenes

30%Programas

Chartran, G. And Oellermann, O.R.

Applied and Algorithmic Graph Theory. Mc Graw Hill. USA, 1993.

Collins, W.J.

Data Structures. An Object Oriented Approach, Addison Wesley, USA, 1992.

Cormen, T.H; L.C.E. & R.R.L.

Introduction to Algorithms,Addison Wesley, USA,1990.

Kingston, J.

Algorithms and Data Structures: Design, Correctness, and Analysis. ,Addison Wesley, USA,1990.

Manber, U.

Introduction to Algorithms. A Creative Approach, Addison Wesley, USA,1989.

Neapolitan, R. and Naimipour, K.

Foundations of Algorithms.D.C. Heath and Company, USA, 1996.

Rawlins, G.J.E.

Compared to what? An Introduction to the Analysis of Algorithms,Computer Science Press, USA, 1991.