ANÁLISIS Y COMPLEJIDAD DE ALGORITMOS


RED NACIONAL UNIVERSITARIA




SYLLABUS



Facultad de Ciencias y Tecnología

Análisis y Complejidad de Algoritmos


TERCER SEMESTRE


Lic. Patricia Caballero V.


Gestión Académica I/2013




















UDABOL
UNIVERSIDAD DE AQUINO BOLIVIA
Acreditada como PLENA mediante R.M. 288/01





VISIÓN DE LA UNIVERSIDAD

Ser la Universidadlíder en calidad educativa.




MISIÓN DE LA UNIVERSIDAD

Desarrollar la Educación Superior Universitaria con calidad y competitividad al servicio de la sociedad.


















SYLLABUS

Asignatura:
ANÁLISIS Y COMPLEJIDAD DE ALGORITMOS
Código:
MAT 211A
Requisito:
CMP 128
Carga Horaria:
80 Horas
Créditos:
8

I. OBJETIVOS GENERALES DE LA ASIGNATURA.
II.Estudiar y analizar la complejidad de los algoritmos desde distintas perspectivas.
Comprender los principios generales del diseño de algoritmos
Analizar la complejidad de problemas y soluciones algorítmicas

II. PROGRAMA ANALÍTICO DE LA ASIGNATURA.

UNIDAD I. ANALISIS DE ALGORITMOS
1. Algoritmo
1.1. Características de un Algoritmo.
1.2. Propiedades de los Algoritmos.
1.3. Fases en eldesarrollo de un Algoritmo.
1.4. Descripción de algoritmos

2. Algoritmia Elemental
2.
2.1. Introducción.
2.2. Eficiencia
2.3. Notación Asintótica
2.4. Relaciones de recurrencia

UNIDAD II. COMPLEJIDAD DE ALGORITMOS
3. Eficiencia y Complejidad
3.
3.1. Introducción.
3.2. Algoritmos numéricos simples
3.3. Problemas de Ordenación
3.4. Problemas de Búsquedas

4. Técnicas de Diseño deAlgoritmos
4.1. Divide y Vencerás.
4.2. Algoritmos Ávidos.
4.3. Programación Dinámica.
4.4. Vuelta Atrás.
4.5. Ramificación y Poda.

UNIDAD III. Análisis y Diseño
5. Taller - Competencias de Programación
4.
4.1. Robot de la Universidad de Valladolid
4.2. Sugerencias sobre programación.
4.3. Como enviar al juez en línea.

6. Teoría de Grafos
6.1. Definiciones básicas
6.2.Representaciones
6.3. Recorridos de grafos
6.4. Algoritmos

7. Clasificación de Problemas
6.1. Problemas P y NP
6.2. Problemas NP completos
6.3. Reducciones.

III. BIBLIOGRAFIA

BRASSARD – BRATLEY, Fundamentos de Algoritmia, Prentice Hall, 2003
AHO, A.; HOPCROFT, J.; ULLMAN, D. Estructuras de Datos y Algoritmos. Addison Wesley.
CARRASCO, R. Curso de Algoritmia Avanzada. Universidad deAlicante. 2006.
SKIENA, S.; REVILLA, M. Programming Challenges. Manual de Entrenamiento para el Concurso de Programación de la ACM. Springer – Verlag New Cork. 2003.
HOROWITZ ., Fundamentals of Data Structures,Computer Science Press, 1981.
REVILLA M., Concursos Internacionales de Informática y Programación, Universidad de Valladolid, 2006.
TERAN J.;Fundamentos de Programación, , 2006.
SHAMSUL A,Art of programming contest - C programming, data structures, algorithms
APUNTES: Adicionalmente el estudiante dispondrá de los Work papers y DIF’s entregados por el docente, los que forman parte del texto de la asignatura.

IV. CONTROL DE EVALUACIONES

1° evaluación parcial: Abril, 2013
Nota: 100 Pts.

2° evaluación parcial: Mayo, 2013
Nota: 100 Pts.

Examen final: Julio, 2013
Nota: 100Pts.

WORK PAPER # 1


No. DE PROCEDIMIENTO:
No. DE HOJAS
ELABORÓ:
CÓDIGO:
TÍTULO DEL WORK PAPER:
Definición de Algoritmo
DPTO.: Facultad de Tecnología
DESTINADO A:
DOCENTES

ALUMNOS
X
ADMINIST.

OTROS

OBSERVACIONES: Análisis y Complejidad de Algoritmos. Ing. Sistemas, Unidad I, Tema 1
FECHA DE DIFUSIÓN: Marzo, 2013
FECHA DE ENTREGA: Marzo, 2013



LA NECESIDAD DEUNA DEFINICIÓN MÁS PRECISA DE ALGORITMO

Definición.-
La palabra Algoritmo procede del vocablo "algoritm", que, a su vez, es la traducción latina del nombre árabe de Al-Khwarizmi, matemático árabe del siglo IX (Abu Ja'far Muhammad ibn Musa Al-Khwarizmi nació en Bagdad en 780 y murió en 850) quien en base a un estudio de geometría y trigonometría pudo establecer por las matemáticas diversos...