Algoritmos

Se ven mejor en Programación II: técnicas algorítmicas.

Un algoritmo es una sucesión finita de pasos o instrucciones para realizar una tarea, cálculo o resolución de un problema en un tiempo finito.

Debe tener las siguientes características:

• Debe terminar en un tiempo finito y debe de tener un número finito de pasos.
• Las instrucciones deben estar ordenadas, ser claras y no ambiguas.
• Recibe unos datos de entrada (Input) y produce una salida (Output).
• Debe ser correcto y efectivo: produce salidas correctas y cada paso se puede realizar (efectivo $\ne$ eficiente).
• Tiene un objetivo concreto y general.

Intuitivamente, un algoritmo de puede entender como una receta: se describen unas acciones ordenadamente y detalladamente para realizar una tarea.

Pseudocódigo

Es una descripción de alto nivel de un algoritmo o programa informático, y utiliza convenciones estructurales (condicionales, bucles, funciones, etc) de un lenguaje de programación, pero está pensado para la lectura de un humano y no de una máquina.

Tipos de algoritmos

• Algoritmos de búsqueda: El objetivo es encontrar un elemento dado en una lista.

  • Lineal / secuencial: comprueba todos los elementos uno por uno.
  • Binario: en una lista ordenada, separa los valores mayores de los menores y busca en la sublista más apropiada.

• Algoritmos de ordenamiento: El objetivo es ordenar los elementos de una lista, tanto de forma ascendente como descendente.

  • Ejemplos: bubble sort, insertion sort, selection sort, merge sort, quick sort…

• Algoritmos voraces / codiciones / greedy: algoritmos dedicados a resolver problemas de optimización, que en lugar de buscar la mejor solución global, producen una local al paso actual. Nunca reconsideran una de estas decisiones. Generalmente estos algoritmos no proporcionan la mejor solución, pero son bastante eficientes.
  • Ejemplo: problema del cambio de la moneda. El algoritmo seleccionará las monedas de mayor tamaño posible y menores a la cantidad restante que hay que pagar.

Problemas indecidibles

Alan Turing mostró que existen problemas que no se pueden resolver mediante algoritmos, como por ejemplo el Problema de la Parada o The Halting Problem:

Es posible escribir un programa de ordenador (procedimiento) que nos diga si dado un programa cualquiera y un conjunto de datos de entrada, podemos decidir si el programa termina, o no, su ejecución. ¿Parará alguna vez?

En este vídeo se explica muy bien el concepto de algoritmo y se «demuestra» porqué el problema de la parada no se puede resolver mediante algoritmos.

Big $O$, $\Omega$ y $\Theta$

Interpretación:

• $O(…)$ crece más que $f$.
• $\Omega(…)$ crece menos que $f$.
• $\Theta(…)$ crece igual que $f$.

Teorema y propiedades

Sabiendo que $f_1 \in O(g_1)$ y $f_2 \in O(g_2)$, se cumplen las siguientes propiedades:

• $(f_1 + f_2) \in O( \max( g_1, g_2 ) )$
• $(f_1 \times f_2) \in O( g_1 \times g_2 )$
• $(a f) \in O(g)$, siendo $a$ una constante
• $f \in O(g), g \in O(h) \implies f \in O(h)$ (propiedad transistiva)

Ejemplos

Complejidad de algoritmos

Se puede analizar un algoritmo desde varios puntos de vista:

• Complejidad temporal: cuantas operaciones necesita un algoritmo para una entrada dada. Estas operaciones pueden ser comparaciones, sumas, restas, multiplicaciones…
• Complejidad espacial: cuanta memoria necesita el algoritmo para funcionar.

Y también se puede analizar en distintos casos:

• Peor caso: $O(\ldots)$
• Caso promedio: $O_p(\ldots)$
• Mejor caso: $\Theta(\ldots)$

Tipos de problemas

O(1)          Constante
O(log n)      Logarítmico
O(sqrt n)     Sublineal
O(n)          Lineal
O(n log n)    Quasilineal / Superlineal
O(n ^ a)      Polinómico                  TRATABLES
------------------------------------------------------
O(a ^ n)      Exponencial                 NO TRATABLES
O(n!)         Factorial
O(n ^ n)      Superexponencial

Con $a > 1$.

P vs NP

• Clase P : problemas tratables en tiempo polinómico.

• Clase NP (Non-deterministic Polynomial): se desconoce si hay un algoritmo que acaba en tiempo polinómico; pero sí se puede comprobar una solución en tiempo polinómico.

• Clase NP-Completo : si hay un algoritmo capaz de resolver uno de estos problemas en tiempo polinómico, los demás de esta categoría también.

NP-Completo

NP

Ejemplos de problemas NP:

• Torres de Hanoi
• Factorización entera
• Isomorfismo de grafos

Ejemplos de problemas NP-Completo:

• Colorear con 3 tres colores un grafo
• Calcular un ciclo hamiltoniano
• Problema del viajante
• Problema de la mochila
• Resolver el Candy-Crush