Algoritmos

Universidad Nacional de Salta - Facultad de Ciencias Exactas Henry Suárez Año 2008

TP Nº5 Investigar • • •

Al menos dos definiciones de algoritmo (citar fuente) y enunciar sus características principales. Características de las diferentes herramientas para especificar algoritmos, en particular: lenguaje natural, diagramas N-S (diagramas de bloques), diagramas de flujo y pseudocódigo. Breve reseña histórica relativa a la programación estructurada.

Algoritmo: Concepto de algoritmo La historia de la informática señala a Abu Abdullah Muhammad bin Musa alKhwarizmi, una de las grandes figuras de la matemática árabe medieval como descubridor del concepto de algoritmo. En su obra "aljabar wa-al-muqabala" sienta las bases del algebra, cuyo nombre procede del comienzo del título, así como "algoritmo" procede del nombre del autor, al-Khwarizmi. • Definición I: Podemos definir algoritmo como un conjunto de pasos o instrucciones finito que se deben seguir para realizar una determinada tarea. Para que dicho conjunto de instrucciones sea considerado un algoritmo, ha de cumplir algunas características: - Un mismo conjunto de datos de partida se debe llegar siempre a un mismo conjunto de resultados. - Las instrucciones han de ser precisas, sin ambigüedad alguna. - El conjunto ha de ser finito. Pedagógicamente se suele dar como ejemplo de algoritmo una receta de cocina. La analogía es clara, siempre que no olvidemos que estamos ante un concepto matemático. Fuente: http://www.error500.net/garbagecollector/archives/categorias/apuntes/concepto_de_al goritmo.php • Definición II: Un algoritmo es un conjunto de operaciones ordenadas de modo tal en que puedan resolver un problema. La ciencia que estudia los algoritmos se llama Algoritmia, siendo la famosa Máquina de Turing la que ha formalizado sus conceptos en un modelo computacional. Los algoritmos tienen algo en común con las funciones matemáticas: reciben una entrada y producen una salida, pero para que pueda ser considerado como algoritmo debe ser eficiente (encontrar una solución en el menor tiempo posible), finito (posee un número determinado de pasos) y definido (se llega al mismo resultado si se sigue el mismo proceso más de una vez). Un ejemplo de algoritmo sería un manual de usuario de un electrodoméstico, también podemos encontrar algoritmos como el método para resolver un Sistema lineal de ecuaciones creado por Gauss. Actualmente pensar en algoritmos nos remite a los programas de computación, pero también pueden en redes neuronales, circuitos eléctricos o aparatos mecánicos.

1

Universidad Nacional de Salta - Facultad de Ciencias Exactas Henry Suárez Año 2008

Fuente: http://www.mastermagazine.info/termino/3806.php

Características de un algoritmo Un algoritmo debe tener al menos las siguientes características: • Ser preciso: esto significa que las operaciones o pasos del algoritmo deben desarrollarse en un orden estricto, ya que el desarrollo de cada paso debe obedecer a un orden lógico. • Ser definido. Ya que en el área de programación, el algoritmo se desarrolla como paso fundamental para desarrollar un programa, es necesario tener en cuenta que el computador solo desarrollará las tareas programadas y con los datos suministrados; es decir, no puede improvisar y tampoco se inventará o adivinará el dato que necesite para realizar un proceso. Por eso, el algoritmo debe estar plenamente definido; esto es, que cuantas veces se ejecute, el resultado depende estrictamente de los datos suministrados. Si se ejecuta con un mismo conjunto de datos de entrada, el resultado será siempre el mismo. • Ser finito: esta característica implica que el número de pasos de un algoritmo, por grande y complicado que sea el problema que soluciona, debe ser limitado. Todo algoritmo, sin importar el número de pasos que incluya, debe llegar a un final. Para hacer evidente esta característica, en la representación de un algoritmo siempre se incluyen los pasos inicio y fin. • Presentación formal: para que el algoritmo sea entendido por cualquier persona interesada es necesario que se exprese en alguna de las formas comúnmente aceptadas; pues, si se describe de cualquier forma puede no ser muy útil ya que solo lo entenderá quien lo diseñó. Las formas de presentación de algoritmos son: el pseudocódigo, diagrama de flujo y diagramas de Nassi/Schneiderman, entre otras. • Corrección: el algoritmo debe ser correcto, es decir debe satisfacer la necesidad o solucionar el problema para el cual fue diseñado. Para garantizar que el algoritmo logre el objetivo, es necesario ponerlo a prueba; a esto se le llama verificación o prueba de escritorio. • Eficiencia: hablar de eficiencia o complejidad de un algoritmo es evaluar los recursos de cómputo que requiere para almacenar datos y para ejecutar operaciones frente al beneficio que ofrece. En cuanto menos recursos requiere será más eficiente el algoritmo. Fuente: http://www.monografias.com/trabajos19/algoritmos/algoritmos.shtml Herramientas para especificar algoritmos Lenguaje natural En la filosofía del lenguaje, el lenguaje natural es el lenguaje hablado y/o escrito y/o signado por humanos para propósitos generales de comunicación, para distinguirlo de otros como puedan ser una lengua construida, los lenguajes de programación o los lenguajes usados en el estudio de la lógica formal, especialmente la lógica matemática.

2

Universidad Nacional de Salta - Facultad de Ciencias Exactas Henry Suárez Año 2008

El término lenguaje natural se refiere al estudio de las propiedades computacionales y de otro tipo implicadas en la comprensión, producción y uso de las lenguas naturales. Diagramas de Nassi – Shneiderman (N-S) El diagrama N-S o también conocido como diagrama de Chapin es una técnica de especificación de algoritmos que combina la descripción textual, propia del pseudocódigo, con la representación gráfica del diagrama de flujo. El diagrama N-S cuenta con un conjunto limitado de símbolos para representar los pasos del algoritmo, por ello se apoya en expresiones del lenguaje natural; sin embargo, dado que el lenguaje natural es muy extenso y se presta para la ambigüedad, solo se utiliza un conjunto de palabras, a las que se denomina palabras reservadas. Las palabras reservadas más utilizadas son: • Inicio Fin Leer Escribir • Mientras Repita Hasta Para • Incrementar Decrementar Hacer Función • Entero Real Caracter Cadena • Lógico Retornar Los símbolos utilizados en el diagrama de Chapin son corresponden a cada tipo de estructura. Dado que se tienen tres tipos de estructuras, se utilizan tres símbolos. Esto hace que los procesos del algoritmo sean más fáciles de representar y de interpretar. Fuente: http://www.monografias.com/trabajos19/algoritmos/algoritmos.shtml Diagramas de flujo Es un esquema para representar gráficamente un algoritmo. Se basan en la utilización de diversos símbolos para representar operaciones específicas. Se les llama diagramas de flujo porque los símbolos utilizados se conectan por medio de flechas para indicar la secuencia de operación. En los diagramas de flujo se presuponen los siguientes aspectos: • Existe siempre un camino que permite llegar a una solución (finalización del algoritmo). • Existe un único inicio del proceso. • Existe un único punto de fin para el proceso de flujo (salvo del rombo que indica una comparación con dos caminos posibles). Fuente: http://es.wikipedia.org/wiki/Diagrama_de_Flujo Pseudocódigo Considerado como un lenguaje falso, el pseudocódigo es un lenguaje intermedio entre nuestro lenguaje y el de programación, debido a que quien lo utiliza se guía por una serie de normas pero sin llegar a usar una estructura tan rígida como la del lenguaje de programación. El objetivo al que apunta es que quien lo pone en práctica se centre más en la solución del algoritmo o el diseño de un software que en el programa que utiliza para crearlo. Y esto es posible porque es más fácil de manipular ya que no tiene que tener en mente el lenguaje en sí y además, más fácil de codificar. De esta manera, al ser un lenguaje intermedio, no tiene una composición estandarizada 3

Universidad Nacional de Salta - Facultad de Ciencias Exactas Henry Suárez Año 2008

por lo que no todos los programadores utilizan la misma sintaxis con exactitud. Pero a la vez, como es una herramienta que está un paso previo al lenguaje formal de programación, es fácil de transformar al que será ejecutado en la computadora. Fuente: http://www.mastermagazine.info/termino/6428.php Programación estructurada A finales de los años sesenta surgió una nueva forma de programar que no solamente daba lugar a programas fiables y eficientes, sino que además estaban escritos de manera que facilitaba su comprensión posterior. El teorema del programa estructurado, demostrado por Böhm-Jacopini, demuestra que todo programa puede escribirse utilizando únicamente las tres instrucciones de control siguientes: • Secuencia • Instrucción condicional. • Iteración (bucle de instrucciones) con condición al principio. Solamente con estas tres estructuras se pueden escribir todos los programas y aplicaciones posibles. Si bien los lenguajes de programación tienen un mayor repertorio de estructuras de control, éstas pueden ser construidas mediante las tres básicas. Por ejemplo, en Visual Basic la secuencia de instrucciones consiste en la escritura de una instrucción debajo de otra (también se pueden poner en la misma línea separadas por el símbolo de dos puntos ":" aunque no es recomendable). La instrucción condicional es la instrucción If y la iteración con condición al inicio sería la instrucción do-while-loop o while-wend. Fuente: http://es.wikipedia.org/wiki/Programaci%C3%B3n_estructurada

4