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.