ALGORITMOSALGORITMOS

DIDIER FERNEY GONZALEZ DIDIER FERNEY GONZALEZ ORTIZORTIZ

DefiniciónDefinición

Conjunto preescrito de instrucciones o reglas Conjunto preescrito de instrucciones o reglas bien definidas, ordenadas y finitas que permite bien definidas, ordenadas y finitas que permite realizar una actividad mediante pasos realizar una actividad mediante pasos sucesivos que no generen dudas a quien lo sucesivos que no generen dudas a quien lo ejecute. Dados un estado inicial y una entrada, ejecute. Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución estado final y se obtiene una solución

CaracterísticasCaracterísticas Tiempo secuencial: Tiempo secuencial: Un algoritmo funciona en tiempo discretizado –paso a Un algoritmo funciona en tiempo discretizado –paso a

paso–, definiendo así una secuencia de estados "paso–, definiendo así una secuencia de estados "computacionalescomputacionales" por cada " por cada entrada válida (la entrada válida (la entradaentrada son los datos que se le suministran al algoritmo son los datos que se le suministran al algoritmo antes de comenzar).antes de comenzar).

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

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

Medios de expresiónMedios de expresión

Diagrama de flujo: Diagrama de flujo: Los diagramas de flujo son Los diagramas de flujo son descripciones gráficas de algoritmos; usan símbolos descripciones gráficas de algoritmos; usan símbolos conectados con flechas para indicar la secuencia de conectados con flechas para indicar la secuencia de instrucciones y están regidos por ISO. Los diagramas instrucciones y están regidos por ISO. Los diagramas de flujo son usados para representar algoritmos de flujo son usados para representar algoritmos pequeños, ya que abarcan mucho espacio y su pequeños, ya que abarcan mucho espacio y su construcción es laboriosa. Por su facilidad de lectura construcción es laboriosa. Por su facilidad de lectura son usados como introducción a los algoritmos, son usados como introducción a los algoritmos, descripción de un lenguaje y descripción de procesos descripción de un lenguaje y descripción de procesos a personas ajenas a la computación. a personas ajenas a la computación.

Pseudo código: Pseudo código: Pseudo código es la Pseudo código es la descripción de un algoritmo que asemeja a un descripción de un algoritmo que asemeja a un lenguaje de programación pero con algunas lenguaje de programación pero con algunas convenciones del lenguaje natural (de ahí que convenciones del lenguaje natural (de ahí que tenga el prefijo tenga el prefijo pseudopseudo, que significa , que significa falsofalso). ). Tiene varias ventajas con respecto a los Tiene varias ventajas con respecto a los diagramas de flujo, entre las que se destaca el diagramas de flujo, entre las que se destaca el poco espacio que se requiere para representar poco espacio que se requiere para representar instrucciones complejas. El pseudo código no instrucciones complejas. El pseudo código no está regido por ningún estándar. está regido por ningún estándar.

Sistemas formales: Sistemas formales: La teoría de autómatas y la La teoría de autómatas y la teoría de funciones recursivas proveen teoría de funciones recursivas proveen modelos matemáticos que formalizan el modelos matemáticos que formalizan el concepto de concepto de algoritmoalgoritmo. Los modelos más . Los modelos más comunes son la máquina de Turing, máquina comunes son la máquina de Turing, máquina de registro y funciones de registro y funciones μ-μ-recursivas. Estos recursivas. Estos modelos son tan precisos como un lenguaje modelos son tan precisos como un lenguaje máquina, careciendo de expresiones máquina, careciendo de expresiones coloquiales o ambigüedad, sin embargo se coloquiales o ambigüedad, sin embargo se mantienen independientes de cualquier mantienen independientes de cualquier computadora y de cualquier implementación.computadora y de cualquier implementación.

Implementación: Implementación: Muchos algoritmos son Muchos algoritmos son ideados para implementarse en un programa. ideados para implementarse en un programa. Sin embargo, los algoritmos pueden ser Sin embargo, los algoritmos pueden ser implementados en otros medios, como una red implementados en otros medios, como una red neuronal, un circuito eléctrico o un aparato neuronal, un circuito eléctrico o un aparato mecánico y eléctrico. Algunos algoritmos mecánico y eléctrico. Algunos algoritmos inclusive se diseñan especialmente para inclusive se diseñan especialmente para implementarse usando lápiz y papel. El implementarse usando lápiz y papel. El algoritmo de multiplicación tradicional, el algoritmo de multiplicación tradicional, el algoritmo de Euclides, la criba de Erastóstenes algoritmo de Euclides, la criba de Erastóstenes y muchas formas de resolver la raíz cuadrada y muchas formas de resolver la raíz cuadrada son sólo algunos ejemplos. son sólo algunos ejemplos.

Tipos de algoritmos.Tipos de algoritmos.

Existen dos tipos de algoritmos dependiendo de Existen dos tipos de algoritmos dependiendo de su función. Estos son:su función. Estos son:

Algoritmo de ordenamiento.Algoritmo de ordenamiento.

Algoritmo de búsqueda.Algoritmo de búsqueda.

Algoritmo de ordenamiento.Algoritmo de ordenamiento. Un algoritmo que pone elementos de una lista o un Un algoritmo que pone elementos de una lista o un

vector en una secuencia dada por una relación de vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar para poner datos en forma canónica y para generar resultados legibles por humanos. resultados legibles por humanos.

Clasificación.Clasificación. según el lugar donde se realice la ordenación según el lugar donde se realice la ordenación

Algoritmos de ordenamiento interno: en la memoria del Algoritmos de ordenamiento interno: en la memoria del ordenador. ordenador.

Algoritmos de ordenamiento externo: en un lugar externo Algoritmos de ordenamiento externo: en un lugar externo como un disco duro. como un disco duro.

Por el tiempo que tardan en realizar la ordenación, dadas Por el tiempo que tardan en realizar la ordenación, dadas entradas ya ordenadas o inversamente ordenadas: entradas ya ordenadas o inversamente ordenadas: Algoritmos de ordenación natural: Tarda lo mínimo posible Algoritmos de ordenación natural: Tarda lo mínimo posible

cuando la entrada está ordenada. cuando la entrada está ordenada. Algoritmos de ordenación no natural: Tarda lo mínimo posible Algoritmos de ordenación no natural: Tarda lo mínimo posible

cuando la entrada está inversamente ordenada. cuando la entrada está inversamente ordenada.

Algoritmo de búsquedaAlgoritmo de búsqueda

Un Un algoritmo de búsquedaalgoritmo de búsqueda es aquel que está es aquel que está diseñado para localizar un elemento concreto diseñado para localizar un elemento concreto dentro de una estructura de datos. Consiste en dentro de una estructura de datos. Consiste en solucionar un problema de existencia o no de solucionar un problema de existencia o no de un elemento determinado en un conjunto finito un elemento determinado en un conjunto finito de elementos, es decir, si el elemento en de elementos, es decir, si el elemento en cuestión pertenece o no a dicho conjunto, cuestión pertenece o no a dicho conjunto, además de su localización dentro de éste. además de su localización dentro de éste.

Clases:Clases:

Búsqueda secuencial: Búsqueda secuencial: Se utiliza cuando el contenido Se utiliza cuando el contenido del vector no se encuentra o no puede ser ordenado. del vector no se encuentra o no puede ser ordenado. Consiste en buscar el elemento comparándolo Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada secuencialmente (de ahí su nombre) con cada elemento del array hasta que éste se encuentre, o elemento del array hasta que éste se encuentre, o hasta que se llegue al final del array. La existencia se hasta que se llegue al final del array. La existencia se puede asegurar desde el momento que el elemento es puede asegurar desde el momento que el elemento es localizado, pero no podemos asegurar la no existencia localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del hasta no haber analizado todos los elementos del array. A continuación se muestra el pseudo código array. A continuación se muestra el pseudo código del algoritmo:del algoritmo:

Búsqueda binaria (dicotómica)Búsqueda binaria (dicotómica): Se utiliza : Se utiliza cuando el vector en el que queremos cuando el vector en el que queremos determinar la existencia o no de un elemento determinar la existencia o no de un elemento está ordenado, o puede estarlo, este algoritmo está ordenado, o puede estarlo, este algoritmo reduce el tiempo de búsqueda reduce el tiempo de búsqueda considerablemente, ya que disminuye considerablemente, ya que disminuye exponencialmente con el número de exponencialmente con el número de iteraciones. iteraciones.

EjemplosEjemplos 1. PROBLEMA:1. PROBLEMA: Un estudiante se encuentra en su casa (durmiendo) y debe ir a la universidad (a tomar la Un estudiante se encuentra en su casa (durmiendo) y debe ir a la universidad (a tomar la

clase de programación!!), ¿qué debe hacer el estudiante?clase de programación!!), ¿qué debe hacer el estudiante? ALGORITMO:ALGORITMO: InicioInicio

1 Dormir 1 Dormir haga haga 11 hasta hasta que suene el despertador (o lo llame la mamá). que suene el despertador (o lo llame la mamá). Mirar la hora.Mirar la hora.

¿Hay tiempo suficiente?¿Hay tiempo suficiente?SiSi hay, hay, entonces entonces     Bañarse.    Bañarse.    Vestirse.    Vestirse.    Desayunar.    Desayunar.Sino,Sino,       Vestirse.      Vestirse.Cepillarse los dientes.Cepillarse los dientes.Despedirse de la mamá y el papá.Despedirse de la mamá y el papá.  

    ¿Hay tiempo suficiente?¿Hay tiempo suficiente?SiSi, Caminar al paradero., Caminar al paradero.SinoSino, Correr al paradero., Correr al paradero.HastaHasta que pase un bus para la universidad que pase un bus para la universidad haga haga ::    Esperar el bus    Esperar el bus    Ver a las demás personas que esperan un  bus.    Ver a las demás personas que esperan un  bus.Tomar el bus.Tomar el bus.Mientras Mientras no llegue a la universidad no llegue a la universidad haga haga : :     Seguir en el bus.    Seguir en el bus.    Pelear mentalmente con el conductor.    Pelear mentalmente con el conductor.Timbrar.Timbrar.Bajarse.Bajarse.Entrar a la universidad. Entrar a la universidad. FinFin

2. PROBLEMA: 2. PROBLEMA: Cambiar la rueda pinchada de un Cambiar la rueda pinchada de un automóvil teniendo un gato mecánico en buen estado, automóvil teniendo un gato mecánico en buen estado, una rueda de reemplazo y una llave inglesa.una rueda de reemplazo y una llave inglesa.

ALGORITMO:ALGORITMO:InicioInicio

PASO 1. AflojarPASO 1. Aflojar los tornillos de la rueda pinchada los tornillos de la rueda pinchada con la llave inglesa.con la llave inglesa.PASO 2. PASO 2.    Ubicar el gato mecánico en su sitio.   Ubicar el gato mecánico en su sitio.PASO 3.PASO 3.    Levantar el gato hasta que la rueda     Levantar el gato hasta que la rueda pinchada pueda girar libremente.pinchada pueda girar libremente.PASO 4. PASO 4.    Quitar los tornillos y la rueda pinchada.   Quitar los tornillos y la rueda pinchada.PASO 5.   PASO 5.    Poner rueda de repuesto y los tornillos. Poner rueda de repuesto y los tornillos.PASO 6PASO 6.    Bajar el gato hasta que se pueda liberar..    Bajar el gato hasta que se pueda liberar.PASO 7.PASO 7.    Sacar el gato de su sitio.    Sacar el gato de su sitio.PASO 8.   PASO 8.    Apretar los tornillos con la llave inglesa. Apretar los tornillos con la llave inglesa.FinFin

3. PROBLEMA:3. PROBLEMA: Realizar la suma de los números 2448 y Realizar la suma de los números 2448 y 5746.5746.

ALGORITMO:ALGORITMO: InicioInicio

PASO 1.PASO 1. Colocar los números el primero encima del segundo, de tal Colocar los números el primero encima del segundo, de tal manera que las unidades, decenas, centenas, etc., de los números queden manera que las unidades, decenas, centenas, etc., de los números queden alineadas. Trazar una línea debajo del segundo número.alineadas. Trazar una línea debajo del segundo número.

PASO 2.PASO 2.  Empezar por la columna más a la derecha.  Empezar por la columna más a la derecha.PASO 3.PASO 3.  Sumar los dígitos de dicha columna.  Sumar los dígitos de dicha columna.

PASO 4.PASO 4. Si la suma es mayor a 9 anotar un 1 encima de la siguiente Si la suma es mayor a 9 anotar un 1 encima de la siguiente columna a la izquierda y anotar debajo de la línea las unidades de la suma. columna a la izquierda y anotar debajo de la línea las unidades de la suma. Si no es mayor anotar la suma debajo de la línea.Si no es mayor anotar la suma debajo de la línea.

PASO 5.PASO 5.  Si hay más columnas a la izquierda, pasar a la siguiente columna   Si hay más columnas a la izquierda, pasar a la siguiente columna a la izquierda y volver a 3.a la izquierda y volver a 3.

PASO 6. PASO 6.  El número debajo de la línea es la solución. El número debajo de la línea es la solución.FinFin

Desarrolle un Desarrolle un algoritmo de la algoritmo de la suma suma comprendida comprendida entre los números entre los números de 1 a 10de 1 a 10