Algoritmos Uno: 2019

Lenguaje Algorítmico y Estructuras de Control

Definición formal de Algoritmo

En general, no existe ningún consenso definitivo en cuanto a la definición formal de algoritmo.

Muchos autores los señalan como listas de instrucciones para resolver un problema abstracto, es decir, que un número finito de pasos convierten los datos de un problema (entrada) en una solución (salida). Sin embargo cabe notar que algunos algoritmos no necesariamente tienen que terminar o resolver un problema en particular.

Por ejemplo, una versión modificada de la premisa de Eratóstenes” que nunca termine de calcular números primos no deja de ser un algoritmo.

A lo largo de la historia varios autores han tratado de definir formalmente a los algoritmos utilizando modelos matemáticos como máquinas de Turing entre otros Sin embargo, estos modelos están sujetos a un tipo particular de datos como son números, símbolos o gráficas mientras que, en general, los algoritmos funcionan sobre una vasta cantidad de estructuras de datos. En general, la parte común en todas las definiciones se puede resumir en las siguientes tres propiedades siempre y cuando no consideremos algoritmos paralelos:

Tiempo secuencial. Un algoritmo funciona en tiempo discretizado –paso a paso–, definiendo así una secuencia de estados "computacionales" por cada entrada válida (la entrada son los datos que se le suministran al algoritmo antes de comenzar).

Estado abstracto. Cada estado computacional puede ser descrito formalmente utilizando una Estructura de primer orden y cada algoritmo es independiente de su implementación (los algoritmos son objetos abstractos) de manera que en un algoritmo las estructuras de primer orden son invariantes bajo isomorfismo.

Exploración acotada. La transición de un estado al siguiente queda completamente determinada por una descripción fija y finita; es decir, entre cada estado y el siguiente solamente se puede tomar en cuenta una cantidad fija y limitada de términos del estado actual.

En resumen, un algoritmo es cualquier cosa que funcione paso a paso, donde cada paso se pueda describir sin ambigüedad y sin hacer referencia a una computadora en particular, y además tiene un límite fijo en cuanto a la cantidad de datos que se pueden leer/escribir en un solo paso. Esta amplia definición abarca tanto a algoritmos prácticos como aquellos que solo funcionan en teoría, por ejemplo el Métodos de Newton y la eliminación Gauss - Jordan funcionan, al menos en principio, con números de precisión infinita; sin embargo no es posible programar la precisión infinita en una computadora, y no por ello dejan de ser algoritmos.

En particular es posible considerar una cuarta propiedad que puede ser usada para validar la Tesis de Curch- Turing de que toda función calculable se puede programar en una máquina de Turing (o equivalentemente, en un lenguaje de programación suficientemente general)

Aritmetizabilidad. Solamente operaciones innegablemente calculables están disponibles en el paso inicial.

Medios de expresión de un algoritmo

Los algoritmos pueden ser expresados de muchas maneras, incluyendo al lenguaje natural, pseudocódigo,diagramas de flujo y lenguajes de programación entre otros.

Las descripciones en lenguaje natural tienden a ser ambiguas y extensas. El usar pseudocódigo y diagramas de flujo evita muchas ambigüedades del lenguaje natural.

Dichas expresiones son formas más estructuradas para representar algoritmos; no obstante, se mantienen independientes de un lenguaje de programación específico.

La descripción de un algoritmo usualmente se hace en tres niveles:

Descripción de alto nivel. Se establece el problema, se selecciona un modelo matemático y se explica el algoritmo de manera verbal, posiblemente con ilustraciones y omitiendo detalles.
Descripción formal. Se usa pseudocódigo para describir la secuencia de pasos que encuentran la solución.
Implementación. Se muestra el algoritmo expresado en un lenguaje de programación específico o algún objeto capaz de llevar a cabo instrucciones.

También es posible incluir un teorema que demuestre que el algoritmo es correcto, un análisis de complejidad o ambos.

Representación de Algoritmos

Hay distintos métodos de representar los algoritmos como:
o Texto: Se usa el lenguaje común para describir el algoritmo

o Pseudocódigo: este tipo de representación mezcla el lenguaje de programación con un idioma, ya sea español, ingles o cualquier otro, se puede definir como un lenguaje de especificación de algoritmos. Es la representación narrativa de los pasos que debe de seguir un algoritmo. Este método es mas compacto, mas fácil de escribir y mas fácil de transcribir a un lenguaje de programación que el diagrama de flujo.

o Diagrama de flujo: son herramientas graficas para representar algoritmos. esta compuesto por símbolos, como: rectángulos rombos, cuadrados, etc., unidos por flechas, estos símbolos representan acciones y orden en como se realizan estas. Es decir, los diagramas de flujo son diagramas que emplean símbolos gráficos para representar algoritmos.

o Diagrama de Nassi-Schneiderman: También conocido como diagrama de Chapín, es un método se representación de algoritmos que combina la descripción textual con la descripción grafica, es como una combinación del Pseudocódigo con el diagrama de flujo. Por lo general todo lo que se puede representar en un diagrama de flujo se puede representar en este tipo de diagrama. Este tipo de representación cuenta con un conjunto limitado de símbolos para representar los pasos del algoritmo

El diagrama Nassi-Shneiderman refleja la descomposición del problema en una forma simple usando cajas anidadas para representar cada uno de los sub-problemas. Ejemplos:

o Nivel de implementación: consiste en expresar un algoritmo mediante una maquinaria, un programa de computadora o algún objeto que realice las acciones planteadas por el algoritmo en cuestión. En general, la implementación es el objetivo de diseñar un algoritmo (pero no siempre).

Descripción Narrada

Este algoritmo es caracterizado porque sigue un proceso de ejecución común y lógico, describiendo textualmente paso a paso cada una de las actividades a realizar dentro de una actividad determinada.

Ejemplo 1 Algoritmo para asistir a clases:

1. Levantarse

2. Bañarse

3. Vestirse

4. Desayunar

5. Cepillarse los dientes

6. Salir de casa

7. Tomar el autobús

8. Llegar a la ESPE

9. Buscar el aula

10. Ubicarse en un asiento

Pseudocódigo

El pseudocódigo (falso lenguaje, el prefijo pseudosignifica falso) es una descripción de alto nivel de un algoritmo que emplea una mezcla de lenguaje natural con algunas convenciones sintácticas propias de lenguajes de programación, como asignaciones, ciclos y condicionales, aunque no está regido por ningún estándar. Es utilizado para describir algoritmos en libros y publicaciones científicas, y como producto intermedio durante el desarrollo de un algoritmo, como los Diagramas de flujo, aunque presentan una ventaja importante sobre estos, y es que los algoritmos descritos en pseudocódigo requieren menos espacio para representar instrucciones complejas.

El pseudocódigo está pensado para facilitar a las personas el entendimiento de un algoritmo, y por lo tanto puede omitir detalles irrelevantes que son necesarios en una implementación. Programadores diferentes suelen utilizar convenciones distintas, que pueden estar basadas en la sintaxis de lenguajes de programación concretos. Sin embargo, el pseudocódigo, en general, es comprensible sin necesidad de conocer o utilizar un entorno de programación específico, y es a la vez suficientemente estructurado para que su implementación se pueda hacer directamente a partir de él.

Así el pseudodocódigo cumple con las funciones antes mencionadas para representar algo abstracto los protocolos son los lenguajes para la programación. Busque fuentes más precisas para tener mayor comprensión del tema.

Ejemplo 1

Diseñar un algoritmo que lea cuatro variables y calcule e imprima su producto, suma y media aritmética.

inicio

leer (a, b, c, d)

producto <-- (a * b * c * d)

suma <-- (a + b + c + d)

media <-- (a + b + c + d) / 4

escribir (producto, suma, media)

fin

Algoritmos Uno

lunes, 15 de abril de 2019

Notas Finales

martes, 2 de abril de 2019

Quiz No. 1

Señores estudiantes, a partir del 2 de abril queda habilitado el Quiz por 8 horas, tomando como referente los conceptos de Turbo Pascal

para su desarrollo tener en cuenta:

martes, 26 de marzo de 2019

Ejercicios en Pascal

martes, 12 de febrero de 2019

Introducción