Estructuras de Datos y
Algoritmos
Introducción
Texto
•
Requerido: Carrano & Prichard: Data
Abstraction and Problem Solving with
Java; Walls and Mirrors, Ed. Addison
Wesley, © 2001, ISBN 0-201-70220-7
(precio de lista $106.00)
•
Recomendado: Flanagan: Java in a
Nutshell : A Desktop Quick Reference,
Fifth Edition, Ed. O'Reilly, © 1999,
ISBN: 0596007736 (precio de lista
$44.95)
Evaluación
Sugerida
 Laboratorios 30%
 Pruebas cortas y otros trabajos: 10%
(todos)
 Exámenes parciales: tres a 15% cada uno
 Examen final: 15%
 Puntuaciones de bono hasta 5% por
actividades opcionales.
Descripción General
El curso contiene un estudio de diversas estructuras y algoritmos para la
representación y procesamiento de datos.
• Estructuras: colas, matrices, árboles y grafos.
• Algoritmos: manejo de la memoria de una computadora, ordenación,
compresión y búsqueda de datos.
• Análisis elementales de algoritmos: peor caso y caso promedio.
• Aplicaciones.
Los estudiantes tendrán la experiencia de realizar un proyecto de
complejidad moderada (aproximadamente 2000 instrucciones) y de
hacerlo como parte de un equipo de programadores.
REPASO
Ingeniería de Software
Ciclo de vida del sofware
•
•
•
•
•
•
•
•
•
Especificación
Diseño
Análisis de riesgo
Verificación
Codificación
Prueba
Refinamiento
Producción
Mantenimiento
Diseño
• Divida su diseño en módulos
• Especifique el propósito de cada módulo,
sus suposiciones, insumo y producto
• Las especificaciones no deben decir cómo
funciona el módulo si no qué hace
• Uso de precondiciones y poscondiciones
Verificación
• Note que este paso va antes que la
codificación
• Utiliza métodos teóricos
• Basado en invariantes, más frecuentemente
utilizadas en funciones y ciclos.
Abstracción y Escondido de
Información
• Abstracción procesal:
diga qué se hace, no
cómo se hace
• Abstracción de dato:
diga qué se hace con
los datos, no cómo se
hace
Tipo de Dato Abstracto
• Es dos cosas:
– Un conjunto de datos
– Las operaciones que se le hacen
ESTA ES LA DEFINICIÓN MÁS
IMPORTANTE DEL CURSO
Ejemplo de TDA
• Una cola de enteros es
– una colección de enteros
– con las operaciones
• boolean vacía(): devuelve T o F dependiendo si está
vacía
• void añade(x): añade el entero x a la cola
• int saca(): elimina el entero más antíguo de la cola y
regresa con él.
Estructura de Datos
• Especificación de cómo se organizan los
datos
• NO es lo mismo que un Tipo de Dato
Abstracto
• Ejemplo:
– TDA: lista ordenada
– ED: arreglo
Programación Orientada a
Objetos
• Principios
– abstracción*
– encapsulación*
– herencia*
– polimorfismo
(* ya lo vimos)
Abstracción
Mecanismos para su implantación: Interfaz, clases abstractas.
Encapsulación: Clases
• Mecanismo para definir objetos
• objetos pertenecen a clases
• puede haber varias instancias de objetos de
una misma clase
• encapsula las definiciones
Polimorfismo
• Un mismo método puede comportarse de
maneras distintas.
• Debe poder cambiar su comportamiento
dependiendo de:
– a qué objeto de le aplica
– qué parámetros usa
Diseño Orientado a
Objetos
• Al diseñar la solución a un problema
– Se identifica los objetos en el problema.
– Se identifica las operaciones que se le hace a
los objetos
Diseño top-down
• Refinamiento de algoritmo
• cada nivel de definición añade detalle a
cada instrucción del nivel superior
• Lleva naturalmente a un producto modular.
¿Cuando usar DOO o TD?
• DOO: cuando el énfasis del problema es en
la manipulación de datos
• TD: cuando el énfasis del problema es en el
algoritmo.
Herencia
• Implantado con el mecanismo de sub clases
• cuando una clase es subclase de otra hereda
su comportamiento: datos y métodos,
propios y heredados
• una subclase puede redefinir métodos de
alguna superclase
Descargar

mate.uprh.edu