• Objetivos y Programa

    Objetivos

    • Presentar los conceptos básicos que hacen a la solución algorítmica de problemas correcta y eficiente: especificación, diseño, implementación, complejidad de cómputo.
    • Introducir tipos abstractos de datos recursivos.
    • Presentar las soluciones concretas más reconocidas para los problemas fundamentales de búsqueda y ordenamiento.
    • Presentar técnicas básicas de análisis y de diseño de algoritmos
    • Resolver por computadora proyectos pequeños y medianos donde se apliquen las herramientas y técnicas aprendidas, incluyendo el tratamiento de archivos secuenciales.

     

    Programa

    1. Tipos abstractos de datos y problemas

    • Tipos abstractos de datos: secuencia; pila; cola; arreglo; árbol binario; conjunto; diccionario.
    • Especificación: descripción de problemas utilizando tipos abstractos; modularización.
    • Recursión: axiomatización de funciones mediante la recursión; inducción estructural.

     

    2. Diseño, estructuras de datos y algoritmos

    • Diseño: conceptos; módulos; relación implementa_a; invariante de representación y función de abstracción; diagramas conmutativos.
    • Complejidad de algoritmos: Análisis asintótico del peor caso y caso promedio. Notación O(). Cotas superiores e inferiores.
    • Estructuras de Datos: representaciones simples para secuencias, pilas y colas; representaciones simples para diccionarios/conjuntos: secuencias, arreglos, punteros, árboles binarios y árboles binarios de búsqueda; representaciones más elaboradas: árboles balanceados, árboles AVL, hashing abierto, hashing cerrado y tries; colas de prioridad: heaps. Búsqueda y ordenamiento en memoria secundaria. Otras estructuras de datos para diccionarios.
    • Algoritmos de Ordenamiento: Métodos básicos: inserción, selección. Métodos elaborados: quicksort, mergesort, heapsort. Algoritmos de ordenamiento para inputs particulares.

     

    3. Técnicas Algorítmicas

    • Divide & Conquer.
    • Generalización de funciones.
    • Eliminación de la Recursión: plegado/desplegado; inmersión de parámetros.
    • Aplicación de algoritmos y estructuras de datos a otros problemas.