Algoritmos Y Complejidad Computacional

Algoritmos y Complejidad computacional
En el presente capitulo presentaremos ideas básicas sobre complejidad computacional. Para ello presentamos algunos conceptos iniciales:
Un problema es una pregunta general que depende de varios parámetros y para el que necesitamos una respuesta.
Un número es primo ¿?
Una instancia es un problema al que se le han asignado valores a los parámetros deentrada.
Si 16 es primo ¿?
Un problema de decisión es el que admite solo 2 posibles respuestas “si” o “no”
Un problema de optimización consiste en obtener el mejor valor de f(x) en un conjunto B donde x pertenece a D y f(x) es una función que la denomina función objetivo.
Para enfrentar un problema de decisión o de optimización es necesario introducir la idea de algoritmo.
Un algoritmo puede servisto como una secuencia de pasos elementales que tienen que ser ejecutados sobre un conjunto de datos (instancia) y que produce un resultado.
Las entradas y salidas de un algoritmo dependen del problema, e d, estos pueden ser: números, cadenas de caracteres, secuencias de números, matrices, vectores, grafos, etc.
Para construir un algoritmo primeramente necesitamos definir un modelo teorico:
*Dadoun alfabeto ∑ definido como el conjunto de signos con al menos 2 elementos
*Definimos ∑* como el conjunto de palabras finitas que puede construirse con el alfabeto ∑
* Un problema de decisión puede definirse de la siguiente forma: Un problema ∏ es un subconjunto de palabras ∑* (∏ contenido en ∑*). La pregunta es: dado x que pertenece a ∑* se cumple x que pertenece a ∏.
Ejms:
1) Dado un numeroentero positivo, es posible determinar si es primo o no ??

∑= {0,1,…,9}

∑*={todos los números que se puede construir con esos 10 numeros}

∏={Todos los números primos}

Dado un numero n que pertenece a ∑*, se cumple n que pertenece a ∏??
2) 2- particionamiento: Dado un conjunto de números enteros s={a1,a2,…,an}
La tarea es decidir si existe 2 conjuntos S1 y S2 =S/S1 tal que
∑ai = ∑ai (aipertenece a S1 y S2 respectivamente)
S={4,7,9,1,3,2,8,4,2,1,9}
S1={4,7,9,1,3,2} S2={8,4,2,1,9}
∑={0,….,9,”, ”,” ”{ “}”,”=”,”S”}
∑*={Todos los conjuntos que puedan formarse a partir de ∑ tal que lSl>=2}
∏={Conjuntos que puedan ser particionados en S1 y S2, tal que S=S1US2 y S1∩S2=vacio} y
∑ai = ∑ai (ai pertenece a S1 y S2 respectivamente)
Dado un conjnto S que pertenece a ∑*, s que pertenece a ∏??Para resolver un problema es necesario almacenar los datos y determinar la cantidad de memoria que usaran dichos datos. El tamaño de estos datos es la longitud total de los strings (arreglos) usados para almacenarlos y se los conoce como la longitud de codificación
Formalmente, dado un x que pertenece a ∑*, la longitud de codificación {x} es el numero de símbolos usados en el alfabeto.Obviamente {x} depende del alfabeto
Ejms: si x=123, {x}=3
Asumiendo que nuestro alfabeto usa el sistema binario para almacenar la información, es decir, ∑={0,1} debido a que vamos a realizar la implementación computacional de algoritmos. Por ejm consideremos la transformación de un numero entero a un sistema binario.
n=131
131 dividido entre 2 es 65 y el residuo es 1
65 dividido entre 2 es 32 y el residuoes 1
32 “” 2 es 16 “” 0
16 “” 2 es 8 “” 0
8 “” 2 es 4 “” 0
4”” 2 es 2 “” 0
2 “” 2 es 1 “” 0
1”” 2 es 0 “” 1
Invertimos el orden de los residuos y se tiene la representación binaria de n que seria igual a
1 0 0 0 0 0 1 1 cuya longitud de codificación de este numero es {n}=8 (necesitamos 8 casillas = 8 bits)
Con este alfabeto se tiene lo siguiente: (siempre el entero superior)
Con{n}=8={log2(n)}
*n pertenece a N: {n}= {log2(n)} ={log n}
*n pertenece a Z: {n}=1+{log(n+1)}
*n pertenece Q: n=p/q, p pertence Z, qpertence N
{n}= 1+ {log(p+1)}+{log(q)}
*sistema lineal Ax=b, A pertence Qmxn , b pertence Qm
Si tomamos el máximo de los numeradores y denominadores
P11, P12, P13,…,Pnm, Pn,m+1 =< K1
q11, q12, q13,…,qnm, qn,m+1 =< K2
La longitud de codificación de {Ax=b} = (función techo)...