Ciencias de la Computación (plan 2013) 2025-1

Quinto Semestre, Análisis de Algoritmos

Objetivos Generales

Se presentan conceptos sobre complejidad. Se estudia cómo justificar, analizar y diseñar algoritmos.

Se revisan: algoritmos sobre búsqueda, ordenamiento y los que involucran gráficas.

Se discuten clases de complejidad, revisando brevemente la Clase de los Problemas NP-Completos.

Se dejan proyectos programación para constatar empíricamente los conceptos aprendidos.

Al final, si hay tiempo, se presenta algún tópico avanzado.

------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------

Requisito Fundamental: Tener aprobado el curso de Estructuras de Datos

*** *** *** *** Tendrán prioridad Inscripciones Ordinarias *** *** *** ***

*** *** *** Iniciaremos clase desde el primer día de clases *** *** ***

++ ++ ++ Primer Día de Clases: Lunes 05 de Agosto del 2024 ++ ++ ++

------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------

Este curso es de Modalidad Presencial

------------ ------------ ------------ ------------ ------------ ------------ ------------

Classroom

Se mantendrá un Classroom para el grupo, con el objetivo de dejar ahí material y tareas.

##### ..... ##### ..... ##### ..... ##### ..... ##### ..... ##### ..... #####

Se darán de alta en el classroom a los alumnos inscritos al curso.

Si después del primer día de clases no estás inscrito en el classroom,

por favor manda correo a la profesora o al ayudante ...

##### ..... ##### ..... ##### ..... ##### ..... ##### ..... ##### ..... #####

..... ..... << Es necesario acceder desde una cuenta de ciencias >> ..... .....

----------- ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------

Recursos Didácticos a usar en el curso

Herramientas digitales:

Classrom, Jamboard, Google Chat, Google Slides, Google Drive, Meet ...

Material didáctico digital:

Libros de texto, tesis y artículos digitales (Bidi-Unam)

Lectures (material tomado de alguna universidad)

Notas de clase del profesor (mis notitas)

Ejercicios y Notas preparadas por el profesor y ayudante.

------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------

T E M A R I O

I. Conceptos Básicos

II. Justificación de Algoritmos ( Iterativos y Recursivos)

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

IV. Búsquedas y Ordenamientos

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

2. Ordenamientos (Insertion Sort, Selection Sort, MergeSort, QuickSort, HeapSort, Radix Sort, ... )

V. Teoría de Gráficas

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

2. Árboles Generadores de peso mínimo (Prim, Kruskal, Boruvka)

3. Ruta más Corta (Dijkstra)

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. Demostración de Problemas NP-Completos

5. Algoritmos de Aproximación

VII. Tópicos Avanzados

1. Flujo en Redes

2. Métodos Numéricos

3. Geometría Computacional

------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------

50% Tareas ... 20% Exámenes ... 30% Programas

*** No se aceptarán tareas después de la fecha fijada de entrega ***

+++ Pasaremos Lista, todos los días +++

*** No habrá reposiciones ***

------------ ------------ ------------ ------------ ------------ ------------ ------------

Bibliografía Básica

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

Cormen, T.H; L.C.E. & R.R.L. Introduction to Algorithms,Addison Wesley, USA, 2nd Edition, Third priting, 2002

Kleingerg, J. & Tardos, E. Algorithm Design. Addison Wesley, 2005

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

Neapolitan, R. & Naimipour K. Fundations of Algorithms. 2nd Ed. Jones and Bartlett Pu, 1999

Papadimitriou, C. H. and Vazirani, U. V. Algorithms. Mc Graw-Hill, 2006

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

Weiss, M. A. Data Structures and Algorithms Analysis in Java, Addison Wesley, 3rd. edition, 2011.