UNIDAD II: ANALISIS Y DISEÑO DE ALGORITMOS
RESUMEN DE O PEQUEÑA
Sea t:N-> R >=n una función arbitraria de los números
naturales en los números enteros no negativos, tal como t(n) = 27n2 +
355/113 n+2. Se puede pensar que n representa la cantidad de un recurso dado
que se invierte en ese ejemplar por ese una implementación particular de este
algoritmo. Por ejemplo podría ser que la implementación invierta t(n)
microsegundos en el ejemplar peor en un caso de tamaño n, o quizá t(n)
represente la cantidad de espacio.
Matemáticamente significa que existe una constante real y
positiva c y un entero umbral no tal que t(n) represente que n>= n0.
Resumen de la O grande.
Es conveniente disponer de un símbolo matemático para
representar “el orden de”. Una vez mas, sea f: N -> R>= D una función
arbitraria de los números naturales en los reales no negativos. Le indicara
mediante O(f)n)) el conjunto de todas las funciones f:N -> R>=0 tales que
t(n) <n cf(n) para todo n>= n0. Para
una constante positiva real c y para un umbral entero no.
RESUMEN DE OMEGA
Considérese una vez mas dos definiciones t: f -> infinito
de los números naturales en los números enteros reales no negativos. Diremos
que f(n) está en omega de f(n), lo cual se denota como t(n) t omega (f(n)), si
f(n) está acotada inferiormente por un múltiplo real positivo de f(n) para todo
n suficientemente grande. Matemáticamente, esto significa que existe una
constante real positiva d y un umbral entero 0 tal que t(n) >= df(n) siempre
que n>=n.
Algunos autores definen la notación omega en una forma que
es diferente de forma sutil pero importante. Dicen que t(n) pertenece a omega
(f(n)) si existe una constante real y positiva d mientras que nosotros
requerimos que esta relación sea valida para todos los valores de n salvo un
numero finito. Con esta definición un algoritmo que requiera un tiempo en omega
(f(n)) en el caso peor es tal que existen infinitos casos en los cuales se
requiere al menos df(n) microsegundos para la constante real postiva adecuada
d.
Algoritmo de o pequeña.
Suma = 0
For (i=1;
i<n; i++)
{
Suma+ = i;
// suma = i+i;
} //Fin
Formula:
T(n) = n2 + 2n
Rapidez -> Eficiencia
Preciso -> Eficacia
Tipos de algoritmos:
1.- Deterministicos
2.- No Deterministicos
3.- Polinomicos
4.- No Polinomicos
DETERMINISTICOS:
El resultado de cada operación esta definido en forma única.
NO DETERMINITICOS:
El resultado de cada operación esta determinado por un
conjunto de posibilidades.
POLINOMMIAL:
Es un algoritmo de complejidad polinomial o inferior.
NO POLINOMIAL:
Es un algoritmo de complejidad exponencial o mayor.
NOTACIÓN DE O GRANDE.
|
O(1)
|
Constante
|
|
O(log log(n))
|
Log log (n)
|
|
O(log (n))
|
Logarítmica
|
|
O(n)
|
Lineal
|
|
O(n log(n))
|
Nlogn
|
|
O(n2 )
|
Cuadrática
|
|
O(n3 )
|
Cubica
|
|
O(nm )
|
Polinomial
|
|
O(mn )
|
Exponencial
|
|
O(n! )
|
Factorial
|
CUESTIONARIO
1.- ¿Qué es la cota inferior y superior de un algoritmo?
Una cota inferior es una función que sirve de cota inferior
de otra función cuando el argumento tiende a infinito, usualmente se utiliza la
notación omega.
Una cota superior es una función que sirve de cota superior
de otra función cuando el argumento tiende a infinito, usualmente se utiliza la
notación O (O grande).
2.- De acuerdo a la complejidad, ¿qué algoritmos son
factibles y cuáles son no factibles?
Los algoritmos factibles son aquellos que se denominan omega
y son eficientes.
Los algoritmos nos factibles son aquellos que se denominan O
(O grande) y su tiempo de ejecución es critico.
3.- De acuerdo a la complejidad, ¿ qué algoritmos son NP, o
NP completos?
La clase NP es el conjunto de problemas cuya solución se
puede comprobar en tiempo polinómico y el NP completo es un subconjunto del NP,
los cuales son los más difíciles en el sentido de no encontrarse en P.
4.- ¿Qué instrumentos de software se usan para efectuar
mediciones de algoritmos?
Métodos y entornos de desarrollo que nos ayudan a medir.
Cuestionario:
1. ¿Qué es recurrencia?
La recursividad es cuando una
función se llama así misma para resolver un algoritmo y la recurrencia también
se refiere a como calculamos el tiempo de ejecución de un algoritmo.
2. ¿Cómo resolver el problema “ejemplo
4.7.15” con recurrencia (considérese la siguiente recurrencia, que define T(n)
cuando n es una potencia de 2?
T(n)= {1/3 si n=1
nT2 (n/2) en caso contrario
1.10. Considérense las siguientes
funciones de n:
F1(n)=n2 cuadrática..
F2(n)=n2+1000n cuadrática
F3(n)= {n si n es
impar
n3 si n es impar cubica
F4(n)= {n si n <=100
n3 si n > 100 polinomial y puede ser cubica
Para cada posible par de valores
i y j, indíquese si f(n) es O(fi(n)) o no y si fi(n) es Ω (fi(n)) o no.
ALGORITMOS VORACES
Los algoritmos voraces se utilizan típicamente
para resolver problemas de optimización. Los ejemplos posteriores de este
capítulo incluyen la búsqueda de la ruta más corta para ir de un nodo a otro a
través de una red de trabajo a la búsqueda del mejor orden para ejecutar un
conjunto de tareas en una computadora.
En tales contextos, un algoritmo
voraz funciona seleccionando el arco, o la tarea, que parezca más
comprometedora en un determinado instante, nunca reconsidera su decisión, sea
cual sea la situación que pudiera surgir más adelante. No hay necesidad de
evaluar alternativas, ni emplear sofisticados procedimientos, que permiten
deshacer las decisiones anteriores.
Existe una función que da el
valor de la situación que hemos hallado: el número de maneras utilizadas para
dar la vuelta, la longitud de la ruta que hemos conseguido, el tiempo necesario
para procesarlas tareas de planificación, o cualquier otro valor que tenemos
intentando optimizar. La función objetiva no parece explícitamente en el
algoritmo voraz.
Cuando el algoritmo voraz
funciona correctamente la primera solución que se encuentre de esta manera es siempre
óptima:
Función voraz(c: conjunto)=conjunto
|c| es el conjunto de candidatos
S ß
0 {construimos la solución en el conjunto S }
Mientras c=/ 0 {y no soluciones
(s) hacer
Xß
seleccionar ©
Cß
c\|x|
