Fundamentos de Programación Otoño 2008 Mtro. Luis …

1 Algoritmos y soluci n de problemas Fundamentos de Programaci n Oto o 2008. Mtro. Luis Eduardo P rez Bernal Departamento de Electr nica, Sistemas e Inform tica Introducci n En las ciencias de la computaci n se ocupa de los problemas computables. Se le llama problema computable a aquella abstracci n de la realidad que tiene representaci n algor tmica. Los algoritmos permiten encontrar la soluci n a problemas computables. Intuitivamente las personas efectuamos cotidianamente una serie de pasos, procedimientos o acciones que nos permitan alcanzar alg n resultado o resolver un problema (al ba arnos, al desayunar, al ir a la universidad). En realidad todo el tiempo estamos aplicando algoritmos para resolver problemas. Departamento de Electr nica, Sistemas e Inform tica Algoritmo Es un m todo para la resoluci n de problemas. Es un conjunto de pasos a seguir para la soluci n a un problema. Es una serie finita de instrucciones para realizar una tarea.

2 Formalmente: Es un conjunto de pasos, procedimientos o acciones que nos permiten alcanzar un resultado o resolver un problema. Departamento de Electr nica, Sistemas e Inform tica Caracter sticas de los algoritmos Las caracter sticas que debe cumplir un algoritmo son: Un algoritmo debe ser Preciso e indicar el rden de realizaci n de cada paso. Un algoritmo debe ser Definido, es decir, si se sigue un algoritmo dos veces, se debe obtener el mismo resultado. Un algoritmo debe ser Finito, es decir, si se sigue el algoritmo se debe terminar el alg n momento. Departamento de Electr nica, Sistemas e Inform tica Otras caracter sticas de los algoritmos Debe cumplir con: Una secuencia de instrucciones claras y finitas Debe ser correcto y debe resolver el problema planteado en todas sus facetas Debe ser legible Departamento de Electr nica, Sistemas e Inform tica Resolver problemas Qu tipo de problemas se pueden resolver?

3 Computables Qu m todos hay para resolver problemas computables? Metodolog a de la programaci n (centrado en los algoritmos). Departamento de Electr nica, Sistemas e Inform tica Fases para resolver un problema computable Dise o de programas An lisis del problema An lisis Dise o del algoritmo Dise o (descendente, Verificaci n manual del refinamiento paso a paso). algoritmo En la computadora Codificaci n del algoritmo Ejecuci n del programa Codificaci n Verificaci n del programa Ejecuci n Mantenimiento Prueba (documentaci n) Mantenimiento Departamento de Electr nica, Sistemas e Inform tica Fases para la soluci n de un problema computable Soluci n de un problema computable Dise o y Codificaci n Ejecuci n An lisis verificaci n Prueba del del del del del Algoritmo Programa problema algoritmo Programa Lenguaje C. Herramientas de Identificar los Identificar los programaci n: Definir y datos de salida Refinamiento -Diagramas de datos de Dise o entender = por flujo Entrada Descendente El problema resultado Pasos - Pseudoc digo Departamento de Electr nica, Sistemas e Inform tica An lisis del problema Es el primer paso a seguir para encontrar la soluci n a un problema computable es el an lisis del problema.

4 En el an lisis del problema se requiere del m ximo de creatividad e imaginaci n. Debido a que se busca una soluci n se debe examinar cuidadosamente el problema a fin de identificar que tipo de informaci n es necesaria producir. En seguida se deben identificar aquellos elementos de informaci n ofrecidos por el problema y que resulten tiles para obtener la soluci n al problema. Finalmente, un procedimiento para producir los resultados deseados a partir de los datos, es decir, el algoritmo. Departamento de Electr nica, Sistemas e Inform tica An lisis del problema An lisis del problema Identificar los datos Definir y entender Identificar los datos de salida El problema de entrada = resultados Departamento de Electr nica, Sistemas e Inform tica Elementos que conforman un algoritmo Entrada. Los datos iniciales que posee el algoritmo antes de ejecutarse. Proceso. Acciones que lleva a cabo el algoritmo.

5 Salida. Datos que obtiene finalmente el algoritmo. Departamento de Electr nica, Sistemas e Inform tica Ejemplo: calcular el rea de un rect ngulo An lisis del problema El c lculo del rea del rect ngulo se puede dividir en: Entrada de datos (altura, base). Proceso: C lculo del rea (= base x altura). Salida de datos (base, altura, rea). Departamento de Electr nica, Sistemas e Inform tica Dise o del algoritmo La soluci n de un problema complejo puede requerir muchos pasos, es necesario dividir el problema en subproblemas m s sencillos de resolver. Este m todo se denomina divide y vencer s y es aplicable a la resoluci n y escritura de algoritmos y programas para computadora. Este m todo de divisi n de un problema en otros subproblemas m s sencillos se puede expresar para conseguir su soluci n en una computadora, mediante el m todo denominado dise o descendente. El proceso de la rotura de un problema principal en etapas o subproblemas m s sencillos se denomina refinamiento paso a paso o sucesivos.

6 Departamento de Electr nica, Sistemas e Inform tica Dise o descendente y refinamiento paso a paso Problema del c lculo Del rea del rect ngulo Entrada de C lculo del Salida de Datos rea resultados Entrada Entrada AREA = Salida Salida Salida ALTURA BASE BASE x ALTURA ALTURA BASE AREA. Departamento de Electr nica, Sistemas e Inform tica Herramientas de programaci n Las herramientas de programaci n utilizadas como lenguajes algor tmicos son: Pseudoc digo: es un lenguaje algor tmico, muy parecido al espa ol pero m s conciso que permite la redacci n r pida del algoritmo. Diagramas de flujo: ha sido la herramienta de programaci n por excelencia, y a n hoy sigue siendo muy utilizada. Es f cil de dise ar pues el flujo l gico del algoritmo se muestra en un diagrama en lugar de palabras. Departamento de Electr nica, Sistemas e Inform tica Pseudoc digo Es un lenguaje de pseudoprogramaci n, es decir, muy parecido a un lenguaje de programaci n.

7 El pseudoc digo es muy f cil de utilizar, ya que es muy similar al espa ol. Algunas palabras utilizadas en el pseudoc digo: Inicio Fin Leer Escribir Asignar (x y+z). Departamento de Electr nica, Sistemas e Inform tica Ejemplo de pseudoc digo Programa CalculoAreaRectangulo Inicio leer; base, altura area base x altura escribir; base, altura, area Fin Departamento de Electr nica, Sistemas e Inform tica Diagramas de flujo Un diagrama de flujo utiliza s mbolos est ndar en el que cada paso del algoritmo se visualiza dentro del s mbolo y en el orden en que estos pasos se ejecutan, se indica conect ndolos con flechas llamadas l neas de flujo, ya que indican el flujo l gico del algoritmo. Los s mbolos utilizados en los diagramas de flujo han sido estandarizados por la ANSI (American National Institute) y por la ISO (International Standard Organization). Departamento de Electr nica, Sistemas e Inform tica S mbolos de diagramas de flujo Departamento de Electr nica, Sistemas e Inform tica Ejemplo: Diagrama de flujo INICIO.

8 Leer: base, altura Area base x altura Imprimir: base, altura, rea FIN. Departamento de Electr nica, Sistemas e Inform tica Fases para la soluci n de un problema computable Soluci n de un problema computable Dise o y Codificaci n Ejecuci n An lisis verificaci n Prueba del del del del del Algoritmo Programa problema algoritmo Programa Lenguaje C. Herramientas de Identificar los Identificar los programaci n: Definir y datos de salida Refinamiento -Diagramas de datos de Dise o entender = por flujo Entrada Descendente El problema resultado Pasos - Pseudoc digo