01.Algoritmos.pdf

Algoritmos  Introducción ◦ Un problema es algo cuyo resultado no está fácilmente disponible. Se requiere un conjunto de pasos que involucran cálculo aritmético y/o manipulación lógica para obtener el resultado deseado. ◦ Existe una ley llamada ley de equifinalidad que establece que el mismo...

Algoritmos  Introducción ◦ Un problema es algo cuyo resultado no está fácilmente disponible. Se requiere un conjunto de pasos que involucran cálculo aritmético y/o manipulación lógica para obtener el resultado deseado. ◦ Existe una ley llamada ley de equifinalidad que establece que el mismo objetivo se puede lograr mediante diferentes cursos de acción y una variedad de caminos, por lo que el mismo resultado se puede obtener de varias maneras. ◦ Las diferentes formas de resolver un problema se denominan estrategias de solución. La forma óptima de resolver un problema para obtener el resultado deseado se puede lograr analizando diferentes estrategias para la solución y luego seleccionando la forma que pueda producir el resultado en el menor tiempo utilizando la mínima cantidad de recursos.  Introducción ◦ El proceso de selección dependerá de la eficiencia de la persona y su comprensión del problema. También debe estar familiarizado con diferentes técnicas de resolución de problemas. ◦ Determinar el conjunto de pasos necesarios para resolver un problema determinado es un arte. ◦ Muestra qué tan bien una persona puede organizar una serie de pasos para que otros puedan seguirlos. Un tipo de análisis llamado análisis de tareas. ◦ Se requiere llegar a la solución a partir de una definición del problema que establezca lo que se quiere lograr.  Definición formal de un algoritmo ◦ El lenguaje de programación es la combinación de símbolos y reglas que permiten la elaboración de programas con los cuales la computadora puede realizar tareas o resolver problemas de manera eficiente. ◦ Los lenguajes de programación se clasifican en: ◦ Lenguaje máquina. Las instrucciones son directamente entendibles por la computadora y no necesitan traductor para que la CPU (unidad de procesamiento central) pueda entender y ejecutar el programa. Utiliza un código binario (0 y 1), se basa en bits (abreviatura inglesa de dígitos binarios). ◦ Lenguaje de bajo nivel (ensamblador). Las instrucciones se escriben en códigos alfabéticos conocidos como mnemotécnicos. ◦ Lenguaje de alto nivel. Es semejante al lenguaje humano (en general en inglés), lo que facilita la elaboración y comprensión del programa. Por ejemplo C, C++, Java, Python, etcétera.  Definición formal de un algoritmo ◦ Un algoritmo es un conjunto ordenado de pasos ejecutables y no ambiguos, que define un proceso finito con un fin determinado. ◦ Observe que la definición requiere que el conjunto de pasos que forman un algoritmo sea ordenado. ◦ Esto significa que los pasos de un algoritmo tienen que tener una estructura bien establecida en términos de su orden de ejecución. ◦ Sin embargo, esto no quiere decir que los pasos deban ejecutarse en una secuencia compuesta de un primer paso seguida de un segundo, y así sucesivamente.  Definición formal de un algoritmo Todo algoritmo debe ser: ◦ Finito en tamaño o número de instrucciones (tiene un primer paso y un último paso) y tiempo de ejecución(debe terminar en algún momento). Por lo tanto, debe tener un punto particular de inicio y fin. ◦ Preciso. Debe tener un orden entre los pasos. ◦ Definido. No debe ser ambiguo (dobles interpretaciones); si se ejecuta el mismo algoritmo el resultado siempre será el mismo, sin importar las entradas proporcionadas. ◦ General. Debe tolerar cambios que se puedan presentar en la definición del problema.  Definición formal de un algoritmo ◦ Toda actividad que realizamos la podemos expresar en forma de algoritmo. Existen dos tipos de algoritmos, los que se desarrollan para ser ejecutados por una computadora, llamados algoritmos computacionales, y los que realiza el ser humano, es decir, algoritmos no computacionales; como ejemplos de éstos tenemos: ◦ Cambiar un neumático (llanta) de un automóvil. ◦ Preparar un plato de comida. ◦ Calcular el área de un triángulo.  Definición formal de un algoritmo ◦ En programación informática, suele haber muchos algoritmos diferentes para realizar una tarea determinada. Cada algoritmo tiene ventajas y desventajas en diferentes situaciones. La clasificación es un área donde se han realizado muchas investigaciones, porque las computadoras pasan mucho tiempo ordenando listas. ◦ Tres razones para utilizar algoritmos son la eficiencia, la abstracción y reutilización.  Definición formal de un algoritmo ◦ Eficiencia: ciertos tipos de problemas, como la clasificación, ocurren con frecuencia en la informática. Se deben utilizar algoritmos eficientes para resolver dichos problemas considerando el factor de tiempo y costo involucrado en cada algoritmo. ◦ Reutilizabilidad: los algoritmos suelen ser reutilizables en muchas situaciones diferentes. Dado que muchos algoritmos conocidos son generalizaciones de otros más complicados, y dado que muchos problemas complicados pueden resumirse en otros más simples, un medio eficiente para resolver ciertos problemas más simples nos permite potencialmente resolver muchos problemas complicados.  Definición formal de un algoritmo ◦ Abstracción: Los algoritmos proporcionan un nivel de abstracción en la resolución de problemas porque muchos de ellos aparentemente complicados. Los problemas se pueden resumir en otros más simples para los cuales existen algoritmos conocidos. ◦ Una vez que vemos un problema más complicado desde una perspectiva más simple, podemos pensar en el problema más simple como simplemente una abstracción del más complicado. Por ejemplo, imagine intentar encontrar la forma más corta de enrutar un paquete entre dos puertas de enlace en Internet. Una vez que nos damos cuenta de que este problema es sólo una variación del problema más general del camino más corto, podemos resolverlo utilizando el enfoque generalizado.  Expresión de Algoritmos ◦ Los algoritmos se pueden expresar en muchas notaciones diferentes, incluidos lenguajes naturales, pseudocódigo, diagramas de flujo y lenguajes de programación. ◦ Las expresiones de algoritmos en lenguaje natural tienden a ser detalladas y ambiguas, y rara vez se utilizan para aplicaciones complejas o complejas. ◦ El pseudocódigo y los diagramas de flujo son formas estructuradas de expresar algoritmos que evitan muchas ambigüedades comunes en las declaraciones del lenguaje natural, sin dejar de ser independientes de un lenguaje de implementación particular. ◦ Los lenguajes de programación están destinados principalmente a expresar algoritmos en una forma que pueda ser ejecutada por una computadora, pero a menudo se usan para definir o documentar algoritmos.  Expresión de Algoritmos ◦ A veces es útil en la descripción de un algoritmo complementar pequeños diagramas de flujo con lenguaje natural y/o expresiones aritméticas escritas dentro de diagramas de bloques para resumir lo que los diagramas de flujo están logrando. ◦ Considere un ejemplo para encontrar el número más grande en una lista de números sin clasificar. Algoritmo que utiliza declaraciones en lenguaje natural: A. Suponga que el primer elemento es el más grande. B. Leer cada uno de los elementos restantes de la lista y si es más grande que el elemento más grande hasta el momento, guardarlo. C. El último elemento anotado es el elemento más grande de la lista cuando el proceso está completado.  Expresión de Algoritmos ◦ Algoritmo que utiliza pseudocódigo: mayor = 0 para cada elemento en la lista (Longitud (L) >= 1), haga si elemento >= mayor, entonces mayor = elemento regresar mayor  Expresión de Algoritmos ◦ Algoritmo que utiliza pseudocódigo: ◦ Ejemplo Supongamos que tenemos la lista L = [3, 5, 2, 8, 6]: Inicializamos mayor a 0. Iteramos sobre cada elemento de la lista: 3 >= 0 → mayor = 3 5 >= 3 → mayor = 5 2 >= 5 → mayor no cambia 8 >= 5 → mayor = 8 6 >= 8 → mayor no cambia Al final del bucle, mayor es 8. El algoritmo devuelve 8.  Beneficios de utilizar algoritmos El uso de algoritmos proporciona una serie de beneficios. ◦ Uno de estos beneficios está en el desarrollo del procedimiento en sí, que implica la identificación de los procesos, los principales puntos de decisión y las variables necesarias para resolver el problema. ◦ Desarrollar un algoritmo permite e incluso obliga a examinar el proceso de solución de manera racional. La identificación de los procesos y puntos de decisión reduce la tarea a una serie de pasos más pequeños de tamaño más manejable.  Beneficios de utilizar algoritmos ◦ Los problemas que serían difíciles o imposibles de resolver en su totalidad pueden abordarse como una serie de pequeños subproblemas solucionables. ◦ Al utilizar un algoritmo, la toma de decisiones se convierte en un proceso más racional. ◦ Además de hacer que el proceso sea más racional, el uso de algoritmos hará que el proceso sea más eficiente y consistente.  Beneficios de utilizar algoritmos ◦ La eficiencia es un resultado inherente del proceso de análisis y especificación. ◦ La coherencia proviene tanto del uso del mismo proceso especificado como de una mayor habilidad en la aplicación del proceso. ◦ Un algoritmo sirve como dispositivo mnemotécnico y ayuda a garantizar que las variables o partes de el problema no se ignora. ◦ Presentar el proceso de solución como un algoritmo permite una comunicación más precisa. Finalmente, la separación de los pasos del procedimiento facilita la división del trabajo y el desarrollo de experiencia.  Beneficios de utilizar algoritmos ◦ Un beneficio final del uso de un algoritmo proviene de la mejora que hace posible. ◦ Si quien soluciona el problema no sabe lo que se hizo, no sabrá qué se hizo mal. A medida que pasa el tiempo y se comparan los resultados con las metas, la existencia de un proceso de solución específico permite identificar debilidades y errores en el proceso. ◦ La reducción de una tarea a un conjunto específico de pasos o algoritmo es una parte importante del análisis, control y evaluación.  Enfoques generales en el diseño de algoritmos ◦ En un sentido amplio, muchos algoritmos abordan los problemas de la misma manera. Por ello, suele ser conveniente clasificarlos según el enfoque que emplean. ◦ Una razón para clasificar algoritmos es obtener información sobre un algoritmo y comprender su enfoque general. Esto también puede darnos ideas sobre cómo analizar problemas similares para los cuales no conocemos algoritmos. ◦ Por supuesto, algunos algoritmos desafían la clasificación, mientras que otros se basan en una combinación de enfoques. Esta sección presenta algunos enfoques comunes.  Algoritmos aleatorios ◦ Los algoritmos aleatorios se basan en las propiedades estadísticas de los números aleatorios. Un ejemplo de algoritmo aleatorio es la clasificación rápida. ◦ Imagínese una pila desordenada de cheques cancelados a mano. Para ordenar esta pila, colocamos los cheques con números menores o iguales a lo que podemos pensar que es el valor mediano en una pila, y en la otra pila colocamos los cheques con números mayores que este. ◦ Una vez que tenemos los dos montones, dividimos cada uno de ellos de la misma manera y repetimos el proceso hasta terminar con un cheque en cada montón. En este punto los cheques están ordenados.  Algoritmos de divide y vencerás: ◦ Los algoritmos de divide y vencerás giran en torno a 3 pasos: dividir, conquistar y combinar. En el paso de división, dividimos los datos en partes más pequeñas y manejables. ◦ En el paso de conquista, procesamos cada división realizando algunas operaciones en ella. ◦ En el paso de combinación, recombinamos las divisiones procesadas. Un ejemplo del algoritmo divide y vencerás es la ordenación Quicksort.  Algoritmos de divide y vencerás: ◦ Como antes, imagine una pila desordenada de cheques cancelados a mano. ◦ Empezamos dividiendo el montón por la mitad. A continuación, dividimos cada una de las dos pilas resultantes por la mitad y continuamos este proceso hasta que terminemos con un cheque en cada pila. ◦ Una vez que todas las pilas contienen un solo cheque, unimos las pilas de dos en dos para que cada pila sea una combinación ordenada de las dos que se unieron. ◦ La unión continúa hasta que terminamos con una gran pila nuevamente, momento en el cual se clasifican los cheques.  Algoritmos codiciosos: ◦ Los algoritmos codiciosos toman decisiones que parecen mejores en el momento. En otras palabras, toman decisiones que son óptimas a nivel local con la esperanza de que conduzcan a soluciones óptimas a nivel global. ◦ El método codicioso extiende la solución con la mejor decisión posible en una etapa algorítmica basada en el óptimo local actual y la mejor decisión tomada en una etapa anterior. ◦ No es exhaustivo y no da respuestas precisas a muchos problemas. Pero cuando funciona, será el método más rápido. ◦ Un ejemplo de algoritmo codicioso es la codificación de Huffman, que es un algoritmo para la compresión de datos.  Algoritmos de aproximación : ◦ Los algoritmos de aproximación son algoritmos que no calculan soluciones óptimas; en cambio, calculan soluciones que son "suficientemente buenas". A menudo utilizamos algoritmos de aproximación para resolver problemas que son costosos desde el punto de vista computacional pero que son demasiado importantes para abandonarlos por completo. ◦ El problema del viajero es un ejemplo de un problema que generalmente se resuelve mediante un algoritmo de aproximación.  Definición de programa de computadora Existen diferentes conceptos; sólo mencionaremos tres: ◦ Es un algoritmo desarrollado en un determinado lenguaje de programación, para ser utilizado por la computadora; es decir, es una serie de pasos o instrucciones ordenadas y finitas que pueden ser procesadas por una computadora, a fin de permitirnos resolver un problema o tarea específica. ◦ Secuencia de instrucciones mediante las cuales se ejecutan diferentes acciones de acuerdo con los datos que se desee procesar en la computadora. ◦ Expresión de un algoritmo en un lenguaje preciso que puede llegar a entender una computadora.  Etapas o pasos en la creación de un programa Las fases para la creación de un programa son siete, aunque para algunos autores pueden describirse en sólo seis, pues omiten la primera porque es una etapa algo obvia. Las etapas se describen a continuación: ◦ Definición del problema ◦ Esta fase la proporciona el enunciado del problema, el cual requiere una definición clara y precisa (no debe ser ambiguo). Es importante que se entienda perfectamente lo que pretendemos que haga la computadora para poder continuar con la siguiente etapa.  Etapas o pasos en la creación de un programa ◦ Analisis del problema ◦ Una vez que se ha comprendido lo que se desea que la computadora haga, la etapa de análisis es muy importante ya que en ésta se identifican tres factores indispensables: ◦ Qué información se necesita para obtener el resultado deseado (datos de entrada). ◦ Qué información se desea producir (datos de salida). ◦ Los métodos y fórmulas que se necesitan para procesar los datos y producir esa salida.  Etapas o pasos en la creación de un programa ◦ Diseño y técnicas para la formulación de un algoritmo ◦ La etapa de diseño se centra en desarrollar el algoritmo basándonos en las especificaciones de la etapa del análisis; podemos representar un algoritmo mediante el diagrama de flujo o el pseudocódigo. ◦ Codificación ◦ En la etapa de codificación se transcribe el algoritmo definido en la etapa de diseño en un código reconocido por la computadora; es decir, en un lenguaje de programación; a éste se le conoce como código fuente. Por ejemplo el lenguaje “C++” es un lenguaje de programación.  Etapas o pasos en la creación de un programa ◦ Prueba y depuración ◦ La prueba consiste en capturar datos hasta que el programa funcione correctamente. A la actividad de localizar errores se le llama depuración. ◦ Existen dos tipos de pruebas: de sintaxis y de lógica. ◦ Las pruebas de sintaxis se ejecutan primero, son las más sencillas y las realiza el compilador del programa cada vez que se ejecuta el programa hasta que el código no presente errores, es decir que la sintaxis que requiere el lenguaje sea la correcta, de lo contrario el propio compilador va mostrando los errores encontrados para que se modifiquen y se pueda ejecutar el código; estos errores pueden ser falta de paréntesis, o puntos y comas o palabras reservadas mal escritas. ◦ Las pruebas de lógica son las más complicadas ya que éstas las realiza el programador; consisten en la captura de diferentes valores y revisar que el resultado sea el deseado, es decir el programador tendría que modificar el código hasta que el programa funcione correctamente.  Etapas o pasos en la creación de un programa ◦ Documentación ◦ Es la guía o comunicación escrita que permite al programador o al usuario conocer la funcionalidad del programa. ◦ La documentación sirve para que el código fuente sea más comprensible para el programador o para otros programadores que tengan que utilizarlo, así como para facilitar futuras modificaciones (mantenimiento). ◦ Hay dos tipos de documentación: ◦ Interna. Se generan en el mismo código y generalmente es mediante comentarios. ◦ Externa. Son los manuales y es independiente al programa. También puede ser la ayuda en el mismo software.  Etapas o pasos en la creación de un programa ◦ Mantenimiento ◦ Se dice que un programa no se termina al 100%, ya que es necesario hacer algún cambio, ajuste o complementación para que siga funcionando correctamente; para llevarlo a cabo se requiere que el programa esté bien documentado. ◦ Todos los programas tienen actualizaciones, por lo que surgen versiones diferentes. Por ejemplo: Windows 3.11, 95, 98, 2000, Millennium, Xp, Vista, 7, 8, 10, 11. Ejemplo de Programa Ejecución de Programa