Encabezado Facultad de Ciencias
Presentación

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

Quinto Semestre, Análisis de Algoritmos

Grupo 7056, 60 lugares. 22 alumnos.
Profesor María de Luz Gasca Soto lu mi vi 12 a 13
Ayudante Andrea Fernanda Muñiz Patiño ma ju 12 a 13

 

Objetivos Generales.

Se presentan los conceptos de complejidad, justificación, análisis y diseño de algoritmos.
Para desarrollar esos temas se revisan: algoritmos de búsqueda, ordenamiento y los que involucran gráficas.
Se discuten clases de complejidad, revisando brevemente la Clase de los Problemas NP-Completos.
Se dejaran proyectos programación para constatar empíricamente los conceptos aprendidos.
Al final se presenta algún tópico avanzado.

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

Requisito Fundamental: Tener aprobado el curso de Estructuras de Datos

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

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

Sitio del curso: https://sites.google.com/ciencias.unam.mx/ada-2021-1grupo7056/inicio

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

>>La liga para las clases se encuentra en el classroom y se actualizo el 4 de Octubre, si no estas en classroom y estas inscrito manda un correo a mu.andrea@ciencias.unam.mx con el asunto [ADA-2021-1] Alta classroom<<

Liga de la primera reunión:

https://meet.google.com/lookup/ag2ql4uqok

***LIGA ACTUALIZADA el 20 de septiembre a las 2:45***

***---*** La primera reunión será el Lunes 21 de Septiembre a la hora de clase ***---***

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

Dinámica del curso en línea

Plataforma en línea: Classromm y Meet

Sesiones de clases síncronas: 3 Clases; 2 con la profesora y 1 con la ayudante.

Sesiones de clases asíncronas: Se dejará material en el Classroom y en el Drive (página del curso)

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

Recursos Didácticos a usar en el curso

Herramientas digitales: Jamboard, Google Chat, Google Slides, Google Drive y Meet

Además de la Página del curso y el Correo electrónico.

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

1. Algoritmos Iterativos.
2. Algoritmos Recursivos

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

IV. Búsquedas y Ordenamientos

1. Búsquedas (Binaria, Exponencial, por Interpolación)
2. Ordenamientos (MergeSort, QuickSort, HeapSort... )

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. Tiempo Amortizado
3. Geometría Computacional
4. Algoritmos que involucran números
------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------ ------------

Calificación

70% Tareas-Examen
30% Programas

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

Bibliografía

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, 2nd Edition, Third priting, 2002

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.

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

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

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

 


Hecho en México, todos los derechos reservados 2011-2016. Esta página puede ser reproducida con fines no lucrativos, siempre y cuando no se mutile, se cite la fuente completa y su dirección electrónica. De otra forma requiere permiso previo por escrito de la Institución.
Sitio web administrado por la Coordinación de los Servicios de Cómputo de la Facultad de Ciencias. ¿Dudas?, ¿comentarios?. Escribenos. Aviso de privacidad.