logoPostgrado nuestro logo



Análisis y Diseño de Algoritmos (AyDA)

Unidades crédito: 4004

Programación semestral: Semestre de 16 semanas con 160 horas/semestre y 10 horas/semana.


la profe

Prof. Isabel M. Besembel Carrera.

Núcleo Pedro Rincón Gutiérrez. La Hechicera. Edificio B. Facultad de Ingeniería. Escuela de Sistemas. Ala Sur. Piso 3. Cubículo 3S07. Mérida 5101-Venezuela.
Tel. +58 274 240 2685 - 240 2811.

TABLA DE CONTENIDO


Descripción del curso,
Conocimiento previo,
Objetivos generales y
Programación semestral


Evaluación y
Bibliografía

1. Técnicas avanzadas de análisis y diseño

2. Estructuras de datos avanzadas

3. Algoritmos para grafos y matemáticos

4. Geometría computacional

5. Complejidad computacional


Descripción del curso:

Se inicia con una descripción detallada de las técnicas de diseño y de análisis de algoritmos aplicadas a los principales métodos de ordenamiento y búsqueda tanto internos como externos, para seguir con las estructuras avanzadas de datos haciendo énfasis en los árboles, se continua con los algoritmos de grafos y los algoritmos matemáticos incluyendo también los algoritmos multihilos. Luego se estudian diversos algoritmos utilizados hasta los momentos en geometría computacional, para finalizar con los problemas de complejidad computacional polinómica y no polinómica.
Durante el curso se utilizarán estrategias de aprendizaje donde se desarrolle investigación documental con su respectiva presentación y defensa de los resultados obtenidos ante el curso.

Conocimiento previo:

  1. Programación digital y manejo de archivos en algún lenguaje de programación, se recomienda el lenguaje java o C++.
  2. Técnicas de acceso asociativo a memoria: hashing e índices
  3. Estructuras de datos: arreglos, registros, cadenas, listas, árboles binarios y montículos.
  4. Técnicas de Ingeniería de Software orientada por objetos.

Objetivos generales:

  1. Consolidar el conocimiento previo en análisis, diseño y uso de algoritmos y estructuras de datos.
  2. Consolidar habilidades de investigación y exposición de resultados sobre temas incluidos en el contenido programático del curso.
  3. Lograr un alto nivel operativo en el uso de algoritmos para estructuras de datos avanzadas, grafos, multihilos, matemáticos, concordancia de patrones y de geometría computacional.
  4. Comprender la importancia de la complejidad computacional y la división de los problemas en aquellos de solución polinómica y los de solución no-polinómica.
  5. Desarrollar habilidades en el análisis, diseño y construcción de algoritmos, que permitan resolver problemas presentados como ejercicios prácticos, en orden de complejidad creciente.

Programación semestral:

Tabla de contenidos


Evaluación:

Bibliografía

Texto:

T. Cormen, C. Leiserson, R. Rivest y C. Stein. Introduction to algorithms. MIT Press and McGraw-Hill. 2009.

Textos de consulta:

Revistas de consulta:

Elsevier. Computational Geometry. Theory and Applications. Cuatrimestral.
ACM Transaction on Database Systems (TODS), SIGMOD, Computing Surveys, Communications, etc.

Tabla de contenidos


Contenidos específicos:

UNIDAD 1.- Técnicas avanzadas de análisis y diseño

SESIÓN

CONTENIDOS

OBJETIVOS

ACTIVIDADES

RECURSOS

EVALUACIÓN

1
2
3

1. Análisis de algoritmos:
Tipos abstractos de datos (TAD), notación TDSO, notaciones estándares, funciones comunes, análisis probabilístico y análisis amortizado: Método agregado, método del contador, método del potencial y tablas dinámicas.
1. Lograr una visión general sobre el análisis de algoritmos y los tipos abstractos de datos (TAD).
  • Lecturas: cap. 1-5 y 17 Cormen y col.
  • Ejercicio 1: sobre TAD.
  • Clase: clase 1, clase 2 y clase 3 .
  • Ejercicio 1
  • Textos
  • Lista del curso
  • Corrección del ejercicio 1.
  • 4
    5
    6

    2. Técnicas de diseño:
    Introducción a las técnicas de diseño: algoritmos incrementales, recursivos, divide-y-vencerás, backtracking y programación dinámica.

    2. Obtener un panorama genérico sobre las técnicas de diseño de algoritmos.

  • Lecturas: guía TDSO Besembel, cap. 2, 4, 15 y 16 Cormen y col.
  • Ejercicio 2: sobre técnicas de diseño.
  • Clases: Clase 4, clase 5 y clase 6
  • Ejercicio 2
  • Textos
  • Lista
  • Corrección del ejercicio 1 (2%).
  • 7
    8

    3. Técnicas de pruebas y corrección de algoritmos:
    Pruebas de corrección parcial, pruebas de parada, pruebas de programas iterativos y recursivos, eliminación de la recursividad.

    2. Desarrollar habilidades en el uso de las técnicas de prueba y corrección de algoritmos.

  • Lecturas: cap. 1-6 Berlioux y Bizard. Cap. 1 Kingston.
  • Ejercicio 3: sobre pruebas de corrección de algoritmos.
  • Clases: clase 7 y clase 8
  • Ejercicio 3
  • Textos
  • Lista
  • Corrección del ejercicio 2 (2%).
  • Tabla de contenidos

    UNIDAD 2.- Estructuras de datos avanzadas

    SESIÓN

    CONTENIDOS

    OBJETIVOS

    ACTIVIDADES

    RECURSOS

    EVALUACIÓN

    9
    10
    11

    1. Fundamentos:
    Estructuras lineales de datos: Pilas, Colas y Listas. Hashing perfecto. Colas por prioridad. Aumento de estructuras de datos y árboles de intervalos. Montículos binarios y de Fibonacci: estructura y operaciones. Conjuntos disjuntos: operaciones, bosques y análisis de la unión por rango con caminos de compresión.
    1. Desarrollar habilidades en el uso de estructuras de datos complejas.
  • Lecturas: Cap. 6, 10-14, 19 y 21 Cormen y col.
  • Ejercicio 4: sobre conjuntos disjuntos.
  • Clase: clase 9 , clase 10 y clase 11.
  • Ejercicio 4
  • Textos
  • Lista del curso
  • Corrección del ejercicio 3 (2%).
  • 12
    13

    2. Árboles monocriterio:
    Introducción. Árbol binarios de búqueda y rojinegros. Familia de árboles_B. Htree.
    2. Lograr una visión general sobre las estructuras de datos para el manejo de índices construidos por una clave.
  • Lecturas: Cap. 12-13, 18 y 20 Cormen y col.
  • Ejercicio 5: sobre árboles_B+.
  • Clase: clase 12 y clase 13 clase 13a.
  • Ejercicio 5
  • Textos y artículo árbol H
  • Lista del curso
  • Corrección del ejercicio 4 (2%).
  • 14
    15

    3. Árboles multicriterio:
    Introducción. Árbol k-d. Quadtree. Octree. Árbol_R.
    3. Lograr una visión general sobre las estructuras de datos para el manejo de índices construidos por dos o más claves.
  • Lecturas: Artículos sobre cada estructura de datos.
  • Ejercicio 6: sobre árboles_R.
  • Clase: clase 14 y clase 15.
  • Ejercicio 6
  • Textos y artículo árbol_R
  • Lista del curso
  • Corrección del ejercicio 5 (3%).
  • Tabla de contenidos

    UNIDAD 3.- Algoritmos para grafos y algoritmos matemáticos

    SESIÓN

    CONTENIDOS

    OBJETIVOS

    ACTIVIDADES

    RECURSOS

    EVALUACIÓN

    16
    17

    1. Fundamentos:
    Definiciones, especificación, representaciones, relaciones, dígrafos, dígrafos acíclicos, búsqueda en amplitud, búsqueda en profundidad, ordenamiento topológico y conectividad. Árboles de expansión mínima: algoritmos de Kruskal y Prim.
    1. Lograr una visión general sobre los algoritmos para grafos.
  • Lecturas: Cap. 22 y 23 Cormen y col.
  • Ejercicio 7: sobre grafos.
  • Clase: clase 16 y clase 17.
  • Ejercicio 7
  • Textos
  • Lista del curso
  • Corrección del ejercicio 6 (3%).
  • 18
    19
    20

    2. Digrafos etiquetados:
    Caminos más cortos y relajación, algoritmo de Dijkstra, algoritmo de Bellman-Ford, restricciones y caminos más cortos (programación lineal), algoritmo de Floyd-Warshall y algoritmo de Johnson. Flujo máximo: Redes de flujo y método de Ford-Fulkerson.

    2. Desarrollar habilidades en el uso de los digrafos etiquetados.

  • Lecturas: Cap. 24-26 Cormen y col.
  • Ejercicio 8: sobre digrafos etiquetados.
  • Clases: clase 18, clase 19 y clase 20.
  • Ejercicio 8
  • Textos
  • Lista
  • Corrección del ejercicio 7 (2%).
  • 21

    3. Matrices:
    Operaciones sobre matrices: Representaciones especiales de matrices, algoritmo de Strassen, sistemas numéricos algebraicos y multiplicación de matrices, sistemas lineales de ecuaciones, inversión de matrices, matrices simétricas positivas y aproximación de mínimos cuadrados.
    3. Desarrollar habilidades en el uso de los algoritmos para matrices.
  • Lecturas: Cap. 28 de Cormen y col.
  • Ejercicio 9: sobre matrices.
  • Clase: clase 21.
  • Ejercicio 9
  • Textos
  • Lista del curso
  • Corrección del ejercicio 8 (3%).
  • 22
    23

    4. Algoritmos Probabilistas y Transformada Rápida de Fourier:
    Algoritmos multihilos y Programación lineal, Transformada discreta de Fourier y transformada rápida de Fourier.

    4. Lograr un alto nivel operativo en el uso de polinomios y transformada rápida de Fourier.

  • Lecturas: Cap. 27 y 29-30 de Cormen y col.
  • Ejercicio 10: sobre polinomios, la transformada rápida de Fourier y teoría de números.
  • Clases: clase 22 y clase 23.
  • Ejercicio 10
  • Textos
  • Lista
  • Corrección del ejercicio 9 (4%).
  • 24
    25

    5. Algoritmos de teoría de números:
    Nociones de teoría de números, máximo común divisor, aritmética modular, sistemas lineales de ecuaciones modulares, teorema de resto chino, potencias de un entero y algoritmo RSA de criptografía.

    5. Desarrollar habilidades en el uso de los algoritmos de teoría de números.

  • Lecturas: Cap. 31 de Cormen y col.
  • Ejercicio 11: sobre algoritmos numéricos.
  • Clases: clase 24 y clase 25
  • Ejercicio 11
  • Textos
  • Lista
  • Corrección del ejercicio 10 (4%).
  • Tabla de contenidos

    UNIDAD 4.- Geometría computacional

    SESIÓN

    CONTENIDOS

    OBJETIVOS

    ACTIVIDADES

    RECURSOS

    EVALUACIÓN

    26
    27

    1. Algoritmos sobre polígonos:
    Teoremas de galería de arte, Teoría de triangulación, área de polígono, intersección de segmentos y algoritmos de triangulación.
    1. Desarrollar habilidades en el uso de algoritmos para polígonos.
  • Lecturas: Cap. 33 de Cormen y col. Cap. 1 O'Rourque.
  • Ejercicio 12: sobre polígonos.
  • Clase: clase 26 y clase 27.
  • Ejercicio 12
  • Textos
  • Lista del curso
  • Corrección del ejercicio 11 (4%).
  • 28

    2. Partición de polígonos:
    Partición monótona, trapeciolización, partición en montañas monótonas, triangulación de tiempo lineal, partición convexa.

    2. Lograr una visión general sobre los métodos de partición de polígonos.

  • Lecturas: cap. 2 O'Rourque.
  • Ejercicio 13: sobre polígonos.
  • Clases: clase 28.
  • Ejercicio 13
  • Textos
  • Lista
  • Corrección del ejercicio 12 (5%).
  • Tabla de contenidos

    UNIDAD 5.- Complejidad Computacional

    SESIÓN

    CONTENIDOS

    OBJETIVOS

    ACTIVIDADES

    RECURSOS

    EVALUACIÓN

    29

    1. Problemas NP-completos:
    Clases P y NP, reducciones polinomiales, problemas NP, algunas pruebas de completitud NP, algoritmos no determinísticos y problemas NP duros.
    1. Lograr una visión general sobre los problemas de completitud computacional.
  • Lecturas: cap. 34 Cormen y col.
  • Ejercicio 14: sobre pruebas de completitud NP y heurísticas.
  • Clase: clase 29 .
  • Ejercicio 14
  • Textos
  • Lista del curso
  • Corrección del ejercicio 13 (5%).
  • 30

    2. Heurísticas y algoritmos de aproximación:
    Algoritmos heurísticos, coloreo de grafos, el problema del vendedor viajero, el problema del morral y aproximaciones a problemas NP duros.

    2. Lograr una visión general sobre el uso de las heurísticas y los algoritmos de aproximación.

  • Lecturas: Cap. 35 de Cormen y col.
  • Clase: clase 30.
  • Textos
  • Lista
  • Corrección del ejercicio 14 (8%).
  • Prueba escrita presencial. (50%).
  • Tabla de contenidos