Introducción: Problemas, programas, estructuras y algoritmos



Descargar 18,95 Kb.
Fecha de conversión23.03.2017
Tamaño18,95 Kb.

Introducción: Problemas, programas, estructuras y algoritmos

  • Problema
  • Programa

Resolución de problemas

  • 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, contradictorios
  • Resultado: modelo abstracto del problema

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.

Realización del programa

  • 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.

Resolución de problemas

  • 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

Herramientas

  • Estructuras de datos + Algoritmos
  • Datos de I/O e intermedios
  • Manipulación de datos
  • Más importante en:
  • Bases de datos Computación numérica
  • Sistemas de información Optimización

Abstracció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

Diseño de la solución

  • A partir del modelo abstracto, determinar:
    • Tipos abstractos de datos
    • Pseudocó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

Verificación y evaluación

  • Verificar:
  • Evaluar:
    • Prestaciones: análisis de eficiencia
    • Se 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

PROGRAMACIÓN

  • Problema real
  • Modelo matemático
  • Algoritmo en lenguaje natural
  • Tipo abstracto de datos
  • Programa en seudolenguaje
  • Estructura de datos
  • Programa ejecutable
  • modelización
  • Estructura 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.

Datos

  • Tipo abstracto:
  • 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

TAD

  • Dominio abstracto de valores
  • +
  • Operaciones sobre el dominio
  • Ej: booleanos
    • Valores: {verdadero,falso}
    • Operaciones: NO, Y, O,XOR, IMPLICA, ...
  • Ej: ventanas de windows
    • Valores: ventanas
    • Operaciones: crear, mover, cambiar tamaño, añadir botones, ...
  • El único significado de los valores es el dado por las operaciones
  • Ocultación de la información: sabemos lo que se hace, no cómo.

Tipos de datos

  • Se debe ajustar al comportamiento del TAD
  • Los 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++, Java
  • definición indica atributos clases incluyen atributos
  • operaciones por separado y operaciones
  • struct
  • PilaEnteros{
  • int datos[];
  • int tope,maximo;
  • }
  • class PilaEnteros{
  • private:
  • int datos;
  • int tope,maximo;
  • public:
  • PilaEnteros(int max);
  • Push(int valor);
  • int Pop();
  • };

Estructuras de datos

  • 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

Tipos de Tipos

  • 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

Tipo genérico o parametrizado

  • Depende de otro tipo pasado como parámetro
  • Ej. de pila en C++ :
    • template
    • class
    • Pila {
    • private: //atributos
    • T datos[];
    • int tope,maximo;
    • public: //operaciones
    • Pila(int max);
    • Push(T valor);
    • T Pop();
    • };

Tipos mutables e inmutables

  • En los tipos mutables los valores pueden cambiar después de haber sido creado
  • Es lo normal. Se puede añadir, quitar, ...
  • En los inmutables no pueden cambiar. Para modificar los datos se crearía una copia.

Tipos

  • 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, ...
  • 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

Puntero

  • 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

tipado

  • C y C++, débilmente tipados
  • Pocas restricciones en la manipulación de los distintos tipos
  • Los 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

Ejemplos de ALGORITMOS

  • Algoritmo de Euclides
  • Dados dos enteros a y b, a>b
  • obtener el m.c.d.
  • Hacer r:=a mod b
  • Si r=0 devolver b
  • En otro caso
    • 3.1. a:=b
    • 3.2. b:=r
    • 3.3. Volver al paso 1
  • Algoritmo de al-Khawarizmi
  • Resolver x2+bx=c
  • Tomar la mitad de b
  • Multiplicarlo por sí mismo
  • Sumarle c
  • Tomar la raíz cuadrada
  • 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 entrada
    • Fó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=1
  • devolver 1
  • en otro caso
  • devolver (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)=1
  • t(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



La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal