Introducción: Problemas, programas, estructuras y
algoritmos
Problema Programa
Estructura de datosAlgoritmo
• Proceso clásico de desarrollo de programas.– Especificación de requisitos del problema.– Análisis del problema.– Diseño de la solución.– Implementación del diseño.– Pruebas.
• Análisis de requisitos:– Personalmente: dificultad de comunicación– Documento de requisitos: ambiguos, incompletos,
contradictoriosResultado: modelo abstracto del problema
Resolución de problemas
Ejemplos• Problema de las cifras.
Dado un conjunto de 6 enteros, encontrar la forma de conseguir otro entero, utilizando las operaciones de suma, resta, producto y división entera.
• Ejemplo 2. Detección de caras humanas.Dada una imagen (bmp, jpg, gif) encontrar el número de caras humanas existentes y la posición de cada una de ellas.
• Refinamiento por pasos sucesivos.– Escribir la estructura de la solución en
pseudocódigo, de manera muy genérica.– Especificar los pasos de forma cada vez
más detallada, y precisa.– Repetimos el refinamiento hasta llegar a
una implementación.
Realización del programa
Resolver problemas ≠ programar
• Resolver problemas: abstracción, herramientas conceptuales
• Programas: técnicas (lenguaje, entorno)
• Evaluación de la solución: herramientas conceptuales y técnicas
Resolución de problemas
Estructuras de datos + Algoritmos
Herramientas
Datos de I/O e intermedios Manipulación de datos
Más importante en:
Bases de datos Computación numéricaSistemas de información Optimización
En el modelado se obtienen algoritmos abstractos¿cómo?– Analogías– Técnicas de diseño– Simplificación– Generalización– ...
• Ejemplo cifras: algoritmo de backtracking• Ejemplo caras: utilización de patrones
Abstracción
• A partir del modelo abstracto, determinar:Tipos abstractos de datosPseudocódigo
• Implementación: implantación correcta a partir de la especificación anterior– TAD → estructura de datos (listas, arrays, ...)– Pseudocódigo → programa (bucle, secuencia, ...)Relacionadas:
Mejor estructura de datos puede requerir modificación del algoritmo
Un algoritmo más eficiente puede requerir una estructura de datos distinta
Diseño de la solución
• Verificar:– Que se cumplen los requisitos– Que se resuelve el problema
• Evaluar:– Prestaciones: análisis de eficienciaSe puede hacer antes de programar, con estudio teórico,
o después, con estudio experimental
Proceso cíclico: si hay algo mal o mejorable reiniciar por el punto adecuado
Verificación y evaluación
PROGRAMACIÓN
Problema real
Modelo matemático
Algoritmo en lenguaje natural
Tipo abstracto de datos
Programa en seudolenguaje
Estructura de datos
Programa ejecutable
modelizaciónEstructura de datos
algorítmica
programación
Validación y evaluación
Heurísticas para una buena programación
• Reutilizar programas existentes: Un nuevo programa no debe partir de cero. Reutilizar librerías, implementaciones de TADs, esquemas de programas, ...
• No resolver casos concretos, sino el problema en general: Si no se requiere un esfuerzo adicional, el algoritmo debe resolver un caso genérico.
• Repartir bien la funcionalidad: Repartir la complejidad del problema de forma uniforme. No crear procedimientos muy largos: usar subrutinas. Además se mejora la legibilidad del código.
• Tipo abstracto:– Dominio de valores: estructura abstracta– Conjunto de operaciones: algoritmos abstractos
• Implementación:• Lenguajes estructurados: módulos• POO: clases
– Estructura de atributos o variables– Procedimientos de manipulación
Datos
• TAD:– Concepto de diseño
• Tipo de datos:– Concepto de programación– Materialización de TAD
• Estructura de datos:– Organización de la información almacenada para un
tipo de datos
Datos
Dominio abstracto de valores+
Operaciones sobre el dominio
Ej: booleanosValores: {verdadero,falso}Operaciones: NO, Y, O,XOR, IMPLICA, ...
Ej: ventanas de windowsValores: ventanasOperaciones: crear, mover, cambiar tamaño, añadir botones, ...
El único significado de los valores es el dado por las operacionesOcultación de la información: sabemos lo que se hace, no cómo.
TAD
Se debe ajustar al comportamiento del TADLos lenguajes proporcionan:• Tipos de datos elementales, que se corresponden con
TAD:– TAD Z (enteros), es integer en Pascal o int , long
int , short int en C• Mecanismos de definición de tipos:C, Pascal C++, Javadefinición indica atributos clases incluyen atributosoperaciones por separado y operaciones
Tipos de datos
structPilaEnteros{
int datos[];int tope,maximo;
}
class PilaEnteros{private:
int datos;int tope,maximo;
public:PilaEnteros(int max);Push(int valor);int Pop();
};
Disposición en memoria de los datos para almacenar los valores del tipo:Un tipo (pilas) se pueden implementar con distintas
estructuras (arrays o listas)Una estructura (lista) se puede usar para implementar
distintos tipos (pilas, colas, ...)
La estructura de datos elegida influye en el gasto de memoria y el tiempo de ejecución
Estructuras de datos
• Primitivos o elementales• Definidos por el usuario
• Simples: un único valor– Normalmente proporcionados por el lenguaje– Definidos por el usuario, enumerado
• Compuesto: varios valores simples o compuestos– Los lenguajes proporcionan mecanismos de
composición: arrays, registros, clases, ...• Tipo contenedor o colección: compuesto que
puede almacenar un número indefinido de valores de otro tipo
Tipos de Tipos
Depende de otro tipo pasado como parámetro
Ej. de pila en C++ :template <class T>class
Pila {private: //atributos
T datos[];int tope,maximo;
public: //operacionesPila(int max);Push(T valor);T Pop();
};
Tipo genérico o parametrizado
• En los tipos mutables los valores pueden cambiar después de haber sido creadoEs lo normal. Se puede añadir, quitar, ...
• En los inmutables no pueden cambiar. Para modificar los datos se crearía una copia.
Tipos mutables e inmutables
• Datos simples:– Enteros: con signo, sin signo, cortos, largos, ...– Reales: simple o doble precisión– Caracteres– Cadenas: simple o compuesto, dependiendo del
lenguaje– Booleanos. No existen en C, sí en Pascal o C++
• Contenedores: listas, pilas, colas, árboles, ...– No forman parte del lenguaje– Normalmente disponibles en librerías
• Registro: contiene varios campos que pueden corresponder a datos de distintos tipos– Puede tener un campo especial (uniones) en función
del cual hay unos campos u otros
Tipos
• Es parametrizado: Puntero[T]• Operaciones:
– Indirección: si a es Puntero[T], a ↑ es el dato apuntado por a
– Obtener dirección: si t es de tipo T, PunteroA(t:T) devuelve un puntero de tipo Puntero[T]
– Puntero nulo (NULO). No tiene referencia válida o no ha sido inicializado
– Creación de una nueva variable: Nuevo(T:Tipo)– Eliminación de una variable: Borrar(a:Puntero[T])
– Comparación
Puntero
• C y C++, débilmente tipadosPocas restricciones en la manipulación de los
distintos tiposLos punteros se tratan como enteros, se pueden
sumar, ...Caracteres como enteros,En C no existen los booleanos, las comparaciones
con enteros
Propicia errores de programación
• Pascal, Modula, fuertemente tipados
tipado
Ejemplos de ALGORITMOS
Algoritmo de Euclides
Dados dos enteros a y b, a>b
obtener el m.c.d.
1. Hacer r:=a mod b2. Si r=0 devolver b3. En otro caso
3.1. a:=b3.2. b:=r3.3. Volver al paso 1
Algoritmo de al-Khawarizmi
Resolver x2+bx=c
1. Tomar la mitad de b2. Multiplicarlo por sí mismo3. Sumarle c4. Tomar la raíz cuadrada5. Restarle la mitad de b
Algoritmo• Conjunto de reglas para resolver un problema. Debe ser:
› Definible. En seudocódigo, pero pueda dar lugar a un programa.› De un conjunto de datos de entrada producir unos datos de salida, en un número finito de pasos (tiempo de ejecución finito). Además debemos diseñar algoritmos eficientes: que el tiempo para acabar sea “razonable”.› Determinista si para la misma entrada produce siempre la misma salida. No determinista en caso contrario (redondeos, probabilistas, paralelos, …)
Algorítmica
• Estudia técnicas para:– construir algoritmos eficientes (diseño de algoritmos)–y medir la eficiencia de los algoritmos (análisis de algoritmos)
• Objetivo: Dado un problema concreto encontrar la “mejor” forma de resolverlo.
Análisis de algoritmos• Estudio de los recursos que necesita la ejecución de un algoritmo.diseñar algoritmos eficientes: que usan pocos recursos:
› memoria› tiempo› otros (memoria secundaria, tiempo de programación, …)
• Pero también importante que los resultados sean correctos. Dependiendo del campo de trabajo puede ser más importante la corrección o la eficiencia.• No confundir con análisis de un problema.• Hay otros criterios importantes: facilidad de mantenimiento, portabilidad, reutilización, ...
Análisis de algoritmos
• Para decidir:
› qué algoritmo programar› qué algoritmo utilizar en resolver un problema para una cierta entrada› detectar fallo en programa que no funciona bien
Factores que influyen en la medición de recursos
• Factores externos al algoritmo:Ordenador, otras tareas usando el procesador, sistema operativo, lenguaje de programación, compilador, opciones de compilación, implementación del algoritmo, ...
• Tamaño del problema: volumen de los datos de entradaFórmula del tiempo u ocupación de memoria en función de ese tamaño.
• Contenido de los datos. Para un mismo tamaño de entrada puede influir la distribución de los datos
– caso más favorable, tm(n) y mm(n)
– más desfavorable, tM(n) y mM(n)
– y promedio, tp(n) y mp(n)
Análisis de algoritmos• Se intenta obtener:
– el tiempo de ejecución para un cierto tamaño de entrada, t:N→R+, t(n)
Contando el número de instrucciones que se ejecutan o algún tipo de instrucción
– la ocupación de memoria para un cierto tamaño de entrada, m:N→R+, m(n)
Que es la memoria necesaria para que pueda ejecutarse• Como influyen factores externos al algoritmo lo que normalmente se estudia la forma en que crece t(n) y m(n), y se utilizan notaciones asintóticas: , O, , o
Con las que se acota la función o se obtiene la forma en que crece
Ej: Cálculo del factorial fact(n):
si n=1devolver 1
en otro casodevolver (fact(n-1)*n)
• tiempo:t(n)=t(n-1)+a=t(n-2)+2*a= ... =t(1)+(n-1)*a
• memoria:m(n)=m(n-1)+c=m(n-2)+2*c= ... =m(1)+(n-1)*c
Ej: Torres de Hanoi
Hanoi(origen,destino,pivote,discos):si discos=1
moveruno(origen,destino)en otro caso
Hanoi(origen,pivote,destino,discos-1)moveruno(origen,destino)Hanoi(pivote,destino,origen,discos-1)
Ej: Torres de Hanoi
Número de movimientos:
t(1)=1t(n)=2t(n-1)+1, si n>1
Expandiendo la recurrencia:
t(n) = 2 t(n-1) +1 = 2 (2t(n-2)+1) +1 = 22 t(n-2) +1+2 = 22 (2t(n-3)+1) +1+2 = 23 t(n-3)+1+2+22
….
2n-1 t(1)+1+2+…+ 2n-2 = 2n-1
Diseño de algoritmos
Técnicas generales aplicables a muchas situaciones, directamente o haciendo modificaciones:
• Divide y vencerás
• Avance rápido
• Programación dinámica
• Backtracking
• Ramificación y poda
Esquemas algorítmicos
Pseudolenguaje
• funciones y procedimientos: operación• variables: var• asignación: :=• comparación: =, ≠• condicional: si ... entonces ... sino• devolver• iteradores: para , mientras , repetir• error, escribir, ...• Comentarios: // ó (*...*)
Heurísticas para una buena programación
• Planificar el diseño de un programa: Mediante refinamientos sucesivos, análisis/diseño, especificaciones formales, ...
• Encapsular: Extraer y agrupar funciones relacionadas. Todas las operaciones sobre un mismo TAD deben estar en el mismo módulo (módulos, clases, unidades, paquetes). Módulo como mecanismo de encapsulación.
• Ocultamiento de la implementación: Los aspectos de implementación no son visibles fuera del módulo. El que usa el módulo sólo debe saber qué hace, no cómo lo hace, y accede a los datos a través del interface.
Heurísticas para una buena programación
• Reutilizar programas existentes: Un nuevo programa no debe partir desde cero. Reutilizar librerías, implementaciones de TADs, esquemas de programas, ...
• No resolver casos concretos, sino el problema en general: Si no se requiere un esfuerzo adicional, el algoritmo debe resolver un caso genérico.
• Repartir bien la funcionalidad: Repartir la complejidad del problema de forma uniforme. No crear procedimientos muy largos: usar subrutinas. Además se mejora la legibilidad del código.
Tablas de dedicación temporal
Tablas de medidas de calidad del software