jueves, 20 de noviembre de 2008
Historia del algoritmo y su Significado.La palabra algoritmo proviene del nombre del matemático llamado Muhammad ibn Musa al-Khwarizmi que vivió entre los siglos VIII y IX. Su trabajo consistió en preservar y difundir el conocimiento de la antigua Grecia y de la India. Sus libros eran de fácil comprensión, de ahí que su principal logro no fuera el de crear nuevos teoremas o corrientes de pensamiento, sino el de simplificar la matemática a punto tal que pudieran ser comprendidas y aplicadas por un mayor número de personas. Cabe destacar cómo señaló las virtudes del sistema decimal indio (en contra de los sistemas tradicionales árabes) y cómo explicó que, mediante una especificación clara y concisa de cómo calcular sistemáticamente, se podrían definir algoritmos que fueran usados en dispositivos mecánicos en vez de las manos (por ejemplo, ábacos). También estudió la manera de reducir las operaciones que formaban el cálculo. Es por esto que aún no siendo el creador del primer algoritmo, el concepto lleva aunque no su nombre, sí su pseudónimo.
Así, de la palabra algorismo, que originalmente hacía referencia a las reglas de uso de la aritmética utilizando dígitos árabes, se evolucionó a la palabra latina, derivación de al-Khwarizmi, algobarismus, que más tarde mutaría a algoritmo en el siglo XVIII. La palabra ha cambiado de forma que en su definición se incluye a todos los procedimientos finitos para resolver problemas.
Ya en el siglo XIX, se produjo el primer algoritmo escrito para un computador. La autora fue Ada Byron, en cuyos escritos se detallaban la máquina analítica en 1842. Por ello que es considerada por muchos como la primera programadora aunque, desde Charles Babbage, nadie completó su máquina, por lo que el algoritmo nunca se implementó.
Ya en el siglo XIX, se produjo el primer algoritmo escrito para un computador. La autora fue Ada Byron, en cuyos escritos se detallaban la máquina analítica en 1842. Por ello que es considerada por muchos como la primera programadora aunque, desde Charles Babbage, nadie completó su máquina, por lo que el algoritmo nunca se implementó.
La falta de rigor matemático en la definición de "procedimiento bien definido" para los algoritmos trajo algunas dificultades a los matemáticos y lógicos del siglo XIX y comienzos de XX. Este problema fue en gran parte resuelto con la descripción de la máquina de Turing, un modelo abstracto de computadora formulado por Alan Turing, y la demostración de que cualquier método anticipado por otros matemáticos que pueda encontrarse para describir "procedimientos bien definidos" puede ser emulado en una máquina de Turing (una afirmación conocida como "tesis de Church-turin"). En la actualidad, el criterio formal para definir un algoritmo es que se trata de un proceso que puede implementarse en una máquina de Turing completamente especificada, o en alguno de los formalismos equivalentes. El interés original de Turing era el problema de la detención: decidir cuándo un algoritmo describe un procedimiento de terminación. En términos prácticos importa más la teoria de la complejidad computacional, que incluye los problemas llamados NP-completos, es decir aquellos sobres los que generalmente se presume que requerirán tiempo más que polinómico para cualquier algoritmo (determinístico). NP denota la clase de los problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinística.
Definicion de Algoritmo
Un algoritmo (del latín, dixit algorithmus y éste a su vez del matemático persa al-Jwarizmi) es una lista bien definida, ordenada y finita de operaciones que permite hallar la solución a un problema. Dado un estado inicial y una entrada, a través de pasos sucesivos y bien definidos se llega a un estado final, obteniendo una solución. Los algoritmos son objeto de estudio de la algoritmia..
En la vida cotidiana se emplean algoritmos en multitud de ocasiones para resolver diversos problemas. Algunos ejemplos se encuentran en los instructivos (manuales de usuario), los cuales muestran algoritmos para usar el aparato en cuestión o inclusive en las instrucciones que recibe un trabajador por parte de su patrón. También existen ejemplos de índole matemático, como el algoritmo de la división para calcular el cociente de dos números, el algoritmo de Euclides para calcular el máximo común divisor de dos enteros positivos, o el método de Gauss para resolver un Sistema lineal de ecuaciones.
Cuando escribimos un programa de computadora, generalmente estamos llevando a cabo un método que se ha inventado para resolver algún problema previamente. Este método es a menudo independiente de la computadora y es probable que sea igualmente apropiado para muchas tipos de computadora y muchos lenguajes de computadora. Es el método, en el programa de computación, el que nosotros debemos estudiar para aprender cómo se está tratando de resolver el problema. El término algoritmo se usa en la informática para describir un método problema-solución conveniente para la aplicación en un programa de computadora. Los algoritmos son los materiales de informática, son los objetos centrales de estudio para muchos, si no la mayoría, de las áreas de campo.
Características de un Algoritmo
1. Entrada: definir lo que necesita el algoritmo.
2. Salida: definir lo que produce.
3. No ambiguo: explícito, siempre sabe qué comando ejecutar.
4. Finito: El algoritmo termina en un número finito de pasos.
5. Correcto: Hace lo que se supone que debe hacer. La solución es correcta
6. Efectividad: Cada instrucción se completa en tiempo finito. Cada instrucción debe ser lo suficientemente básica como para que en principio pueda ser ejecutada por cualquier persona usando papel y lápiz.
7. General: Debe ser lo suficientemente general como para contemplar todos los casos de entrada.
2. Salida: definir lo que produce.
3. No ambiguo: explícito, siempre sabe qué comando ejecutar.
4. Finito: El algoritmo termina en un número finito de pasos.
5. Correcto: Hace lo que se supone que debe hacer. La solución es correcta
6. Efectividad: Cada instrucción se completa en tiempo finito. Cada instrucción debe ser lo suficientemente básica como para que en principio pueda ser ejecutada por cualquier persona usando papel y lápiz.
7. General: Debe ser lo suficientemente general como para contemplar todos los casos de entrada.
Elementos de un algoritmo
- Variable: es un elemento del algoritmo que posee un valor, conocido por un nombre o identificador y que pertenece a un tipo de dato definido al inicio del algoritmo. Una variable es un nombre asociado a un elemento de datos que está situado en posiciones contiguas de la memoria principal, y su valor puede cambiar durante la ejecución de un programa.
- Constante: Son los elementos del algoritmo que no cambian de valor a lo largo del algoritmo. Las constantes deben ser inicializadas de acuerdo con el tipo de dato al que pertenecen. Una constante es un dato cuyo valor no puede cambiar durante la ejecución del programa. Recibe un valor en el momento de la compilación y este permanece inalterado durante todo el programa.
- Expresión: es una combinación de variables, constantes, valores constantes, operadores y funciones especiales que, en cada momento, al evaluarla tiene un valor concreto. Las expresiones más representativas son las numéricas y las lógicas.
Estructuras de Control
Las estructuras de control de un lenguaje de programación se refieren a el orden en que las instrucciones de un algoritmo se ejecutarán. El orden de ejecución de las sentencias o instrucciones determinán el flujo de control.
Estas estructuras de control son por consiguiente fundamentales en los lenguajes de programación y en los diseños de algoritmos especialmente los pseudocódigos.
Las tres estructuras de control básico son:
- secuencial
- selección
- repetición
Estructura Secuencial
Es aquélla en la que una acción (instrucción) sigue a otra en secuencia. Las tareas se suceden de tal modo que la salida de una es la entrada de la siguiente y así sucesivamente hasta el fin del proceso.
Características
- La estructura secuencial tiene una entrada y una salida.
- Un programa puede contener simplemente una secuencia de instrucciones.
- Es aquella que ejecuta las acciones sucesivamente unas a continuación de otras sin posibilidad de omitir ninguna y naturalmente, sin bifurcaciones.
Su representación gráfica es la siguiente:
Definicion de Dato
El dato (del latín datum), es una representación simbólica (numérica, alfabética, algorítmica etc.), atributo o característica de una entidad. El dato no tiene valor semántico (sentido) en sí mismo, pero convenientemente tratado (procesado) se puede utilizar en la realización de cálculos o toma de decisiones. Es de empleo muy común en el ámbito informático. Un dato es la expresión general que describe las características de las entidades sobre las cuales opera un algoritmo.
Datos son los hechos que describen sucesos y entidades."Datos" es una palabra en plural que se refiere a más de un hecho. A un hecho simple se le denomina "data-ítem" o elemento de dato. Los datos son comunicados por varios tipos de símbolos tales como las letras del alfabeto, números, movimientos de labios,puntos y rayas, señales con la mano, dibujos, etc. Estos símbolos se pueden ordenar y reordenar de forma utilizable y se les denomina información. Los datos son símbolos que describen condiciones, hechos, situaciones o valores. Los datos se caracterizan por no contener ninguna información. Un dato puede significar un número, una letra, un signo ortográfico o cualquier símbolo que represente una cantidad, una medida, una palabra o una descripción. La importancia de los datos está en su capacidad de asociarse dentro de un contexto para convertirse en información. Por si mismos los datos no tienen capacidad de comunicar un significado y por tanto no pueden afectar el comportamiento de quien los recibe. Para ser útiles, los datos deben convertirse en información para ofrecer un significado, conocimiento, ideas o conclusiones.
Tipos de Datos
- Datos Significativos: Para ser significativos, los datos deben constar de símbolos reconocibles, estar completos y expresar una idea no ambigua.Los símbolos de los datos son reconocibles cuando pueden ser correctamente interpretados. Muchos tipos diferentes de símbolos comprensibles se usan para transmitir datos.La integridad significa que todos los datos requeridos para responder a una pregunta específica están disponibles. Por ejemplo, un marcador de béisbol debe incluir el tanteo de ambos equipos. Si se oye el tanteo "New York 6" y no oyes el del oponente, el anuncio será incompleto y sin sentido.Los datos son inequívocos cuando el contexto es claro. Por ejemplo, el grupo de signos 2-x puede parecer "la cantidad 2 menos la cantidad desconocida llamada x" para un estudiante de álgebra, pero puede significar "2 barra x" a un vaquero que marca ganado. Tenemos que conocer el contexto de estos símbolos antes de poder conocer su significado.Otro ejemplo de la necesidad del contexto es el uso de términos especiales en diferentes campos especializados, tales como la contabilidad. Los contables utilizan muchos términos de forma diferente al público en general, y una parte de un aprendizaje de contabilidad es aprender el lenguaje de contabilidad. Así los términos Debe y Haber pueden significar para un contable no más que "derecha" e "izquierda" en una contabilidad en T, pero pueden sugerir muchos tipos de ideas diferentes a los no contables.
- Datos Pertinentes: Decimos que tenemos datos pertinentes cuando pueden ser utilizados para responder a preguntas propuestas.Disponemos de un considerable número de hechos en nuestro entorno. Solo los hechos relacionados con las necesidades de información son pertinentes. Así la organización selecciona hechos entre sucesos y entidades particulares para satisfacer sus necesidades de información.
Diagrama de flujo
Es la representación gráfica de flujo o secuencia de rutinas simples, es una forma de especificar los detalles algorítmicos de un proceso mediante la esquematización gráfica para entenderlo mejor. 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 la operación.Un diagrama de flujo es la representación gráfica del flujo o secuencia de rutinas simples. Tiene la ventaja de indicar la secuencia del proceso en cuestión, las unidades involucradas y los responsables de su ejecución; en pocas palabras es la representación simbólica o pictórica de un procedimiento administrativo.
El método de ordenación más conocido y popular entre estudiantes y aprendices de programación, es el método burbuja, por su facilidad de comprensión y programación. El método de búsqueda es una operación que tiene por objeto la localización de un elemento dentro de la estructura de datos. Encontramos dos técnicas que utiliza este método de acceso, para encontrar elementos dentro de un array: Búsqueda secuencial y búsqueda binaria.
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.Para hacer comprensible los Diagramas a todas las personas , los Símbolos se sometieron a una normalización, o lo que es en realidad se hicieron símbolos casi universales, ya que , en un principio cada usuario podría tener sus propios símbolos para representar sus procesos en forma de Diagrama de Flujo. Esto trajo como consecuencia que solo el que conocía sus símbolos, los podía interpretar.
Simbolos Utilizados en el Diagrama de Flujo
Pseudicodigo
Un pseudocódigo (falso lenguaje), es una serie de normas léxicas y gramaticales parecidas a la mayoría de los lenguajes de programación, pero sin llegar a la rigidez de sintaxis de estos ni a la fluidez del lenguaje coloquial. Esto permite codificar un programa con mayor agilidad que en cualquier lenguaje de programación, con la misma validez semántica, normalmente se utiliza en las fases de análisis o diseño de Software, o en el estudio de un algoritmo. Forma parte de las distintas herramientas de la ingeniería de software.
Para probar el algoritmo se utiliza un Pseudo intérprete el cual se encuentra disponible para las plataformas GNU/Linux y Windows, es de código libre y está escrito en C++. El mismo se ejecuta en un Terminal.
El pseudocódigo describe un algoritmo utilizando una mezcla de frases en lenguaje común, instrucciones de programación y palabras clave que definen las estructuras básicas. Su objetivo es permitir que el programador se centre en los aspectos lógicos de la solución a un problema.
No siendo el pseudocódigo un lenguaje formal, varían de un programador a otro, es decir, no hay una estructura semántica ni arquitectura estándar. Es una herramienta ágil para el estudio y diseño de aplicaciones, veamos un ejemplo, que podríamos definir como: lenguaje imperativo, de tercera generación, según el método de programación estructurada.
Pseudocódigo = Pseudo (Supuesto) + Código (Instrucción)
Algoritmo Cualitativo
Son todos aquellos pasos o instrucciones descritos por medio de palabras que sirven para llegar a la obtención de una respuesta o solución de un problema cualquiera.
Como ejemplo podemos decir que la utilización de un directorio (Búsqueda de un teléfono). Para poder buscar un teléfono en un directorio, se debe conocer el algoritmo que se va a utilizar, es decir la forma en que están codificados los nombres de las personas, para así lograr encontrarlos y localizar el número telefónico correspondiente.
Como ejemplo podemos decir que la utilización de un directorio (Búsqueda de un teléfono). Para poder buscar un teléfono en un directorio, se debe conocer el algoritmo que se va a utilizar, es decir la forma en que están codificados los nombres de las personas, para así lograr encontrarlos y localizar el número telefónico correspondiente.
Ejercicio de un Algoritmo Cualitativo
Como Hacer una Llamada Telefónica. Condición: De un teléfono público. El algoritmo Finaliza cuando se realice la llamada.
Como Hacer una Llamada Telefónica. Condición: De un teléfono público. El algoritmo Finaliza cuando se realice la llamada.
Inicio
Buscar el número
¿Encontró el Número?: SI: Ir Paso 4 NO: Ir Paso 2
Ubicar el Teléfono
¿Hay Teléfono?: SI: Ir Paso 6 NO: Ir Paso 4
Levantar el auricular.
¿Esta Bueno el teléfono?: SI: Ir Paso 8 NO: Ir Paso 15
Marcar el Número Telefónico.
¿Esta desocupada la Línea?: SI: Ir Paso 10 NO: Ir Paso 8
Esperar a que levanten la bocina del Teléfono.
¿Tomaron el teléfono?: SI: Ir Paso 12 NO: Ir Paso 15
Preguntar por la Persona con quien desea hablar.
¿Está la Persona?: SI: Ir Paso 14 NO: Ir Paso 15
Hablar con la Persona
Fin.
Video de un Algoritmo