Algoritmos

1. Fundamentos

1.1. Conceptos básicos

1.1.1. La palabra algoritmo proviene del nombre al-Khwarizmi matemático, astrónomo y geografo persa.

1.1.2. Los algoritmos son parte del núcleo de la computación.

1.1.3. muchos problemas algorítmicos exhiben dos características que son comunes

1.1.3.1. • Primero tienen muchos candidatos de solución

1.1.3.2. • Son o pueden ser aplicaciones prácticas

1.1.4. Definición de algoritmo

1.1.4.1. Según Schneider and Gersting: “Un algoritmo es una colección bien ordenada de operaciones no-ambiguas y computables efectivamente que cuando son ejecutadas producen un resultado y se detienen en una cantidad finita de tiempo.”

1.2. Caracteristicas

1.2.1. Para que un algoritmo sea ejecutable en una computadora, debe poseer ciertas características

1.2.1.1. 1. Los algoritmos están bien ordenados

1.2.1.1.1. Si el orden en un algoritmo no es claro, puede ejecutarse la instrucción equivocada o ser incierta qué instrucción debe ejecutarse a continuación.

1.2.1.2. 2. Los algoritmos contienen operaciones no-ambiguas

1.2.1.2.1. Los algoritmos que van a ser ejecutados en una computadora deben escribirse con operaciones básicas conocidas como operaciones primitivas.

1.2.1.3. 3. Los algoritmos contienen operaciones computables efectivamente.

1.2.1.3.1. Hay operaciones que no son computables efectivamente como lo es la división sobre 0 o la raíz cuadrada de un numero negativo.

1.2.1.4. 4. Los algoritmos producen un resultado

1.2.1.4.1. Un algoritmo se trata de un método para resolver problemas.

1.2.1.5. 5. Los algoritmos se detienen en una cantidad finita de tiempo

1.2.1.5.1. Los algoritmos deben estar compuestos de un número finito de operaciones y deben completar su ejecución en una cantidad determinada de tiempo

1.3. Complejidad

1.3.1. Después de que un algoritmo funciona bien y ya esta en un programa se definen criterios para su rendimiento

1.3.1.1. 1. Sencillez del algoritmo

1.3.1.1.1. Este aspecto facilita la verificación, estudio de eficiencia y mantenimiento de un algoritmo.,

1.3.1.2. 2. Uso eficiente de los recursos

1.3.1.2.1. Se mide en dos parámetros

1.3.2. Principio de Invarianza

1.3.2.1. afirma que existen una constante real c > 0 y un número natural n0 tales que para todo 𝑛 ≥𝑛0 se verifica que 𝑇1(𝑛)≤𝑐𝑇2(𝑛).

1.3.2.1.1. Es decir el tiempo de ejecución de dos implementaciones distintas de un mismo algoritmo, no va a diferir más que en una constante multiplicativa.

1.3.3. Casos de estudio

1.3.3.1. Para un mismo algoritmo, suelen estudiarse tres casos

1.3.3.1.1. 1. Mejor caso

1.3.3.1.2. 2. Peor caso

1.3.3.1.3. 3. Caso promedio

1.3.3.2. -La medición del tiempo se hace en función del número de operaciones elementales que realiza el algoritmo.

1.3.4. Análisis de algoritmos

1.3.4.1. El análisis de un algoritmo es un proceso cíclico: analizar, estimar y refinar el análisis hasta que se obtenga una respuesta del nivel de detalle deseado.

1.3.5. Complejidad

1.3.5.1. -La meta del estudio de la complejidad de un algoritmo es demostrar que su tiempo de ejecución es 𝑂(𝑓(𝑛)) para alguna función f, y que no puede haber un algoritmo con un tiempo de ejecución de O(g(n)) para cualquier función 𝑔(𝑛) más “pequeña” (una función con lim𝑛→∞𝑔(𝑛)/𝑓(𝑛)=0).

1.3.5.2. Un enfoque para estudiar el rendimiento de los algoritmos es estudiar el rendimiento del peor caso

1.3.5.2.1. Primero hay que hacer la noción de “proporcional a” matemáticamente precisa, separando al mismo tiempo el análisis de un algoritmo de cualquier implementación particular.

1.3.6. Análisis del caso promedio

1.3.6.1. En la situación más simple, podemos caracterizar las entradas del algoritmo

1.3.6.1.1. Tiene al menos 3 dificultades

1.4. NP-Completo

1.4.1. P: El conjunto de todos los problemas que pueden ser resueltos por algoritmos determinísticos en tiempo polinomial.

1.4.1.1. Por determinístico queremos decir que en cualquier momento, sin importar lo que el algoritmo esté elaborando, existe solamente una cosa que puede hacer a continuación.

1.4.2. NP: El conjunto de todos los problemas que pueden ser resueltos por algoritmos no-determinísticos en tiempo polinomial.

1.4.2.1. “no-determinismo”: asegurar que cuando un algoritmo se enfrenta con una selección de varias opciones, tiene la facultad de “adivinar” la correcta

1.4.3. Si cualquiera de los problemas puede ser resuelto en un tiempo polinomial en una máquina determinística, entonces todos los problemas en NP pueden ser resueltos (esto es, P = NP).

1.4.3.1. Estos problemas son NP-completos

1.4.3.1.1. La teoría de NP-Completos se basa en el concepto de transformación polinomial.