ALGORITMOS

ALGORITMOS Práctica 1 IMD Grado en I.I. Tecnologías Informáticas

¿Qué es un algoritmo? n 

n 

n 

Es todo conjunto ordenado y finito de operaciones susceptibles de ser utilizadas por un ordenador para resolver un problema. Un problema es resoluble algoritmicamente (decidible) si es posible diseñar un algoritmo tal que para cada dato de entrada nos produzca una solución concreta. En caso contrario es irresoluble (indecidible).

Instrucciones n 

1)  2) 

n 

Un algoritmo consta de un conjunto finito de instrucciones y cada una de ellas debe especificar: Cuál es la tarea a realizar Cuál es la siguiente instrucción a ejecutar. Si no hay siguiente instrucción, el algoritmo para o termina. En cada paso de un algoritmo se pueden realizar una o varias operaciones.

Operaciones n  n 

n 

Cada operación debe estar bien definida Debe ser efectiva (susceptible de ser realizada en tiempo finito) Estar escritas con exactitud, para ello se usa un lenguaje (pseudocódigo) que después se traducirán a cualquier lenguaje de programación

Instrucciones válidas n  n  n  n  n  n  n  n  n  n  n 

variable ← expresión si condición entonces instrucción si condición. entonces instrucción sino instrucción. mientras condición entonces instrucción repetir instrucciones hasta que condición para variable ← valor inical hasta valor final hacer instrucción. etiqueta: instrucción ir a etiqueta Procedimiento nombre (lista de procedimientos) Función nombre (lista de parámetros) devolver

Características de un algoritmo n 

Conjuntos de entrada y salida: Una mala interpretación del conjunto de entrada, puede provocar un uso inadecuado del algoritmo: INPUT: n i f1 mientras n>1 hacer i f i ⋅ n n f n-1 fin mientras OUTPUT: i

Características de un algoritmo n 

Si la entrada es un nº real x, el algoritmo devuelve

x( x − 1) ⋅ ⋅ ⋅ ⋅( x − ⎣x⎦ + 1)

n 

Si es un natural n, devuelve n! que es en realidad la finalidad del algoritmo

Características de un algoritmo n 

Finitud: un algoritmo debe terminar siempre, tras un número finito de pasos, sin depender de la entrada inicial. INPUT: n iternf0 mientras n>1 hacer si n es par n fn+2 en otro caso nf3n+1 iternfitern +1 fin mientras OUTPUT: itern

Se trata de la conjetura de Collatz (no se ha podido probar si este algoritmo es finito)

Características de un algoritmo n 

Determinismo: todo algoritmo debe responder de manera única ante los mismos datos de entrada (es decir, debe ser una aplicación)

n 

Efectividad (o corrección parcial): un algoritmo debe terminar alcanzando la finalidad para la que ha sido creado. Se puede probar (en ocasiones) encontrando una expresión que permanezca invariante a lo largo del proceso y que permite dilucidar si la salida es la esperada.

Análisis y Complejidad n 

n 

El análisis de un algoritmo consiste en determinar la cantidad de recursos (tiempo T(n) y espacio) usando herramientas matemáticas La complejidad debe precisar dados dos algoritmos que resuelven el mismo problema, cuál de los dos tienen mejor coste.

Complejidad n 

n 

El tamaño de un dato x , |x|, es el número de dígitos binarios necesarios para representarlo en el ordenador El coste de un dato no sólo depende de su tamaño, así que acotamos el coste de los datos de un mismo tamaño por una función que sólo dependa del tamaño para todo x |x|=n, T(x) ≤ f (n)

Complejidad n  n  n  n 

Tomaremos como unidad de tiempo las operaciones elementales: La asignación de un valor a una variable La suma o multiplicación de enteros razonablemente pequeños Principio de invariancia: El coste de dos implementaciones distintas de un mismo algoritmo, difieren en una constante multiplicativa. Existen c y d,

T1 (n) ≤ cT2 (n)

T2 (n) ≤ dT1 (n)

Comportamiento asintótico n 

n 

El orden de T(n) expresa el comportamiento dominante para datos de gran tamaño Sean f,g, se dice que f es del orden de g, f ∈ Ο(g ) si existen constantes m, k tales que

f (n) ≤ kg (n)

n  n 

para todo n mayor o igual que m Todas las funciones constantes son O(1) Regla de la suma:

Ο( f (n) + g (n)) = Ο(max( f (n), g (n)))

Comportamiento asintótico n 

Regla del producto:

Ο( f (n))⋅ Ο(g (n)) = Ο( f (n)⋅ g (n))

n 

Por tanto:

Ο(cf (n)) = Ο( f (n)) n  n 

Cualquier polinomio de grado k es de orden n^k El orden de

Ο(log a n) = Ο(log b n) = Ο(log n)

Ordenes frecuentes en orden creciente n  n  n  n  n  n  n  n  n 

O(1) constante O(log n) logarítmica O(n) lineal O(n log n) O(n^2) cuadrática O(n^3) cúbica O(n^m) polinomial O(c^n) exponencial O(n!) factorial

Eficiente

Tratable Intratable

Comportamiento asintótico

Reglas prácticas n  n  n 

n 

n 

Estructuras sencillas (si/entonces) O(1) Secuencia de instrucciones: máximo de la complejidad de cada una (regla de la suma) Bucle con iteraciones fijas: multiplicar el número de iteraciones por la complejidad del cuerpo (regla del producto) Bucle con iteraciones variables: igual pero considerando el mayor número de iteraciones posibles (peor caso) Llamadas a subprogramas o funciones: tiempo de evaluación de cada parámetro más el tiempo de ejecución del cuerpo.

Ejemplo de complejidad lineal INPUT: n i f 1 mientras n>1 hacer i f i ⋅ n n f n-1 fin mientras OUTPUT: i

¿Cuánto vale T(n)? El algoritmo comienza con una asignación, después un bucle mientras que tiene una comparación, una asignación y una multiplicación, otra asignación y una resta. Por último hay otra comparación. Ésta se realiza cuando n=1 y el mientras termina. Luego T(n)=1+5(n-1)+1=5n-3, es decir es O(n)