FACULTAD DE INGENIERÍA

ESCUELA DE INGENIERÍA DE SISTEMAS

DEPARTAMENTO DE COMPUTACIÓN
PROGRAMA DE LA ASIGNATURA: Programación 3. Sección. 2.
PRELACIÓN: Programación 2
TPLU: 3124
Isabel M. Besembel Carrera. Oficina: 3S07. Tlf. 2402685.
 CÓDIGO:ISBPR3
UBICACIÓN: 4to. semestre.
FECHA: del 9/4/12 al 27/7/12. (Sem. A-12)
Preparador: Por asignar

TABLA DE CONTENIDO

Descripción del curso
Prerrequisitos
Objetivos generales
Programación semestral
Evaluación
Bibliografía

Contenidos específicos.
Unidades:
1. Análisis de algoritmos
2. Listas
3. Dispersión
4. Montículos
5. Árboles
6. Ordenamiento

Descripción del curso:

Este curso es el último de la cadena de programación, donde se culmina la enseñanza de las principales estrucuras de datos, necesarias para soportar la solución de problemas típicos en las Ciencias Computacionales. Asimismo, este curso sirve de introducción al curso de Diseño y Análisis de Algoritmos, donde se completará la formación en el área de la programación en computadoras.

Prerrequisitos:

  1. Programación digital básica en algún lenguaje de programación, se recomienda el lenguaje C o C++.
  2. Manejo de archivos en programación digital.
  3. Técnicas de programación orientadas por objetos.

Objetivos generales:

  1. Lograr un alto nivel operativo sobre los principales tipos abstractos de datos (TAD), las estructuras de datos lineales y aquellas orientadas hacia la búsqueda y su uso en la solución de problemas de programación.
  2. Desarrollar habilidades en el uso de los principales métodos de ordenamiento.
  3. Obtener una visión global sobre los criterios b´sicos para el diseño, selección y an´lisis de estructuras de datos y algoritmos para situaciones de la Ingeniería.

Programación semestral:

Tabla de contenidos

Evaluación:

Bibliografía:

Tabla de contenidos

UNIDAD 1.- Análisis de algoritmos

CONTENIDOS OBJETIVOS ACTIVIDADES RECURSOS EVALUACIÓN
  1. Tipos abstractos de datos y algoritmos correctos:
    Problemas y especificaciones. Recursividad. Algoritmos correctos iterativos y recursivos. Tipos abstractos de datos.
  1. Lograr una concepción general sobre el concepto de algoritmos correctos.
  • Sesiones de clases: clase de análisis de algoritmos. TDSO.
  • Resolución de los problemas asignados como ejercicio 1 de cada tema.
  • Sesiones prácticas en el Laboratorio Nikolaus Walczuch de la Facultad de Ingeniería.
  • Consultas al profesor.
  • Realización de la primera prueba escrita sobre la unidad 1.
  • Transparencias y presentaciones en web.
  • Laboratorio Nikolaus Walczuch de la Facultad de Ingeniería
  • Heileman. Cap. 1. Joyanes y Zahonero. Cap. 3, Sec. 9.1, 9.2, 16.1 y 16.2.
  • Manuales del lenguaje de programación C y C++.
  • Manuales en línea del depurador de código y del sistema operativo.
  • Corrección de la prueba diagnóstico, donde se evalúan todos los prerrequisitos de la asignatura.

  • Corrección de al menos una consulta sobre los ejercicios asignados.
  • Corrección del ejercicio 1.
  • Corrección de la prueba escrita 1 sobre la unidad 1.
  1. Análisis de algoritmos:
    Operaciones características y complejidad de cálculo. Notaciones. Evaluación de eficiencia. Técnicas algorímicas.
  1. Desarrollar habilidades en el análisis de los algoritmos iterativos, para medir su eficiencia.

Tabla de contenidos

UNIDAD 2.- Listas

CONTENIDOS OBJETIVOS ACTIVIDADES RECURSOS EVALUACIÓN
  1. Listas:
    Introducción. TAD Lista. Conceptos básicos. Especificación. Listas secuenciales y enlazadas, doble y circular. Implementación correcta del TAD y análisis de eficiencia. Gestión de memoria. Ejemplos.
  1. Lograr una concepción general y un uso eficiente del TAD Lista.
  • Sesiones de clases.
  • Sesiones prácticas en el Laboratorio Nikolaus Walczuch de la Facultad de Ingeniería.
  • Consultas al profesor.
  • Realización del ejercicio 2 práctico, incluído en la carpeta de trabajos prácticos de la materia.
  • Realización de la segunda prueba escrita sobre la unidad 2.
  • Guía de clase
  • Laboratorio Nikolaus Walczuch de la Facultad de Ingeniería
  • Heileman. Cap. 5 y 6. Joyanes y Zahonero. Cap. 5-8.
  • Manuales del lenguaje de programación C y C++.
  • Manuales en línea del depurador de código y del sistema operativo.
  • Corrección de un ejercicio teórico asignado.
  • Corrección del ejercicio práctico 2.
  • Corrección de la prueba escrita sobre la unidad 2.
  • Corrección de al menos una consulta sobre las ejercicios asignados.
  1. Listas de acceso restringido:
    TAD Pila y TAD Cola.. Conceptos básicos. Especificación. Pilas secuenciales y enlazadas. Colas secuenciales y enlazadas. Implementación correcta del TAD y análisis de eficiencia. Ejemplos.
  1. Lograr un manejo eficiente de los TAD Pila y Cola.

Tabla de contenidos

UNIDAD 3.- Dispersión

CONTENIDOS OBJETIVOS ACTIVIDADES RECURSOS EVALUACIÓN
  1. Dispersión o transformación clave-dirección:
    TAD: TabHash. Dispersión abierta y cerrada. Especificación. Funciones de dispersión. Manejo de las colisiones. Dispersión extensible. Implementación correcta del TAD y análisis de eficiencia. Aplicaciones.
  1. Lograr un uso eficiente del TAD TabHash.
  • Sesiones de clases.
  • Sesiones prácticas en el Laboratorio Nikolaus Walczuch de la Facultad de Ingeniería.
  • Consultas al profesor.
  • Realización del ejercicio 3 práctico, incluído en la carpeta de trabajos prácticos de la materia.
  • Realización de la tercera prueba escrita sobre la unidad 3.
  • Guía de clase
  • Laboratorio Nikolaus Walczuch de la Facultad de Ingeniería
  • Heileman. Cap. 8. Joyanes y Zahonero. Sec. 18.2.
  • Manuales del lenguaje de programación C y C++.
  • Manuales en línea del depurador de código y del sistema operativo.
  • Corrección de un ejercicio teórico asignado.
  • Corrección del ejercicio práctico 3.
  • Corrección de la prueba escrita sobre la unidad 3.
  • Corrección de al menos una consulta sobre las ejercicios asignados.

Tabla de contenidos

UNIDAD 4.- Montículos

CONTENIDOS OBJETIVOS ACTIVIDADES RECURSOS EVALUACIÓN
  1. Colas de prioridad o montículos binarios:
    TAD: MontBin. Conceptos básicos. Especificación. Implementación correcta del TAD y análisis de eficiencia. Aplicaciones.
  1. Lograr un uso eficiente del TAD MontBin.
  • Sesiones de clases.
  • Resolución de los problemas asignados como ejercicios de cada tema.
  • Sesiones prácticas en el Laboratorio Nikolaus Walczuch de la Facultad de Ingeniería.
  • Consultas al profesor.
  • Realización del ejercicio 4 práctico incluído en la carpeta de trabajos prácticos de la materia.
  • Realización de la cuarta prueba escrita sobre la unidad 4.
  • Transparencias
  • Laboratorio Nikolaus Walczuch de la Facultad de Ingeniería
  • Heileman. Cap. 9. Joyanes y Zahonero. Sec. 4.5.1.
  • Manuales del lenguaje de programación C y C++.
  • Manuales en línea del depurador de código y del sistema operativo.
  • Corrección del ejercicio práctico 4.
  • Corrección de al menos una consulta sobre las ejercicios asignados.
  • Corrección de la prueba escrita sobre la unidad 4.

Tabla de contenidos

UNIDAD 5.- Árboles

CONTENIDOS OBJETIVOS ACTIVIDADES RECURSOS EVALUACIÓN
  1. Árbol binario de búsqueda:
    TAD ArBinBus. Conceptos básicos. Especificación. implementación correcta del TAD y análisis de eficiencia. Aplicaciones.
  1. Lograr un uso eficiente del TAD ArBinBus.
  • Sesiones de clases.
  • Resolución de los problemas asignados como ejercicios de cada tema.
  • Sesiones prácticas en el Laboratorio Nikolaus Walczuch de la Facultad de Ingeniería.
  • Consultas al profesor.
  • Realización del ejercicio 5 práctico incluído en la carpeta de trabajos prácticos de la materia.
  • Realización de la quinta prueba escrita sobre las unidades 5 y 6.
  • Transparencias
  • Laboratorio Nikolaus Walczuch de la Facultad de Ingeniería
  • Heileman. Cap. 7 y 11. Joyanes y Zahonero. Cap. 10-12.
  • Manuales del lenguaje de programación C y C++.
  • Manuales en línea del depurador de código y del sistema operativo.
  • Corrección del ejercicio práctico 5.
  • Corrección de al menos una consulta sobre las ejercicios asignados.
  • Corrección de la prueba escrita sobre las unidades 5 y 6.
  1. Árbol de búsqueda equilibrado:
    Árbol AVL: Rotaciones y despliegue. Aplicaciones. Otros árboles binarios equilibrados. .
  1. Lograr una concepción general sobre los árboles de búsqueda equilibrados y sus usos.
  1. Árboles_B:
    TAD: ArbolB y TAD ArbolB+. Especificación, implementación correcta del TAD y análisis de eficiencia. Aplicaciones.
  1. Desarrollar habilidades en el uso del TAD ArbolB+.

Tabla de contenidos

UNIDAD 6.- Ordenamiento

CONTENIDOS OBJETIVOS ACTIVIDADES RECURSOS EVALUACIÓN
  1. Métodos simples:
    Inserción, selección, burbuja, por montículo.
  1. Lograr una concepción general sobre los métodos sencillos de ordenamiento de colecciones de datos.
  • Sesiones de clases: Ordenamineto.
  • Sesiones prácticas en el Laboratorio Nikolaus Walczuch de la Facultad de Ingeniería.
  • Consultas al profesor.
  • Realización de la quinta prueba escrita sobre las unidades 5 y 6.
  • Transparencias
  • Laboratorio Nikolaus Walczuch de la Facultad de Ingeniería
  • Heileman. Sec. 2.4. Tremblay. Cap. 6. Joyanes y Zahonero. Cap. 15.
  • Manuales del lenguaje de programación C y C++.
  • Manuales en línea del depurador de código y del sistema operativo.
  • Corrección de al menos una consulta sobre las ejercicios asignados.
  • Corrección de la quinta prueba escrita sobre las unidades 5 y 6.
  1. Métodos complejos:
    con árbol binario, mezcla y rápido.
  1. Lograr una concepción general sobre los métodos complejos de ordenamiento de colecciones de datos.

Tabla de contenidos