La palabra algoritmo tiene dos fuentes, del término griego y latín, algobarismus, y del nombre del matemático persa Muhammad ibn Musa al-Khwarizmi, traducido al latin cómo Algoritmi.

La Real Academia de la Lengua Española define el concepto de algoritmo cómo:

• Un conjunto ordenado y finito de operaciones que permite hallar la solución de un problema.

Mi definición es:

• Una serie de reglas finitas no ambiguas y pasos sucesivos ordenados que conjuntamente definen, sin déficit de información y de manera única, una actividad a realizar.

Opcionalmente, podemos éste termine en tiempo finito.

Actualmente, algoritmos de tiempo infinito sólo se consideran en los ámbitos teóricos de la teoría de la computación.

Formalizaciones del concepto de algoritmo fueron propuestos de manera independiente y casi concurrente por Alonzo Church y Alan Turing en 1935-37.

• Estos modelos son el cálculo \(\lambda\) y las máquinas de Turing, respectivamente.

• La tesis de Church-Turing conjetura que todo lo que se puede realizar por medio de un algoritmo se puede realizar por una máquina de Turing y viceversa.

• Todas las operaciones que podemos realizar en una computadora se pueden hacer en una máquina de Turing.
  

• La mayoría de los lenguajes de programación son Turing completos: Pueden correr una máquina de Turing de cinta finita.

• Vamos a considerar como algoritmo a todo proceso que podremos programar en C con un propósito en específico (el resolver un problema).

  • La eficiencia de un algoritmo se mide en el tiempo de ejecución del caso promedio en función del tamaño de la entrada (tamaño del problema).

  • Un algoritmo es óptimo cuando este resuelve un problema con una eficiencia que no se e puede mejorar.

  • Un algoritmo es adecuado si cumple con nuestros propósitos.
    • Un algoritmo adecuado puede no ser óptimo y un algoritmo óptimo puede no ser adecuado, aunque esto es raro que se de.

Los algoritmos de fuerza bruta o búsqueda son aquellos que usan la técnica más general para resolver problemas:

• Generar de manera sistemática todas las posibles soluciones y verificar si alguno de los candidatos resuelven el problema.

• Los algoritmos de fuerza bruta son útiles como punto de partida para resolver un problema.

• Puede que la solución sea adecuada.

• También puede que sean (casi) óptimos (problemas NP-Dificiles).

• Siempre son muy lentos e intratables para problemas grandes.

  • El tiempo de ejecución crece de forma exponencial o más.

Un algoritmo es intratable cuando el tiempo de computo requerido para generar una solución es demasiado grande.

En programación e Ingeniera de software, el concepto de Top-down, de arriba hacia abajo, y bottom-up, de abajo hacia arriba, tienen principalmente dos campos de aplicación.

El primer campo de aplicación concierne a la aplicación general de resolver un problema y la planeación e implementación de un sistema de software.

Desde un punto de vista Top-Down:

• Durante la planeación de un algoritmo o un sistema de software se enfatiza una planeación integral de un sistema.
• Se delega la implementación de código hasta que se haya adquirido un diseño general del sistema de forma satisfactoria.

• Es una de los enfoques más usados en la programación estructurada.

• Primero se diseñan las características principales de un programa al especificar las partes de más alto nivel de este.
• Estas partes son en general más complejas.

• Estas se descomponen y subdividen de manera sucesiva en piezas menos complejas hasta completar el sistema.

Pare implementar un programa usando un enfoque top-down, primero se escribe la función principal que va ha llamar a las funciones principales que se van ha usar.

Después, se analizan cada una de las funciones que se especificaron y se repite el proceso en cada una.

El software se termina cuando las funciones no necesitan subrutinas y se pueden implementar con instrucciones sencillas de código.

Las rutinas en el nivel más bajo se enfocan generalmente en una sola tarea y requieren pocas lineas de código.

Ventajas.

• El analizar los grandes rasgos de un problema promueve el encontrar mejores soluciones para este.
• La interfaz de comunicación entre cada una de las partes de un programa se definen de manera clara.
• El tener una visión general del problema fomenta una mejor planeación del proyecto.
• Es una forma natural de atacar un problema cuando se tiene poca información sobre como se puede resolver.

Desventajas.

• Es relativamente fácil subestimar la complejidad de tareas sencillas cuándo no se tiene la experiencia adecuada.
• Puede que mejores soluciones locales sean pasadas por alto durante el diseño general.
• La implementación de código se relega hasta pasos posteriores, por lo que se posterga la obtención de resultados, aún cuando estos sean parciales.
• Por lo anterior, se dificulta la corrección de errores, tanto en implementación (bugs) como de diseño.

Desde un punto de vista Bottom-up:

• Primero se especifican, en gran detalle, los módulos base del sistema.
• Estás subrutinas base se implementan al momento.
• Estas subrutinas se unen para formar nuevas subrutinas hasta obtener el nivel más alto: el sistema completo.

• Es el principal enfoque en la programación funcional y se usa mucho en programación orientada a objetos.

• En genral, primero se diseñan los componentes de un sistema y se deja su integración hasta etapas posteriores.

Para implementar un programa usando un enfoque bottom-up primero se diseñan e implementan las partes que consideran que servirían para la implementación del sistema o la resolución de un problema.

Estas subrutinas base se unen para formar subrutinas de nivel más alto.

Se repite el proceso hasta tener el programa deseado.

El diseño del cada módulo de más alto nivel depende de la forma en que fueron implementadas las rutinas en el nivel bajo inmediato.

Ventajas.

• Ya que durante las primeras etapas de desarrollo se escribe código que realiza tareas, es posible obtener resultados parciales durante las primeras etapas de la implementación.

• Si una idea no funciona o es de difícil implementación, esta se puede descartar sin comprometer el diseño general del sistema.

• Promueve el desarrollo de código reusable.

• Es más facil el detectar errores de implementación (bug) y de diseño.

Desventajas.

• Se requiere de buena intuición y/o mucho conocimiento en la solución del problema para saber qué rutinas de bajo nivel van a ser útiles en la solución de un problema o la implementación de un sistema.

• Al enfocarse primeros en los pequeños detalles, es posible que se pasen por alto soluciones alternativas (Missing the forest for the trees).

• Se tiene que tener mucho cuidado en que las rutinas se puedan acoplar de manera ordenada.

• Es posible que lo que desarrolle no sea útil para la resolución del problema o la implementación de un sistema, dificultando la planeación del mismo.

Divide y vencerás (Divide and Conquer) es una técnica para resolver problemas y/o implementar sistemas que consiste en dividir un problema en varios subproblemas similares al problema principal pero de menor tamaño.

Esta división se realiza hasta que obtengamos subproblemas de un tamaño lo suficientemente pequeño para que la solución sea fácil de implementar.

Estos subproblemas son similares al problema principal, por lo que la solución es la misma y se puede reusar, generando una estructura recursiva.

Estas soluciones se combinan para generar la solución al problema original.

Un proceso es recursivo cuando este se invoca a sí mismo.

Para esta sección, vamos a interpretar lo anterior como un proceso que se repite varias veces en diferentes niveles del un problema.

Por ejemplo, podemos ver a un ciclo (while o for) como una recursión, donde el proceso es el código que se encuentra dentro del ciclo.

Los pasos de divide y vencerás son:

• Divide el problema en subproblemas que son instancias más pequeñas del mismo problema.

• Conquista los subproblemas de forma * recursiva * .
  • Esto es, reusa la misma solución y divide hasta que los problemas sean lo suficientemente pequeños pare ser resueltos fácilmente.

• Combina la solución de los problemas hasta obtener la solución del problema original.

Dividimos el problema:

• Dividimos el problema en invertir los enlaces de un único nodo.

Conquistamos el problema.

• Invertimos los enlaces de un nodo.

        actual -> siguiente = anterior;
        

Combinamos la solución (Definimos la iteración):

    anterior = NULL;
    actual = l -> primero;
    siguiente = actual -> siguiente;
    
    while(siguiente != NULL){
        actual -> siguiente = anterior;
        
        anterior = actual;
        actual = siguiente;
        siguiente = actual -> siguiente;
    }
    actual -> siguiente = anterior; 
    l -> primero = actual;

Merge sort (ordenar por medio de uniones) es un algoritmo eficiente para ordenar conjuntos.

Problema: Ordenar una serie de secuencia de \(n\) elementos.

Estrategia:

• Dividimos la serie de \(n\) elementos en dos subsecuencia con \(\frac{n}{2}\) elementos cada una.

• Conquistamos el problema al ordenar las dos secuencias de forma recursiva usando merge sort.

• Combinamos el ordenamiento de ambas subsecuencias en una sola secuencia ordenada.

Supongamos que dos secuencias \({x_1,...,x_n}\) y \({y_1,...,y_n}\) que están ordenadas.

Comparamos a \(x_i\) con \(y_i\), poniendo el menor primeo.

Repetimos el procedimiento hasta terminar con ambas subsecuencias.

De esta forma, la lista unificada esta ordenada.

Por ejemplo.

Tenemos la secuencia: {8,3,1,2,5,6,4,7}.

Dividimos: Cada secuencia a la mitad.

• {8,3,1,2}, {5,6,4,7}

• {8,3,1,2}, {5,6,4,7}

• {8,3}, {1,2}, {5,6}, {4,7}

• {8}, {3}, {1}, {2}, {5}, {6}, {4}, {7}

Conquistamos: Ordenamos cada una de las subsecuencias.

Comparamos cada uno de los elementos de una subsecuencia con el primero y el ultimo de la lista adyacente y los ponemos en orden.

• {8}, {3}, {1}, {2}, {5}, {6}, {4}, {7}

• {3,8}, {1,2}, {5,6}, {4,7}

  • Comparamos a 3 con 1, ponemos el 1: {1}.
  • 3 con 2, ponemos el 2: {1,2}.
  • Ya que no quedan elementos en la segunda secuencia, ponemos el 3 al final: {1,2,3}.
  • Lo mismo con el 8: {1,2,3,8}.

• {1,2,3,8}, {5,6}, {4,7}

  • Comparamos a 5 con 4, ponemos el 4: {4}.
  • 5 con 7, ponemos el 5: {4,5}.
  • Comparamos el 6 con el 7, ponemos el 6: {4,5,6}
  • Ya que no quedan elementos en la segunda secuencia, ponemos el 7 al final: {4,5,6,7}.

• {1,2,3,8}, {4,5,6,7}.

  • Repetimos el proceso y obtenemos:

Para una lista tamaño \(n\):

• Dividir: \[\sum_{i=0}^{\log_2 (n)} \alpha n = \alpha n \log_2 (n) \]

• Conquistar: Para dos listas de tamaño \(\frac{n}{2^i}\) realizamos, a lo más, \(2\beta\frac{n}{2^i}\) operaciones.

• Combinar: Dado lo de arriba: \[ \sum_{i=0}^{\log_2 (n)} \frac{n}{2^i} \times 2\beta\frac{n}{2^i} \leq \gamma n \log_2 (n).\]

De manera informal, una proceso u objeto se llama recursivo o recurrente si su definición esta en términos de si mismo.

En otros palabras un proceso es recursivo si su definición hace referencia al objeto en sí.

• Las estructuras recursivas están íntimamente ligadas con los procesos cíclicos. Aún mas, la recursión puede substituir a esta últimas en su totalidad.

• En particular, yo argumento que la propiedad de recursividad es una estructura más básica que los ciclo.

• • Por ejemplo:

i=i+1;

Nos define un proceso recursivo.

• El tener un lenguaje que nos permite realizar recurrencias nos acerca al cómputo universal.

Para evitar loops (ciclos) infinitos, vamos a definir a un proceso como dos partes fundamentales.

• Casos base: Los cases son casos específicos en los cuales el proceso no se define de forma recursiva.

• Proceso recursivo: Las operaciones (la subrutina) que se repite a lo largo de la ejecución del algoritmo.

  • Estas se tienen que reducir a un caso base, de lo contrario estamos en un ciclo infinito.

• Casos base: \[f_0=0,\] \[f_1 = 1.\]

• Función recursiva: \[f_n = f_{n-1}+f_{n-2}.\]

Sucesión: 0,1,1,2,3,5,8,13,21,34,55,89,144,233,…