Descargar

Algoritmos y estructuras de datos (página 2)

Enviado por Pablo Turmero


Partes: 1, 2
edu.red

Esquema de una máquina RAM memoria entrada procesador Salida

edu.red

En este modelo suponemos que:

La unidad de entrada es una cinta de registros en cada uno de los cuales se puede almacenar un entero. La memoria es una sucesión de registros, cada uno de los cuales puede almacenar un entero de tamaño arbitrario. Los cálculos se hacen en el primero de ellos, r0. El programa no se almacena en en la memoria y no se modifica a si mismo. El conjunto de instrucciones es similar al de las computadoras reales. Cada instrucción tiene un nombre y una dirección.

Este modelo sirve para modelar situaciónes donde tenemos memoria suficiente para almacenar el problema y donde los enteros que se usan en los cálculos entran en una palabra.

edu.red

Ejemplo( sacado del libro de Aho, Hopcroft y Ullmann)

Ejemplo Instrucciones de una máquina RAM

LOAD operando – Carga un valor en el acumulador STORE operando – Carga el acumulador en un registro ADD operando – Suma el operando al acumulador SUB operando – Resta el operando al acumulador MULT operando – Multiplica el operando por el acumulador DIV operando – Divide el acumulador por el operando READ operando – Lee un nuevo dato de entrada ! operando WRITE operando – Escribe el operando a la salida JUMP label – Salto incondicional JGTZ label – Salta si el acumulador es positivo JZERO label – Salta si el acumulador es cero HALT – Termina el programa

edu.red

Los operandos pueden ser:

LOAD = a: Carga en el acumulador el entero a. LOAD i : Carga en el acumulador el contenido del registro i . LOAD *i : Carga en el acumulador el contenido del registro indexado por el valor del registro i .

edu.red

Ejemplo de un programa para calcula nn en esta máquina RAM ===================== READ 1 leer r1 LOAD 1 si r1 = 0 entonces write 0 JGTZ pos " WRITE = 0 " JUMP endif pos LOAD 1 sino r2 ?– r1 STORE 2 " LOAD 1 r3 ?– r1 -1 . SUB = 1 " STORE 3 " while LOAD 3 mientras r3 > 0 hacer . JGTZ continue " JUMP endwhile " continue LOAD 2 r2 ?– r2 * r1 . MULT 1 " STORE 2 " LOAD 3 r2 ?– r2 * r1 SUB = 1 " STORE 3 " JUMP while endwhile WRITE 2 write r2 endif HALT ========================================

edu.red

Cómo calculamos la complejidad de un algoritmo con este modelo? tj : tiempo de ejecución de la instrucción j. T: tiempo de ejecución de un programa que ejecuta nj instrucciones de tipo j.

T = ?j nj tj

Si suponemos que todos los tj son iguales tenemos

T = ?j nj

—————————————————————————- Esta es el modelo que usamos implícitamente cuando "calculamos" la complejidad de un algoritmo en la práctica

edu.red

Tamaño de la entrada de un problema Número de símbolos de un alfabeto finito necesarios para codificar todos los datos de una instancia de un problema. El tamaño de la entrada de un problema depende de la base o alfabeto elegidos.

para almacenar un entero positivo N en base 2 se necesitan L =?log2(N+1) ? dígitos binarios. en una base b cualquiera se necesitan L =?logb(N+1) ? si a y b ? 1 entonces logb N = loga N / loga b

qué implica esto desde el punto de vista de la complejidad de un algoritmo?

edu.red

Podemos considerar distintos modelos para determinar la complejidad en función del tamaño de la entrada del problema.

Modelo uniforme: suponemos que los valores a almacenar están acotados.

Modelo logarítmico: consideramos la representación binaria de los números a almacenar, o sea medimos el tamaño de la entrada en bits.

Qué consecuencias puede tener usar uno u otro modelo?

edu.red

Máquina de Turing (determinística) Componentes de una máquina de Turing =========================================================== Cinta infinita dividida en celdas iguales que pueden contener un único símbolo de un alfabeto finito T. Cabeza de lectura escritura que apunta a una de las celdas. lista finita de estados posibles {qi}. Hay al menos un estado final. operaciones: i) lectura del símbolo ti inscripto en la celda señalada por la cabeza. ii) guardar en esta celda el símbolo tf determinado por qi. iii) transición al estado qf determinado por ti y qi . iv) movimiento de la cabeza de lectura/escritura a izquierda o derecha. V) inicio de un nuevo ciclo. Para cuando llega a un estado final. ==========================================================

edu.red

Un programa correspondiente a esta máquina de Turing es un conjunto finito de quintuplas (qi,ti,qs, ts, m).

La instrucción (qi,ti,qs, ts, m) se interpreta como:

" si la máquina está en el estado qi y lee en la posición actual de la cabeza de lectora el símbolo del alfabeto ti , entonces escribe en dicha posición el símbolo ts , pasa al estado qs y se mueve a la izquierda o a la derecha según el valor de m sea -1 ó +1 ".

edu.red

Ejemplo Máquina de Turing para resolver el problema de determinar si dados N y M con M > 1, N es divisible por M.

Alfabeto T = { A, B, 0, 1, 2 } Se almacenan en la cinta M y N codificados en base 1, separados por el símbolo B y con el símbolo A marcando el fin del número. Estado inicial: q0 Estados posibles Q = {q0, q1 ,q2,qs, qn} Estados finales: qs, qn

edu.red

Programa Instrucciones

(q0, A,, q2 , A , + 1) (q1, A,, qn , * , *) (q2, A,, qs , * , *) (q0, B,, q0 , B , – 1) (q1, B,, q1 , B , + 1) (q2, B,, q2 , B , + 1) (q0, 0 , q0 , 0 , – 1) (q1, 0,, q1 , 0 , + 1) (q2, 0, q2 , 0 , + 1) (q0, 1 , q1 , 2 , + 1) (q1, 1 , q0 , 0 , – 1) (q2, 1 , q0 , 1 , -1) (q0, 2, q0 , 2 , -1) (q1, 2 , q1 , 2 , + 1) (q2, 2, q2 , 1 , + 1)

Cómo funciona esto?. Usar esta máquina para decidir si 5 es divisible por 3.

edu.red

Cómo se calcula la complejidad de un algoritmo representado por una máquina de Turing?.

Formalmente un algoritmo es un objeto asociado a una máquina de Turing que resuelve un determinado problema. La complejidad del mismo debería ser calculada en función del mismo.

En la práctica sin embargo usaremos una noción un poco menos formal de algoritmo y también para determinar la complejidad de un algoritmo, que se parece más al modelo RAM.

Desde el punto de vista práctico ambos enfoques han mostrado ser equivalentes.

Determinaremos la complejidad contando la cantidad de operaciones básicas de alto nivel que realiza el algoritmo, en función del tamaño del problema. Es correcto esto?. Puede ser peligroso?

edu.red

Cuándo decimos que un algoritmo es bueno?Armemos esta tabla….. supongamos que tenemos algoritmos con las siguientes complejidades y los corremos en la misma máquina(los tiempos están dados en segundos )

edu.red

La tabla queda así…(los tiempos están dados en segundos salvo cuando dice otra cosa)

edu.red

Los datos de la tabla anterior corresponden a una máquina MUY vieja (son datos del libro de Garey y Johnson de 1979).Qué pasa si tenemos una máquina 1000 veces más rápida?. Un millón de veces más rápida?. Cuál sería el tamaño del problema que podemos resolver en una hora comparado con el problema que podemos resolver ahora?.

Qué pasaría si tuviéramos una computadora 1 millón de veces más rápida?

edu.red

Cuándo diremos entonces que un algoritmo es bueno?. Cuándo un algoritmo es suficientemente eficiente para ser usado en la práctica?

============================= POLINOMIAL = "bueno" EXPONENCIAL = "malo" =============================

edu.red

Qué pasa si tengo complejidades como las siguientes?:

n 80 1.001n

esto no ocurre en la práctica

edu.red

Puede ocurrir que un algoritmo sea "malo" en el peor caso y bueno en la práctica?. Hay muy pocos casos.

Ejemplo clásico: método simplex para problemas de programación lineal. En el peor caso es exponencial pero en la práctica el tiempo de ejecución es generalmente O(m3) donde m es el número de ecuaciones del problema de programación lineal (es un método MUY usado en la industria y los servicios para resolver problemas de optimización.desde hace 60 años)

edu.red

Cuándo decimos que un problema está computacionalmente bien resuelto?

Cuándo hay un algoritmo polinomial para resolverlo.

Como veremos más adelante hay problemas para los cuales no sabemos si existe o no un algoritmo polinomial para resolverlos. Saber si una gran familia de estos problemas tiene solución polinomial o no es el problema abierto más importante de teoría de la computación…….

continuará en el último capítulo del curso…….

edu.red

Repasando notaciones Dadas dos funciones f y g : N+ ? R decimos que:

f(n) = O (g(n)) si ? c? 0 y n0 ?N tal que f(n) ? c g(n) ? n ? n0 . f(n) = ? (g(n)) si ? c? 0 y n0 ?N tal que f(n) ? c g(n) ? n ? n0 . f(n) = ? (g(n)) si ? c,c'? 0 y n0 ?N tal que c g(n) ? f(n) ? c' g(n) ? n ? n0

Si f(n) = O (g(n)) se dice que f es de orden g(n).

edu.red

Complejidad de algunos algoritmos conocidos Busqueda secuencial: O(n) Busqueda binaria: O(log(n)) Bubblesort: O(n2) Quicksort: O(n2) en el peor caso Heapsort: O(n log(n))

edu.red

Cálculo de determinantes

Sea una matriz M = (aij ) y sea Mij la submatriz de M que se obtiene sacando de M la fila i y la columna j.

Fórmula recursiva para calcular el determinante: (desarrollo por la primera fila)

det (M) = ? j (- 1) j+1 a ij det (M 1j)

edu.red

Complejidad de este método?.

Se puede calcular usando la fórmula recursiva que se deduce de la versión recursiva que dimos del algoritmo:

t(n) = n t(n – 1) + O (n)

Complejidad O(n!) Hay métodos más eficientes de calcular el determinante de una matriz?.

SI (triangular la matriz por el método de Gauss y calcular el producto de la diagonal)

Está este problema bien resuelto computacionalmente?.

edu.red

Búsqueda secuencial Datos: n, b, (a1,a2,………….an)

Paso 1: para i = 1,n hacer if b = ai parar Paso 2 : parar

=========================

Complejidad?

edu.red

Búsqueda Binaria Function Bin (T,x) si n = 0 o x < T entonces return i ? 1 j ? n mientras i < j hacer k ? ? (i+j+1)/2? si x < T (k) entonces j ? k-1 sino i ? k return i ========================= Complejidad?

edu.red

Algoritmos de ordenamiento Algoritmo de burbujeo Datos: (a1,a2, ……………….an) Paso 0: poner k = n Paso 1: mientras k ? 1 hacer Paso 2: poner i = 1 Paso 3: mientras i ? k hacer Paso 4 : si ai ? ai+1 cambiar ai con ai+1 Paso 5: poner i = i + 1 Paso 6 : poner k = k -1 Paso 7 : parar ========================= Complejidad?

edu.red

Heap sort Heap: árbol binario casi completo, donde cada nodo tiene asignado un valor de forma que el valor de un nodo es mejor (mayor) que el de sus hijos. Puede ser representado por un arreglo T en el cual los nodos del nivel k se guardan en las posiciones T [2k], T [2k+1], …………….T [2k+1-1]

edu.red

ejemplo T [1]

T [2] T [3]

T [4] T [5] T [6] T [7]

T [8] T [9] T [10]

edu.red

Ordenar T = ?1, 6, 9, 2, 7, 5, 2, 7, 4, 10? usando Heapsort.

1 6 9 2 7 5 2 7 10 4

edu.red

Algoritmo Make-Heap Dado un arreglo T los siguientes procedimientos nos permiten ordenarlo:

procedure sift-down(T [1..n], i) ("baja" el nodo i hasta que T [1..n] vuelve a ser un heap, suponiendo que T sea suficientemente grande para ser un heap (caso base?) k ? i repetir mientras j ? k j ? k if 2j ? n y T [2j ] > T [k ] entonces k ? 2j if 2j < n y T [2j +1 ] > T [k ] entonces k ? 2j + 1 intercambiar T [j ] y T [k ] fin

edu.red

procedure make-heap (T [1..n]) (arma el heap) para i = ?n /2? ….1 hacer sift-down (T,i) fin

procedure heapsort ((T [1..n]) (ordena T) make-heap (T) para i = n , 2 hacer intercambiar T [1] y T [i] sift-down(T [1..i-1], 1) fin

edu.red

Límite inferior para la complejidad de un algoritmo

Cuándo se puede obtener? Importancia

edu.red

EJEMPLO: algoritmos de ordenamiento basados en comparaciones. Se pueden modelar por un árbol binario de decisión. Los estados finales del algoritmos están representados en las hojas.

Entonces nro de hojas ? n! Como el árbol es binario, nro de hojas ? 2h (h altural del árbol) y 2h ? n! . Entonces

h ? log2 (n!) = log2 (n (n-1)….2. 1) > log2 (n (n-1)….?n/2?) > log2 n /2 (n/2) = = n/2 (log2 n – 1) ) = ? (n log2 n )

Conclusión: HEAPSORT es "óptimo" dentro de este tipo de algoritmos.

edu.red

Técnicas de diseño de algoritmos

Dividir y conquistar Recursividad Algoritmos golosos Programación dinámica Backtracking Algoritmos Probabilísticos

edu.red

El algoritmo se puede mejorar un poco, cambiando la forma de verificar cuando un conjunto de tareas es factible (ver libro de Brassard y Bratley).

edu.red

Dividir y conquistar Si la instancia I es pequeña, entonces utilizar un algoritmo ad-hoc para resolver el problema.

En caso contrario:

i) Dividir I en sub-instancias I1; I2; : : : ; Ik más pequeñas. ii) Resolver recursivamente las k sub- instancias. iii) Combinar las soluciones para las k sub-instancias para obtener una solución para la instancia original I .

edu.red

Dividir y conquistar ESQUEMA GENERAL: ——————————————————————————– Función DQ (x) Si x es suficientemente chico o simple entonces return ADHOC(x) Sino, descomponer x en subinstancias x1…xk . Para i=1,k hacer yi = DQ (xi) Combinar las soluciones yi para construir una solución y para x Return y ——————————————–

Recursividad, Caso Base

edu.red

Ejemplos:

Búsqueda binaria Merge Sort Quick Sort Algoritmo de multiplicación de Strassen

Cómo calcular la complejidad de estos algoritmos?. Ecuaciones de recurrencia.

edu.red

Ejemplo: Mergesort

Algoritmo divide and conquer para ordenar un arreglo A de n elementos (von Neumann, 1945).

Si n es pequeño, ordenar por cualquier método sencillo. Si n es grande:

— A1 := primera mitad de A. — A2 := segunda mitad de A. — Ordenar recursivamente A1 y A2 por separado. — Combinar A1 y A2 para obtener los elementos de A ordenados.

Este algoritmo contiene todos los elementos típicos de la técnica divide and conquer.

edu.red

Complejidad de MergeSort Cómo calcular t(n), complejidad de ordenar un arreglo de longitud n?

Podemos plantear la siguiente formula recursiva para la complejidad: t(n) = 2 t (?n/2?) + t(?n/2?) O (n) entonces t(n) es O(n log n)

edu.red

Algoritmo de multiplicación de Strassen Cómo calcular el producto de dos matrices de dos por dos usando menos multiplicaciones que con el método tradicional.

Dadas dos matrices

A = a11 a12 y B = b11 b12 a21 a22 b21 b22

podemos poner..

edu.red

m1 = (a21 + a 22 – a 11 ) (b22 – b 12 + b 11 ) m2 = a11 b11 m3 = a12 b21 m4 = (a 11 – a 21 ) (b 22 – b 12 ) m5 = (a21 + a 22 ) (b 12 – b 11 ) m6 = (a12 – a 21 + a11- a 22 ) b22 m7 = a22 ( b11 + b22 – b 12 – b 21 )

Entonces el producto AB queda: m2 + m3 m1 + m2 + m5 + m6 m1 + m2 + m4 – m7 m1 + m2 + m4 + m5

Este procedimiento requiere 7 multiplicaciones para cacular el producto de A y B (pero más sumas que el método tradicional!!).

edu.red

Si reemplazamos cada elemento de A y B por una matriz de n x n, las fórmulas anteriores nos dan una forma de multiplicar dos 2n X 2n matrices. A partir de esto tenemos un método recursivo para calcular el producto de matrices con n potencia de 2.

Cómo se calcula para n par, la complejidad t(n) de este algoritmo?.

t(n) = 7 t(n/2) + g(n) con g(n) ? O(n2)

Se puede demostrar que t(n) ? ? (n log 7) y por lo tanto t(n) ? O (n 2.81). (ejercicio)

Este método se puede generalizar también a matrices cuyas dimensiones no sean de la forma 2 n.

edu.red

Algoritmos Golosos Idea: Construir una solución seleccionando en cada paso la mejor alternativa, sin considerar las implicancias de esta selección en los pasos futuros ni en la solución final.

Se usan principalmente para problemas de optimización.

edu.red

Componentes:

Lista o conjunto de candidatos Conjunto de candidatos ya usados Función que verifica si un conjunto de candidatos da una solución al problema. Función que verifica si un conjunto de candidatos es hasta el momento factible. Función de selección Función objetivo

edu.red

——————————————————————————— Función GREEDY (C) {C es el conjunto de candidatos} S ?—— ? Mientras NOT solución(S) y C ? ? hacer x ?——————– elemento que maximice select (x) C < ——————– C {x} Si S U {x} es factible entonces s ?——— S U {x} Si solución(S) entonces RETURN S sino RETURN "no hay solución" ———————————————————————————

Qué hacen las funciones solución(S) y select (x) ?

edu.red

Minimizar el tiempo de espera en un sistema

Un servidor tiene n clientes para atender. Se sabe que el tiempo requerido para atender cada cliente i es ti. Se quiere minimizar

T = ?i (tiempo que i está en el sistema)

El algoritmo goloso que atiende al cliente que requiere el menor tiempo de atención entre los que aún están en la cola resuelve el problema. (hay que demostrarlo)

edu.red

Supongamos que I = ( i1,i2,……in) es una permutación de los enteros {1,2….n}. Si los clientes son atendidos en el orden I entonces

T = ti1 + (ti1+ ti2) + (ti1 + ti2 + ti3) + …… = ?k (n-k+1) tik

Usando esta expresión podemos probar que el algoritmo goloso es correcto…..

edu.red

Supongamos que en I hay dos enteros a y b con a < b y tal que tia > tib. O sea el cliente a es atendido antes que el b, a pesar de que el primero requiere mas tiempo de servicio. Si intercambiamos cambiamos las posiciones de a y b tenemos un nuevo orden I´ para el cual

T (I´) = (n-a + 1) tib +(n-b+1) tia + ?k?a,b (n-k+1) tik

Entonces T(I) – T ( I´) = (n-a + 1) (tia – tib ) +(n-b+1) (tib – tia )= = (b-a) (tia – tib ) > 0

Vemos que podemos seguir mejorando el valor de T intercambiando el orden de los clientes hasta obtener el orden óptimo dado por el algoritmo goloso.

================================== Cuál es la complejidad de este algoritmo?

edu.red

Problema de la mochila Quiero decidir cuáles son los elementos que tengo que elegir para llevar en la mochila para maximizar mi beneficio respetando la restricción de capacidad de la misma.

Max z =?j cj xj sujeto a que ?j aj xj ? b xj ? N+

b : capacidad de la mochila cj : beneficio de llevar una unidad del elemento j aj : peso del elemento j

b, cj , aj positivos

edu.red

En esta primera versión del problema de la mochila vamos a suponer que podemos llevar a lo sumo un objeto de cada tipo o "partes" de los mismos, es decir que consideraremos que las variables xj son reales positivas, o sea queremos resolver el siguiente problema:

Max ?j cj xj sujeto a que ?j aj xj ? b 0 ? xj ? 1

edu.red

Ejemplo: n = 5, b = 100 y los beneficios y pesos están dados en la tabla

Posibles ideas para un algoritmo goloso para este problema:

Elegir los objetos en orden decreciente de su beneficio.. Elegir los objetos en orden creciente de su peso…..

Sirven estas ideas?. Dan el resultado correcto?

edu.red

Que pasa si ordenamos los objetos por su relación beneficio/peso? O sea en orden decreciente de los cj /aj ?.

Lema: Si los objetos se eligen en el orden decreciente de los valores cj /aj entonces el algoritmo goloso encuentra la solución óptima al problema de la mochila con variables continuas.

Dem: supongamos que tenemos los elementos ordenados en orden decreciente de su relación cj /aj . Sea X = (x1,.xn) la solución encontrada por el algoritmo goloso. Si todos los xi son 1 la solución es óptima. Sino sea j el menor índice tal que sea xj < 1. Es claro que xi = 1 para i < j y que xi = 0 para i > j y que ? ai xi = b

edu.red

Sea V(X) = ? ci xi el valor de la solución dada por el algoritmo goloso.

Sea Y = (y1..yn) otra solución cualquiera factible. Como

b = ? ai xi ? ? ai yi

se puede ver que ? ( xi – yi ) ai ? 0

Además para todo índice i se verifica que

( xi – yi ) ci /ai ? ( xi – yi ) cj /aj entonces

V (X) – V ( Y ) = ? ( xi – yi ) ci = ? ( xi – yi ) aici /ai ? ? (cj / aj ) ? ( xi – yi ) ai ? 0

O sea el valor de la solución determinada por el algoritmo goloso es mejor o igual al valor de cualquier otra solución.

edu.red

Veamos que ocurre con el problema de la mochila, en el caso de que las variables xj tengan que tomar necesariamente valores enteros (como ocurre en la práctica, es decir cuando no podemos llevar un "pedazo" de un objeto).

Algoritmo goloso para el problema de la mochila con variables enteras nonegativas: ———————————————– Ordenar los elementos de forma que cj / aj ? cj+1 / aj+1

Para j=1,n y mientras b ? 0 hacer xj = ?b / aj? b = b – aj xj z = z + cj xj

Parar ————————————————

edu.red

Cuando las variables son enteras este algoritmo goloso no da siempre la solución óptima para el problema de la mochila.

Ejemplo: tenemos una mochila de tamaño 10 y 3 objetos, uno de peso 6 y valor 8, y dos de peso 5 y valor 5.

En el caso de variables enteras el algoritmo goloso que presentamos puede considerarse como una heurística para resolver el problema.

edu.red

Planificación de tareas Hay n tareas que deben ser ejecutadas cada una de las cuales requiere una unidad de tiempo. En cada momento se puede ejecutar una sola tarea. Cada tarea i produce un beneficios gi y debe ser ejecutada antes del tiempo di.

Ejemplo con n = 4

edu.red

Algoritmo goloso para este problema En cada paso elegir para ejecutar la tarea aún no realizada que produce el mayor beneficio, siempre y cuando el conjunto de tareas resultante sea factible.

Cómo se ve que un conjunto de tareas es factible?. Cuando hay un ordenamiento de esas tareas que permite ejecutarlas a todas a tiempo.

edu.red

Lema: sea J un conjunto de tareas y s = (s1, s2,…, sk) una permutación de dichas tareas tal que ds1 ? ds2 ? … ? dsk J es factible si y sólo si s también lo es.

Dem: ? obvio. Si J es factible existe al menos una sucesión de los trabajos ? = (r1, r2,…rk) tal que dri ? i, para 1? i ? k. Si fuera s? ? , sea a el menor índice tal que sa ? ra y sea b el índice tal que rb = sa. Claramente b > a y dra ? dsa = drb. Entonces el trabajo ra podría ser ejecutado más tarde en el lugar de rb y este último en el lugar de ra. Si los cambiamos en ? tenemos una sucesión factible que tiene un trabajo más en coincidencia con s. Repitiendo este procedimiento podemos llegar a obtener s y ver entonces que es factible.

edu.red

Lema: Este algoritmo goloso obtiene la solución óptima para este problema de planificación de tareas.

Dem: Supongamos que el conjunto I elegido por el algoritmo goloso es distinto de un conjunto J óptimo. Sean SI y Sj dos sucesiones factibles para estos conjuntos. Hacemos intercambios de modo de obtener dos sucesiones factibles S´I y S´j tal que los trabajos comunes en ambas secuencias sean ejecutados en el mismo momento (pueden quedar gaps en alguna de las planificaciones).

edu.red

O sea si tenemos las secuencias.

SI p y q x r – – – SJ r s t p u v q w

podemos reordenarlas de la siguiente forma

S´I x y – p r – q – S´J u s t p r v q w

(En S´I y S´J se siguen respetando los tiempos de entrega di)

edu.red

Como hemos supuesto que los conjuntos I y J son distintos, consideremos ahora un momento en el cual la tarea que está programada en S´I es distinta de la programada en S´j :

Si una tarea a está programada en S´I y en S´j hay un gap (la tarea no pertenece a J) entonces J ? {a} sería mejor que J, absurdo porque J es óptimo.

Si alguna tarea b está programada en S´j y en S´I hay un gap entonces I ? {b} es factible y por lo tanto el algoritmo goloso tendría que haber incluído a b y no lo hizo.

edu.red

La última posibilidad es que haya una tarea a programada en S´I y otra b en S´j. Esto implica que a no aparece en J y b no aparece en I : – si fuera ga > gb se podría substituir a por b en J y mejorar a J (absurdo porque J era óptimo). – si fuera fuera gb > ga el algoritmo goloso tendría que haber elegido a b antes de considerar a. – entonces gb = ga

Por lo tanto S´I y S´j tienen programadas en cada momento, o ninguna tarea, la misma tarea o distintas tareas que dan el mismo beneficio. Y entonces como J era óptimo I también lo es.

edu.red

Algoritmo goloso para este problema de planificación de tareas

(se supone que las tareas están numeradas de modo que g1? g2 ? ….? gn) ——————————————————————- Función sequence (d[0..n]) d[0], j[0] ?——— 0 k, j[1] ?——1 Para i= 1,n hacer r < -k mientras d[j [r]] > max ( d(i),r) hacer r = r-1 si d[j [r]] ? d[i] y d[i] > r entonces para l=k-1, r+1 hacer j[l+1] = j[l] j[r+1] ?———i k ?—- k+1 Return k, j[1,..k] ——————————————————————

edu.red

Backtracking Técnica para recorrer sistemáticamente todas las posibles configuraciones de un espacio. Puede pensarse también que es una técnica para explorar implícitamente árboles dirigidos (o grafos dirigidos en general pero sin ciclos).

Habitualmente s utiliza un vector a = (a1; a2; : : : ; ak ) para representar una solución candidata, cada ai pertenece un dominio/conjunto ordenado y finito Si .

Se extienden las soluciones candidatas agregando un elemento más al final del vector a, las nuevas soluciones candidatas son sucesores de la anterior.

edu.red

Procedure backtrack (v[1..k]) {v es un vector k-prometedor } si v es una solución al problema entonces escribir v sino para cada vector "k+1-prometedor" w tal que w[1.k] = v[1.k] hacer backtrack (w[1.k+1]) ===================================== No necesariamente exploramos todas las ramas del árbol : "poda"

edu.red

Problema de las 8 reinas

Ubicar 8 reinas en el tablero de ajedrez sin que ninguna "amenace" a otra.

Cuántas operaciones tenemos que hacer si consideramos todas las combinaciones del tablero tomadas de a 8 y después vemos cuales sirven?

? 64? = 442616536 ? 8 ?

Si mejoramos esto usando la representación (i1, i2, i3 ,i4, i5 ,i6,i7 ,i8 ) donde ij indica que hay una reina en la columna j y la fila ij y analizamos cuales son factibles o no. cuántas operaciones tendremos?. 8 8 = 16777216 (se encuentra una solución después de revisar "sólo" 1299 852 posiciones)

edu.red

Si vemos que dos reinas no pueden estar ni en la misma fila ni en la misma columna vemos que en realidad podemos representar el problema mediante las permutaciones de (1,2,3,4,5,6,7,8). Cuántas operaciones tenemos en este caso?.

8! = 40320

(implementando este algoritmo podemos ver que hay que revisar 2830 posiciones hasta encontrar una primera solución)

edu.red

Algoritmo de bactracking Decimos que un arreglo V de los enteros 1 a 8 es k-prometedor si ninguna de las reinas ubicadas en las posiciones (1, v(1)), (2,v(2)), (3,v(3)),…(k,v(k)), 1? k ? n amenaza a las otras.

O sea v es k-prometedor si para todo i?j entre 1 y k, tenemos que v(i) -v(j) ? {i-j,0,j-i}.

Un vector 8-prometedor es solución del problema de las 8 reinas.

edu.red

Algoritmo de backtracking ———————————————————————————— Procedimiento Queens (k, try, diag45, diag 135) {try[1,.k] es k-prometedor, col = {try [i], 1? i? k} diag45 = {try [i]-i +1, 1? i? k} diag135 = {try [i] + i – 1, 1? i? k}} Si k = 8 entonces {un vector 8-prometedor es solución}. Return try Sino {explorar las k+1-prometedoras extensiones de try} Para j=1,8 si j ? col y j-k ? diag45 y j+k ? diag135 entonces try[k+1] ?–j {try [1,..k+1] es k+1-prometedor} Queens (k+1, col U {j}, diag45 U {j}, diag135 U {j+k}

————————————————————————————-

edu.red

Se puede ver computacionalmente que este árbol de bactracking tiene 2057 nodos y que es suficiente explorar 114 para encontrar la primera solución. (Cómo se hace para calcular esto?).

Cuál es la complejidad de este algoritmo de bactracking?

Ejercicio: Mostrar un valor de n ? 2 para el cual el problema de las n reinas no tiene solución.

edu.red

Otros ejemplos Encontrar, usando backtracking todas las soluciones enteras de

x1+ 2×2 + x3 ? 10

1 ? xi ? 4 i =1,2,3

edu.red

Algoritmos probabilísticos Cuando un algoritmo tiene que hacer una elección a veces es preferible elegir al azar en vez de gastar mucho tiempo tratando de ver cual es la mejor elección.

Pueden dar soluciones diferentes si se aplican dos veces a la misma instancia. Los tiempos de ejecución también pueden ser muy diferentes.

Tiempo promedio de un algoritmo determinístico: considera todas las instancias de un mismo tamaño son "similares". (ejemplo: quicksort) Tiempo esperado promedio de un algoritmo probabilístico : es el tiempo medio de los tiempos de resolver la misma instancia del mismo problema "muchas veces".

Peor tiempo esperado: tomando en cuenta el peor caso de todas las instancias de un cierto tamaño.

edu.red

Clasificación de algoritmos probabilisticos

Algoritmos al azar para problemas numéricos: la respuesta es siempre aproximada pero se espera que la solución sea mejor cuando más tiempo hay para ejecutar el algoritmo. (simulación, integración numérica).

Algoritmos de Monte Carlo: se quiere una respuesta exacta. Por ejemplo problemas de decisión. Un algoritmo Monte Carlo da siempre una respuesta pero la respuesta puede no ser correcta. La probabilidad de suceso, es decir de respuesta correcta crece con el tiempo disponible para correr ese algoritmo. La principal desventaja es que en general no se puede decidir eficientemente si la respuesta es correcta o no.(ejemplo: decidir si un arreglo T tiene un elemento mayoritario, o sea que aparece en T más de n/2 veces)

edu.red

Algoritmos Las Vegas: nunca dan una respuesta incorrecta pero pueden no dar ninguna respuesta. También la probabilidad de suceso, es decir de tener respuesta correcta crece con el tiempo disponible para correr ese algoritmo. (ejemplo: en el problema de las 8 reinas poner las reinas al azar en las filas que aún están desocupadas, cuidando solamente que la solución en construcción sea factible)

Algoritmos Sherwood : en este caso el algoritmo siempre da una respuesta y la respuesta es siempre correcta. Se usan cuando algún algoritmo determinístico para resolver un algoritmo es mucho más rápido en promedio que en el peor caso. Al incorporar un factor de azar el algoritmo puede llegar a eliminar la diferencia entre buenas y malas instancias. (ejemplo: Quicksort)

edu.red

En todos estos casos suponemos que tenemos disponible un generador de números al azar de costo computacional unitario. O sea dados reales a y b con a < b, uniform (a,b) devuelve un número x elegido al azar en el intervalo a ? x < b. La distribución de x es uniforme en el intervalo y llamadas sucesivas del generados dan valores independientes de x.

Para generar enteros al azar uniform (i.j) devuelve un entero k elegido al azar uniformemente en el intervalo i?k ?j

edu.red

Ejemplo de algoritmo tipo MonteCarlo: ver si un arreglo tiene un elemento mayoritario. —————————————- Function may(T[1,.n]) i = uniform (1,.n) x = T[i] k = 0 Para j =1,n hacer if T[j] = x then k = k +1

Return (k > n/2) ——————————

Cuál es la probabilidad de que este algoritmo de la respuesta correcta?

edu.red

Ejemplo de algoritmo tipo Las Vegas: el problema de las 8 reinas. Procedimiento Queens LV (var sol[1.8], sucess) array ok[1.8] (posiciones disponibles) col, diag45, diag135 ? ? Para k = 0,7 hacer (sol [1.k] es k prometedor, hay que ubicar a la reina k+1) nb = 0 para j = 1, 8 hacer si j ? col y j-k ? diag45 y j+k ? diag135 entonces (la columna j esta disponible) nb = nb +1 ok[nb] = j si nb = 0 entonces sucess =false j = ok[uniform (1..nb)] col = col U {j} diag45 = diag45 U {j} diag 135 = diag135 U {j+k} sol[k+1] = j return success = true

edu.red

Pueden encontrar más ejemplos de aplicación de las diferentes técnicas de diseño de algoritmos en el libro de Brassard y Bratley

edu.red

Heurísticas Dado un problema ? , un algoritmo heurístico es un algoritmo que intenta obtener soluciones para el problema que intenta resolver pero no necesariamente lo hace en todos los casos.

Sea ? un problema de optimización, I una instancia del problema, x*(I) el valor óptimo de la función a optimizar en dicha instancia. Un algoritmo heurístico obtiene una solución con un valor que se espera sea cercano a ese óptimo pero no necesariamente el óptimo.

Si H es un algoritmo heurístico para un problema de optimización llamamos xH(I) al valor que devuelve la heurística.

edu.red

Porqué usar algoritmos heurísticos?. En que tipo de problemas? Las heurísticas que son de utilidad práctica son algoritmos polinomiales.

Cuándo decimos que una heurística es "buena"? Cómo hacemos para saber si una heurística es buena?

edu.red

Algoritmos aproximados Decimos que H es un algoritmo e- aproximado para el problema ? si para algún e > 0

?? xH(I) – x*(I) | = e | x*(I) |

O equivalentemente un algoritmo es aproximado si existe ? > 0 tal que para toda instancia I xH(I) / x*(I) = ? (problema de minimización)

Situación ideal, pero poco frecuente

edu.red

Cómo evaluamos una heurística?

Comportamiento medio Análisis probabilístico Comportamiento en peor caso (algoritmos aproximados): i) razón de perfomance en el peor caso : r = sup {xH(I) / x*(I) } ó r = inf {xH(I) / x*(I) } según estemos minimizando o maximizando. ii) error relativo er = | xH(I) – x*(I) | /| x*(I)|

En la práctica no podemos calcular exactamente estos valores pero si a veces obtener cotas para ellos.

edu.red

Ejemplo de algoritmo aproximado Cuando las variables son enteras, el algoritmo goloso que vimos para el problema de la mochila es un algoritmo aproximado.

Se puede demostrar que para toda instancia I de dicho problema se verifica que:

xH(I) / x*(I) ? (c1?b/a1? )/ (c1 (b /a1)) = = ?b/a1? / (b/a1) ? 0.5

(es un problema de maximización)

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente