You are here: TWiki> AED Web>WebHome (2017-08-17, MarioStorti)

Universidad Nacional del Litoral
Facultad de Ingeniería y Ciencias Hídricas

Algoritmos y Estructuras de Datos

Ir a la Página de Notas

Novedades feed

[New]

Indice

Cátedra e info de la materia. Contacto

  • Carreras: Ingeniería Informática, Analista en Informática Aplicada
  • Extension: Cuatrimestral
  • Carga horaria: 90 hs de clases (30 hs teoría / 60 hs práctica)

  • Docentes:
    • Mario Storti, (mario.storti at gmail.com)
    • Juan Marcelo Giménez (jmarcelogimenez at gmail.com)
    • Pablo Novara (zaskar_84 at yahoo.com.ar)
    • Lautaro Romeo (lau337.r at gmail.com)

Programa Analítico

Está accesible la planificación de la materia.

  1. Diseño y análisis de algoritmos.
    • Conceptos básicos de algoritmos. Ejemplo: Sincronización de acceso a objetos en cálculo distribuido. Introducción básica a grafos. Planteo del problema mediante grafos. Algoritmo de búsqueda exhaustiva. Generación de las coloraciones. Crecimiento del tiempo de ejecución. Búsqueda exhaustiva mejorada. Algoritmo heurístico. Crecimiento del tiempo de ejecución para el algoritmo ávido. Conclusión del ejemplo.
    • Tipos abstractos de datos. Operaciones abstractas y características del TAD conjunto. Interfase del TAD conjunto. Implementación del TAD conjunto. Tiempo de ejecución de un programa. Notación asintótica. Invariancia ante constantes multiplicativas. Invariancia de la tasa de crecimiento ante valores en un conjunto finito de puntos. Transitividad. Regla de la suma. Regla del producto. Funciones típicas utilizadas en la notación asintótica. Equivalencia. La función factorial. Determinación experimental de la tasa de crecimiento. Otros recursos computacionales. Tiempos de ejecución no-polinomiales. Problemas P y NP. Varios parámetros en el problema
    • Conteo de operaciones para el cálculo del tiempo de ejecución. Bloques if. Lazos. Suma de potencias. Llamadas a rutinas. Llamadas recursivas
  2. Tipos de datos abstractos fundamentales.
    • El TAD Lista. Descripción matemática de las listas. Operaciones abstractas sobre listas. Una interfase simple para listas. Funciones que retornan referencias. Ejemplos de uso de la interfase. Implementación de listas por arreglos. Eficiencia de la implementación por arreglos. Implementación mediante celdas enlazadas por punteros. El tipo posición. Celda de encabezamiento. Las posiciones `begin' y `end'. Detalles de implementación. Implementación mediante celdas enlazadas por cursores. Cómo conviven varias celdas en un mismo espacio. Gestión de celdas. Analogía entre punteros y cursores. Tiempos de ejecución de los métodos en las diferentes implementaciones. Interfase STL. Ventajas de la interfase STL. Ejemplo de uso. Uso de templates y clases anidadas. Operadores de incremento prefijo y postfijo. Listas doblemente enlazadas.
    • El TAD pila. Ejemplo: Una calculadora RPN con una pila. Operaciones abstractas sobre pilas. Interfase para pila. Implementación de una calculadora RPN. Implementación de pilas mediante listas. La pila como un adaptador. Interfase STL.
    • El TAD cola. Ejemplo: Intercalación de vectores ordenados. Ordenamiento por inserción. Tiempo de ejecución. Particularidades al estar las secuencias pares e impares ordenadas. Algoritmo de intercalación con una cola auxiliar. Operaciones abstractas sobre colas. Interfase para cola. Implementación del algoritmo de intercalación de vectores. Tiempo de ejecución.
    • El TAD correspondencia. Interfase simple para correspondencias. Implementación de correspondencias mediante contenedores lineales. Implementación mediante contenedores lineales ordenados. Implementación de mediante listas ordenadas. Interfase compatible con STL. Tiempos de ejecución para listas ordenadas. Implementación mediante vectores ordenados. Tiempos de ejecución para vectores ordenados. Definición de una relación de orden.
  3. Arboles.
    • Nomenclatura básica de árboles. Altura de un nodo. Profundidad de un nodo. Nivel. Nodos hermanos. Orden de los nodos. Particionamiento del conjunto de nodos. Listado de los nodos de un árbol. Orden previo. Orden posterior. Orden posterior y la notación polaca invertida. Notación Lisp para árboles. Reconstrucción del árbol a partir de sus órdenes.
    • Operaciones con árboles. Algoritmos para listar nodos. Inserción en árboles. Algoritmo para copiar árboles. Supresión en árboles. Operaciones básicas sobre el tipo árbol.
    • Interfase básica para árboles. Listados en orden previo y posterior y notación Lisp. Funciones auxiliares para recursión y sobrecarga de funciones. Algoritmos de copia. Algoritmo de poda. Implementación de la interfase básica por punteros. El tipo iterator. Las clases `cell' e `iterator'. La clase tree. Interfase avanzada. Ejemplo de uso de la interfase avanzada. Tiempos de ejecución
    • Arboles binarios. Listados en orden simétrico. Notación Lisp. Árbol binario lleno. Operaciones básicas sobre árboles binarios. Interfases e implementaciones. Interfase básica. Predicados de igualdad y espejo. Hacer espejo "in place". Implementación con celdas enlazadas por punteros . El algoritmo apply y principios de programación funcional. . Implementación de la interfase avanzada.
    • Arboles de Huffman. Condición de prefijos. Representación de códigos como árboles de Huffman. Códigos redundantes. Tabla de códigos óptima. Algoritmo de búsqueda exhaustiva. Generación de los árboles. Un toque de programación funcional. El algoritmo de combinación. Función auxiliar que calcula la longitud media . El algoritmo de Huffman. Implementación del algoritmo. Ejemplo: Un programa de compresión de archivos.
  4. Conjuntos.
    • Introducción a los conjuntos. Notación de conjuntos. Interfase básica para conjuntos. Análisis de flujo de datos.
    • Implementación por vectores de bits. Conjuntos universales que no son rangos contiguos de enteros. Descripción del código.
    • Implementación con listas. Similaridad entre los TAD conjunto y correspondencia. Algoritmo lineal para las operaciones binarias. Descripción de la implementación. Tiempos de ejecución.
    • Interfase avanzada para conjuntos.
    • El diccionario. La estructura tabla de dispersión. Tablas de dispersión abiertas. Detalles de implementación. Tiempos de ejecución. Funciones de dispersión. Tablas de dispersión cerradas. Costo de la inserción exitosa. Costo de la inserción no exitosa. Costo de la búsqueda. Supresión de elementos. Costo de las funciones cuando hay supresión. Reinserción de la tabla. Costo de las operaciones con supresión. Estrategias de redispersión. Detalles de implementación.
    • Conjuntos con árboles binarios de búsqueda. Representación como lista ordenada de los valores. Verificar la condición de ABB. Mínimo y máximo. Buscar un elemento. Costo de mínimo. Operación de inserción. Operación de borrado. Recorrido en el árbol. Operaciones binarias. Detalles de implementación. Tiempos de ejecución. Balanceo del árbol.
  5. Ordenamiento.
    • Introducción. Relaciones de orden débiles. Signatura de las relaciones de orden. Predicados binarios. Relaciones de orden inducidas por composición. Estabilidad. Primeras estimaciones de eficiencia. Algoritmos de ordenamiento en las STL.
    • Métodos de ordenamiento lentos. El método de la burbuja. El método de inserción. El método de selección. Comparación de los métodos lentos. Estabilidad.
    • Ordenamiento indirecto. Minimizar la llamada a funciones.
    • 5.4. El método de ordenamiento rápido, quick-sort. Tiempo de ejecución. Casos extremos. Elección del pivote. Tiempo de ejecución. Caso promedio. Dispersión de los tiempos de ejecución. Elección aleatoria del pivote. El algoritmo de partición . Tiempo de ejecución del algoritmo de particionamiento. Búsqueda del pivote por la mediana. Implementación de quick-sort. Estabilidad. El algoritmo de intercambio (swap). Tiempo de ejecución del quick-sort estable.
    • Ordenamiento por montículos. El montículo. Propiedades. Inserción. Costo de la inserción. Eliminar el mínimo. Costo de re-heap. Implementación in-place. El procedimiento make-heap. Implementación. Propiedades de la clasificación por montículo.
    • 5.6. Ordenamiento por fusión. Implementación. Estabilidad. Versión estable de split. Merge-sort para vectores. Clasificación externa.
    • 5.7. Comparación de algunas implementaciones de algoritmos de ordenamiento.

Bibliografía

La bibliografía principal a utilizar serán los apuntes de la cátedra (disponible en esta página) y el libro de Aho.

  • Material generado por la catedra:
  • Aho, Hopcroft y Ullman, Estructura de Datos Y Algoritmos, Ed. Addison-Wesley (1988).
  • Tenenbaum y Augenstein, Estructura de Datos en Pascal, Ed. Prentice-Hall (1983).
  • Weiss, Estructuras de Datos y Algoritmos, Ed. Addison Wesley (1995).
  • Wirth, Algoritmos y Estructura de Datos, Ed. Prentice Hall (1987).


Videos de las clases de teoría

Durante el dictado 2016 las clases de teoría han sido grabadas en formato de screencast. Los videos se pueden ver aquí Videos de las clases de teoría o directamente en la siguiente _Youtube playlist_


Modalidad de Dictado

Se dictarán clases:

  • Teoría [a cargo de M. Storti]:
    • Martes de 14hs a 16hs - Aula 2
  • Práctica [a cargo de J. Gimenez y P. Novara]:
    • Martes de 16hs a 18hs - Aula 2
    • Jueves de 16hs a 18hs - Aula 7 del Aulario Común (CUBO)

Evaluación

La evaluación se realiza mediante dos exámenes parciales y tres trabajos prácticos de laboratorio (TPL). Los parciales constan de 6 secciones: CLAS1, PREG1, OPER1, CLAS2, OPER2, PREG2. La regularidad se logra si

  • DP==0 && DTPL==0 && PP>=70
  • donde

    • DP es la cantidad de secciones de parciales adeudadas
    • DTPL es la cantidad de TPLs adeudados
    • PP es el promedio pesado de los parciales y TPL.

    Recuerden que para aprobar cada sección tienen que tener un porcentaje mínimo de 60% en teoría, y 50% en las restantes.

    Lograrán promoción directa cuando

    Se calcula una Nota Final igual al promedio pesado PP de las secciones.

    Se realizará un Examen Recuperatorio. Las reglas del mismo se pueden consultar aquí.

    Aquellos alumnos que no logren promoción directa, deberán rendir un examen final. Los exámenes finales incluyen todos los temas dados en la materia y constan de una evaluación de teoría, que puede ser oral, y una parte escrita que incluye programación, operativos, y clases.

    Cronograma Tentativo

    Inicio de Clases: Semana 1 (Martes 2017-08-15)
    TPL1 (Trab Práctico de Laboratorio 1): Semana 4 (Jueves 2017-09-07)
    Parcial 1: Semana 8 (Jueves 2017-10-05)
    TPL2: Semana 9 (Jueves 2017-10-12)
    TPL3: Semana 12 (Jueves 2017-11-02)
    Recup TPLs: Semana 13 (Martes 2017-11-14)
    Parcial 2: Semana 14 (Jueves 2017-11-16)
    Recuperatorio de los dos parciales : Semana 15 (Jueves 2017-11-23)

    Guías de Trabajos Prácticos

    Aquí se puede bajar las guías en formato PDF. Conforme avancen las clases se irán incorporando nuevas guías.

    Guía 1: Diseño y análisis de algoritmos
    Guía 2: Tipos de datos abstractos fundamentales
    Guía 3: Árboles
    Guía 4: Conjuntos

    Exámenes parciales y finales tomados previamente

    (Previo a 2002 en formato MS-Word, posteriores en formato PDF)
    (A partir de 2013 incluye los ZIP con el material de los TPL (no encriptados))

    Los exámenes finales se empezaron a tomar en C++ a partir de la primera fecha de julio 2004. Hasta entonces se tomaba en Pascal.
    Todos los ejemplos se escribirán en C++.
    http://www.cs.princeton.edu/~rs/shell/animate.html: Clasificación animada interactiva (se puede cambiar la secuencia de algoritmos que trabajan con distintos incrementos), se ve muy bien el último paso en clasificación shellsort
    http://oopweb.com/Algorithms/Documents/PLDS210/VolumeFrames.html: OOP, algoritmos y estructura de datos. Parece una buena referencia online.
    http://www.brpreiss.com/books/opus4/: También, una muy buena referencia online sobre OOP, algoritmia y estructuras.
    http://www-cg-hci.informatik.uni-oldenburg.de/~da/peters/Kalvin/Doku-SN.htm Algoritmos de clasificación y sus fuentes. Animaciones.

    Año 2000 (exam00.zip)
    Año 2001 (exam01.zip)
    Año 2002 (exam02.zip)
    Año 2003 (exam03.zip)
    Año 2004 (exam04.zip)
    Año 2005 (exam05.zip)
    Año 2006 (exam06.zip)
    Año 2007 (exam07.zip)
    Año 2008 (exam08.zip)
    Año 2009 (exam09.zip)
    Año 2010 (exam10.zip)
    Año 2011 (exam11.zip)
    Año 2012 (exam12.zip)
    Año 2013 (exam13.zip)
    Año 2014 (exam14.zip)
    Año 2015 (exam15.zip)
    Año 2016 (exam16.zip)
    Todos hasta 2015 inclusive (zippeados: aed-all-exam.zip, en un gran PDF: aed-all-exam.pdf)

    Migración de Pascal a C++

    El lenguaje de programación que se usa desde el cursado 2004 es C++. (Anteriormente se daba en Pascal)

    Los exámenes finales se empezaron a tomar en C++ a partir de la primera fecha de julio 2004. Hasta entonces se tomaba en Pascal.
    Todos los ejemplos se escribirán en C++.

    Enlaces de interés


    http://www.cs.princeton.edu/~rs/shell/animate.html: Clasificación animada interactiva (se puede cambiar la secuencia de algoritmos que trabajan con distintos incrementos), se ve muy bien el último paso en clasificación shellsort
    http://oopweb.com/Algorithms/Documents/PLDS210/VolumeFrames.html: OOP, algoritmos y estructura de datos. Parece una buena referencia online.
    http://www.brpreiss.com/books/opus4/: También, una muy buena referencia online sobre OOP, algoritmia y estructuras.
    http://www-cg-hci.informatik.uni-oldenburg.de/~da/peters/Kalvin/Doku-SN.htm Algoritmos de clasificación y sus fuentes. Animaciones.

    Repositorio de archivos

    En el repositorio de archivos se pueden encontrar ejercicios resueltos de las guías o tomados en exámenes parciales y finales previos. (El viejo repositorio con programas en Pascal se accede aqui )

    Torneo de Programación

    La cátedra organiza un Torneo de Programación

    Topic attachments
    I Attachment Action Size Date Who Comment
    pdfpdf aed-programa.pdf manage 86.3 K 2015-07-27 - 17:48 MarioStorti  
    pdfpdf gtp1_aed.pdf manage 139.6 K 2017-08-12 - 14:02 CimecUser  
    pdfpdf gtp2_aed.pdf manage 150.7 K 2017-08-12 - 14:03 CimecUser  
    pdfpdf gtp3_aed.pdf manage 160.6 K 2016-10-18 - 19:46 CimecUser  
    pdfpdf gtp4_aed.pdf manage 202.1 K 2016-10-24 - 22:00 CimecUser Guía de TPs nro 4 - 2016
    elsehpp ver1.hpp manage 3.2 K 2015-08-12 - 17:18 MarioStorti  
    Topic revision: r244 - 2017-08-17 - 10:57:37 - MarioStorti
     

    TWIKI.NET
    This site is powered by the TWiki collaboration platformCopyright � by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
    Ideas, requests, problems regarding TWiki? Send feedback