Examen diagnóstico

1. ¿Qué es una computadora?

2. ¿Qué es un algoritmo?

3. ¿Qué es un SO?

4. ¿Qué es la abstracción de datos?

5. ¿Qué es un lenguaje de programación?

6. ¿Qué es un objeto?

7. ¿Qué es una clase?

Unidad 1Introducción a las estructuras de datos.

Lic. En C.C. Ann Margareth Meza Rodríguezann.meza@gmail.com

1.1 Tipos de datos abstractos (TDA).

Un tipo de dato es un conjunto de valores y un grupo de operaciones sobre tales valores.

Este conjunto y estas operaciones forman una estructuramatemática que se implementa usando una estructura particular de datos de hardware o software.

El tipo de un dato es el conjunto de valores que puede tomar durante el programa. Si se le intenta dar un valor fuera del conjunto se producirá un error.

La asignación de tipos a los datos tiene dos objetivos principales:

• Detectar errores en las operaciones• Determinar cómo ejecutar estas operaciones

Clasificación en los tipos de datos

Tipos de datos

Dinámicos

Estáticos

Cadena

Estructurados

Simples

Ordinales

No ordinales

AbstracciónPermite dividir la información en componentes aislados que posteriormente se ensamblan para construir el todo

Aplicaciones de la abstracción

Diferentes niveles• Nos centramos en los elementos mas grandes e

importantes

Progresivamente• Tratamos volúmenes de información menores

que revelen más detalles

Diferentes tipos• Funcional o procedural de los datos

Encapsulación

“Proceso de almacenar en un mismo compartimento los elementos de una abstracción que constituyen suestructura y su comportamiento”.[Booch, 1996]

Tipos de datos

Un tipo de dato es un conjunto de valores y un conjunto de operaciones definidas por sus valores.

Tipo de dato = Representación + Operaciones

Ejemplo:

Tipo de dato OperacionesEntero +,-,*,/Cadena concatenar,

subcadena, longitud

Tipos abstractos de datos (TDA)

• Permiten ampliar los tipos de datos definidos por los lenguajes de programación

• El programador define este nuevo tipo de dato, al igual que los tipos de datos consta de datos y operaciones que se pueden realizar sobre dichos datos.

• Poseen interfaces graficas públicas (operaciones que se pueden realizar en cualquier momento de la ejecución del programa), pero su implementación es privada (sólo se ejecuta para la instancia actual )

Un TAD consta de:

Tipo Tipo que se está especificando*

Operaciones Signatura (tipo de argumentos y resultado)

Axiomas definición implícita del valor de la función

Invariantes condición booleana que debe mantenerse con exactitud

Precondiciones

Postcondiciones

*Conjunto de objetos

Tipo Pila[X]

Operaciones Poner:Pila[X]xXPila[X]Vacia:Pila[X]BooleanItem:Pila[X]XNew:Pila[X]

Axiomas Para x: T, s: Pila[T];item(poner(s,x)) = xvacia(new)not vacia(poner(s,x))

InvariantesPrecondiciones item (s:Pila[T]) requiere not vacia(s)Postcondiciones

Ejemplo

TDA IntegerDatos: Una secuencia de dígitos que opcionalmente presentan como prefijo un signo más o un signo menos. Nos referimos a este número entero con signo como N. Operaciones:

Constructor: Crea un nuevo enteroAdd(k): Crea un nuevo entero a partir de la suma de N y k

POSTCONDICION: SUM=N+KSub(k): Crea un nuevo entero a partir de la diferencia de N y k

POSTCONDICION: SUM=N-KSet(k): Asigna a N el valor de k.

POSTCONDICION: N=Kend

¡No confundir ésto con los enunciados de asignación tal como se usan en los lenguajes de programación! Es más bien una ecuación matemática que da "verdadero" por cada valor sum, N y k después que add ha sido ejecutada.

TDA Integer.

(a) ¿Por qué no hay precondiciones para las operaciones add y sub? (b) Obviamente, la descripción TDA de Integer está incompleta. Agrega los métodos mul, div y otros cualesquiera. Describe sus impactos especificando pre- y postcondiciones.

Ejercicio

Tarea

1 Diseña un TDA Fraction que describa propiedades de las fracciones.

(a) ¿Qué estructuras de datos se pueden usar? ¿Cuáles son sus elementos? (b) ¿Cuál serían sus operaciones? (c) Menciona unos cuantos axiomas y precondiciones.

2. Describe con tus propias palabras las propiedades de tipos de datos abstractos. 3. ¿Por qué es necesario incluir axiomas y precondiciones a la definición de un tipo de datos abstracto?

1.1 Modularidad

“Propiedad que tiene un sistema que ha sido descompuesto en un conjunto de módulos cohesivos y débilmente acoplados”. [Booch, 1996]

Alta cohesión: Un modulo con responsabilidades altamente relacionadas y que no hace una gran cantidad de trabajo.

Bajo acoplamiento: Un módulo que no depende de otros módulos

Comprensión modular: Es posible entender un modulo sin conocer los otros.

Continuidad modular: Un cambio en la especificación, afecta solo a un modulo o a unos pocos.

Protección modular: El efecto de una situación anormal producida en un modulo afecta solo a éste y a unos pocos

Los módulos se comunican mediante interfaces bien definidas

Programa modular: Se dice que un programa es modular cuando está formado por un conjunto de módulos.

MóduloUnidad básica de descomposición de un sistema de software. Los módulos deben ser los mas independientes posibles.

Método de software modularEs modular si ayuda a producir sistemas de software a partir de elementos autónomos interconectados por una estructura simple y coherente

Programación modularTrata de descomponer un programa en un pequeño número de abstracciones coherentes que pertenecen al dominio del problema cuya complejidad interna esta oculta por la interfaz

• Un modulo se estructura mediante una interfaz y una implementación

• Está compuesto por un conjunto de operaciones y atributos

Primitivas de acceso

Atributos Operaciones

Interfaz

Sección privada

Reglas para obtener módulos • Unidades modulares: El lenguaje debe proporcionar estructuras modulares con las cuales se puedan describir las diferentes unidades (POO-Clases)• Ocultación de información

• Todos los módulos deben seguir el principio de ocultación de información• En una abstracción de datos pueden verse dos caras

InterfazOperaciones que definen el comportamiento (cliente)

Implementación(programador)

Ejemplo Modulo que define las cuentas bancarias en un banco

Interfazdepositar()verSaldo()retirar()

RepresentaciónNombreCliente:StringCodigo:StringSaldo:Float

OperacionescalcularIntereses()deposito()verSaldo()

Un modulo incluye una estructura de datosjunto con un conjunto de operaciones para manipularla

Mecanismos para diseñar programas modulares• Procedimientos o funciones

• Módulos

• Tipos abstractos de datos (TADS)

• Objetos

Ejercicio Formar equipos de 4-5 personas y definir 3 módulos para los siguientes casos

• Registro de ventas de una tienda• Control de vacunas de una mascota• Monitoreo de entradas y salidas de un estacionamiento

Tarea. Definir 2 módulos para los siguientes casos:• Salón de belleza• Inventario de una zapatería• Menú en una cafetería