Análisis y diseño de algoritmos y tipos de datos
Abstract
Este libro está orientado a la enseñanza de la asignatura Análisis y Diseño de Datos y Algoritmos, que es la continuación natural de Fundamentos de Programación. Para abordar el diseño de algoritmos, es necesario tener asimilados los elementos de la programación en algún lenguaje previo; en este sentido es importante conocer el lenguaje Java y sus peculiaridades para seguir el contenido, en el que ocupan un lugar central las técnicas para el diseño de algoritmos iterativos, las técnicas de diseño de algoritmos recursivos, su análisis y las transformaciones de un tipo de algoritmo en otros. Junto al diseño de algoritmos también se abordan el diseño de tipos y el uso de tipos diseñados por otros. Al final, se incluyen ejemplos, muchos de ellos resueltos, de diseños de algoritmos y de diseño de tipos de datos. Este manual es el resultado de la experiencia docente acumulada durante varios años en la Universidad de Sevilla.
Full text
Miguel Toro Bonilla ANÁLISIS Y DISEÑO DE ALGORITMOS Y TIPOS DE DATOS Cubierta
Análisis y diseño de algoritmos y tipos de datos Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Portadilla
Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Página de la colección Colección: ManualesdeInformáticadel InstitutodeIngenieríaInformática DirectordelaColección MiguelToroBonilla.UniversidaddeSevilla ConsejodeRedacción MiguelToroBonilla.UniversidaddeSevilla MarianoGonzálezRomano.UniversidaddeSevilla AndrésJiménezRamírez.UniversidaddeSevilla ComitéCientífico AntónCívitBallcells.UniversidaddeSevilla MaríaJoséEscalonaCuaresma.UniversidaddeSevilla FranciscoHerreraTriguero.UniversidaddeGranada CarlosLeóndeMora.UniversidaddeSevilla AlejandroLinaresBarranco.UniversidaddeSevilla MarioPérezJiménez.UniversidaddeSevilla MarioPiattini.UniversidaddeCastilla-LaMancha ErnestoPimentel.UniversidaddeMálaga JoséRiquelmeSantos.UniversidaddeSevilla AgustínRiscoNúñez.UniversidaddeSevilla NievesRodríguezBrisaboa.UniversidaddeCastilla-LaMancha AntonioRuizCortés.UniversidaddeSevilla JoséLuisSevillanoRamos.UniversidaddeSevilla ErnestTeniente.UniversidadPolitécnicadeCataluña FranciscoTiradoFernádez.UniversidadComplutensedeMadrid
MiguelToroBonilla Análisis y diseño de algoritmos y tipos de datos Sevilla2023 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Portada
Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Página de créditos Colección: ManualesdeInformáticadel InstitutodeIngenieríaInformática Núm.:3 EditorialUniversidaddeSevilla2023 c/Porvenir,27-41013Sevilla. Tlfs.:954487447;954487451;Fax:954487443 Correo electrónico: [email protected] Web: https://editorial.us.es MiguelToro2023 DOI:https://dx.doi.org/10.12795/9788447225064 Maquetación:MiguelToro Diseñodecubiertayediciónelectrónica: refer[email protected] Estaobrasedistribuyeconlalicencia CreativeCommonsAtribución-NoComercial-CompartirIgual4.0Internacional (CCBY-NC-SA4.0) Comitéeditorial: AraceliLópezSerena (DirectoradelaEditorialUniversidaddeSevilla) ElenaLealAbad (Subdirectora) ConcepciónBarreroRodríguez RafaelFernándezChacón MaríaGraciaGarcíaMartín MaríadelPópuloPablo-RomeroGil-Delgado ManuelPadillaCruz MartaPalenque MaríaEugeniaPetit-BreuilhSepúlveda MarinaRamosSerrano José-LeonardoRuizSánchez AntonioTejedorCabrera
7 Índice ÍNDICE 7 ÍNDICE DE FIGURAS 11 NOTACIÓN 12 AGRADECIMIENTOS 14 INTRODUCCIÓN 16 ALGORITMOS ITERATIVOS 21 SECUENCIAS, ITERABLES Y STREAMS 32 IMPLEMENTACIÓN DE SECUENCIAS 33 FACTORÍA DE SECUENCIAS 40 OPERACIONES SOBRE SECUENCIAS 42 ACUMULADORES SECUENCIALES 47 FACTORÍAS DE ACUMULADORES SECUENCIALES 50 All(p) 50 None(p) 53 Any(p) 55 Sum 56 Count 57 First 58 Last 60 Joining 61 Reduce 62 ToList, ToSet, ToMultiset 65 GroupsSize 67 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Índice ÍNDICEDEFIGURAS.................................................................................................................. 11 NOTACIÓN...................................................................................................................................... 12 AGRADECIMIENTOS.................................................................................................................. 14 INTRODUCCIÓN........................................................................................................................... 16 ALGORITMOSITERATIVOS..................................................................................................... 21 SECUENCIAS,ITERABLESYSTREAMS.............................................................................. 32 Implementacióndesecuencias................................................................................. 33 Factoríadesecuencias.................................................................................................. 40 Operacionessobresecuencias.................................................................................. 42 ACUMULADORESSECUENCIALES....................................................................................... 47 Factoríasdeacumuladoressecuenciales.......................................................... 50 All(p)................................................................................................................................ 50 None(p)........................................................................................................................... 53 Any(p).............................................................................................................................. 55 Sum................................................................................................................................... 56 Count................................................................................................................................ 57 First................................................................................................................................... 58 Last.................................................................................................................................... 60 Joining.............................................................................................................................. 61 Reduce............................................................................................................................. 62 ToList,ToSet,ToMultiset.......................................................................................... 65 GroupsSize..................................................................................................................... 67 GroupingList,GroupingSet..................................................................................... 69 GroupingReduce.......................................................................................................... 70 TRANSFORMACIÓNDEALGORITMOSITERATIVOS................................................... 73 Delanotaciónfuncionalalaimperativa......................................................... 73 Delanotaciónimperativaalafuncional......................................................... 74 Delaformaiterativaarecursivafinalyviceversa................................... 80 7
Índice 8 GroupingList, GroupingSet 69 GroupingReduce 70 TRANSFORMACIÓN DE ALGORITMOS ITERATIVOS 73 DE LA NOTACIÓN FUNCIONAL A LA IMPERATIVA 73 DE LA NOTACIÓN IMPERATIVA A LA FUNCIONAL 74 DE LA FORMA ITERATIVA A RECURSIVA FINAL Y VICEVERSA 80 COMPLEJIDAD 85 ÓRDENES DE COMPLEJIDAD 85 Jerarquía de órdenes de complejidad exactos 88 Otros órdenes de complejidad 89 Algunas propiedades de los órdenes de complejidad 90 ECUACIONES EN DIFERENCIAS: RECURRENCIAS LINEALES 91 ECUACIONES RECURRENCIA SOLUBLES POR EL TEOREMA MAESTRO (MASTER THEOREM) 93 SUMATORIOS Y RECURRENCIAS 94 COMPLEJIDAD DE LOS ALGORITMOS 95 Complejidad de los algoritmos iterativos y recursivos sin memoria 96 Complejidad de los algoritmos recursivos con memoria 100 FÓRMULAS DE RESUMEN 101 DISEÑO Y VERIFICACIÓN DE ALGORITMOS ITERATIVOS 105 DISEÑO DE ALGORITMOS ITERATIVOS 105 VERIFICACIÓN DE ALGORITMOS ITERATIVOS 114 ESQUEMAS RECURSIVOS 118 DISEÑO DE ALGORITMOS RECURSIVOS 121 Generalización de un problema 122 Definición de una función de partición 128 Partir de un conjunto de propiedades 134 A partir de una restricción de entrada salida 136 TRANSFORMACIONES RECURSIVO-ITERATIVO EN RECURSIVIDAD SIMPLE 137 TRANSFORMACIÓN RECURSIVO MÚLTIPLE A ITERATIVO 143 RECURSIVIDAD MÚLTIPLE Y ACUMULADORES PARALELOS 147 DISEÑO DE TIPOS: TIPOS DE DATOS RECURSIVOS 156 DISEÑO DE TIPOS 156 ÁRBOLES 159 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla COMPLEJIDAD.............................................................................................................................. 85 Órdenesdecomplejidad............................................................................................... 85 Jerarquíadeórdenesdecomplejidadexactos................................................ 88 Otros órdenes de complejidad.............................................................................. 89 Algunas propiedades de los órdenes de complejidad................................. 90 Ecuacionesendiferencias:recurrenciaslineales...................................... 91 EcuacionesrecurrenciasolublesporelTeoremaMaestro(Master Theorem)............................................................................................................................... 93 Sumatoriosyrecurrencias......................................................................................... 94 Complejidaddelosalgoritmos................................................................................ 95 Complejidaddelosalgoritmositerativosyrecursivossinmemoria... 96 Complejidaddelosalgoritmosrecursivosconmemoria.......................... 100 Fórmulasderesumen..................................................................................................... 101 DISEÑOYVERIFICACIÓNDEALGORITMOSITERATIVOS........................................ 105 Diseñodealgoritmositerativos............................................................................ 105 Verificacióndealgoritmositerativos................................................................ 114 ESQUEMASRECURSIVOS......................................................................................................... 118 Diseñodealgoritmosrecursivos........................................................................... 121 Generalizacióndeunproblema............................................................................ 122 Definicióndeunafuncióndepartición............................................................. 128 Partir de un conjunto de propiedades............................................................... 134 A partir de una restricción de entrada salida................................................. 136 Transformacionesrecursivo-iterativoenrecursividadsimple.......... 137 Transformaciónrecursivomúltipleaiterativo........................................... 143 RECURSIVIDADMÚLTIPLEYACUMULADORESPARALELOS.................................. 147 DISEÑODETIPOS:TIPOSDEDATOSRECURSIVOS..................................................... 156 Diseñodetipos.................................................................................................................. 156 Árboles.................................................................................................................................. 159 Algoritmos sobre árboles........................................................................................ 166 Generalizacionesenalgoritmossobreárboles.............................................. 170 Expresionesyárbolesdesintaxisabstracta.................................................. 173 Algoritmossobreexpresionesyárbolesdesintaxisabstracta............... 176 Patronessobretiposrecursivos............................................................................ 176 Representacióntextualdelostiposrecursivos.......................................... 179 IMPLEMENTACIÓNDETIPOS............................................................................................... 182 8
Índice 9 Algoritmos sobre árboles 166 Generalizaciones en algoritmos sobre árboles 170 EXPRESIONES Y ÁRBOLES DE SINTAXIS ABSTRACTA 173 Algoritmos sobre expresiones y árboles de sintaxis abstracta 176 PATRONES SOBRE TIPOS RECURSIVOS 176 REPRESENTACIÓN TEXTUAL DE LOS TIPOS RECURSIVOS 179 IMPLEMENTACIÓN DE TIPOS 182 GRAFOS 185 TÉRMINOS DE UN GRAFO 186 FORMATOS DE FICHEROS PARA REPRESENTAR GRAFOS Y SU VISUALIZACIÓN 189 VISTAS DE GRAFOS 195 RECUBRIMIENTOS Y COMPONENTES CONEXAS 195 Recubrimiento mínimo 196 Recubrimiento de vértices 197 Componentes conexas 198 Ejemplos 200 COLOREADO DE GRAFOS 201 RECORRIDOS SOBRE GRAFOS 203 Recorrido en anchura 203 Recorrido en profundidad 207 Orden topológico 210 CAMINO MÍNIMO 213 Problema del viajante 214 PROBLEMAS DE COMPLEJIDAD 215 EJEMPLOS DE COMPLEJIDAD DE ALGORITMOS ITERATIVOS 216 EJEMPLOS DE COMPLEJIDAD DE ALGORITMOS RECURSIVOS 223 PROBLEMAS DE ALGORITMOS RECURSIVOS SIMPLES A ITERATIVOS 230 INTRODUCCIÓN 230 ALGUNOS PROBLEMAS SENCILLOS 231 Problemas de lectura de ficheros 235 Comprobar si una lista está ordenada. 238 Encontrar el mayor en una lista ordenada y rotada 240 Problema del palíndromo 241 Índice de un elemento en una secuencia 242 Problema del entero más cercano 246 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla GRAFOS........................................................................................................................................... 185 Términosdeungrafo.................................................................................................... 186 Formatosdeficherospararepresentargrafosysuvisualización... 189 Vistasdegrafos................................................................................................................ 195 Recubrimientosycomponentesconexas............................................................ 195 Recubrimientomínimo............................................................................................ 196 Recubrimientodevértices...................................................................................... 197 Componentesconexas.............................................................................................. 198 Ejemplos......................................................................................................................... 200 Coloreadodegrafos...................................................................................................... 201 Recorridossobregrafos............................................................................................. 203 Recorridoenanchura............................................................................................... 203 Recorridoenprofundidad...................................................................................... 207 Orden topológico........................................................................................................ 210 Caminomínimo.................................................................................................................... 213 Problemadelviajante............................................................................................... 214 PROBLEMASDECOMPLEJIDAD........................................................................................... 215 Ejemplosdecomplejidaddealgoritmositerativos..................................... 216 Ejemplosdecomplejidaddealgoritmosrecursivos.................................... 223 PROBLEMASDEALGORITMOSRECURSIVOSSIMPLESAITERATIVOS.............. 230 Introducción...................................................................................................................... 230 Algunosproblemassencillos................................................................................... 231 Problemasdelecturadeficheros......................................................................... 235 Comprobar si una lista está ordenada............................................................... 238 Encontrarelmayorenunalistaordenadayrotada.................................... 240 Problemadelpalíndromo....................................................................................... 241 Índice de un elemento en una secuencia.......................................................... 242 Problema del entero más cercano....................................................................... 246 Inversióndefuncionesmonótonas..................................................................... 246 Definicionesrecursivasapartirdepropiedades.......................................... 248 Fusión de secuencias ordenadas.......................................................................... 251 Algunosproblemasconocidos.................................................................................. 253 Evaluacióndepolinomios....................................................................................... 253 Problemascondígitosdeunnúmeroentero.................................................. 256 Elproblemadelapotenciaentera....................................................................... 260 PROBLEMASDEALGORITMOSRECURSIVOSMÚLTIPLES....................................... 262 Sumaymultiplicacióndeenterosgrandes...................................................... 262 Problemas de listas.................................................................................................... 265 Subsecuenciadesumamáxima............................................................................ 267 9
16 Introducción n cursos anteriores, estudiamos diferentes tipos de algoritmos para hacer cálculos sobre flujos de datos. Vimos dos estilos de implementar estos algoritmos: el estilo imperativo y el estilo funcional. El estilo imperativo construye los algoritmos mediante tipos de datos (básicos y agregados), sentencias de asignación y las sentencias de control: if, while, for. El estilo funcional obtiene del agregado de datos de partida un flujo de datos, un objeto de tipo Stream<E>, y a este objeto le aplica diferentes operaciones de filtro, transformación y acumulación. Los algoritmos que hemos estudiado, ya en forma imperativa o funcional, eran algoritmos iterativos. Junto con ellos existen algoritmos recursivos. Un algoritmo es recursivo si se llama a sí mismo. Es decir, en un algoritmo recursivo aparece una llamada a sí mismo dentro de su cuerpo. Los algoritmos recursivos son más generales que los iterativos. Como iremos viendo, algunos algoritmos recursivos tienen un equivalente iterativo directo. Otros no. Los algoritmos iterativos en su forma imperativa tienen un equivalente en su forma funcional y viceversa. E Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Introducción
Introducción 17 Veamos un ejemplo para sumar una lista en sus diferentes versiones: Double sumLista(List<Double> list) { Integer i = 0; Double b = 0.; while(i < list.size()){ Double e = list.get(i); i = i+1; b = b + e; } return b; } Como vemos, el anterior es un algoritmo iterativo, no se llama a sumLista en su cuerpo. Está escrito en notación imperativa porque usa sentencias de asignación, while y podría usar if y for. Veamos el mismo algoritmo en notación funcional. Double sumLista(List<Double> ls) { return ls.stream().mapToDouble(x->x).sum(); } Es iterativo porque no llama a sumLista en su cuerpo, pero está escrito en notación funcional: obtiene un flujo de datos, un stream, del agregado, la lista, y aplicando sucesivos métodos obtiene el resultado. Veamos su versión recursiva. Double sumLista(List<Double> list) { return sumLista(list,0,0.); } Double sumLista(List<Double> list, Integer i, Double b) { if(i<list.size()){ Double e = list.get(i); b = sumLista(list,i+1,b+e); } return b; } La versión anterior se compone de dos funciones: la primera llama a la segunda que tiene algunos parámetros adicionales; la segunda función se llama a sí misma dentro de su cuerpo. Es una función recursiva. Vamos a aprender a transformar algoritmos de un estilo a otro cuando eso sea posible. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Introducción 18 En muchos casos los algoritmos, principalmente en los casos recursivos, los escribiremos en forma de esquemas como: 𝑛𝑛𝑛𝑛! = �1, 𝑛𝑛𝑛𝑛= 0 𝑛𝑛𝑛𝑛∗(𝑛𝑛𝑛𝑛−1)!, 𝑛𝑛𝑛𝑛> 0 Que es equivalente a código: Integer f(Integer n) { Integer r; if(n==0){ r = 1; } else { r = n*f(n-1); } return r; } Como podemos ver, un esquema de un algoritmo es un boceto de este. Algunos detalles, el tipo de las variables, por ejemplo, quedan implícitos pero a partir del esquema es fácil escribir el algoritmo en un lenguaje de programación dado. Aquí lo haremos en Java. Los algoritmos recursivos se pueden clasificar en simples y múltiples. Los primeros tienen una sola llamada recursiva dentro de su cuerpo; los segundos, varias llamadas recursivas. A su vez, los algoritmos recursivos simples se clasifican en recursivos finales y recursivos no finales. Un algoritmo recursivo simple es recursivo final si el resultado es igual al de la llamada recursiva sin ninguna operación posterior. En un algoritmo recursivo simple no final el resultado se obtiene aplicando algunas operaciones al valor devuelto por la llamada recursiva. Veamos algunos ejemplos. Algoritmo recursivo final: 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑑𝑑𝑑𝑑(𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏)=�𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏= 0 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑑𝑑𝑑𝑑(𝑏𝑏𝑏𝑏,𝑎𝑎𝑎𝑎%𝑏𝑏𝑏𝑏), 𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏> 0 Algoritmo recursivo simple no final: 𝑛𝑛𝑛𝑛! = �1, 𝑛𝑛𝑛𝑛= 0 𝑛𝑛𝑛𝑛∗(𝑛𝑛𝑛𝑛−1)!, 𝑛𝑛𝑛𝑛> 0 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Introducción 19 Algoritmo recursivo múltiple: 𝑓𝑓𝑓𝑓𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖(𝑛𝑛𝑛𝑛) = �𝑛𝑛𝑛𝑛, 0 ≤𝑛𝑛𝑛𝑛≤1 𝑓𝑓𝑓𝑓𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖(𝑛𝑛𝑛𝑛−1)+𝑓𝑓𝑓𝑓𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖(𝑛𝑛𝑛𝑛−2), 𝑛𝑛𝑛𝑛> 1 En muchos casos, por simplicidad y generalidad del esquema algorítmico, es conveniente compactar varias variables en una tupla y una secuencia de asignaciones en una asignación de tuplas. Dado el ejemplo anterior: Double sumLista(List<Double> list) { Integer i = 0; Double b = 0.; while(i < list.size()){ Double e = list.get(i); i = i+1; b = b + e; } return b; } Podemos escribirlo como Double sumLista(List<Double> list) { (Integer,Double) (i,b) = (0,0.); while(i < list.size()){ (i,b) = (i+1,b+list.get(e)); } return b; } Una secuencia de sentencias de asignación se le llama un bloque básico. Más adelante aprenderemos a transformar bloques básicos en asignaciones de tuplas y viceversa. Un primer detalle que queremos enfatizar es que los algoritmos iterativos, imperativos o funcionales, y los algoritmos recursivos simples finales son equivalentes entre sí en el sentido de que dado un algoritmo en una de las formas podemos encontrar sistemáticamente el algoritmo equivalente en las otras dos. Un segundo detalle importante es que en cualquier algoritmo podemos sustituir los bloques básicos por asignaciones de tuplas lo que nos permitirá disponer de un esquema más compacto del algoritmo. Aprenderemos más adelante como hacerlo Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Introducción 20 Vemos, por tanto, que las tuplas desempeñan un papel muy importante en el diseño de algoritmos. Algunos lenguajes como Python ya proporcionan el tipo tupla. Java no lo proporciona directamente, pero podemos simularlas mediante records, concepto que ya estudiamos en cursos anteriores. Así la declaración y asignación de tuplas siguiente: (Integer,Double) (i,b) = (0,0.); Podemos simularlo por record T(Integer i,Double b){} T t = new T(0,0.); El acceso a las propiedades de la tupla se hace mediante los métodos t.i(), t.b(). Normalmente la declaración del tipo record se complementa de un método de factoría y entonces la asignación de tuplas queda en la forma: record T(Integer i,Double b){ public static T of(Integer i,Double b) { return new T(i,b); } } T t = T.of(0,0.); Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
21 Algoritmos iterativos omo vamos a ver, un algoritmo iterativo y los recursivos simples se pueden pensar como combinaciones de secuencias y acumuladores. Veamos estos conceptos en primer lugar y su relación con los algoritmos. En esta sección vamos a ver los conceptos relacionados con los algoritmos iterativos ly los recursivos simples asociados, su forma general y diversos casos particulares, los mecanismos para transformarlos y la forma de verificarlos y diseñarlos. Veremos la forma clásica, imperativa, de estos algoritmos, en su versión iterativa o recursiva, y su equivalente funcional que es más adecuada en los lenguajes más modernos. Partamos del ejemplo anterior: Double sumLista(List<Double> list) { Integer i = 0; Double b = 0.; while(i < list.size()){ Double e = list.get(i); i = i+1; b = b + e; } return b; } C Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Algoritmositerativos
Algoritmos iterativos 22 Su versión con tuplas Double sumLista(List<Double> list) { (Integer,Double) (i,b) = (0,0.); while(i < list.size()){ (i,b) = (i+1,b+list.get(i)); } return b; } O en su versión recursiva final. Double sumLista(List<Double> list) { return sumLista(0,0.,list); } Double sumLista(Integer i, Double b, List<Double> list) { if(i<list.size()){ b = sumLista(i+1,b+list.get(i),list); } return b; } En la versión recursiva solo hay que tener en cuenta, por ahora, que un algoritmo recursivo es aquel (como sumLista(list,i,b)) que hace una llamada a si mismo dentro de su cuerpo). Podemos observar la relación estrecha entre el algoritmo imperativo en su formato de tuplas y la versión recursiva final. Vemos que la función recursiva tiene todos los parámetros de la tupla más los parámetros de entrada de la función. La llamada a la función se hace con los parámetros de la parte derecha de la asignación de tuplas. El while se ha sustituido por if. El while, en el algoritmo iterativo, representa iteración que se sustituye por el if de la llamada recursiva que indica que se hace una llamada a sí misma mientras que se cumpla la misma condición que para el while. O su versión funcional Double sumListaFunc(List<Double> ls) { return ls.stream() .mapToDouble(e->e) .sum(); } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Algoritmos iterativos 23 Para obtener la versión funcional hemos tenido que darnos cuenta de que existe una secuencia, los elementos de la lista, que podemos obtener mediante el método stream() y un acumulador, en este caso la variable b que se inicializa a cero y va acumulando, sumando en este caso, los sucesivos elementos de la secuencia. Las tres versiones (iterativa, recursiva simple final y funcional) son algoritmos equivalentes en el sentido que producen el mismo resultado cuando se le proporciona la misma entrada. Para poder transformar de una versión a otra debemos encontrar sus elementos comunes: el acumulador y la secuencia. El acumulador viene definido por una variable b, que puede ser una tupla de tipo B, con un valor inicial b0, y una función de acumulación c(b,e). En este caso B es Integer, el valor inicial es 0 y la función de acumulación (b,e)- >b+e. El tipo B puede ser mutable o inmutable. Si el acumulador es mutable la función de acumulación toma forma de método b.c(e). El acumulador acumula los sucesivos valores de la secuencia a partir del valor inicial dado. Cada acumulador tiene un nombre y viene definido por el tipo de acumulador, B, su valor inicial, b0, y la función de acumulación c(b,e). A partir de la versión funcional podemos deducir que el acumulador es un sumador y sus características son Integer, 0, (b,e)->b+e. Esto nos permite completar una parte del algoritmo en su versión imperativa. Otro elemento es la secuencia. En la versión funcional una secuencia se implementa en el lenguaje Java mediante un objeto de tipo Stream<E>. Podemos obtener streams, flujos de datos, de los diferentes agregados de datos mediante métodos adecuados. En el caso de las colecciones este método es stream(). En la versión imperativa no disponemos de stream para representar secuencias. En ese caso usamos un iterador. Un iterador, en Java, es un Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Algoritmos iterativos 24 objeto de tipo Iterator<E> que nos puede proporcionar uno tras otro los objetos de un agregado. En Java el tipo Iterator viene definido como: interface Iterator<E> { boolean hasNext(); E next(); } Un iterador es un objeto mutable que implementa el tipo Iterator<E>. El método hasNext nos indica si hay más elementos. El método next nos da el siguiente elemento, si hay alguno disponible, y actualiza el estado. Los agregados de datos, reales o virtuales, que pueden ser recorridos se dice que son iterables. En Java implementan el tipo Iterable<E> que es de la forma: interface Iterable<E> { Iterator<E> iterator(); } Un iterable es, en definitiva, una factoría de iteradores. Un iterador también puede ser obtenido de un objeto de tipo Stream<E> mediante del método iterator(). Disponiendo de un iterador podemos escribir las formas imperativas del algoritmo de una manera que nos permitirá poder generalizarlo. Double sumLista(List<Double> list) { Iterator<Double> it =list.iterator(); Double b = 0.; while(it.hasNext()){ Double e = it.next(); b = b + e; } return b; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Algoritmos iterativos 25 Java ya aporta una sentencia for para recorrer iterables por lo que el algoritmo anterior se puede escribir: Double sumLista(List<Double> list) { Double b = 0.; for(Integer e: list){ b = b + e; } return b; } La sentencia for, por lo tanto, obtiene un iterador del iterable y de él va obteniendo un elemento tras otro mientras haya elementos. En este epígrafe aprenderemos a encontrar, dada una de las versiones, las otras dos que son equivalentes. Para poder hacerlo debemos encontrar la secuencia y el acumulador asociados al algoritmo. La versión recursivo final usando el iterador se compone de dos funciones. Una primera en cuyo cuerpo se obtiene el iterador y se hace una llamada a una segunda función que tiene como parámetros el acumulador y el iterador. Double sumLista(List<Double> list) { Iterator<Double> it = list.iterator(); return sumLista(it,0.,list); } Double sumLista(Iterator<Double> it,Double b, List<Double> list) { if(it.hasNext()){ Double e = it.next(); b = sumLista(list,it,b+e); } return b; } Vemos, por lo tanto, que disponemos de tres formas equivalentes de escribir algoritmos iterativos: en forma imperativa, en forma funcional y de manera recursivo final. En las tres formas existe un acumulador y una secuencia. La secuencia se puede implementar de forma general mediante un objeto de tipo Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
32 Secuencias, iterables y streams omo ya hemos dicho antes las secuencias son flujos secuenciales de elementos que se pueden recorrer uno tras otro. Es decir, secuencialmente. Las secuencias son elementos abstractos que nos sirven para modelar nuestros algoritmos, pero necesitamos tipos concretos que las implementen. Ya hemos visto dos posibilidades un iterador o un objeto de tipo stream. Tienen los siguientes elementos: • Sus valores son de tipo 𝐸𝐸𝐸𝐸 con valor inicial 𝑒𝑒𝑒𝑒𝑜𝑜𝑜𝑜. • Los sucesivos valores que toma el estado se van obteniendo por la aplicación del operador unario 𝑒𝑒𝑒𝑒→𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛(𝑒𝑒𝑒𝑒). • Un predicado 𝑒𝑒𝑒𝑒→𝑔𝑔𝑔𝑔(𝑒𝑒𝑒𝑒) que indica que la secuencia se extiende mientras 𝑔𝑔𝑔𝑔(𝑒𝑒𝑒𝑒) es verdadero. Si en predicado es de la forma 𝑒𝑒𝑒𝑒→𝑡𝑡𝑡𝑡𝑟𝑟𝑟𝑟𝑡𝑡𝑡𝑡𝑒𝑒𝑒𝑒 estamos definiendo una secuencia infinita. Algunos ejemplos: • Secuencia aritmética entre dos valores a y b con paso c: s = (a, e- >e<b, e->e+c) • Secuencia infinita de números primos: (2, e->true, e->siguientePrimo(e)) La primera conclusión que queremos destacar es: C Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Secuencias,iterablesystreams
Secuencias, iterables y streams 33 Un algoritmo iterativo tiene asociada una secuencia finita definida por 𝑙𝑙𝑙𝑙= (𝑒𝑒𝑒𝑒0,𝑒𝑒𝑒𝑒→𝑔𝑔𝑔𝑔(𝑒𝑒𝑒𝑒),𝑒𝑒𝑒𝑒→𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛(𝑒𝑒𝑒𝑒)). Es importante destacar que un algoritmo, para que lo sea, deber tener asociada una secuencia finita. Y debe ser finita porque el algoritmo, para que lo sea, tiene que acabar. También podemos darnos cuenta de que algunas secuencias pueden ser vacías. No tienen ningún elemento. Ni siquiera el primer elemento indicado pertenece a la secuencia. Ejemplo: s= (10, e-> e < 5, e-> e+1). La descripción anterior de una secuencia se define, como hemos visto, de tres elementos: elemento inicial, un predicado y una función que da el elemento siguiente. Implementación de secuencias Ya hemos visto dos posibilidades: un iterador o un objeto de tipo stream. En Java el tipo Stream<E> representa un flujo de datos general y, junto con la vista secuencial, ofrece otra vista paralela que veremos más adelante. Lo detalles internos de la implementación de streams los veremos más adelante. Por ahora si queremos diseñar un algoritmo en notación funcional usaremos las streams que nos proporciona Java. En la versión imperativa no usamos streams para representar secuencias. En ese caso usamos un iterador. Un iterador, en Java, es un objeto de tipo Iterator<E> que nos puede proporcionar uno tras otro los objetos de un agregado. En Java el tipo Iterator viene definido como: interface Iterator<E> { boolean hasNext(); E next(); } Un iterador es un objeto mutable que implementa el tipo Iterator<E>. El método hasNext nos indica si hay más elementos. El método next nos da el siguiente elemento, si hay alguno disponible, y actualiza el estado. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Implementacióndesecuencias
Secuencias, iterables y streams 34 Los agregados de datos, reales o virtuales, que pueden ser recorridos se dice que son iterables y, en Java implementan el tipo Iterable<E> que es de la forma: interface Iterable<E> { Iterator<E> iterator(); } Un iterable es, en definitiva, una factoría de iteradores. Podemos poner todo junto e implementar el tipo ListIterator<E>. En primer elegimos un estado para el iterador. Este estado se concreta en los atributos privados de la clase que implementa el iterador. En este caso el estado es (i,list) lo que implica que el siguiente elemento devuelto por el iterador es list.get(i). Demos implementar el método de factoría iterator(). class ListIterator<E> implements Iterator<E>, Iterable<E> { public static <E> Iterator<E> of(List<E> list){ return new ListIterator<E>(0, list); } private Integer i; private List<E> list; private ListIterator(Integer i, List<E> list) { this.i = i; this.list = list; } @Override public Iterator<E> iterator() { return new ListIterator<E>(0, list); } … } El siguiente paso es implementar los métodos hasNext() y next(). Con el estado elegido habrá más elementos mientras que I se un índice válido de la lista: i<list.size(). El método next() actualizará el estado y devolverá el siguiente elemento previsto. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Secuencias, iterables y streams 35 @Override public boolean hasNext() { return i < list.size(); } @Override public E next() { E e = list.get(i); i = i + 1; return e; } Se deja como ejercicio implementar un iterador sobre listas que recorre los elementos desde los índices mayores a los menores. Un iterador, en general, se diseña para ocultar los detalles de su estado. Pero hay muchos casos en los que, por alguna razón, queremos hacerlo explícito. En este caso un iterador viene definido por un estado 𝑡𝑡𝑡𝑡 de tipo 𝑇𝑇𝑇𝑇, con valor inicial y tres funciones sin efectos laterales 𝑏𝑏𝑏𝑏𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵 ℎ𝐵𝐵𝐵𝐵𝑙𝑙𝑙𝑙𝑎𝑎𝑎𝑎𝐵𝐵𝐵𝐵𝑒𝑒𝑒𝑒𝑡𝑡𝑡𝑡1(𝑇𝑇𝑇𝑇 𝑡𝑡𝑡𝑡), 𝐸𝐸𝐸𝐸 𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑒𝑒𝑒𝑒𝑡𝑡𝑡𝑡1(𝑇𝑇𝑇𝑇 𝑡𝑡𝑡𝑡), 𝐸𝐸𝐸𝐸 𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑒𝑒𝑒𝑒𝑡𝑡𝑡𝑡2(𝑇𝑇𝑇𝑇 𝑡𝑡𝑡𝑡). Hemos escogido los nombres para que sean similares a los correspondientes métodos de un iterador implementado como un objeto. De forma compacta las representaremos por hn, n1, n2. Por los tanto un iterador podemos caracterizarlo por el tipo del 𝑇𝑇𝑇𝑇 estado, el tipo E de los elementos devueltos y las tres funciones indicadas previamente. Dados T y E un iterador se define de por las funciones: 𝑖𝑖𝑖𝑖𝑡𝑡𝑡𝑡= (𝑡𝑡𝑡𝑡0, 𝑡𝑡𝑡𝑡→ℎ𝐵𝐵𝐵𝐵(𝑡𝑡𝑡𝑡), 𝑡𝑡𝑡𝑡→𝐵𝐵𝐵𝐵𝑒𝑒𝑒𝑒1(𝑡𝑡𝑡𝑡), 𝑡𝑡𝑡𝑡→𝐵𝐵𝐵𝐵𝑒𝑒𝑒𝑒2(𝑡𝑡𝑡𝑡)) Que de forma compacta lo representaremos por 𝑖𝑖𝑖𝑖𝑡𝑡𝑡𝑡= (𝑡𝑡𝑡𝑡0, ℎ𝐵𝐵𝐵𝐵,𝐵𝐵𝐵𝐵𝑒𝑒𝑒𝑒1, 𝐵𝐵𝐵𝐵𝑒𝑒𝑒𝑒2) Que definen, respectivamente el valor inicial del estado, si hay o no más elementos, hasNext1, el siguiente elemento a partir del estado, next1, y el estado siguiente, next2. En el ejemplo anterior del iterador que proporciona los elementos de una lista en orden de sus índices de menor a mayor hemos considerado como Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Secuencias, iterables y streams 36 estado del iterador la tupla (Integer, List<E>). Es el tipo 𝑇𝑇𝑇𝑇. Y las funciones que definen el iterador (0, 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙),(𝑖𝑖𝑖𝑖,𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙)→𝑖𝑖𝑖𝑖<𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙.𝑙𝑙𝑙𝑙𝑖𝑖𝑖𝑖𝑠𝑠𝑠𝑠𝑒𝑒𝑒𝑒(), (𝑖𝑖𝑖𝑖,𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙)→𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙.𝑔𝑔𝑔𝑔𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒(𝑖𝑖𝑖𝑖),(𝑖𝑖𝑖𝑖,𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙)→(𝑖𝑖𝑖𝑖+ 1, 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙) A esta información la llamaremos iterador explícito. El algoritmo iterativo general con iterador implícito es: R alg(x) { Iterator<E> it = it(x); B b = b0; while(it.hasNext()&& !f(b)){ e = it.next(); b = c(b,e); } return r(b); } Un algoritmo que use un iterador implícito, como el anterior, se puede transformar en otro que use un iterador explícito si conocemos la información pertinente (el tipo del estado, su valor inicial, y las funciones hn, nx1, nx2). R alg(x) { T t = it(x); B b = b0; while(hn(t)&& !f(b)){ E e =nx1(t); t = nx2(t); b = c(b,e); } return r(b); } En definitiva hacemos las siguientes sustituciones: • Sustituimos Iterator<E> it por su estado T t en la declaración y en el uso it po t. • Sustituimos it.hasNext() por hn(t). • Sustituimos e = it.next() por la secuencia E e = nx1(t); t = nx2(t); En lo que sigue diseñaremos los algoritmos con iteradores implícitos, pero si tenemos la información adecuada, podemos hacer explícito el iterador Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Secuencias, iterables y streams 37 de forma sistemática. También podemos hacerlo en sentido contrario: implementar un iterador para ocultar el estado. Hay muchos tipos en Java iterables. Es decir que implementan Iterable<E>. Entre ellos tenemos listas, conjuntos, maps, etc. Otros tienen métodos asociados que producen iteradores: ficheros, cadenas, arrays, etc. Un iterador también puede ser obtenido de un objeto de tipo Stream<E> mediante del método iterator(). Disponiendo de un iterador podemos escribir las formas imperativas del algoritmo de una manera que nos permitirá generalizarlo: Double sumLista(List<Double> list) { Iterator<Double> it = list.iterator(); Double b = 0.; while(it.hasNext()){ Double e = it.next(); b = b + e; } return b; } Si hacemos explicito el estado del iterador el esquema anterior se convierte en: Double sumLista(List<Double> list) { Integer i = 0; Double b = 0.; while(i<list.size()){ //hasNext1 Double e = ls.get(i); //next1 (i,ls) = (i+1,ls); //next2 b = b + e; } return b; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Secuencias, iterables y streams 38 Java ya aporta una sentencia for para recorrer iterables por lo que el algoritmo anterior, al ser la lista iterable, se puede escribir: Double sumLista(List<Double> list) { Double b = 0.; for(Integer e: list){ b = b + e; } return b; } Igualmente, la versión recursivo final usando el iterador es: Double sumLista(List<Double> list) { Iterator<Double> it = list.iterator(); return sumLista(it,0.); } Double sumLista(Iterator<Double> it,Double b) { if(it.hasNext()){ Double e = it.next(); b = sumLista(it,b+e); } return b; } Si queremos hacer explícito el estado del iterador incluimos como parámetros las componentes de la tupla que define el estado del iterador además de los parámetros iniciales y otros cálculos útiles. Double sumLista(List<Double> list) { Integer n = list.size(); return sumLista(i,0.,list,n); } Y la función recursiva con todos los parámetros añadidos. Double sumLista(Integer i,Double b,List<Double> list, Integer n) { if(i<n){ //hasNext1 Double e = list.get(i); //next1 i = i+1; //next2 b = sumLista(i,b+e,list,n); } return b; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Secuencias, iterables y streams 39 En muchos casos es necesario conseguir un iterable a partir de un iterator. En Java un iterable se puede conseguir de un Stream<E> o de un Iterator<E> con los métodos siguientes: public static <E> Iterable<E> ofIterator(Iterator<E> it) { return ()->it; } public static <E> Iterable<E> ofStream(Stream<E> stream) { return () -> stream.iterator(); } Por otra parte, un Stream<E> se puede conseguir de un Iterator<E> o de un Iterable<E> con los métodos: public static <E> Stream<E> of(Iterable<E> iterable) { return StreamSupport.stream( Spliterators.spliteratorUnknownSize( iterable.iterator(), Spliterator.ORDERED ), false ); } public static <E> Stream<E> of(Iterator<E> iterator) { return StreamSupport.stream( Spliterators.spliteratorUnknownSize( iterator, Spliterator.ORDERED ), false ); } Tanto los objetos de tipo Iterator<E> como del tipo Stream<E> se consumen una vez que se recorren. Es decir, solo se pueden recorrer una vez. Si necesitamos recorrerlo más de una vez necesitamos un iterable, o una factoría de streams, que nos proporcione un iterador o un stream nuevos cada vez que los necesitemos. En Java todos los agregados iterables tienen un método iterator() que proporciona un Iterator<E>. También disponen de un método que actúa como factoría de streams. Para muchos agregados es el método stream() aunque para otros tiene otro nombre. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Secuencias, iterables y streams 40 En definitiva, implementar una secuencia es desarrollar una clase que implemente Iterator<E>. A partir de un iterador podemos obtener un stream. Más adelante veremos cómo implementar un stream directamente si queremos que el flujo de datos al que está asociada la secuencia pueda verse como secuencial o paralelo. Factoría de secuencias En primer lugar, necesitamos una factoría de secuencias y sus iteradores o streams asociados. Diseñar una factoría de secuencias consiste en definir, e implementar, un conjunto de secuencias iniciales y otras obtenidas a partir de las primeras mediante algunas operaciones. Para definir una secuencia nueva, ya sea inicial o a partir de otra, debemos implementar un iterador y a partir de él (o directamente) obtener un stream. Veamos algunos de ellos junto con sus propiedades y el código iterativo equivalente para producir los mismos elementos de la secuencia. Los iteradores asociados se pueden ver en el repositorio. Rango: Es una secuencia, de enteros o reales, que comienza en a hasta b (b>a) sin incluir. 𝑟𝑟𝑟𝑟𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎(𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏)≡(𝑎𝑎𝑎𝑎,𝑎𝑎𝑎𝑎→𝑎𝑎𝑎𝑎<𝑏𝑏𝑏𝑏,𝑎𝑎𝑎𝑎→𝑎𝑎𝑎𝑎+ 1) Es la secuencia definida en Java por IntStream.range(a,b). El código imperativo correspondiente es: for(int i = a; i<b; i++){ … } Iterate: Es una secuencia general, cuyos elementos son de tipo E, definida por un valor inicial, un predicado y un operador unario. 𝑖𝑖𝑖𝑖𝑡𝑡𝑡𝑡𝑎𝑎𝑎𝑎𝑟𝑟𝑟𝑟𝑎𝑎𝑎𝑎𝑡𝑡𝑡𝑡𝑎𝑎𝑎𝑎(𝑎𝑎𝑎𝑎0, 𝑝𝑝𝑝𝑝,𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛)≡(𝑎𝑎𝑎𝑎0, 𝑎𝑎𝑎𝑎→𝑎𝑎𝑎𝑎(𝑎𝑎𝑎𝑎),𝑎𝑎𝑎𝑎→𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛(𝑎𝑎𝑎𝑎)) Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Factoríadesecuencias
Secuencias, iterables y streams 41 El código imperativo correspondiente es: E e = e0; while(e->g(e)){ e = nx(e); … } Un ejemplo: Stream<Double> iterate(Double a, Double b, Double c){ Double e0 = a; Predicate<Double> g = e->e<b; UnaryOperator<Double> nx = e->e*c; return Stream.iterate(e0,g,nx); } Su equivalente imperativo: Double e = a; while(e<b){ e = e*c; … } Concatenar: Se representa en Java por s3 = Stream.concat(s1,s2) y obtiene otra secuencia con los elementos de s1 seguidos por los de s2. En la forma imperativa tendremos que usar dos for consecutivos: uno para simular cada uno de los streams. Secuencias asociadas a los agregados: Un elemento importarte para hacer posible la abstracción de datos es que los agregados exporten un iterador, o un stream, para poder recorrer los elementos que contienen y ocultar los detalles del estado de este. Es decir los detalles de implementación. Un agregado puede proporcionar varios iteradores para ofrecer distintos recorridos posibles. En la medida que un agregado exporta un iterador se dice que es iterable. Además los agregados ofrecen también un objeto de tipo stream. En Java esto se consigue con el método c.stream() para las colecciones, Files.lines(file) para los ficheros, text.chars() para las cadenas de caracteres, Arrays.stream(a) para los arrays, etc. Junto a los iteradores o streams ofrecidos por un lenguaje en particular podemos implementar Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Acumuladores secuenciales 48 R alg(x) { T t = it(x); B b = b0; while(hn(t)&&!f(b)){ E e = nx1(t); t = nx2(t); b = c(b,e); } return r(b); } Y sin hacer explícito el estado del iterador: R alg(x) { Iterator<E> it = it(x); B b = b0; while(it.hasNext()&& !f(b)){ e = it.next(); b = c(b,e); } return r(b); } Y su equivalente funcional, de forma abstracta, es: R alg(x) { A a = �𝑏𝑏𝑏𝑏0, (𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒)→𝑚𝑚𝑚𝑚(𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒),𝑏𝑏𝑏𝑏→𝑟𝑟𝑟𝑟(𝑏𝑏𝑏𝑏),𝑏𝑏𝑏𝑏→𝑓𝑓𝑓𝑓(𝑏𝑏𝑏𝑏)�; S s = = (() →𝑒𝑒𝑒𝑒0,𝑒𝑒𝑒𝑒→𝑔𝑔𝑔𝑔(𝑒𝑒𝑒𝑒),𝑒𝑒𝑒𝑒→𝑙𝑙𝑙𝑙(𝑒𝑒𝑒𝑒)); R r = s.collect(a); return r; } Como ya hemos comentado en este esquema hay una serie de elementos que definen una secuencia finita, como ya hemos visto, definida por 𝑙𝑙𝑙𝑙= (𝑒𝑒𝑒𝑒0,𝑒𝑒𝑒𝑒→𝑔𝑔𝑔𝑔(𝑒𝑒𝑒𝑒),𝑒𝑒𝑒𝑒→𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛(𝑒𝑒𝑒𝑒)). El resto de los elementos definen un acumulador secuencial. Esencialmente un acumulador secuencial puede ser definido por: 𝑎𝑎𝑎𝑎= (𝑏𝑏𝑏𝑏0, (𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒)→𝑚𝑚𝑚𝑚(𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒),𝑏𝑏𝑏𝑏→𝑟𝑟𝑟𝑟(𝑏𝑏𝑏𝑏),𝑏𝑏𝑏𝑏→𝑓𝑓𝑓𝑓(𝑏𝑏𝑏𝑏)) La forma anterior es la adecuada si el tipo B es inmutable. Si B es mutable la forma del acumulador es: 𝑎𝑎𝑎𝑎= (() →𝑏𝑏𝑏𝑏0, (𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒)→𝑏𝑏𝑏𝑏.𝑚𝑚𝑚𝑚(𝑒𝑒𝑒𝑒), 𝑏𝑏𝑏𝑏→𝑟𝑟𝑟𝑟(𝑏𝑏𝑏𝑏),𝑏𝑏𝑏𝑏→𝑓𝑓𝑓𝑓(𝑏𝑏𝑏𝑏)) Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Acumuladores secuenciales 49 Es decir el valor inicial es de tipo un Supplier<B> en los mutables y de tipo B en los inmutables y la función de combinación de tipo BiConsumer<B,E> en los mutables frente a BiFunction<B,E,B> en los inmutables. En lo que sigue los escribiremos asumiendo que la base del acumulador es inmutable. Si fuera mutable habrá que sustituir b0 por ()->b0 y (b,e)- >c(b,e) por (b,e)->b.c(e). Veamos cada uno de los elementos: • El acumulador tiene un estado, la base del acumulador, de tipo 𝐵𝐵𝐵𝐵 y con valor inicial 𝑏𝑏𝑏𝑏0. El tipo B puede ser mutable o inmutable. • Los elementos 𝑒𝑒𝑒𝑒, de tipo 𝐸𝐸𝐸𝐸, de la secuencia 𝑙𝑙𝑙𝑙 definida previamente se acumulan en la base mediante la función de acumulación (𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒)→ 𝑚𝑚𝑚𝑚(𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒). En principio asumimos que el tipo de la base es inmutable. Si fuera mutable la función de acumulación se convierte en b.c(e) • El algoritmo devuelve, al terminar, el valor de la base del acumulador transformado por la función de retorno 𝑏𝑏𝑏𝑏→𝑟𝑟𝑟𝑟(𝑏𝑏𝑏𝑏). El valor devuelto es del tipo 𝑅𝑅𝑅𝑅. Por lo tanto un acumulador es un tipo genérico basado en los tipos 𝐸𝐸𝐸𝐸,𝐵𝐵𝐵𝐵,𝑅𝑅𝑅𝑅. • El algoritmo puede terminar antes de que la secuencia acabe si se cumple alguna condición sobre la base del acumulador. Esta condición la establece el predicado 𝑏𝑏𝑏𝑏→𝑓𝑓𝑓𝑓(𝑏𝑏𝑏𝑏), que es verdadero si con el valor de la base podemos considerar que el trabajo está terminado y no es necesario seguir. Por similitud con las características de cortocircuito de algunos operadores llamaremos a esta función la función de cortocircuito del acumulador. • Hay muchos acumuladores, que llamaremos simples, donde se cumple que la función de retorno es la función identidad y la función de cortocircuito devuelve siempre false. En este caso sólo indicaremos los dos primeros elementos del acumulador. Es decir 𝑎𝑎𝑎𝑎= (() → 𝑏𝑏𝑏𝑏0, (𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒)→𝑚𝑚𝑚𝑚(𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒)) Como vemos un acumulador se define mediante un un valor inicial (o un supplier si la base es mutable), una bifunction como función de acumulación (o un consumer si la base del acumulador es mutable), una function para definir el retorno y un predicate para definir la función de cortocircuito. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Acumuladores secuenciales 50 Factorías de acumuladores secuenciales Un acumulador de tipo A viene definido por el tipo de los elementos a acumular E, el tipo de la base B, y el tipo de retorno R, más el valor inicial de la base y el resto de las funciones comentadas. 𝐴𝐴𝐴𝐴=(𝐸𝐸𝐸𝐸,𝐵𝐵𝐵𝐵,𝑅𝑅𝑅𝑅),𝑎𝑎𝑎𝑎= (𝑏𝑏𝑏𝑏0, (𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒)→𝑚𝑚𝑚𝑚(𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒),𝑏𝑏𝑏𝑏→𝑟𝑟𝑟𝑟(𝑏𝑏𝑏𝑏),𝑏𝑏𝑏𝑏→𝑓𝑓𝑓𝑓𝑛𝑛𝑛𝑛(𝑏𝑏𝑏𝑏)) Definir un acumulador es concretar todos sus detalles. Es conveniente disponer de una factoría de acumuladores secuenciales. Cada acumulador vendrá definido por todas sus propiedades o por una versión reducida. En la versión reducida asumimos que 𝑟𝑟𝑟𝑟(𝑏𝑏𝑏𝑏)=𝑏𝑏𝑏𝑏,𝑓𝑓𝑓𝑓(𝑏𝑏𝑏𝑏)=𝑓𝑓𝑓𝑓𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑒𝑒𝑒𝑒. Una factoría de acumuladores secuenciales dispondrá de métodos adecuados para crear los acumuladores más usados. En Java se dispone de la factoría Collectors. Pero los acumuladores creados por ella son, a la vez, paralelos y secuenciales, por lo que los veremos más adelante. Es conveniente conocer un catálogo de acumuladores. Un conjunto de acumuladores conocidos se muestra a continuación. Para cada acumulador se muestra un algoritmo iterativo que acumula una secuencia con ese acumulador. Mostramos el algoritmo en sus formas imperativa, recursiva final y funcional. All(p) All(p): 𝐵𝐵𝐵𝐵=𝑅𝑅𝑅𝑅=𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑎𝑎𝑎𝑎𝑒𝑒𝑒𝑒𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛,𝑎𝑎𝑎𝑎= (𝑡𝑡𝑡𝑡𝑟𝑟𝑟𝑟𝑡𝑡𝑡𝑡𝑒𝑒𝑒𝑒, (𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒)→𝑝𝑝𝑝𝑝(𝑒𝑒𝑒𝑒),𝑏𝑏𝑏𝑏 →𝑏𝑏𝑏𝑏,𝑏𝑏𝑏𝑏 →!𝑏𝑏𝑏𝑏) Este acumulador devuelve true si el predicado es verdadero al ser aplicado a cada elemento de la secuencia. El esquema iterativo, funcional e imperativo, con este acumulador es: Boolean all(X x, Predicate<E> p) { Steam<E> st = st(x); return st.allMatch(p); } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Factoríasdeacumuladoressecuenciales All(p)
Acumuladores secuenciales 51 Boolean all(X x, Predicate<E> p) { Iterator<E> it = it(x); Boolean b = true; while(it.hasNext()&& b){ E e = it.next(); b = p(e); } return b; } La version recursiva final: Boolean all(X x, Predicate<E> p) { Iterator<E> it = it(x); Boolean b = true; b = all(it,b,p); return b; } Boolean all(Iterator<E> it, Boolean b, Predicate<E> p){ if(it.hasNext()&& b){ E e = it.next(); b = p(e); b = all(it,b,p); } return b; } 1. Diseñar una función que compruebe si todos los elementos de una secuencia son iguales La idea es comprobar que se verifica que todos los elementos son iguales al primero. El primero, sin consumir la secuencia, lo podemos obtener con la función peek. <E> Boolean allEquals(Stream<E> st) { MutableType<E> first = MutableType.of(null); return st.peek(e->{if(first.value()==null) first.setValue(e);}) .allMatch(e->e.equals(first.value())); } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Acumuladores secuenciales 52 Esta función allEquals es muy útil para resolver problemas. La versión imperativa podemos obtenerla teniendo en cuenta el esquema para allMatch anterior y ampliando el estado del algoritmo con la variable que guarda el primer elemento. Boolean allEquals(Iterable<E> st) { Iterator<E> it = st.iterator(); Boolean b = true; E first = null; while(it.hasNext()&& b){ E e = it.next(); if(first == null) first = e; b = e.equals(first); } return b; } 2. Decidir si los enteros de una secuencia forman una progresión aritmética. La solución de este problema usa el ejercicio anterior. La secuencia es aritmética si formada la secuencia de diferencias entre elementos consecutivos todos los elementos son iguales. Boolean esAritmetica(Stream<Integer> st) { Stream<Integer> stc = Stream2.consecutivePairs(st) .map(p->p.second()-p.first()); return Stream2.allEquals(stc); } La versión imperativa se puede conseguir escogiendo un estado del algoritmo que incluya el elemento anterior y el primer elemento tal como se hace en las funciones consecutivePairs y allEquals. Además, usar es esquema del acumulador all. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Acumuladores secuenciales 53 Boolean esAritmetica(Iterable<Integer> iterable) { Iterator<Integer> it = iterable.iterator(); Integer last,e; if(it.hasNext()) e = it.next(); else return true; Boolean b = true; Integer r = null; while(it.hasNext() && b){ last = e; e = it.next(); if(r == null) r = e-last; b = e-last == r; } return b; } None(p) None(p): 𝐵𝐵𝐵𝐵=𝑅𝑅𝑅𝑅𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵,𝐵𝐵𝐵𝐵= (𝑓𝑓𝑓𝑓𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑎𝑎𝑎𝑎𝐵𝐵𝐵𝐵, (𝑏𝑏𝑏𝑏,𝐵𝐵𝐵𝐵)→𝑝𝑝𝑝𝑝(𝐵𝐵𝐵𝐵),𝑏𝑏𝑏𝑏 →!𝑏𝑏𝑏𝑏,𝑏𝑏𝑏𝑏 →𝑏𝑏𝑏𝑏) Este acumulador devuelve true si el predicado es falso al ser aplicado a cada elemento de la secuencia. El esquema iterativo con este acumulador es: Boolean none1(X x, Predicate<E> p) { Iterator<E> it = it(x); Boolean b = false; while(it.hasNext()&& !b){ e = it.next(); b = p(e); } return !b; } Boolean none2(X x, Predicate<E> p) { Iterator<E> it = it(x); Boolean b = false; b = none(it,b,p); return !b; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla None(p)
Acumuladores secuenciales 54 Boolean none2(Iterator<E> it, Boolean b, Predicate<E> p){ if(it.hasNext()&& !b){ E e = it.next(); b = p(e); b = alg(it,b,p); } return b; } Boolean none3(X x, Predicate<E> p) { Steam<E> st = st(x); return st.noneMatch(p); } 3. Decidir si un número es primo Un número 𝑛𝑛𝑛𝑛 es primo si no es divisible por ningún número entero en el rango [2, √𝑛𝑛𝑛𝑛]. Vemos que una secuencia adecuada es la que recorre los valores 2 … √𝑛𝑛𝑛𝑛 y el acumulador none con el predicado esDivisible. Esta secuencia y este acumulador se pueden definir como: 𝑙𝑙𝑙𝑙= (2, 𝑒𝑒𝑒𝑒→𝑒𝑒𝑒𝑒≤√𝑛𝑛𝑛𝑛,𝑒𝑒𝑒𝑒→𝑒𝑒𝑒𝑒+ 1) 𝐵𝐵𝐵𝐵=𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑙𝑙𝑙𝑙𝑒𝑒𝑒𝑒𝑙𝑙𝑙𝑙𝑛𝑛𝑛𝑛,𝑙𝑙𝑙𝑙= (𝑓𝑓𝑓𝑓𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑒𝑒𝑒𝑒, (𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒)→𝑝𝑝𝑝𝑝(𝑒𝑒𝑒𝑒),𝑏𝑏𝑏𝑏 →!𝑏𝑏𝑏𝑏,𝑏𝑏𝑏𝑏 →𝑏𝑏𝑏𝑏) 𝑝𝑝𝑝𝑝(𝑒𝑒𝑒𝑒)=𝑀𝑀𝑀𝑀𝑙𝑙𝑙𝑙𝑎𝑎𝑎𝑎ℎ2. 𝑒𝑒𝑒𝑒𝑙𝑙𝑙𝑙𝑒𝑒𝑒𝑒𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑙𝑙𝑙𝑙𝑖𝑖𝑖𝑖𝑏𝑏𝑏𝑏𝑙𝑙𝑙𝑙𝑒𝑒𝑒𝑒(𝑛𝑛𝑛𝑛,𝑒𝑒𝑒𝑒) La secuencia puede ser implementada con un iterador con estado formado por un entero que se va incrementando de uno en uno. A partir de ahí podemos obtener la versión funcional, imperativa, recursiva final siguiendo los pasos genéricos anteriores. boolean esPrimo1(Long n){ Long sqrt = (long)Math.sqrt((double)n); return LongStream.rangeClosed(2, sqrt) .noneMatch(x->Math2.esDivisible(n, x)); } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Acumuladores secuenciales 55 boolean esPrimo2(Long n){ Long sqrt = (long)Math.sqrt((double)n); Long e = 2L; Boolean b = false; while(e <= sqrt && !b){ b = Math2.esDivisible(n, e); e = e + 1; } return !b; } boolean esPrimo3(Long n){ Long sqrt = (long)Math.sqrt((double)n); Long e = 2L; Boolean b = false; return !esPrimo3(n,sqrt,e,b); } boolean esPrimo3(Long n, Long sqrt, Long e, Boolean b){ if(e <= sqrt && !b){ b = esPrimo3(n,sqrt,e+1,Math2.esDivisible(n, e)); } return b; } Any(p) Any(p): 𝐵𝐵𝐵𝐵=𝑅𝑅𝑅𝑅=𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙,𝑙𝑙𝑙𝑙= (𝑓𝑓𝑓𝑓𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑎𝑎𝑎𝑎𝑙𝑙𝑙𝑙, (𝑏𝑏𝑏𝑏,𝑙𝑙𝑙𝑙)→𝑝𝑝𝑝𝑝(𝑙𝑙𝑙𝑙),𝑏𝑏𝑏𝑏 →𝑏𝑏𝑏𝑏,𝑏𝑏𝑏𝑏 →𝑏𝑏𝑏𝑏) Este acumulador devuelve true si el predicado es verdadero al ser aplicado a algún elemento de la secuencia. El esquema funcional y el imperativo con este acumulador son: Boolean any1(X x, Predicate<E> p) { Stream<E> st = st(x); return st.anyMatch(p); } Boolean any2(X x, Predicate<E> p) { Iterator<E> it = it(x); Boolean b = false; while(it.hasNext()&& !b){ e = it.next(); b = p(e); } return b; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Any(p)
Acumuladores secuenciales 56 La version recursive final Boolean any3(X x, Predicate<E> p) { Iterator<E> it = it(x); Boolean b = true; b = alg(it,b); return b; } Boolean any3(Iterator<E> it, Boolean b, Predicate<E> p){ if(it.hasNext()&& !b){ E e = it.next(); b = p(e); b = any(it,b,p); } return b; } Sum Sum(): 𝐵𝐵𝐵𝐵=𝑅𝑅𝑅𝑅=𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎,𝑎𝑎𝑎𝑎= (0, (𝑎𝑎𝑎𝑎,𝑎𝑎𝑎𝑎)→𝑎𝑎𝑎𝑎+𝑎𝑎𝑎𝑎) Este acumulador devuelve la suma de los elementos de la secuencia. Las diferentes versiones del esquema iterativo con este acumulador son: Double sum(X x) { Stream<E> st = st(x); return st.mapToDouble(e->e).sum(); } Double sum(X x) { Iterator<E> it = it(x); Double b = 0.; while(it.hasNext()){ e = it.next(); b = b+e; } return b; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Sum
Acumuladores secuenciales 57 Double sum alg(X x) { Iterator<Double> it = it(x); Double b = 0.; b = sum(it,b); return b; } Boolean sum(Iterator<Double> it, Double b){ if(it.hasNext()){ Double e = it.next(); b = b+e; b = sum(it,b); } return b; } Count Count(): 𝐵𝐵𝐵𝐵=𝑅𝑅𝑅𝑅=𝐼𝐼𝐼𝐼𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛,𝑎𝑎𝑎𝑎= (0, (𝑏𝑏𝑏𝑏,𝑛𝑛𝑛𝑛)→𝑏𝑏𝑏𝑏+ 1) Este acumulador devuelve el número de elementos de la secuencia. Las diferentes versiones del esquema iterativo con este acumulador son: Long count1(X x) { Steam<E> st = st(x); return st.count(); } Long count2(X x) { Iterator<E> it = it(x); Long b = 0L; while(it.hasNext()){ e = it.next(); b = b+1; } return b; } Long count3(X x) { Iterator<E> it = it(x); Long b = 0L; b = count(it,b); return b; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Count
Acumuladores secuenciales 64 Optional<E> reduce2(X x, BinaryOperator<E> op) { Iterator<E> it = it(x); B b = null; b = alg(it,b,op); return Optional.ofNullable(b); } B reduce2(Iterator<E> it, B b, BinaryOperator<B> op){ if(it.hasNext()){ E e = it.next(); if(b==null) b = e; else b = op(b,e); b = reduce2(it,b,op); } return b; } Casos particulares de este reduce son los acumuladores min y max escogiendo como operadores binarios min(a,b) o max(a,b). La tercera versión transforma el elemento de entrada antes de acumularlo. B reduce0(X x, Function<E,B> f, BinaryOperator<B> op, E b0) { Stream<E> st = st(x); return st.collect(Collectors.reduce(b0,f,op)); } Dejamos como ejercicio los esquemas imperativos y recursivos finales de ambas versiones. Las versiones recursiva final y funcional de esta variante se dejan como ejercicio. Un caso aún más general es un reduce que incluya la función de cortocircuito B reduce(X x, B b0, Function<E,B> f, BinaryOperator<B> op, Predicate<B> p) { Iterator<E> it = it(x); B b = b0; while(it.hasNext() && !p(b)){ e = it.next(); b = op(b,f(e)); } return b; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Acumuladores secuenciales 65 Casos particulares de este último son all, any, none, findFirst, etc. Las versiones recursiva final y funcional de este último se dejan como ejercicio. 6. Obtener un String con lo primeros de caracteres de una lista de String public static String ts(List<String> ls) { return ls.stream() .collect(Collectors.reducing("", s->s.substring(0, 1),(x,y)->x+y)); } Las versiones imperativa y recursiva final quedan como ejercicio. Pueden hacerse siguiendo los esquemas anteriores. ToList, ToSet, ToMultiset ToList: B=R=List<E> ToSet: B=R=Set<E> ToMultiset: B=R=Multiset<E> Este acumulador devuelve los elementos de la secuencia en una lista. El esquema ToSet y ToMultiset son similares, pero sustituyendo la lista por un conjunto o un Mmultiset. Al acumular los elementos de un agregado en un conjunto podemos encontrar los elementos distintos que hay en el iterable. Al acumular en un Multiset obtenemos la frecuencia de cada elemento. El esquema iterativo en su versión funcional es; List<E> toList(X x) { Stream<E> st = st(x); return st.toList(); } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla ToList,ToSet,ToMultiset
Acumuladores secuenciales 66 La versión imperativa; List<E> toList(X x) { Iterator<E> it = it(x); List<E> b = new ArrayList<>(); while(it.hasNext()){ e = it.next(); b.add(e); } return b; } Y la version recursive final: List<E> toList(X x) { Iterator<E> it = it(x); List<E> b = new ArrayList<>(); b = alg(it,b); return b; } List<E> toList(Iterator<E> it, List<E> b){ if(it.hasNext()){ E e = it.next(); b.add(e); b = toList(it,b); } return b; } 7. Diseñar una función que indique si todos los elementos de un iterable son diferentes Esta acumulación se puede conseguir acumulando en un conjunto y a la vez contando los elementos. Los elementos serán diferentes si el número Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Acumuladores secuenciales 67 de elementos en el conjunto es igual al número de elementos contados. La versión imperativa es: Boolean allDifferents(X x) { Iterator<E> it = it(x); Integer n = 0; Set<E> b = new HashSet<>(); while(it.hasNext()){ e = it.next(); b.add(e); n = n+1; } return n==b.size(); } 8. Encontrar las veces que aparece cada elemento en un iterable Si agrupamos el iterable en un multiset obtenemos las frecuencias Multiset frecuencias(X x) { Iterator<E> it = it(x); Multiset<E> b = Multiset.empty(); while(it.hasNext()){ e = it.next(); b.add(e); } return b; } GroupsSize GroupsSize(key): key: 𝐸𝐸𝐸𝐸→𝐾𝐾𝐾𝐾, B=R=Map<K,Integer> Este acumulador devuelve el número de elementos en cada uno de los grupos de los elementos definidos por la función key. El esquema en su versión funcional es: Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla GroupsSize
Acumuladores secuenciales 68 Map<K,Integer> groupsSize1(X x, Function<E,K> key) { Stream<E> st = st(x); return st.collect( Collectors.groupingBy(key, Collectors.collectingAndThen( Collectors.counting(),Long::intValue))); } La versión recursiva final Map<K,Integer> groupsSize3(X x, Function<E,K> key) { Iterator<E> it = it(x); Map<K,Integer> b = HashMap<>(); b = GroupsSize3(it,b); return b; } Map<K,Integer> groupsSize3(Iterator<E> it,Map<K,Integer> b){ if(it.hasNext()){ e = it.next(); K k = key(e); if(b.containsKey(k)) b.put(k,b.get(k)+1); else b.put(k, 1); b = GroupsSize3(it,b); } return b; } La versión imperativa es: Map<K,Integer> GroupsSize2(X x, Function<E,K> key) { Iterator<E> it = it(x); Map<E,Integer> b = HashMap<>(); while(it.hasNext()){ e = it.next(); K k = key(e); if(b.containsKey(k)){ b.put(k,b.get(k)+1); else b.put(k, 1); } return b; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Acumuladores secuenciales 69 9. Dado un iterable de ciudades encontrar el número de ellas en cada provincia Siendo el tipo Ciudad record Ciudad(String nombre, String provincia) { public static Ciudad of(String nombre, String provincia){ return new Ciudad(nombre, provincia); } } List<Ciudad> = … Map<String,Integer> m = groupsSize(ls.stream(),c->c.provincia()); GroupingList, GroupingSet GroupingList(key): key: 𝐸𝐸𝐸𝐸→𝐾𝐾𝐾𝐾, B = R = Map<K,List<E>>. GroupingSet(key): key: 𝐸𝐸𝐸𝐸→𝐾𝐾𝐾𝐾, B = R = Map<K,Set<E>>. Este acumulador devuelve grupos en forma de listas de elementos de la secuencia definidos por la función key. El esquema GroupingSet es similar y forma un conjunto por grupo. El esquema en su versión funcional e imperativa es; Map<K,Integer> groupingList(X x, Function<E,K> key) { Stream<E> st = st(x); return st.collect(Collectors.groupingBy(key)); } Map<K,List<E>> groupingList(X x, Function<E,K> key) { Iterator<E> it = it(x); Map<K,List<E>> b = HashMap<>(); while(it.hasNext()){ e = it.next(); K k = key(e); if(b.containsKey(k)) b.get(k).add(e); else { List<E> ls = new ArraList<>(); ls.add(e) b.put(e,ls); } } return b; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla GroupingList,GroupingSet
Acumuladores secuenciales 70 Y en su versión recursivo final: Map<K,List<E> groupingList(X x, Function<E,K> key) { Iterator<E> it = it(x); Map<K,List<E>> b = HashMap<>(); b = alg(it,b); return b; } Map<K,List<E>> groupingList(Iterator<E> it, Map<K,List<E>> b){ if(it.hasNext()){ e = it.next(); K k = key(e); if(b.containsKey(k)) b.get(k).add(e); else { List<E> ls = new ArraList<>(); ls.add(e) b.put(e,ls); } b = groupingList(it,b); } return b; } GroupingReduce GroupingReduce(key,f,op,v0): B = R = Map<K,V> Este acumulador forma grupos con los elementos de la secuencia definidos por la función key. Posteriormente acumula cada grupo mediante una reducción con transformación. La versión funcional es: Map<K,R> groupingReduce1(X x, Function<E,K> key, Function<E,R> f,BinaryOperator<R> op){ Stream<E> st = st(x); return st.collect(Collectors.groupingBy(key, Collectors.mapping(f, Collectors.collectingAndThen( Collectors.reducing(op), g->g.get())))); } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla GroupingReduce
Acumuladores secuenciales 71 La versión imperativa. Map<K,R> groupingReduce2(X x, Function<E,K> key, Function<E,R> f, BinaryOperator<R> op){ Iterator<E> it = it(x); Map<K,R> b = new HashMap<>(); while(it.hasNext()){ E e = it.next(); K k = key.apply(e); R r = f.apply(e); if(b.containsKey(k)) b.put(k,op.apply(b.get(k),r)); else b.put(k,r); } return b; } La recursive final: Map<K,R> groupingReduce3(X x, Function<E,K> key, Function<E,R> f,BinaryOperator<R> op){ Iterator<E> it = it(x); Map<K,R> b = HashMap<>(); b = groupingReduce(it,b); return b; } Map<K,R> groupingReduce3(Iterator<E> it, Function<E,K> key, Function<E,R>f, BinaryOperator<R>){ if(it.hasNext()){ e = it.next(); K k = key.apply (e); R r = f.apply (e); if(b.containsKey(k)) b.put(k,op.apply(b.get(k),r); else b.put(k,r); b = groupingReduce(it,b); } return b; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Acumuladores secuenciales 72 10. Dado un iterable de personas encontrar los de mayor edad para cada nombre Sea el tipo Persona definido por el record record Persona(String nombre, Integer edad) { public static Persona of(String nombre, Integer edad) { return new Persona(nombre,edad); } } El objetivo es agrupar a las personas por su nombre y encontrar el máximo para cada grupo según la edad. Es un caso concreto de GroupsReduce con la clave el nombre y la operación de reducción obtenida aplicando el operador binario mínimo para la propiedad edad. List<Persona> ls = … Map<String,Integer> m = groupingReduce(ls.stream(), p->p.nombre(),p->p.edad(), BinaryOperator.maxBy(Comparator.naturalOrder())); Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
73 Transformación de algoritmos iterativos omo hemos estado viendo hay tres formas de representar un algoritmo iterativo: imperativa, funcional o recursiva final. Veamos como transformar de una a otra, De la notación funcional a la imperativa Como hemos visto existe una fuerte correlación entre la notación funcional y la imperativa de los tipos de algoritmos iterativos que estamos viendo aquí. Veamos cómo transformarlas de una a otra. Ya sea en un sentido o en otro se trata de identificar la secuencia y el acumulador y a partir de aquí escribir el algoritmo. Si partimos de la notación funcional la identificación de la secuencia y el acumulador suele ser sencilla. A partir de este paso y de las equivalencias de la sección anterior podemos escribir el algoritmo imperativo. Veamos el siguiente ejemplo. C Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Transformacióndealgoritmositerativos Delanotaciónfuncionalalaimperativa
Transformación de algoritmos iterativos 80 Un algoritmo iterativo imperativo normalizado tiene la forma: R alg(x) { E e = e0(x); while(g(e)){ e = nx(e); } return r(e); } Al e lo llamamos estado del algoritmo. Donde e puede ser una tupla, s, r funciones sobre tuplas y g un predicado sobre tuplas. El equivalente funcional del anterior algoritmo imperativo normalizado es R alg(x) { E e = Stream.iterate(e0(x),x->nx(x)) .filter(x->!g(x)) .findFirst() .get(); return r(e); } En muchos casos es posible separar la tupla en dos partes: acumulador y secuencia. Cuando esto es posible hacemos explícito el acumulador y la secuencia el algoritmo normalizado queda: R alg(x) { E e = e0(x); B b = b0(x); while(g(e)){ b = c(b,e); e = nx(e); } return r(b,e); } De la forma iterativa a recursiva final y viceversa Los algoritmos iterativos tienen siempre algoritmos equivalentes recursivos finales. Aquí mostramos la equivalencia junto a la notación funcional. Como vemos para hacer la transformación es necesario identificar claramente la secuencia, es decir el iterador y el acumulador. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Delaformaiterativaarecursivafinalyviceversa
Transformación de algoritmos iterativos 81 𝑆𝑆𝑆𝑆 𝑙𝑙𝑙𝑙= (𝑒𝑒𝑒𝑒0,𝑒𝑒𝑒𝑒→𝑔𝑔𝑔𝑔(𝑒𝑒𝑒𝑒),𝑒𝑒𝑒𝑒→𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛(𝑒𝑒𝑒𝑒)) 𝐴𝐴𝐴𝐴 𝑎𝑎𝑎𝑎= (𝑏𝑏𝑏𝑏0, (𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒)→𝑚𝑚𝑚𝑚(𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒),𝑏𝑏𝑏𝑏→𝑟𝑟𝑟𝑟(𝑏𝑏𝑏𝑏),𝑏𝑏𝑏𝑏→𝑑𝑑𝑑𝑑(𝑏𝑏𝑏𝑏)) Por simplificar la presentación de los esquemas siguientes consideramos que s y a vienen dados. Como ya hemos dicho una secuencia la podemos implementar mediante un iterador o un stream. Asumimos que tenemos un iterador que implementa la secuencia y también un stream. Podemos obtener ambos de los parámetros iniciales del problema con las funciones it(x) e st(x) que nos dan, respectivamente un iterador y un stream en su estado inicial. Como ya comentamos un iterador viene definido por un estado de tipo T, un valor inicial t0 y las funciones hn, next1, next2 que ya hemos estudiado y que tienen una fuerte relación con las que definen la secuencia. 𝐼𝐼𝐼𝐼𝑡𝑡𝑡𝑡 𝑖𝑖𝑖𝑖𝑡𝑡𝑡𝑡= (() →𝑡𝑡𝑡𝑡0, 𝑡𝑡𝑡𝑡→ℎ𝑛𝑛𝑛𝑛(𝑡𝑡𝑡𝑡), 𝑡𝑡𝑡𝑡→𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛1(𝑡𝑡𝑡𝑡), 𝑡𝑡𝑡𝑡→𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛2(𝑡𝑡𝑡𝑡)) Haciendo explícito el estado del acumulador tenemos, como ya hemos visto, equivalencias que nos permiten, si hemos identificado la secuencia y el acumulador, obtener las equivalencias imperativas y recursivo final a partir de un algoritmo en notación funcional. La versión imperativa R alg(X x) { T t = it(x); B b = b0; while(hn(t)&&!f(b)){ E e = nx1(t); t = nx2(t); b = c(b,e); // Si t e mutable b.c(e) } return r(s(t,b)); } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Transformación de algoritmos iterativos 82 La versión recursivo final R alg(X x) { T t = it(x); B b = b0; B b = alg(t,b); return r(b); } B alg(T t,B b) { if(hn(t)&&!f(b)){ E e = nx1(t); t = nx2(t); b = c(b,e); // Si t e mutable b.c(e) b = alg(t,b); } else { b = s(t,b); //En muchos casos s(t,b) = b } return b; } La versión funcional R alg(X x) { Stream<E> st = st(x); return s.collect(a); } El proceso anterior de combinar una secuencia con un acumulador se le denomina acumulación como hemos comentamos arriba. Esta acumulación la llamamos acumulación por la izquierda. Si el acumulador es uno de reducción, ya visto, lo llamaremos reducción por la izquierda. Los esquemas anteriores nos permiten pasar de versiones imperativas de los algoritmos a otras funcionales o recursivas finales o viceversa. Como ejemplo veamos el algoritmo para calcular el máximo común divisor: 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑑𝑑𝑑𝑑(𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏)=�𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏= 0 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑑𝑑𝑑𝑑(𝑏𝑏𝑏𝑏,𝑎𝑎𝑎𝑎%𝑏𝑏𝑏𝑏), 𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏> 0 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Transformación de algoritmos iterativos 83 El esquema tiene el equivalente en código Integer mcd(a,b) { R r = a; if(b>0) r = mcd(b,a%b); return r; } Es recursivo final y por lo tanto admite la versión iterativa equivalente. Integer mcd(a,b) { while(b > 0){ (a,b) = (b,a%b) } return a; } En este caso el estado del iterador es de tipo (Integer,Integer) con valor inicial (a,b), la función de guarda es 𝑔𝑔𝑔𝑔(𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏)≡𝑏𝑏𝑏𝑏> 0, la función siguiente 𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛(𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏)≡(𝑏𝑏𝑏𝑏,𝑎𝑎𝑎𝑎%𝑏𝑏𝑏𝑏) y la función de retorno 𝑟𝑟𝑟𝑟(𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏)≡𝑎𝑎𝑎𝑎. Ahora tenemos que convertir la asignación de tuplas a un bloque básico. Según lo explicado introducimos las dos variables a1, b1 y posteriormente eliminamos a1 de la siguiente manera: a1 = b; b1 = a%b; a = b1; b = a1; _____ a1 = a; a = a%b; b = a1; En las transformaciones anteriores hemos usado las equivalencias entre asignación de tuplas a una secuencia de asignaciones y posteriormente las reglas para simplificar un bloque básico. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Transformación de algoritmos iterativos 84 Quedando el algoritmo: Integer mcd(a,b) { while(b > 0){ a1 = b; b = a%b; a = a1; } return a; } La versión funcional usa la tupla: record Tm(Integer a, Integer b){ public static Tm of(Integer a, Integer b){ return new Tm(a,b); } } Integer mcd(Integer a, Integer b) { Stream<Tm> st = Stream.iterate(Tm.of(a,b), t->Tm.of(t.b(),t.a()%t.b())); Tm tr = st.filter(t->t.b()<=0).findFirst().get(); return tr.a(); } En las transformaciones anteriores hemos usado las equivalencias entre la versión recursiva final y la iterativa usando tuplas y posteriormente la equivalencia de la asignación de tuplas a una secuencia de asignaciones. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
85 Complejidad uando diseñamos algoritmos es necesario demostrar en primer lugar que acaba y hacen el cometido especificado. Pero en segundo lugar es conveniente estimar el tiempo que tardará en ejecutarse en función del tamaño del problema a resolver. El análisis de la complejidad de los algoritmos trata de hacer esa estimación y es lo que vamos a estudiar en este capítulo. En primer lugar vamos a introducir un conjunto de conceptos y herramientas necesarias para el estudio de la complejidad de un algoritmo. Órdenes de complejidad En general estamos interesados en el tiempo de ejecución como una función del tamaño del problema cuando el tamaño es grande. Representaremos el tamaño de un problema por n. En general n será una función de los valores de las propiedades x del problema. Es decir, n = f(x). Representaremos por T(n) la función que nos da el tiempo de ejecución en función del tamaño. En los estudios de complejidad de algoritmos asumimos que todas las funciones T(n) son monótonas crecientes y C Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Complejidad Órdenesdecomplejidad
Complejidad 86 normalmente sólo estaremos interesados en los aspectos cualitativos de T(n), es decir en su comportamiento para valores grandes de n. Para ello clasificamos las funciones según su comportamiento para grandes valores de n. Esta clasificación agrupará las funciones T(n) en órdenes de complejidad. Cada orden de complejidad es un conjunto de funciones con comportamiento equivalente para grandes valores de n. Para concretar lo anterior introduciremos una relación de orden total entre las funciones. Este orden define implícitamente una relación de equivalencia y unas operaciones de mínimo y máximo asociadas. Representaremos este orden por el símbolo <∞. Una función h(n) es menor que otra g(n) según este orden cuando el límite de su cociente es cero. Es decir: ℎ(𝑛𝑛𝑛𝑛)<∞𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)↔lim 𝑛𝑛𝑛𝑛→∞ℎ(𝑛𝑛𝑛𝑛) 𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)= 0 De la misma manera definimos el concepto de mayor, equivalente, mayor igual y menor igual. ℎ(𝑛𝑛𝑛𝑛)>∞𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)↔lim 𝑛𝑛𝑛𝑛→∞ℎ(𝑛𝑛𝑛𝑛) 𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)=∞ ℎ(𝑛𝑛𝑛𝑛)≈∞𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)↔0 < lim 𝑛𝑛𝑛𝑛→∞ℎ(𝑛𝑛𝑛𝑛) 𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)<∞ ℎ(𝑛𝑛𝑛𝑛)=∞𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)↔lim 𝑛𝑛𝑛𝑛→∞ℎ(𝑛𝑛𝑛𝑛) 𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)= 1 ℎ(𝑛𝑛𝑛𝑛)≤∞𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)↔0≤lim 𝑛𝑛𝑛𝑛→∞ℎ(𝑛𝑛𝑛𝑛) 𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)<∞ ℎ(𝑛𝑛𝑛𝑛)≥∞𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)↔lim 𝑛𝑛𝑛𝑛→∞ℎ(𝑛𝑛𝑛𝑛) 𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)> 0 Es decir dos funciones son equivalentes en el infinito, que representaremos por ≈∞, cuando el límite de su cociente es un número mayor que cero y menor que infinito. Podemos definir una noción más fuerte de esta equivalencia, que representaremos por =∞, para el caso en que el límite del cociente es 1. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Complejidad 87 La relación de equivalencia anterior define un conjunto de clases de equivalencia. Cada clase de equivalencia es un Orden de Complejidad Exacto. Más exactamente, el orden de complejidad exacto de una función g(n), que representaremos por Θ�𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)�, es el conjunto de funciones que son equivalentes a ella en el infinito según la definición anterior. Así: Θ�𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)�= { 𝑓𝑓𝑓𝑓(𝑛𝑛𝑛𝑛) | lim 𝑛𝑛𝑛𝑛→∞𝑓𝑓𝑓𝑓(𝑛𝑛𝑛𝑛) 𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)=𝑘𝑘𝑘𝑘, 0 < 𝑘𝑘𝑘𝑘<∞} De entre todas las funciones que forman parte de un mismo orden de complejidad exacto escogemos una de ellas como representante de la clase. Así por ejemplo Θ(𝑛𝑛𝑛𝑛) representa el conjunto de funciones equivalentes a n en el infinito. Entre estas funciones se encuentran los polinomios de primer grado en n. El orden anterior <∞ definido entre funciones se puede extender a los órdenes de complejidad. La relación de equivalencia entre funciones se convierte en relación de igualdad entre órdenes de complejidad. Cuando quede claro por el contexto usaremos < en lugar de <∞ y ≈ en vez de ≈∞. También definimos los operadores binarios 𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎∞ y 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑛𝑛𝑛𝑛∞ entre órdenes de complejidad x, y de la forma: 𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎∞(𝑎𝑎𝑎𝑎,𝑘𝑘𝑘𝑘)=�𝑎𝑎𝑎𝑎,𝑎𝑎𝑎𝑎≥∞𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘,𝑎𝑎𝑎𝑎<∞𝑘𝑘𝑘𝑘 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑛𝑛𝑛𝑛∞(𝑎𝑎𝑎𝑎,𝑘𝑘𝑘𝑘)=�𝑎𝑎𝑎𝑎,𝑎𝑎𝑎𝑎≤∞𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘,𝑎𝑎𝑎𝑎>∞𝑘𝑘𝑘𝑘 Igualmente definimos los operadores binarios 𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎∞ y 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖𝑛𝑛𝑛𝑛∞ los usaremos indistintamente entre órdenes de complejidad o entre funciones y si, debido al contexto, no hay duda los sustituiremos por max y min. A partir de la definición podemos comprobar los siguientes ejemplos: • Θ(𝑛𝑛𝑛𝑛)<Θ(𝑛𝑛𝑛𝑛2) • Θ(𝑛𝑛𝑛𝑛)≈Θ(𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛+𝑏𝑏𝑏𝑏) para dos constantes a, b positivas cualesquiera • Θ(𝑛𝑛𝑛𝑛)>Θ(log𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛) para cualquier a • Θ(𝑛𝑛𝑛𝑛𝑎𝑎𝑎𝑎)<Θ(𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛) para cualquier entero a > 1 • Θ(𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛)≈Θ(0)<Θ(1) para cualquier entero a < 1 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Complejidad 88 • Θ�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑+𝜀𝜀𝜀𝜀�>Θ�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑎𝑎𝑎𝑎𝑝𝑝𝑝𝑝𝑛𝑛𝑛𝑛� para cualquier d > 0, a > 0, p > 0, 𝜀𝜀𝜀𝜀> 0 • Θ(𝑛𝑛𝑛𝑛)≈max (Θ(𝑛𝑛𝑛𝑛),Θ(log 𝑛𝑛𝑛𝑛)) Para facilidad posterior introducimos el concepto de contante multiplicativa mediante la definición: 𝑓𝑓𝑓𝑓(𝑛𝑛𝑛𝑛)=∞𝑘𝑘𝑘𝑘𝐵𝐵𝐵𝐵(𝑛𝑛𝑛𝑛)↔lim 𝑛𝑛𝑛𝑛→∞𝑘𝑘𝑘𝑘𝐵𝐵𝐵𝐵(𝑛𝑛𝑛𝑛) 𝑓𝑓𝑓𝑓(𝑛𝑛𝑛𝑛)= 1 En la definición anterior f(n) y g(n) son del mismo orden de complejidad y k es denominado constante multiplicativa. Jerarquía de órdenes de complejidad exactos Como hemos explicado anteriormente los órdenes de complejidad exactos son conjuntos de funciones entre los cuales se puede definir una relación de igualdad y otra de orden. En el análisis de algoritmos hay varios órdenes de complejidad exactos que reciben nombres especiales. Éstos, a su vez, podemos organizarlos en una jerarquía de menor a mayor: Tabla 1: Clases de Complejidad • Θ(1) orden constante • Θ(log 𝑛𝑛𝑛𝑛) orden logarítmico • Θ(𝑛𝑛𝑛𝑛) orden lineal • Θ(𝑛𝑛𝑛𝑛log 𝑛𝑛𝑛𝑛) orden cuasi-lineal • Θ(𝑛𝑛𝑛𝑛2) orden cuadrático • Θ(𝑛𝑛𝑛𝑛𝑎𝑎𝑎𝑎) orden polinómico (a > 2) • Θ(2𝑛𝑛𝑛𝑛) orden exponencial • Θ(𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛) orden exponencial (a > 2) • Θ(𝑛𝑛𝑛𝑛!) orden factorial • Θ(𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛) Para hacernos una idea intuitiva de la jerarquía de órdenes de complejidad y las relaciones entre ellos veamos la siguiente tabla. En ella se muestra, en primer lugar, el efecto, en el tiempo T(n), de una Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Jerarquíadeórdenesdecomplejidadexactos
Complejidad 89 duplicación de n, el tamaño del problema. Para ello escogiendo las constantes multiplicativas adecuadas se muestran los valores de las T(n) para un valor de n=200 siempre que para n=100 el valor sea de 1s. En segundo lugar se muestra el tamaño del problema que puede ser resuelto en un tiempo t = 2s suponiendo que el tiempo necesitado para un problema de tamaño n = 100 es de 1s. La observación más importante es la gran diferencia entre los algoritmos de orden exponencial o mayor y los de orden polinómico o menor. Tabla 2: Tiempos T(n) n=100 n=200 t = 1 s t = 2 s k1 log n 1 s 1,15 s n=100 n=10000 k2 n 1 s 2 s n=100 n=200 k3 n log n 1 s 2,30 s n=100 n=178 k4 n 2 1 s 4 s n=100 n=141 k5 n 3 1 s 8 s n=100 n=126 k6 2n 1 s 1,27·1030 s n=100 n=101 Otros órdenes de complejidad Junto con el orden de complejidad exacto, Θ (g(n)), se usan otras notaciones O(g(n)) (cota superior), Ω (g(n)) (cota inferior). Todos definen conjuntos de funciones: 𝑓𝑓𝑓𝑓(𝑛𝑛𝑛𝑛)∈ 𝑂𝑂𝑂𝑂(𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)) 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 lim 𝑛𝑛𝑛𝑛→∞𝑓𝑓𝑓𝑓(𝑛𝑛𝑛𝑛) 𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)<∞ 𝑓𝑓𝑓𝑓(𝑛𝑛𝑛𝑛)∈ Ω(𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)) 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 lim 𝑛𝑛𝑛𝑛→∞𝑓𝑓𝑓𝑓(𝑛𝑛𝑛𝑛) 𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)> 0 La notación O(g(n)) define un conjunto de funciones que podemos considerar menores o iguales a g(n) en su comportamiento para grandes Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Otros órdenes de complejidad
Complejidad 96 En los algoritmos recursivos podemos entender que cada llamada recursiva resuelve un problema distinto y el tamaño de cada uno de los subproblemas debe ser menor que el tamaño del problema original. Por analogía, los algoritmos iterativos van transformando un problema en otro, también de tamaño más pequeño, hasta que se encuentra la solución. Dado un conjunto de problemas y un algoritmo para resolverlos el tiempo que tardará el algoritmo para resolver un problema dado dependerá del tamaño de este 𝑛𝑛𝑛𝑛=𝑡𝑡𝑡𝑡(𝑛𝑛𝑛𝑛). El tiempo que tarda el algoritmo en función del tamaño del problema que resuelve lo representamos por la función 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛). Complejidad de los algoritmos iterativos y recursivos sin memoria Un algoritmo se compone de secuencia de bloques que clasificaremos en tres tipos: • Bloque básico: una secuencia de asignaciones • Bloque básico con llamada a función: uno con asignaciones y llamadas a función pero sin if ni while. • Bloque while: Una sentencia while con un cuerpo de alguno de los tres tipos. El flujo de control de la ejecución de un algoritmo se define un camino. Un camino es una secuencia de bloques básicos, bloques con llamadas a función o bloques while. El camino viene definido por las sucesivas ramas de los bloques if elegidas según los parámetros de entrada. Para un problema dado y unas propiedades de entrada algoritmo fijadas, el camino recorrido por algoritmo es único. El coste de ejecutar un algoritmo para resolver un problema es el coste de ejecutar los bloques en el camino recorrido. Por lo tanto la suma del coste de los bloques que lo forman. Veamos cada uno de ellos. Asumimos que las propiedades del problema son 𝑛𝑛𝑛𝑛, su tamaño 𝑛𝑛𝑛𝑛=𝑡𝑡𝑡𝑡(𝑛𝑛𝑛𝑛) y el coste de ejecutarlo 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛). Es decir calculamos el coste en función del tamaño del problema. Recordemos que estamos interesados en el orden de complejidad exacto, es decir Θ(𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)), o alternativamente 𝑂𝑂𝑂𝑂(𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)) o Ω(𝑔𝑔𝑔𝑔(𝑛𝑛𝑛𝑛)), pero no en el coste 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛) directamente. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Complejidaddelosalgoritmositerativosyrecursivossinmemoria
Complejidad 97 Complejidad de un bloque básico. Como hemos dicho un bloque básico es una secuencia de asignaciones sin if, sin while y sin llamadas a funciones. Su tiempo de ejecución es constante independientemente del tamaño del problema. Su complejidad es, por tanto, Θ(1). Como hemos dicho un bloque con llamada a función es una secuencia de asignaciones y llamada a funciones, pero sin if ni while. Su tiempo de ejecución es la suma de los tiempos de cada una de las sentencias. La llamada a función tardará un tiempo que dependerá de los parámetros. En definitiva, dependerá del tamaño del problema que resuelve obtenido de los parámetros. Complejidad del bloque while. La estructura de un bloque while se puede escribir en la forma: while(g){ s; } Donde g es una expresión lógica y s un bloque de código de alguno de los tipos anteriores. El boque while es el elemento central en todo algoritmo iterativo. A cada bloque while podemos asociar una variable entera 𝑖𝑖𝑖𝑖 que va contando el número de iteraciones. Esta variable se va a mover en algún tipo de secuencia (aritmética, geométrica, etc.) que llamaremos 𝐼𝐼𝐼𝐼. En cada iteración del bucle el algoritmo transforma un problema con propiedades 𝑛𝑛𝑛𝑛𝑖𝑖𝑖𝑖 en otro con propiedades 𝑛𝑛𝑛𝑛𝑗𝑗𝑗𝑗 hasta llegar a un problema cuyas propiedades no satisfagan la guarda. Cada uno de los sucesivos problemas tiene asociado un tamaño 𝑡𝑡𝑡𝑡(𝑛𝑛𝑛𝑛𝑖𝑖𝑖𝑖) que debe ser cada vez más pequeño para que el algoritmo acabe. El tiempo de ejecución de un bloque while dependerá del número de iteraciones que tenga. La guarda más el cuerpo de la forma un bloque de alguno de los tres tipos anteriores. Podemos calcular su tiempo de ejecución como hemos ido explicando. En tiempo de ejecución de la iteración 𝑖𝑖𝑖𝑖,ejecución de la guarda más el bloque 𝑙𝑙𝑙𝑙,es 𝑇𝑇𝑇𝑇𝑠𝑠𝑠𝑠(𝑖𝑖𝑖𝑖). Con estas ideas Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Complejidad 98 El tiempo de ejecución del bucle while es entonces la suma del tiempo de sus ejecuciones: 𝛩𝛩𝛩𝛩(𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)) = 𝛩𝛩𝛩𝛩(�𝑇𝑇𝑇𝑇𝑠𝑠𝑠𝑠(𝑖𝑖𝑖𝑖) 𝑖𝑖𝑖𝑖∈𝐼𝐼𝐼𝐼 ) 1. Ejemplo de cálculo de complejidad for (int i = 1; i <= n; i++) { r += a * i; } �𝑘𝑘𝑘𝑘=𝑘𝑘𝑘𝑘 𝑛𝑛𝑛𝑛 ∈Θ(𝑛𝑛𝑛𝑛) 𝑛𝑛𝑛𝑛 𝑖𝑖𝑖𝑖=1 Dependiendo del problema concreto a resolver, en definitiva, de las condiciones iniciales del algoritmo, se seguirá un camino de ejecución u otro. Estos caminos dependen del problema concreto y como puede haber diferentes problemas con el mismo tamaño, pero diferentes propiedades pueden ocurrir que para diferentes problemas del mismo tamaño se sigan caminos diferentes. Distinguimos, entonces, el caso mejor, el caso peor y el caso medio a la hora de calcular la complejidad de un algoritmo. • El caso mejor es el que ejecuta el camino de complejidad más baja • El caso peor es el que ejecuta el camino de complejidad más alta • El caso medio es el que ejecuta todos los caminos posibles cada uno de ellos con una probabilidad que tendremos que establecer Como segundo ejemplo sea una lista de números enteros de tamaño n y los algoritmos siguientes que pretenden encontrar si existe algún múltiplo de s. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Complejidad 99 boolean contieneMultiploDe(List<Integer> ls, Integer s) { return contieneMultiploDe3(0,ls,r); } boolean contieneMultiploDe(Integer i, List<Integer> ls, Integer s) { boolean r; if(lis.get(i)%s==0) r= true; else r = contieneMultiploDe(i+1,ls); return r; } Observando el código del algoritmo generalizado vemos que el tamaño es 𝑛𝑛𝑛𝑛−𝑖𝑖𝑖𝑖. Siendo 𝑛𝑛𝑛𝑛 el tamaño de la lista. Podemos ver, también, que hay dos caminos posibles según la guarda 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙.𝑔𝑔𝑔𝑔𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒(𝑖𝑖𝑖𝑖)%𝑙𝑙𝑙𝑙== 0 sea verdadera o falsa. Aquí podemos estudiar el caso mejor, pero y medio. • Caso mejor: El primer elemento es múltiplo de r. Complejidad Θ�𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)�=Θ(1) • Caso peor: No hay múltiplo de r. Complejidad 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛) = 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛−1) + 1 cuya solución es Θ(𝑛𝑛𝑛𝑛) • Complejidad del caso medio. Asumiendo que la probabilidad de que un número entero sea múltiplo de 𝑙𝑙𝑙𝑙 es 1/𝑙𝑙𝑙𝑙 entonces la complejidad verifica 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛) = 𝑠𝑠𝑠𝑠−1 𝑠𝑠𝑠𝑠𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛−1) + 1𝑠𝑠𝑠𝑠. Cuya solución es Θ(1). Como 𝑠𝑠𝑠𝑠−1 𝑠𝑠𝑠𝑠< 1 y recordando el tipo de recurrencias a aplicar en este caso 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 𝑎𝑎𝑎𝑎𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛−𝑏𝑏𝑏𝑏)+ (𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝑔𝑔𝑔𝑔𝑛𝑛𝑛𝑛)𝑝𝑝𝑝𝑝 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑) Cuya solución es: 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)=�𝛩𝛩𝛩𝛩�𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛/𝑏𝑏𝑏𝑏(log 𝑛𝑛𝑛𝑛)𝑝𝑝𝑝𝑝�, 𝑙𝑙𝑙𝑙𝑖𝑖𝑖𝑖 𝑎𝑎𝑎𝑎> 1 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑+1(log 𝑛𝑛𝑛𝑛)𝑝𝑝𝑝𝑝�, 𝑙𝑙𝑙𝑙𝑖𝑖𝑖𝑖 𝑎𝑎𝑎𝑎= 1 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑(log 𝑛𝑛𝑛𝑛)𝑝𝑝𝑝𝑝�, 𝑙𝑙𝑙𝑙𝑖𝑖𝑖𝑖 𝑎𝑎𝑎𝑎< 1 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Complejidad 100 El algoritmo tiene una versión secuencial siendo su complejidad igual: boolean contieneMultiploDe(List<Integer> ls, Integer s) { boolean r = false; for(Integer e: lis){ r = e%s==0; if(r) break; } return r; } • Caso mejor: El primer elemento es múltiplo de 3. Hay cero iteraciones. Complejidad Θ�𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)�=Θ(1) • Caso peor: No hay múltiplo de 3. Hay 𝑛𝑛𝑛𝑛 iteraciones. Complejidad 𝛩𝛩𝛩𝛩�𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)�=𝛩𝛩𝛩𝛩(�1 𝑛𝑛𝑛𝑛−1 𝑖𝑖𝑖𝑖=0 )) = 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛) • Complejidad del caso medio. Puede haber de 0 a n iteraciones. Cada iteración tiene coste constante pero la probabilidad de que ocurra es que no se haya encontrado en las iteraciones anteriores es decir �𝑠𝑠𝑠𝑠−1 𝑠𝑠𝑠𝑠�𝑖𝑖𝑖𝑖. Luego la complejidad del caso medio es 𝛩𝛩𝛩𝛩(1𝑠𝑠𝑠𝑠∑(𝑠𝑠𝑠𝑠−1 𝑠𝑠𝑠𝑠)𝑖𝑖𝑖𝑖 𝑛𝑛𝑛𝑛−2 𝑖𝑖𝑖𝑖=0 )) = 𝛩𝛩𝛩𝛩(1) Complejidad de los algoritmos recursivos con memoria En los algoritmos con memoria el cálculo de la complejidad es distinto. Ahora cada problema se resuelve una vez y debemos tener en cuenta el conjunto de problemas 𝑃𝑃𝑃𝑃 que debemos resolver para encontrar la solución de uno dado. Si 𝑇𝑇𝑇𝑇(𝑝𝑝𝑝𝑝) es el tiempo que tarda el problema 𝑝𝑝𝑝𝑝 en resolverse asumiendo constante las llamadas a los subproblemas entonces la complejidad de un problema es 𝛩𝛩𝛩𝛩(�𝑇𝑇𝑇𝑇(𝑝𝑝𝑝𝑝) 𝑝𝑝𝑝𝑝∈𝑃𝑃𝑃𝑃 ) Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Complejidaddelosalgoritmosrecursivosconmemoria
Complejidad 101 2. Ejemplo: Problema de Fibonacci En el problema de Fibonacci cada problema es representado por su propiedad n. Podemos comprobar que el conjunto de problemas a resolver es 𝑃𝑃𝑃𝑃= {0,1,2, … , 𝑛𝑛𝑛𝑛}. Según lo explicado antes 𝑇𝑇𝑇𝑇(𝑝𝑝𝑝𝑝) = 𝑘𝑘𝑘𝑘. Luego la complejidad del problema de Fibonacci resuelto con memoria es ∑𝑘𝑘𝑘𝑘=𝑘𝑘𝑘𝑘∑1 𝑝𝑝𝑝𝑝∈𝑃𝑃𝑃𝑃 ≅𝑛𝑛𝑛𝑛 𝑝𝑝𝑝𝑝∈𝑃𝑃𝑃𝑃 . En el problema de la Potencia Entera cada subproblema se representa por su propiedad 𝑛𝑛𝑛𝑛. Ahora 𝑃𝑃𝑃𝑃= {𝑛𝑛𝑛𝑛,𝑛𝑛𝑛𝑛2,𝑛𝑛𝑛𝑛4, … ,1} y |𝑃𝑃𝑃𝑃|=𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵2𝑛𝑛𝑛𝑛+ 1. Por lo tanto la complejidad de la Potencia Entera con Memoria es ∑𝑘𝑘𝑘𝑘=𝑘𝑘𝑘𝑘∑1 𝑝𝑝𝑝𝑝∈𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝∈𝑃𝑃𝑃𝑃 ≅ 𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑛𝑛𝑛𝑛. Veremos otros ejemplos en el apéndice. Estas ideas nos permiten decidir cuándo usar Divide y Vencerás con y sin Memoria. Sólo usaremos la Memoria cuando la complejidad del problema se reduzca (caso del problema de Fibonacci). Si la complejidad es la misma (caso del problema de la Potencia Entera) no es conveniente usar Memoria. Las razones para que la complejidad sea distinta (usando memoria y sin usarla) es la aparición de subproblemas repetidos al resolver un problema. Esto ocurre en el problema de Fibonacci y no ocurre en el Problema de la Potencia Entera. Por lo tanto, un criterio directo para decidir si usar memoria o no es verificar si aparecen subproblemas repetidos o no. Fórmulas de resumen • Expresiones importantes con sumatorios �𝑎𝑎𝑎𝑎𝑖𝑖𝑖𝑖 𝑛𝑛𝑛𝑛 𝑖𝑖𝑖𝑖=0 =�1, 𝑎𝑎𝑎𝑎< 1 𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛,𝑎𝑎𝑎𝑎≥1 �𝑎𝑎𝑎𝑎𝑖𝑖𝑖𝑖 𝑙𝑙𝑙𝑙𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑟𝑟𝑟𝑟𝑛𝑛𝑛𝑛 𝑖𝑖𝑖𝑖=0 ≅𝑎𝑎𝑎𝑎𝑙𝑙𝑙𝑙𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑟𝑟𝑟𝑟𝑛𝑛𝑛𝑛≅𝑛𝑛𝑛𝑛𝑙𝑙𝑙𝑙𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑟𝑟𝑟𝑟𝑎𝑎𝑎𝑎 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Fórmulas de resumen
Complejidad 102 � 𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑(𝑙𝑙𝑙𝑙𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛)𝑝𝑝𝑝𝑝 𝑛𝑛𝑛𝑛 𝑥𝑥𝑥𝑥=𝑖𝑖𝑖𝑖0+𝑟𝑟𝑟𝑟 𝑖𝑖𝑖𝑖≅1 𝑟𝑟𝑟𝑟(𝑑𝑑𝑑𝑑+ 1) 𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑+1(𝑙𝑙𝑙𝑙𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛)𝑝𝑝𝑝𝑝 � 𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑(𝑙𝑙𝑙𝑙𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛)𝑝𝑝𝑝𝑝 𝑛𝑛𝑛𝑛 𝑥𝑥𝑥𝑥=𝑖𝑖𝑖𝑖0 𝑟𝑟𝑟𝑟𝑖𝑖𝑖𝑖≅�(𝑙𝑙𝑙𝑙𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛)𝑝𝑝𝑝𝑝+1,𝑑𝑑𝑑𝑑= 0 𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑(𝑙𝑙𝑙𝑙𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛)𝑝𝑝𝑝𝑝,𝑑𝑑𝑑𝑑> 0 • Recurrencias lineales y su solución 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 𝑎𝑎𝑎𝑎𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛−𝑏𝑏𝑏𝑏)+ 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑)𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑝𝑝𝑝𝑝𝑛𝑛𝑛𝑛 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)=�𝛩𝛩𝛩𝛩�𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛/𝑏𝑏𝑏𝑏𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑝𝑝𝑝𝑝𝑛𝑛𝑛𝑛�, 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑎𝑎𝑎𝑎> 1 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑+1𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑝𝑝𝑝𝑝𝑛𝑛𝑛𝑛�, 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑎𝑎𝑎𝑎= 1 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑝𝑝𝑝𝑝𝑛𝑛𝑛𝑛�, 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑎𝑎𝑎𝑎< 1 • Recurrencias no lineales y su solución 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 𝑎𝑎𝑎𝑎𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛/𝑏𝑏𝑏𝑏)+ 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑)𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑝𝑝𝑝𝑝𝑛𝑛𝑛𝑛 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)=�𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑙𝑙𝑙𝑙𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑏𝑏𝑏𝑏𝑎𝑎𝑎𝑎� 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑎𝑎𝑎𝑎>𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑 𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑝𝑝𝑝𝑝+1𝑛𝑛𝑛𝑛� 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑎𝑎𝑎𝑎=𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑 𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑝𝑝𝑝𝑝𝑛𝑛𝑛𝑛� 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑎𝑎𝑎𝑎<𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑 3. Un ejemplo double f (int n, double a) { double r; if (n == 1) { r = a; } else { r = f (n/2, a+1) – f (n/2, a–1); for (int i = 1; i <= n; i++) { r += a * i; } } return r; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Complejidad 103 La parte iterativa, según el Ejemplo 1, es Θ(𝑛𝑛𝑛𝑛). Por lo tanto: 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 2𝑇𝑇𝑇𝑇�𝑛𝑛𝑛𝑛2�+Θ(𝑛𝑛𝑛𝑛) Cuya solución es: a= 2, b= 2, d =1, 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)∈Θ(𝑛𝑛𝑛𝑛log 𝑛𝑛𝑛𝑛) 4. Un segundo ejemplo es int f (int n) { int i, j, z, r; if (n < 1) { r = 1; } else { z = 0; for (i = 1; i < n; i++) { for (j = 1; j < i ∗ i; j++) { z ++; } } r = z ∗ (( f (n – 2)) ^ 2); } return r; fin Tomando el resultado del ejemplo 5 tenemos: 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)=𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛−2)+Θ(𝑛𝑛𝑛𝑛3) Con a = 1, b= 2, d = 3, tenemos: 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)∈Θ(𝑛𝑛𝑛𝑛4) En el caso anterior si la expresión f (n – 2)) ^ 2 la escribiéramos de la forma f (n – 2))* f (n – 2)) la complejidad sería 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 2𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛−2)+Θ(𝑛𝑛𝑛𝑛3) Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Complejidad 104 Cuya solución es 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)∈Θ�2𝑛𝑛𝑛𝑛2�=Θ�√2𝑛𝑛𝑛𝑛� En ambos casos si utilizamos memoria la complejidad es �𝑖𝑖𝑖𝑖3≅Θ(𝑛𝑛𝑛𝑛4) 𝑛𝑛𝑛𝑛 𝑖𝑖𝑖𝑖=2𝑢𝑢𝑢𝑢 En este caso asumimos que los subproblemas están calculados. Entonces cada problema tiene un coste de Θ(𝑖𝑖𝑖𝑖3) y los subproblemas que es necesario calcular están en una secuencia aritmética de paso 2. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
105 Diseño y verificación de algoritmos iterativos as ideas vistas previamente nos van a permitir usar algunas estrategias para diseñar algoritmos iterativos. Hay varias posibilidades que vamos a ver ahora. Dejamos para más adelante la posibilidad de diseñar, con estrategias recursivas, un algoritmo recursivo final para obtener a partir de él uno iterativo en forma imperativa o funcional. Diseño de Algoritmos Iterativos Hay varias estrategias • Buscar un estado, una secuencia, con su iterador asociado, un acumulador secuencial y combinarlos en un algoritmo iterativo. A veces una función de partición que a partir de un problema obtenga otro más pequeño puede ayudarnos a definir una secuencia formada de problemas y subproblemas • Buscar un estado y sobre él definir un invariante. Un invariante es un predicado que debe cumplirse en todos los estados que va recorriendo el algoritmo. Dado el estado y el invariante se trata de encontrar la secuencia cuyos estados cumplen el invariante. L Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Diseñoyverificacióndealgoritmositerativos Diseñodealgoritmositerativos
Diseño y verificación de algoritmos iterativos 112 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏] iguales al pivote, en la sublista 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑚𝑚𝑚𝑚,𝑛𝑛𝑛𝑛] mayores al pivote y en 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑏𝑏𝑏𝑏,𝑚𝑚𝑚𝑚] la relación de los elementos con el pivote es desconocida. Tabla 4: Invariante de la bandera holandesa 0 a b c n <p =p ? >p El tamaño del problema será 𝑚𝑚𝑚𝑚−𝑏𝑏𝑏𝑏. Iremos reduciendo el tamaño de la zona desconocida, el tamaño, en cada iteración. La función existe siguiente, la guarda, es ℎ𝑛𝑛𝑛𝑛(𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏,𝑚𝑚𝑚𝑚) = 𝑚𝑚𝑚𝑚−𝑏𝑏𝑏𝑏> 0. Con los elementos anteriores se propone se siguiente algoritmo: bh(ls, p){ n = |ls|; (a,b,c) = (0,0,n); while(c-b>0){ if(ls[b] < p ){ it(a,b,ls); a++; b++; }else if(ls[b] == p){ b++; }else{ it(b,c-1,ls); c--; } } return (a,b); } Donde la función 𝑖𝑖𝑖𝑖𝑡𝑡𝑡𝑡 intercambia los valores de las dos casillas 𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏 y es de la forma: it(a,b,ls){ (ls[a],ls[b]) = (ls[b],ls[a]); } Podemos comprobar que la función de cota se reduce en cada iteración. Veamos que se mantiene el invariante. Hay tres casos dependiendo de la relación del elemento ls[b], el primero de la zona desconocida, con el pivote p: Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Diseño y verificación de algoritmos iterativos 113 • ls[b] < p. Reubicamos el elemento en la casilla b en la zona [0,a) intercambiando el elemento en b por el que hay en a, e incrementando los valores de a, b. • ls[b] = p. Reubicamos el elemento en la casilla b en la zona [a,b) simplemente aumentando b. • ls[b] > p. Reubicamos el elemento en la casilla b en la zona [c,n) intercambiando el elemento en b por el que hay en c-1 y decrementando el valor de c. Cada vez que ubicamos un elemento disminuye 𝑏𝑏𝑏𝑏−𝑚𝑚𝑚𝑚 y por lo tanto el tamaño del problema. Como vemos el acumulador va produciendo cambios en la lista. Un esquema de la versión recursiva final es de forma análoga: (Integer, Integer) bh(ls, p){ n = |ls|; (a,b,c) = (0,0,n); (a,b,c) = bh(a,b,c,ls,p); return (a,b); } (Integer, Integer, Integer) bh(a,b,c,ls,p){ if(c-b>0){ if(ls[b] < p ){ it(a,b,ls); a++; b++; }else if(ls[b] == p){ b++; }else{ it(b,c-1,ls); c--; } (a,b,c) = bh(a,b,c,ls,p); } return (a,b,c); } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Diseño y verificación de algoritmos iterativos 114 Y finalmente la versión funcional asumiendo que la función it devuelve la lista modificada: T = (Integer, Integer, Integer, List<E>, E) n = ls.size(); s0 = (0,0,n,ls,p); hn = (0,0,n,ls,p) -> c-b>0; hnn = (0,0,n,ls,p) -> c-b==0; nx = (a,b,c,ls,p) -> if(ls[b] < p ) (a++,b++,c, it(a,b,ls),p) else if(ls[b] == p) (a,b++,c,ls,p) else (a,b,c--,it(b,c-1,ls),p); rt = (a,b,c,ls,p) -> (a,b); (Integer,Integer( bb(ls,e){ Stream(T) st = Stream.iterate(so,x->true,nx); T r = st.filter(hnn).findFirst().get(); return rt(r); } Una variante de este algoritmo es la siguiente: Dado un array y un elemento del mismo tipo que las casillas, que llamaremos pivote, reordenarlo para que queden dos bloques: los menores que el pivote, y los iguales o mayores al pivote. El algoritmo debe devolver un entero que separa los dos bloques formados. El diseño de este algoritmo sigue los mismos pasos que el anterior. Verificación de algoritmos iterativos Para verificar un algoritmo iterativo, en su forma imperativa o funcional, partimos de un algoritmo dado y una restricción de entrada-salida. Verificar un algoritmo iterativo supone demostrar que cumple la restricción entrada-salida dada. Por comodidad para hacer la verificación es conveniente normalizar el algoritmo en primer lugar. Para hacer esto tenemos que deducir, a partir del algoritmo, el estado, la secuencia y la función de retorno y si es el caso el acumulador correspondiente. Luego, debemos imaginar un invariante, demostrar por inducción que se cumple en todos los estados. La demostración por inducción implica demostrar que el invariante es válido en el estado inicial y supuesto válido en un estado demostrar que es válido en el siguiente. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Verificacióndealgoritmositerativos
Diseño y verificación de algoritmos iterativos 115 Junto con lo anterior, para que la demostración por inducción sea válida debe acabar, necesitamos imaginar un tamaño, llamado a menudo función de cota, y demostrar que decrece en cada iteración. El tamaño es una función del estado del algoritmo y mide el trabajo que falta por hacer: las iteraciones que faltan. Finalmente deducir la restricción entrada-salida de los elementos anteriores. Para ello hay que tener en cuenta que al final del bucle se cumple el invariante, la negación de la guarda y la relación establecida por la función de retorno entre el estado y los parámetros de salida. Veamos, en primer lugar, la verificación de algoritmos que calculen la factorial de un número 𝑛𝑛𝑛𝑛. La restricción de salida es 𝑅𝑅𝑅𝑅(𝑛𝑛𝑛𝑛,𝑟𝑟𝑟𝑟)≡𝑟𝑟𝑟𝑟=𝑛𝑛𝑛𝑛!. El algoritmo a verificar el que se incluye abajo. Long f(n) { t = 1; b = 1; while(t <= n){ e = t; t = t + 1; b = b * e; } return b; } Transformando los bloques básicos en asignación de tuplas y eliminando la variable t tenemos: Long factorial(n) { (e,b) = (1,1); while(e <= n){ (e,b) = (e + 1, b*e); } return a; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Diseño y verificación de algoritmos iterativos 116 Diseñando el record A(Integer e, Integer b) y factoría of, podemos escribirlo como: Long factorial(Integer n) { A t = A.of(1,1); while(t.e() <= n){ t = A.of(t.e() + 1, t.b()*t.e()); } return t.b(); } O usando el acumulador reduce con valor inicial: Long factorial(Integer n) { return LongStream.rangeClosed(1, n) .reduce(1,(x,y)->x*y); } Los elementos para la verificación, siguiendo la forma normalizada son: • El estado es (e,a) • La secuencia viene definida por (e0, a0) = (1, 1), g(e, a) = e ≤ n , s(e, a) = (e+1, a∗e); • Un invariante puede ser I(e,a) ≡ a = (e−1)! • Una función de cota C(e,a) = n−e • El invariante se cumple en el estado inicial. En efecto I(1,1), 1 = 0! Si el invariante se cumple en un estado se cumple en el siguiente. Para ello usamos la restricción entrada salida asociada a la asignación de tuplas interior del bucle tenemos las restricciones: // Si esto se cumple I(e,a) ≡ a =(e−1)! // // Debe cumplirse I(s(e,a)) ≡ I(e+1,a ∗ e) ≡ a ∗ e =(e+1−1)! = e!, a ∗ e = e! //Usando las propiedades de la factorial y usando lo supuesto a =(e−1)!, e! =(e−1)! ∗ e ≡ a ∗ e = e! La función de cota disminuye en cada iteración C(s(e,a)) < C(e,a) ≡ n−(e+1) = n−e−1 < n−e Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Diseño y verificación de algoritmos iterativos 117 La restricción de entrada salida es: R(r,n)≡ r = a , a = (e−1)! , !(e <= n) r = a , a = (e−1)! , e = n +1 r = n! Donde se ha eliminado a, e y que !(e <= n) implica e = n+1 dada la secuencia del algoritmo. Como podemos comprobar podemos hacer explícita una secuencia y un acumulador: s = (1, e -> e <= n, e -> e +1) a = (1, (a,e) -> a*e) Es decir, el algoritmo acumula la secuencia con el acumulador dado. Este acumulador acumula los productos de los elementos de la secuencia. La idea de la demostración es válida para todos los algoritmos que explicitan la secuencia y el acumulador. En esos algoritmos la secuencia es acumulada por el acumulador y siempre es la misma demostración. La demostración también es válida en el caso que se haga explícito el filtro, la transformación y el aplanamiento. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
118 Esquemas recursivos a definición recursiva de un problema es una especificación de la solución de este en base a la de otros problemas de la misma naturaleza, pero de un tamaño más pequeño. Todo problema tiene un conjunto de propiedades y posiblemente una solución. En toda definición recursiva aparecen los conceptos de caso base, caso recursivo y tamaño de un problema. Lo primero que debemos tener en cuenta en una definición recursiva de un problema es que siempre debemos partir de un conjunto de problemas. Llamaremos dominio a un predicado que nos indica si un problema pertenece al conjunto de problemas. En lo que sigue representaremos los problemas por p, p1, p2, …, pr. Un conjunto de problemas lo representaremos por P. Cada problema tendrá unas propiedades x que puede ser una tupla x = (x1, …, xm). Como en el diseño de tipos estas propiedades pueden ser individuales, compartidas, básicas, derivadas, etc. Un problema concreto podemos pensarlo como un objeto del tipo que representa todos los problemas posibles del conjunto de problemas P. El dominio lo representamos por D(x). Dentro de un conjunto de problemas P los valores de sus propiedades identifican al problema de manera única. El dominio, D(x), es una L Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Esquemasrecursivos
Esquemas recursivos 119 expresión lógica válida para las propiedades de todos los problemas que están incluidos en el conjunto de problemas de interés. A cada problema le asociamos el concepto de tamaño que es una nueva propiedad derivada del mismo. Normalmente representaremos el tamaño de un problema mediante n y lo calcularemos mediante una función sobre sus propiedades. El tamaño del problema deber ser un entero mayor o igual que cero que nos dé una idea de la complejidad de este. Problemas de tamaño mayor serán más complejos que otros de tamaño menor. Puede haber distintas formas para escoger el tamaño de un problema. Dentro de un conjunto de problemas aquellos que tienen una solución directa los llamamos casos base. Estos suelen tener un tamaño pequeño. Puede haber más de un caso base. El resto de los problemas del conjunto de problemas considerado los denominaremos casos recursivos. La solución de un caso recursivo se define en función de la de otros problemas de tamaño menor. Estos los denominaremos subproblemas. Un mismo problema puede tener diferentes definiciones recursivas. Como hemos dicho antes, una definición recursiva necesita partir de un conjunto de problemas de interés para poder expresar la solución de un problema en base a la de otro u otros de tamaño más pequeño. En muchos casos debemos imaginar ese conjunto de problemas a partir del problema original. A ese proceso lo llamamos generalizar. Desde este punto de vista, generalizar un problema es añadir propiedades al problema original para considerarlo un caso particular de un conjunto de problemas más amplio. La generalización ya la hemos visto previamente cuando teníamos que escoger un estado para diseñar un algoritmo iterativo. Un algoritmo recursivo donde cada caso recursivo se define en base a un solo problema se dice que es de recursivo simple y si se define en base a más de uno recursivo múltiple. Un algoritmo recursivo simple es recursivo final si el resultado es igual al de la llamada recursiva sin ninguna operación posterior. Algoritmo recursivo final: 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑑𝑑𝑑𝑑(𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏)=�𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏= 0 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑑𝑑𝑑𝑑(𝑏𝑏𝑏𝑏,𝑎𝑎𝑎𝑎%𝑏𝑏𝑏𝑏), 𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏> 0 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Esquemas recursivos 120 Algoritmo recursivo simple no final: 𝑛𝑛𝑛𝑛! = �1, 𝑛𝑛𝑛𝑛= 0 𝑛𝑛𝑛𝑛∗(𝑛𝑛𝑛𝑛−1)!, 𝑛𝑛𝑛𝑛> 0 Algoritmo recursivo múltiple: 𝑓𝑓𝑓𝑓𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖(𝑛𝑛𝑛𝑛) = �𝑛𝑛𝑛𝑛, 0 ≤𝑛𝑛𝑛𝑛≤1 𝑓𝑓𝑓𝑓𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖(𝑛𝑛𝑛𝑛−1)+𝑓𝑓𝑓𝑓𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖(𝑛𝑛𝑛𝑛−2), 𝑛𝑛𝑛𝑛> 1 El esquema general de un algoritmo recursivo múltiple es: R f(x) { if(b(x)){ s = sb(x); } else { (y0,y1,..) = sp(x); (s0,s1,..) = (f(y0),f(y1),..) s = c(s1, s2,…, x); } return s; } En un algoritmo recursivo aparecen los siguientes conceptos: • 𝑖𝑖𝑖𝑖(𝑛𝑛𝑛𝑛): Es una función lógica que devuelve verdadero si el problema es un caso base • 𝑙𝑙𝑙𝑙𝑖𝑖𝑖𝑖(𝑛𝑛𝑛𝑛): Es una función que devuelve la solución del caso base. • 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙(𝑛𝑛𝑛𝑛): Es una función que devuelve una tupla de los subproblemas al que se reduce el problema original. Esta función la podemos denominar, también, función de partición. • 𝑚𝑚𝑚𝑚(𝑙𝑙𝑙𝑙0, 𝑙𝑙𝑙𝑙1, … , 𝑛𝑛𝑛𝑛): Es una función, que llamaremos función de combinación, que obtiene la solución del problema combinando las soluciones de los subproblemas con las propiedades del problema. • 𝑘𝑘𝑘𝑘0, 𝑘𝑘𝑘𝑘1, … Son los subproblemas. • 𝑙𝑙𝑙𝑙0, 𝑙𝑙𝑙𝑙1, … Son las soluciones de los subproblemas. En muchos algoritmos recursivos puede que se repitan muchos subproblemas lo que hace que el algoritmo tarde más en ejecutarse. Para evitar los cálculos repetidos podemos mejorar el esquema recursivo Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Esquemas recursivos 121 anterior intentando recordar los cálculos ya realizados. Para ello diseñamos un nuevo algoritmo recursivo que llamaremos divide y vencerás con memoria (en anterior era divide y vencerás sin memoria). Para ello necesitamos una variable m, de tipo diccionario, que guarde la solución s para cada problema x ya resuelto. El esquema es: S f(x){ Map<P,S> m = …; return fm(x,m); } S fm(x,m) { … if(x en m.keys()) { s = m[x]; } else if(b(x)){ s = sb(x); m[x] = s; } else { (y0,y1,..) = sp(x); (s0,s1,..) = (f(y0),f(y1),..) s = c(s1, s2,…, x); m[x] = s; } return s; } Diseño de algoritmos recursivos Con las estrategias de diseño de algoritmos recursivos obtenemos algoritmos recursivos en muchos casos múltiples y en otros casos simples no finales o finales. Para diseño de algoritmos recursivos disponemos de las siguientes estrategias • Generalizar el problema añadiendo más propiedades, y tras definir un tamaño del problema, y los casos base, reducir cada problema a subproblemas y definir la solución de problema dadas las de los subproblemas. • Definir una función de partición que obtenga los subproblemas de un problema dado y a partir de ahí definir la solución de un Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Diseñodealgoritmosrecursivos
Esquemas recursivos 128 R algr(D d) { Iterator<E> it = d.iterator(); B b = algr(it,d); return r(b); } B algr(Iterator<E> it, D d){ B r = sb(d); if(it.hasNext()){ E e = it.next(); r = algr(it,d); r = c(e,r,d); } return r; } Definición de una función de partición Esta estrategia es similar a la anterior pero es más general que la anterior de generalización para secuencial indexables en el sentido que se puede aplicar a agregados de datos no indexables y a otros agregados que son secuencial. Asumimos que tenemos un agregado de datos de tipo 𝑒𝑒𝑒𝑒 compuesto de elementos de tipo 𝐸𝐸𝐸𝐸. Esencialmente una función de partición es una función que dado un agregado de datos de tipo 𝑒𝑒𝑒𝑒 nos devuelve una tupla con sus partes y quizás algún elemento de particular. A cada resultado de una función de partición le llamamos una vista del agregado de datos y asumimos que el tipo D tiene el método size() que nos indica su tamaño. Estas vistas podemos clasificarlas en: • Vistas de tipo 1, record View1<D,E> (E e, D rs). Donde e un elemento que puede quede ser definido en cada caso y rs el resto del agregado. En los casos más frecuentes e es el primer o el último elemento del agregado. • Vistas de tipo 2, record View2<D> (D left,D right). Donde left es la parte izquierda del agregado y right la parte derecha. Según los casos ambas partes pueden ser del mismo o diferente tamaño. • Vistas de tipo 2 con elemento, record View2E<D> (E e,D left,D right). Donde e es un elemento del agregado, left es la parte izquierda del agregado y right la parte derecha. Según los casos ambas partes pueden ser del mismo o diferente tamaño. Igualmente la vista puede ser cerrada o abierta. Abierta si e no pertenece a left ni a Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Definicióndeunafuncióndepartición
Esquemas recursivos 129 right y estas son disjuntas. Cerrada si left y right tienen una intersección que es justamente e. • Vistas de tipo 4, record View4<D> (D a, D b, D c, D d). Donde a, b, c, d son cada una de las cuatro partes en las que se divide el agregado. Algunas de las generalizaciones anteriores para secuencias indexables pueden ser reinterpretadas como vistas. Así tenemos algunas posibilidades: • (𝑙𝑙𝑙𝑙[𝑖𝑖𝑖𝑖], (𝑖𝑖𝑖𝑖+ 1, 𝑙𝑙𝑙𝑙)) = 𝑣𝑣𝑣𝑣𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖1((𝑖𝑖𝑖𝑖,𝑙𝑙𝑙𝑙)) • (((𝑖𝑖𝑖𝑖,𝑘𝑘𝑘𝑘,𝑙𝑙𝑙𝑙),𝑘𝑘𝑘𝑘,(𝑘𝑘𝑘𝑘,𝑗𝑗𝑗𝑗,𝑙𝑙𝑙𝑙)=𝑣𝑣𝑣𝑣𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖2�(𝑖𝑖𝑖𝑖,𝑗𝑗𝑗𝑗,𝑙𝑙𝑙𝑙)�,𝑘𝑘𝑘𝑘=(𝑖𝑖𝑖𝑖+𝑗𝑗𝑗𝑗)/2. • (s[k],((𝑖𝑖𝑖𝑖,𝑘𝑘𝑘𝑘,𝑙𝑙𝑙𝑙),𝑘𝑘𝑘𝑘,(𝑘𝑘𝑘𝑘,𝑗𝑗𝑗𝑗,𝑙𝑙𝑙𝑙)=𝑣𝑣𝑣𝑣𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖2𝑖𝑖𝑖𝑖�(𝑖𝑖𝑖𝑖,𝑗𝑗𝑗𝑗,𝑙𝑙𝑙𝑙)�,𝑘𝑘𝑘𝑘=(𝑖𝑖𝑖𝑖+𝑗𝑗𝑗𝑗)/2. Los esquemas para este tipo de vistas son similares a los vistos para las generalizaciones de secuencias y la complejidad la misma. Repetimos, como ilustración, el caso de view2e. R algr(D d) { B b = algr2(s); return r(b); } B algr(D d){ B r; if(d.size() < nu){ r = sb(d); }else{ View2E<D,E> (e,left,right) = view2e(d); R rl = algr(left); R rr = algr(right); r = c(rl,rr,e); } return r; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Esquemas recursivos 130 Además de las secuencias indexables hay vistas de tipo 1 para otros tipos de agregados dando lugar a los esquemas: R algr(D d) { B b = algr2(s); return r(b); } B algr(D d){ B r; if(d.size() < nu){ r = sb(d); }else{ View1<D,E> (e,rs) = view1(d); R r = algr(rs); r = c(r,e); } return r; } Un caso de ellas vistas de tipo 1 es un iterable. Así podemos tener View1<Iterable<E>,E> (e,it2) = view1(it) con e el elemento obtenido con it.next() y it2 el iterador resultante. Las generalizaciones prefija o sufija de secuencias y las que usan iteradores dan lugar a esquemas similares usando vistas. La ventaja que tiene usar vistas es que pueden estar implementadas para cada tipo de datos y reutilizadas. En el repositorio hay implementadas para algunos tipos de datos. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Esquemas recursivos 131 El uso de la View4 da lugar a esquemas del tipo: R algr(D d) { B b = algr2(s); return r(b); } B algr(D d){ B r; if(d.size() < nu){ r = sb(d); }else{ View4<D> (abcd) = view2e(d); R ra = algr(a); R rb = algr(a); R rc = algr(a); R rd = algr(a); r = c(a,b,c,d); } return r; } Este tipo de esquemas produce, en general, algoritmos recursivos múltiples y con una complejidad en el caso peor dada por la ecuación: 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛) = 4𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛/2) + 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑) Con solución dependiendo del valor de d. Recordemos que la solución es: 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)=�𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑙𝑙𝑙𝑙𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑏𝑏𝑏𝑏𝑎𝑎𝑎𝑎� 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑎𝑎𝑎𝑎>𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑 𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑝𝑝𝑝𝑝+1𝑛𝑛𝑛𝑛� 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑎𝑎𝑎𝑎=𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑 𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑝𝑝𝑝𝑝𝑛𝑛𝑛𝑛� 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑎𝑎𝑎𝑎<𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑 Suponemos que cada parte de la vista tiene la mitad del tamaño que el agregado completo como es el caso con las matrices. Entonces 𝑎𝑎𝑎𝑎= 4, 𝑏𝑏𝑏𝑏= 2. Por lo tanto para 𝑑𝑑𝑑𝑑= 2 se cumple 𝑎𝑎𝑎𝑎=𝑏𝑏𝑏𝑏2,para 𝑑𝑑𝑑𝑑< 2, 𝑎𝑎𝑎𝑎> 𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑 y para 𝑑𝑑𝑑𝑑> 2 entonces 𝑎𝑎𝑎𝑎<𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑. La solución anterior se concreta en: 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)=�𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛2) 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑑𝑑𝑑𝑑< 2 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛2 𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑛𝑛𝑛𝑛) 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑑𝑑𝑑𝑑= 2 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑� 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑑𝑑𝑑𝑑> 2 Veamos un ejemplo: obtener la multiplicación de dos matrices: • De forma iterativa Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Esquemas recursivos 132 • De forma recursiva dividiéndolas en cuatro submatrices Para enfocar el problema proponemos un sistema de coordenadas para nombrar las casillas de la matriz. Nombremos las filas de arriba abajo por 𝑖𝑖𝑖𝑖 y las columnas por 𝑗𝑗𝑗𝑗 de tal forma que (0,0) es la casilla superior izquierda. Una matriz vendrá definida por su número de filas y su número de columnas: : 𝑛𝑛𝑛𝑛𝑓𝑓𝑓𝑓×𝑛𝑛𝑛𝑛𝑚𝑚𝑚𝑚. Una submatriz es una vista de una matriz definida por un vértice superior izquierdo y un tamaño de filas y columnas (𝑚𝑚𝑚𝑚,𝑖𝑖𝑖𝑖0, 𝑛𝑛𝑛𝑛𝑓𝑓𝑓𝑓,𝑗𝑗𝑗𝑗0, 𝑛𝑛𝑛𝑛𝑚𝑚𝑚𝑚). Es una idea similar a sublist. Una matriz la podemos dividir en cuatro vistas que denominaremos a, b, c, d. La vista a vendrá definida por (0, 𝑛𝑛𝑛𝑛𝑓𝑓𝑓𝑓/2,0, 𝑛𝑛𝑛𝑛𝑚𝑚𝑚𝑚/2) y de forma similar el resto. Cada submatriz tiene asociadas unas coordenadas locales tales que el vértice superior izquierdo es (0,0). Llamemos Matrix<E> al tipo que representa una matriz o una vista de esta. Las funciones para operar con este tipo son: • Matrix<E> of(E[][] datos): Una nueva matriz definida por un array • Matrix<E> zero(int nf, int nc): Una nueva matriz con todos sus elementos cero • Matrix<E> one(int n): Una nueva matriz unidad de n x n. • E get(int i, int j): El valor de la casilla i, j • void set(int i, int j, E value): Actualización de la casilla i, j con value. • View4<E> views(): Las cuatro vistas de una matriz • Matrix<E> compose(Matrix<E> a, Matrix<E> b, Matrix<E> c, Matrix<E> d): Construye una matriz a partir de sus vistas Con View4, como hemos comentado, de la forma: public record View4<D>(D a,D b,D c,D d) {} El método views() es el que consigue los subproblemas. Diseñamos la multiplicación de las dos matrices cuadradas 𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏. Teniendo en cuenta que �𝑎𝑎𝑎𝑎1𝑏𝑏𝑏𝑏1 𝑚𝑚𝑚𝑚1𝑑𝑑𝑑𝑑1�∗�𝑎𝑎𝑎𝑎2𝑏𝑏𝑏𝑏2 𝑚𝑚𝑚𝑚2𝑑𝑑𝑑𝑑2�=�𝑎𝑎𝑎𝑎1∗𝑎𝑎𝑎𝑎2 + 𝑏𝑏𝑏𝑏1∗𝑚𝑚𝑚𝑚2𝑎𝑎𝑎𝑎1∗𝑏𝑏𝑏𝑏2 + 𝑏𝑏𝑏𝑏1∗𝑑𝑑𝑑𝑑2 𝑚𝑚𝑚𝑚1∗𝑎𝑎𝑎𝑎2 + 𝑑𝑑𝑑𝑑1∗𝑑𝑑𝑑𝑑2𝑚𝑚𝑚𝑚1∗𝑏𝑏𝑏𝑏2 + 𝑑𝑑𝑑𝑑1∗𝑑𝑑𝑑𝑑2� Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Esquemas recursivos 133 Un algoritmo iterativo y otro recursivo son: Matrix<E> multiply(Matrix<E> in2){ Matrix<E> r = Matrix.zero(this.nf,in2.nc); for (int i = 0; i < this.nf; i++) { for (int j = 0; j < in2.nc; j++) { r.set(i,j,this.field.getZero()); for (int k = 0; k < this.nc; k++){ E val = (this.get(i,k).multiply(in2.get(k,j))) .add(r.get(i,j)); r.set(i,j,val); } } } return r; } Matrix<E> multiply_r(Matrix<E> m2){ Matrix<E> r; if(this.nc < 2 || this.nf < 2 || m2.nf < 2 || m2.nc < 2) { r = this.multiply(m2); } else { View4<Matrix<E>> v1 = this.views(); View4<Matrix<E>> v2 = m2.views(); Matrix<E> a = v1.a.multiply_r(v2.a) .add(v1.b.multiply_r(v2.c)); Matrix<E> b = v1.a.multiply_r(v2.b) .add(v1.b.multiply_r(v2.d)); Matrix<E> c = v1.c.multiply_r(v2.a) .add(v1.d.multiply_r(v2.c)); Matrix<E> d = v1.c.multiply_r(v2.b) .add(v1.d.multiply_r(v2.d)); r = Matrix.compose(a, b, c, d); } return r; } Como podemos que también la multiplicación iterativa y la recursiva tienen complejidad a Θ(𝑛𝑛𝑛𝑛3) 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 8𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛/2)+𝑛𝑛𝑛𝑛2,Θ�𝑛𝑛𝑛𝑛log28�= Θ(𝑛𝑛𝑛𝑛3) Esta complejidad puede reducirse aún más reordenado el cálculo en la forma (es el denominado algoritmo de Strassen): 𝑝𝑝𝑝𝑝1 = 𝑎𝑎𝑎𝑎(𝑓𝑓𝑓𝑓−ℎ),𝑝𝑝𝑝𝑝2 = (𝑎𝑎𝑎𝑎+𝑏𝑏𝑏𝑏)ℎ,𝑝𝑝𝑝𝑝3 = (𝑚𝑚𝑚𝑚+𝑑𝑑𝑑𝑑)𝑒𝑒𝑒𝑒,𝑝𝑝𝑝𝑝4 = 𝑑𝑑𝑑𝑑(𝑔𝑔𝑔𝑔−𝑒𝑒𝑒𝑒) Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Esquemas recursivos 134 𝑝𝑝𝑝𝑝5 = (𝑎𝑎𝑎𝑎+𝑑𝑑𝑑𝑑)(𝑒𝑒𝑒𝑒+ℎ),𝑝𝑝𝑝𝑝6 = (𝑏𝑏𝑏𝑏−𝑑𝑑𝑑𝑑)(𝑔𝑔𝑔𝑔+ℎ),𝑝𝑝𝑝𝑝7 = (𝑎𝑎𝑎𝑎−𝑚𝑚𝑚𝑚)(𝑒𝑒𝑒𝑒+𝑓𝑓𝑓𝑓) �𝑎𝑎𝑎𝑎1𝑏𝑏𝑏𝑏1 𝑚𝑚𝑚𝑚1𝑑𝑑𝑑𝑑1�∗�𝑎𝑎𝑎𝑎2𝑏𝑏𝑏𝑏2 𝑚𝑚𝑚𝑚2𝑑𝑑𝑑𝑑2�=�𝑝𝑝𝑝𝑝5 + 𝑝𝑝𝑝𝑝4−𝑝𝑝𝑝𝑝2 + 𝑝𝑝𝑝𝑝6𝑝𝑝𝑝𝑝1 + 𝑝𝑝𝑝𝑝2 𝑝𝑝𝑝𝑝3 + 𝑝𝑝𝑝𝑝4𝑝𝑝𝑝𝑝1 + 𝑝𝑝𝑝𝑝5−𝑝𝑝𝑝𝑝3−𝑝𝑝𝑝𝑝7� Para la multiplicación de matrices podemos seguir, también, el esquema siguiente que como podemos comprobar tendrá asociada la ecuación de recurrencia 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 7𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛/2)+𝑛𝑛𝑛𝑛2, Θ�𝑛𝑛𝑛𝑛log27�= Θ(𝑛𝑛𝑛𝑛2.8) Partir de un conjunto de propiedades Esta es una estrategia muy adecuada cuando se disponen de propiedades sobre el problema que queremos resolver. Pero disponer de propiedades no es lo mismo que disponer de una definición recursiva. Una definición recursiva especifica la solución de un problema en base a otros problemas de tamaño menor y, además, da la solución para los casos base. Un conjunto de propiedades normalmente tiene que ser completada para convertirlo en una definición de recursiva. Pero cuando disponemos de un conjunto de propiedades debemos aprovecharlas. Las siguientes son propiedades de la factorial, pero no constituyen una definición recursiva. 𝑛𝑛𝑛𝑛! = �(𝑛𝑛𝑛𝑛+ 1)! 𝑛𝑛𝑛𝑛+ 1 ,𝑛𝑛𝑛𝑛≥0 𝑛𝑛𝑛𝑛! = 𝑛𝑛𝑛𝑛∗(𝑛𝑛𝑛𝑛−1)! 1! = 1 0! = 1 Escogiendo n como tamaño podemos construir un algoritmo con la segunda y la cuarta, pero no podemos usar la primera porque indica la solución en base a la de otro problema de tamaño mayor. La definición recursiva es: 𝑛𝑛𝑛𝑛! = �1, 𝑛𝑛𝑛𝑛= 0 𝑛𝑛𝑛𝑛∗(𝑛𝑛𝑛𝑛−1)!, 𝑛𝑛𝑛𝑛> 1 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Partir de un conjunto de propiedades
Esquemas recursivos 135 Otro ejemplo es calcular el máximo común divisor de a, b partiendo de las propiedades: • El entero a%b tiene los mismos divisores que los divisores comunes entre a, b. Esto puede ser fácilmente demostrado porque cualquier número que divida a a,b también divide a a%b. • El máximo común divisor de a, 0 es 0. Lo cual es evidente. Con lo anterior podemos escoger un estado de tipo (a,b) y comprobar que sus divisores comunes lo son también a (b, a%b). Si escogemos como tamaño b vemos que podemos definir una secuencia de estado que van manteniendo el conjunto de divisores comunes hasta llegar a un del tipo (a,0). La definición recursiva es: 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑑𝑑𝑑𝑑(𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏) = �𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏= 0 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑑𝑑𝑑𝑑(𝑏𝑏𝑏𝑏,𝑎𝑎𝑎𝑎%𝑏𝑏𝑏𝑏), 𝑏𝑏𝑏𝑏> 0 Esta definición es recursiva final como ya hemos visto anteriormente y tiene un equivalente iterativo. Es el llamado algoritmo de Euclides. Un ejemplo más complejo es el número combinatorio. Los números combinatorios tienen las propiedades: ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ �𝑛𝑛𝑛𝑛0�=�𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛�= 1, 𝑛𝑛𝑛𝑛≥0 �𝑛𝑛𝑛𝑛1�=�𝑛𝑛𝑛𝑛 𝑛𝑛𝑛𝑛−1�=𝑛𝑛𝑛𝑛,𝑛𝑛𝑛𝑛≥1 �𝑛𝑛𝑛𝑛𝑘𝑘𝑘𝑘�=�𝑛𝑛𝑛𝑛 𝑛𝑛𝑛𝑛−𝑘𝑘𝑘𝑘�,𝑛𝑛𝑛𝑛≥𝑘𝑘𝑘𝑘 �𝑛𝑛𝑛𝑛𝑘𝑘𝑘𝑘�+�𝑛𝑛𝑛𝑛 𝑘𝑘𝑘𝑘+ 1�=�𝑛𝑛𝑛𝑛+ 1 𝑘𝑘𝑘𝑘+ 1�,𝑛𝑛𝑛𝑛≥𝑘𝑘𝑘𝑘 Escogiendo como tamaño n tenemos el algoritmo recursivo: �𝑛𝑛𝑛𝑛𝑘𝑘𝑘𝑘�=�1, 𝑘𝑘𝑘𝑘,𝑛𝑛𝑛𝑛−𝑘𝑘𝑘𝑘= 0 𝑛𝑛𝑛𝑛,𝑘𝑘𝑘𝑘,𝑛𝑛𝑛𝑛−𝑘𝑘𝑘𝑘= 1 �𝑛𝑛𝑛𝑛−1 𝑘𝑘𝑘𝑘−1�+�𝑛𝑛𝑛𝑛−1 𝑘𝑘𝑘𝑘�,𝑘𝑘𝑘𝑘> 1 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Esquemas recursivos 136 A partir de una restricción de entrada salida Como ejemplo de la última estrategia definir una restricción entrada salida y a partir de ella encontrar un algoritmo que la verifique veamos el ejemplo de más abajo. Una restricción entrada salida es un predicado que relaciona los parámetros de entrada con los resultados del algoritmo ignorando las variables intermedias del mismo. Esto implica encontrar un estado y un invariante. Este invariante se suele obtener por relajación de la restricción de entrada salida y a partir de ellos encontrar una relación recursiva. La relación recursiva implica un concepto de tamaño porque el subproblema debe ser de un tamaño más pequeño que el problema. Como ejemplo veamos cómo obtener un algoritmo para que dados dos enteros a, b podamos encontrar su cociente y su resto: c, r. Los parámetros de entrada son a, b y lo de salida c,r. La restricción entrada salida: 𝑅𝑅𝑅𝑅(𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏,𝑚𝑚𝑚𝑚,𝑟𝑟𝑟𝑟)≡ 𝑎𝑎𝑎𝑎 = 𝑏𝑏𝑏𝑏∗𝑚𝑚𝑚𝑚+𝑟𝑟𝑟𝑟 ∧ 𝑟𝑟𝑟𝑟<𝑏𝑏𝑏𝑏∧ 𝑟𝑟𝑟𝑟<𝑚𝑚𝑚𝑚∧ 𝑎𝑎𝑎𝑎≥0∧ 𝑏𝑏𝑏𝑏> 0 Imaginemos un estado formado por (𝑎𝑎𝑎𝑎1, 𝑏𝑏𝑏𝑏1, 𝑚𝑚𝑚𝑚1, 𝑟𝑟𝑟𝑟1) con un invariante relajado de la relación anterior 𝐼𝐼𝐼𝐼(𝑎𝑎𝑎𝑎1, 𝑏𝑏𝑏𝑏1, 𝑚𝑚𝑚𝑚1, 𝑟𝑟𝑟𝑟1) ≡ 𝑎𝑎𝑎𝑎1 = 𝑏𝑏𝑏𝑏1∗𝑚𝑚𝑚𝑚1 + 𝑟𝑟𝑟𝑟1 ∧ 𝑎𝑎𝑎𝑎≥0∧ 𝑏𝑏𝑏𝑏> 0 Si expresamos la restricción en la forma 𝑎𝑎𝑎𝑎1 = 𝑏𝑏𝑏𝑏1∗𝑚𝑚𝑚𝑚1 + 𝑏𝑏𝑏𝑏1−𝑏𝑏𝑏𝑏1 + 𝑟𝑟𝑟𝑟1 = 𝑏𝑏𝑏𝑏1∗(𝑚𝑚𝑚𝑚1 + 1) + 𝑟𝑟𝑟𝑟1 − 𝑏𝑏𝑏𝑏1 Lo cual quiere decir que la tupla (a1,b1,c1+1,r1-b1) cumple el invariante y además ha decrecido la cantidad r1-b1 que ha pasado a ser r1 a r1-b1. Teniendo en cuenta que a, b no cambian tenemos la definición recursiva: 𝑚𝑚𝑚𝑚𝑟𝑟𝑟𝑟(𝑚𝑚𝑚𝑚1, 𝑟𝑟𝑟𝑟1)=�(𝑚𝑚𝑚𝑚1, 𝑟𝑟𝑟𝑟1), 𝑟𝑟𝑟𝑟1−𝑏𝑏𝑏𝑏< 0 𝑚𝑚𝑚𝑚𝑟𝑟𝑟𝑟(𝑚𝑚𝑚𝑚1 + 1, 𝑟𝑟𝑟𝑟1−𝑏𝑏𝑏𝑏1), 𝑟𝑟𝑟𝑟1−𝑏𝑏𝑏𝑏≥0 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla A partir de una restricción de entrada salida
Esquemas recursivos 137 Claramente el problema requiere un problema inicial. Este podría ser (a,b,0,a). Tal como podemos ver la definición es recursiva final y por lo tanto podemos escribir un algoritmo recursivo. public static record Cr(Integer c, Integer r) {} public static Cr cr(Integer a, Integer b) { return cr(a,b,0,a); } public static Cr cr(Integer a,Integer b,Integer c,Integer r) { Cr s = new Cr(c,r); if(r-b>0){ s = cr(a,b,c+1,r-b); } return s; } El algoritmo tiene un equivalente iterativo. La asignación de tuplas puede desplegarse en este caso fácilmente y para el resultado usamos un record: public static record Cr(Integer c, Integer r) {} Cr cr(Integer a, Integer b) { Integer c = 0; Integer r = a; while(r-b>0){ c = c+1; r = r-b; } return new Cr(c,r); } La versión funcional se deja como ejercicio. En este caso el diseño recursivo nos ha llevado a un algoritmo iterativo por resultar la definición recursiva final. Transformaciones recursivo-iterativo en recursividad simple Después de aplicadas las estrategias de diseño de algoritmos obtenemos algoritmos recursivos de diversos tipos: recursivos simples y múltiples y entre los simples finales y no finales. Veamos ahora estrategias de transformación de estos algoritmos recursivos. En primer lugar veamos las transformaciones de los algoritmos recursivos simples. Si son finales Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Transformacionesrecursivo-iterativoenrecursividadsimple
Esquemas recursivos 144 Este esquema se puede implementar con memoria y sin memoria. Llamémoslos fbsm, fbm. El de problema de Fibonacci es el caso concreto a=b=1, d0 =0, d1 = 1. Definimos el problema generalizado con el estado 𝑒𝑒𝑒𝑒=(𝑖𝑖𝑖𝑖,𝑡𝑡𝑡𝑡,𝑣𝑣𝑣𝑣) y el invariante 𝑡𝑡𝑡𝑡=𝑓𝑓𝑓𝑓𝑏𝑏𝑏𝑏𝑖𝑖𝑖𝑖(𝑖𝑖𝑖𝑖+ 1),𝑣𝑣𝑣𝑣=𝑓𝑓𝑓𝑓𝑏𝑏𝑏𝑏𝑖𝑖𝑖𝑖(𝑖𝑖𝑖𝑖). El problema final es 𝑖𝑖𝑖𝑖=𝑛𝑛𝑛𝑛. Un problema inicial que cumple el invariante es (0,1,0). Decidimos incrementar en cada paso la variable i en 1. Pretendemos deducir de la invariante y del incremento decidido para i la función siguiente. (i’,u’,v’) = (i+1, fbi(i+2), fbi(i+1)) = (i+1, fbi(i+1)+fbi(i), fib(i+1)) = (i+1, a*u+b*v, u) Y de aquí el esquema resultante es: fblin(n,a,b,d1,d0){ (i,u,v) = (0,d1,d0); while(i < n){ (i,u,v) = (i+1,a*u+b*v,u); } return v; } Desplegando la asignación paralela: fblin(n,a,b,d1,d0){ i = 0; u = d1; v = d2; while(i < n){ i = i+1; u0 = u; u = a*u+b*v; v = u0; } return v; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Esquemas recursivos 145 Aunque con el método anterior es posible hay otro método más sencillo y general usando un Map de la forma: Long rc(Integer n,Integer a,Integer b,Long d0,Long d1) { Map<Integer,Long> m = new HashMap<>(); for(int i=0; i<=n; i++) { if(i==0) m.put(0,d0); else if(i==1) m.put(1,d1); else { Long r = a*m.get(i-1)+b*m.get(i-2); m.put(i,r); } m.remove(i-3); } return m.get(n); } La clave está en recorrer los valores de i bottom-up. En esta estrategia es muy importante liberar los datos de la memoria que no son necesarios Números combinatorios La idea anterior se puede generalizar a un conjunto variable de subproblemas usando un Map para mantener las soluciones ya calculadas. Veamos como ejemplo de este caso el cálculo del número combinatorio. �𝑛𝑛𝑛𝑛𝑘𝑘𝑘𝑘�=�1, 𝑘𝑘𝑘𝑘,𝑛𝑛𝑛𝑛−𝑘𝑘𝑘𝑘= 0 𝑛𝑛𝑛𝑛,𝑘𝑘𝑘𝑘,𝑛𝑛𝑛𝑛−𝑘𝑘𝑘𝑘= 1 �𝑛𝑛𝑛𝑛−1 𝑘𝑘𝑘𝑘−1�+�𝑛𝑛𝑛𝑛−1 𝑘𝑘𝑘𝑘�,𝑘𝑘𝑘𝑘> 1 esquema iterativo equivalente comienza con los casos base y va calculando todos los problemas de tipo �𝑖𝑖𝑖𝑖𝑗𝑗𝑗𝑗� para los valores posibles de 𝑖𝑖𝑖𝑖 en [0, 𝑛𝑛𝑛𝑛] y 𝑗𝑗𝑗𝑗 en [0, 𝑖𝑖𝑖𝑖] a partir de las soluciones de los problemas �𝑖𝑖𝑖𝑖−1 𝑗𝑗𝑗𝑗−1� , �𝑖𝑖𝑖𝑖−1 𝑗𝑗𝑗𝑗� que ya han debido ser calculados. Vamos incrementando uno a uno el valor de i desde 0 hasta alcanzar n y de j de 0 a i. Hemos de tener en cuenta que para los casos base ya tenemos la solución y para los casos recursivos la tenemos en la memoria. El esquema iterativo es: Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Esquemas recursivos 146 record Bn(Long a, Long b) { public static Bn of(Long a, Long b) { return new Bn(a,b); } } Long binom(Long n, Long k) { Map<Bn,Long> m = new HashMap<>(); for(long i=0; i<=n; i++) { for(long j=0; j<=i;j++) { if(j==0) m.put(Bn.of(i, 0L),1L); else if(j==1 || i-j ==1) m.put(Bn.of(i,j),i); else { Long r = m.get(Bn.of(i-1, j-1))+ m.get(Bn.of(i-1, j-1)); m.put(Bn.of(i,j),r); } m.remove(Bn.of(i-2,k)); } } return m.get(Bn.of(n, k)); } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
147 Recursividad múltiple y acumuladores paralelos os agregados de datos pueden ser convertidos en flujos de datos para ser acumulados. Los flujos de datos obtenidos pueden ser secuenciales o paralelos. Un flujo de datos secuencial va proporcionando uno tras otro, en algún orden, los elementos del agregado. Esto se implementa, como ya hemos visto, construyendo un iterable a partir del agregado. Un agregado de datos también puede proporcionar un flujo de datos paralelo. Este divide el agregado en partes, que se puede volver a subdividir las veces que sean necesarias hasta que cada parte es suficientemente pequeña y posteriormente ofrece uno tras otro los datos de cada parte. En Java un flujo de datos se representa por el tipo Stream. El tipo Stream puede representar un flujo secuencial de datos y también un flujo de datos paralelo. La vista secuencial del tipo Stream<E>, que se obtiene con el método iterator(), devuelve un Iterator<E> como ya hemos visto. L Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Recursividadmúltipleyacumuladoresparalelos
Recursividad múltiple y acumuladores paralelos 148 Para entender el funcionamiento paralelo de Stream<E> y el acumulador paralelo asociado recordemos el esquema que vimos asociado a la vista View2 R algr(D d) { B b = algr2(s); return r(b); } B algr(D d){ B r; if(d.size() < u){ r = reduce(d,f,b0); }else{ View2<D> (left,right) = view2e(d); R rl = algr(left); R rr = algr(right); r = c(rl,rr); } return r; } Para acercarnos aún más al tipo Stream<E> asumimos que el tipo B es mutable, que b0 es un Supplier<B>, es decir ()->b0, que f es BiConsumer<B,E>, es decir ((b,e)->b.c(e)) y c es BinaryOperator<B>, es decir (b1,b2) -> op(b1,b2). Supongamos además que disponemos de m procesadores. La idea del algoritmo anterior es la siguiente: divide el agregado de datos de dos partes y continúa dividiendo recursivamente hasta que el tamaño del agregado este por debajo de un umbral u. Cuando lo consigue pasa ese agregado a un procesador para que resuelva el problema iterativamente usando un algoritmo de tipo reduce, que ya hemos estudiado, con parámetros f y b0. Los resultados conseguidos por cada procesador serán de tipo B y se irán combinando con el operador binario c. Intuitivamente podemos ver que si el algoritmo se ejecuta sobre un solo procesador y tarda un tiempo T entonces al disponer de m procesadores conseguiremos un tiempo de T/m. Evidentemente habrá costes adicionales que no vamos a tener en cuenta de paso de un procesador a otro. El algoritmo se puede sintetizar en un flujo de datos paralelo, un Spliterator<E> y un acumulador paralelo, un Collector<E,B,R>. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Recursividad múltiple y acumuladores paralelos 149 La vista paralela del tipo Stream<E> se puede obtener mediante el método spliterator() que devuelve un Spliterator<E>. Un Spliterator<E> sobre un agregado de datos está asociado a la View2 de es agregado. Tiene los métodos: interface Spliterator<E> { boolean tryAdvance(Consumer<? super T> action); // Intenta consumir un elemento Spliterator() trySplit(); // Intenta partir el agregado de datos. Si puede // devuelve una parte y si no puede null } El método trySplit() es equivalente al siguiente código que utiliza una vista: if(d.size() < nu){ B b = reduce(d,f,b0); }else{ View2<D> (left,right) = view2e(d); El método trySplit() divide el agregado de datos en dos partes si su tamaño es suficientemente grande. Una parte queda cubierta por el nuevo Spliterator y la otra por el antiguo. Si el tamaño del agregado es pequeño el método trySplit() devuelve null. El método tryAdvance va consumiendo los elementos del agregado uno tras otro para conseguir una reducción iterativa. Este método usa un iterador del flujo de datos, una función de combinación y un elemento inicial. El iterador se pude conseguir del Spliterator mediante el método Es decir es el esquema reduce(d,f,b0) It it = it(d); B b = ()->b0(); do { boolean r = this.tryAdvance(f); } while(r); El método tryAdvance intenta consumir un elemento. Si lo consigue devuelve true y si no lo consigue false. Al consumir un elemento ejecuta la acción f. A su vez los acumuladores podemos clasificarlos en acumuladores secuenciales y paralelos. Cada uno de ellos es adecuado al tipo de flujo, Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Recursividad múltiple y acumuladores paralelos 150 secuencial o paralelo, que tengamos. Los algoritmos secuenciales que vimos anteriormente tienen asociados un flujo de datos secuencial, que define una secuencia, y un acumulador secuencial. Los acumuladores paralelos se asocian a flujos de datos paralelos y a algoritmos recursivos. Ya vimos las propiedades de un acumulador secuencial. Vemos ahora las del paralelo. Muchas de ellas son similares. Siendo 𝑒𝑒𝑒𝑒 un elemento del flujo a acumular, de tipo 𝐸𝐸𝐸𝐸, 𝑏𝑏𝑏𝑏 la base del acumulador de 𝐵𝐵𝐵𝐵 y 𝑟𝑟𝑟𝑟 el valor devuelto, de tipo 𝑅𝑅𝑅𝑅, los acumuladores secuenciales tienen las funciones: • Valor inicial 𝑏𝑏𝑏𝑏0 de la base del acumulador • Función de acumulación (𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒)→𝑚𝑚𝑚𝑚(𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒). • Función de retorno 𝑏𝑏𝑏𝑏→𝑟𝑟𝑟𝑟(𝑏𝑏𝑏𝑏). • Función de cortocircuito 𝑏𝑏𝑏𝑏→𝑑𝑑𝑑𝑑(𝑏𝑏𝑏𝑏) Los acumuladores paralelos están pensados para poder dividir el flujo de entrada en varias partes, acumular cada parte y posteriormente combinar los resultados. Tienen las funciones: • Valor inicial de la base 𝑏𝑏𝑏𝑏0 del tipo B de la base del acumulador • Función de acumulación secuencial de un elemento en la base (𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒)→ 𝑓𝑓𝑓𝑓(𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒). • Función de combinación de dos bases (𝑏𝑏𝑏𝑏1, 𝑏𝑏𝑏𝑏2)→𝑚𝑚𝑚𝑚(𝑏𝑏𝑏𝑏1, 𝑏𝑏𝑏𝑏2) . Deber ser asociativa y tener elemento neutro. • Función de retorno 𝑏𝑏𝑏𝑏→𝑟𝑟𝑟𝑟(𝑏𝑏𝑏𝑏). Por otra parte, el acumulador será mutable o inmutable según lo sea el tipo 𝐵𝐵𝐵𝐵 de la base del acumulador. Estos acumuladores se implementan por el tipo Collector<E,B,R> que tiene los siguientes métodos: • Supplier<B> supplier(). Proporciona el valor inicial de la base. Es 𝑏𝑏𝑏𝑏0. • BiConsumer<B,E> consumer(). Acumula secuencialmente en la base el nuevo elemento. Es 𝑓𝑓𝑓𝑓(𝑏𝑏𝑏𝑏,𝑒𝑒𝑒𝑒) • BinaryOperator<B> combiner(). Combina dos valores de la base obtenidos de resultados procesados en paralelo. Es 𝑚𝑚𝑚𝑚(𝑏𝑏𝑏𝑏1, 𝑏𝑏𝑏𝑏2). Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Recursividad múltiple y acumuladores paralelos 151 • Function<B,R> finisher(). Calcula el resultado a partir del valor de la base. Es 𝑟𝑟𝑟𝑟(𝑏𝑏𝑏𝑏). En Java se nos proporciona un método de factoría para crear acumuladores: <E,B,R> Collector<E,B,R> Collector.of( Supplier<B> supplier, BiConsumer<B,E> accumulator, BinaryOperator<B> combiner, Function<B,R> finisher ) Este método asume que el tipo de la base es mutable. Si la base es inmutable un adaptador adecuado es: Collector<E,MutableType<B>,R> ofBaseInmutable( Supplier<B> supplier, BiFunction<B,E,B> consumer, BinaryOperator<B> combiner, Function<B,R> finisher){ return Collector.of( ()->MutableType.of(supplier.get()), (b,e)->b.newValue(consumer.apply(b.value,e)), (x,y)->MutableType.of(combiner.apply(x.value,y.value)), x->finisher.apply(x.value)); } Y el método del tipo Stream para acumular el flujo de datos mediante un acumulador paralelo es: <R,B> R collect(Collector<? super E,B,R> collector); Que se usa en la forma: R f(x) { Collector<E,B,R> a = Collectors…; R r = Stream.iterate(e0, e->g(e), e->s(e)).collect(a); return r; } Una implementación secuencial de la acumulación crearía la base de un acumulador utilizando la función de creación proporcionada, invocaría la función de acumulación una vez para cada elemento del flujo de datos. Una Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Recursividad múltiple y acumuladores paralelos 152 implementación paralela dividiría el flujo de datos, crearía una base del acumulador para cada parte, acumularía el contenido de cada parte en su respectivo acumulador, y luego usaría la función de combinación para fusionar los resultados parciales. Una implementación paralela posible de ese método collect es: R collect(Stream<E> flow, Collector<E,B,R> c) { B b = collect(flow.spliterator(),c); return c.finisher().apply(b); } B collect(Spliterator<E> flow, Collector<E,B,R> c) { B b; Spliterator<E> f2 = flow.trySplit(); if(f2 != null){ B b1 = collect(f2,c); B b2 = collect(flow,c); b = c.combiner().apply(b1,b2); } else { b = c.supplier().get(); Boolean r; do { r = flow.tryAdvance(e->c.accumulator() .accept(b,e)); }while(r); } return b; } La implementación paralela es, en realidad, más compleja. Aquí la acumulación paralela se ha presentado como un algoritmo recursivo. Para que sea paralelo, además, cada vez que se divide el flujo hay que crear una nueva hebra que pueda ser asignada a uno de los procesadores disponibles. Para crear un acumulador paralelo que acumule un flujo en un multiconjunto los divisores de todos los números enteros entre a y b. <E> Collector<E,Multiset<E>,Multiset<E>> toMultiset() { return Collector.of( ()->Multiset.create(), (x,e)->x.add(e), (x,y)->Multiset.add(x, y), x->x); } Multiset<Long> rr4 = Stream.iterate(a,x->x<b,x->x+1) .flatMap(x->divisores(x)) .collect(Collectors2.toMultiset()); Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Recursividad múltiple y acumuladores paralelos 153 Un problema de recursividad múltiple se puede transformar en muchos casos en un flujo de datos paralelo y un acumulador paralelo. Las condiciones para que esto sea posible son: • Un problema de tamaño grande debe poder ser dividido en dos partes separadas y su solución debe ser una combinación de la solución de las dos partes. La solución del problema se obtendrá combinando la de las dos partes mediante una función (combiner). • Un problema de tamaño pequeño debe poder considerado como un flujo de datos secuencial y su solución se puede obtener acumulando por la izquierda ese flujo secuencial mediante un acumulador secuencial de base mutable. En definitiva un problema de recursividad múltiple se puede transformar en un flujo de datos paralelo si podemos implementar un SplitIterator<E> con los datos del problema. El algoritmo de ordenación mergeSort puede ponerse en forma de flujo paralelo más acumulador. Para ello necesitamos un flujo de datos paralelo. Es decir un Stream<E> y una implementación de Collector<E,B,R> con los detalles: Collector<E,List<E>,List<E>> mergeSort(Comparator<E> cmp) { return Collector.of( ()->new ArrayList<>(), (x,e)->Lists2.insertOrdered(x,e,cmp), (x,y)->Lists2.mergeOrdered(x,y,cmp), x->x); } Las funciones usadas pueden verse en el repositorio. Y la forma de usarlo: public static void main(String[] args) { Random r = new Random(System.nanoTime()); Stream<Integer> s = r.ints(5000).boxed(); List<Integer> rr = s.parallel() .collect(Collectors2.mergeSort()); Strings2.toConsole(rr, "Ordenada"); } Como hemos visto hay una gran relación entre un Spliterator<E> y las vistas View1<D,E> y View2<D,E>. Es posible hacer una implementación de Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de algoritmos recursivos simples a iterativos 256 Es evidente que si alguno de 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖 es cero el producto también lo será. Cuando todos los 𝑚𝑚𝑚𝑚𝑖𝑖𝑖𝑖 son distintos de cero podemos usar los mismos algoritmos que antes pero ahora el acumulador será producto en lugar de suma. Tomado los coeficientes de menor a mayor y acumulando por la izquierda tenemos el algoritmo siguiente que usaremos más abajo: Double prodI(List<Double> c, Double v){ Double b = 1.; Integer i = 0; Double p = 1.; Integer n = c.size(); while(i<n) { Double cf = p*c.get(i); i = i+1; p = p*v; b = b * cf; } return b; } Problemas con dígitos de un número entero Veamos ahora diversos problemas con dígitos de enteros en base a. • Contar cuantos dígitos son cero en la representación en base a de n • Obtener una lista con los dígitos de un número n en base a. • A partir de una lista con los dígitos de un número n en base a obtener n. • Dado un entero n en base a obtener otro m cuyos dígitos en la misma base estén invertidos. Ejemplo: sean inversos invierte (1024,10) =4201. Sea n el entero, a la base, 𝑑𝑑𝑑𝑑𝑖𝑖𝑖𝑖 los dígitos de n en esa base y r el orden del primer dígito entonces podemos expresar: 𝑛𝑛𝑛𝑛= 𝑑𝑑𝑑𝑑𝑟𝑟𝑟𝑟𝑎𝑎𝑎𝑎𝑟𝑟𝑟𝑟+⋯+𝑑𝑑𝑑𝑑1𝑎𝑎𝑎𝑎1+𝑑𝑑𝑑𝑑0= 𝑑𝑑𝑑𝑑0+𝑑𝑑𝑑𝑑1𝑎𝑎𝑎𝑎1+⋯+𝑑𝑑𝑑𝑑𝑟𝑟𝑟𝑟𝑎𝑎𝑎𝑎𝑟𝑟𝑟𝑟 𝑛𝑛𝑛𝑛%𝑎𝑎𝑎𝑎=𝑑𝑑𝑑𝑑0 En definitiva, un entero puede ser expresado como un polinomio cuyos coeficientes son los dígitos en una determinada base a. La secuencia de los Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Problemascondígitosdeunnúmeroentero
Problemas de algoritmos recursivos simples a iterativos 257 dígitos de menor a mayor significación, 𝑑𝑑𝑑𝑑0,𝑑𝑑𝑑𝑑1,…,𝑑𝑑𝑑𝑑𝑟𝑟𝑟𝑟, puede ser generada por: 𝑙𝑙𝑙𝑙=�𝑛𝑛𝑛𝑛,𝑒𝑒𝑒𝑒→𝑒𝑒𝑒𝑒> 0, 𝑒𝑒𝑒𝑒→𝑒𝑒𝑒𝑒𝑎𝑎𝑎𝑎�.𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎(𝑒𝑒𝑒𝑒→𝑒𝑒𝑒𝑒%𝑎𝑎𝑎𝑎) Esta secuencia genera los dígitos de menor a mayor: es decir [𝑑𝑑𝑑𝑑0,𝑑𝑑𝑑𝑑1,..,𝑑𝑑𝑑𝑑𝑟𝑟𝑟𝑟]. Si en esa secuencia filtramos los dígitos que son cero y la acumulamos con el acumulador contador obtenemos el primer resultado. El acumulador contador puede acumularse por la izquierda o por la derecha. Por la izquierda en forma iterativa resulta: Integer numeroDeCeros(Integer n, Integer a){ Integer b = 0; while(n>0) { Integer d = n%a; if(d == 0){ b = b+1; } n = n/a; } return b; } 14. Obtener la representación de n en base a. Si acumulamos la secuencia s anterior con el acumulador toList obtendremos una lista con los dígitos. Dado que el operador concatenar listas es no conmutativo las listas que se obtienen acumulando por la izquierda y por la derecha son inversas. Como s genera los dígitos de menor a mayor y queremos la lista con los dígitos de mayor a menor acumulamos la secuencia por la derecha con el acumulador toList. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de algoritmos recursivos simples a iterativos 258 El código recursivo es: List<Integer> digitos(Integer n, Integer a){ List<Integer> r; if(n>a) { r = digitos(n/a,a); Integer d = n%a; r.add(d) } else { r = new Arraylist<>(); } return r; } Este es un algoritmo recursivo no final, pero teniendo en cuentas las propiedades del operador de concatenación podemos disponer de un algoritmo iterativo: List<Integer> digitosI(Integer n, Integer a){ List<Integer> b = new ArrayList<>(); while(n>0) { Integer d = n%a; b.add(0,d); n = n/a; } return b; } 15. Obtener el entero asociado a una lista de dígitos Es similar a evaluar el polinomio correspondiente donde la variable toma la base como valor. Como la secuencia está de mayor a menor acumulamos por la derecha. A partir de los dígitos de mayor a menor y acumulando por Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de algoritmos recursivos simples a iterativos 259 la derecha la secuencia [𝑑𝑑𝑑𝑑𝑟𝑟𝑟𝑟,𝑑𝑑𝑑𝑑𝑟𝑟𝑟𝑟−1,..,𝑑𝑑𝑑𝑑0] con el acumulador de Horner 𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚= (0, (𝑏𝑏𝑏𝑏,𝑑𝑑𝑑𝑑)→𝑏𝑏𝑏𝑏∗𝑎𝑎𝑎𝑎+𝑑𝑑𝑑𝑑) y resulta el código siguiente: Long entero(List<Integer> digitos, Integer a){ return entero(digitos, a,0,d.size()); } Long entero(List<Integer> digitos, Integer a,Integer i,Integer n){ Long b = 0; if(n-i> 0){ b = entero(digitos, a, i + 1, n); Integer d = digitos[i); b = b * a + d; } return b; } 16. Construir un entero m cuya representación en una base a sea inversa que la de n. Partimos de la secuencia de dígitos de n generados por la secuencia 𝑙𝑙𝑙𝑙=�𝑛𝑛𝑛𝑛,𝑒𝑒𝑒𝑒→𝑒𝑒𝑒𝑒> 0, 𝑒𝑒𝑒𝑒→𝑒𝑒𝑒𝑒𝑛𝑛𝑛𝑛�.𝑚𝑚𝑚𝑚𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎(𝑒𝑒𝑒𝑒→𝑒𝑒𝑒𝑒%𝑎𝑎𝑎𝑎) Y la acumulamos por la izquierda con el acumulador 𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚 anterior la secuencia de dígitos de mayor a menor obtenemos m que se ha pedido. Esto nos da: Integer inverso(Integer n, Integer a){ Integer b = 0; while(n > 0){ Integer d =n%a; b = b * a + d; n = n/a; } return b; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de algoritmos recursivos simples a iterativos 260 El problema de la potencia entera Veamos la forma de obtener un algoritmo iterativo de complejidad log 𝑛𝑛𝑛𝑛 para la potencia entera. Una definición para la potencia entera es: 𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛=�1, 𝑛𝑛𝑛𝑛= 0 (𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛/2)2𝑎𝑎𝑎𝑎,𝑛𝑛𝑛𝑛> 0, 𝑛𝑛𝑛𝑛%2 == 1 (𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛/2)2,𝑛𝑛𝑛𝑛> 0, 𝑛𝑛𝑛𝑛%2 == 0 Esta definición nos proporciona la secuencia 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙= (𝑛𝑛𝑛𝑛,𝑛𝑛𝑛𝑛→𝑛𝑛𝑛𝑛> 0, 𝑛𝑛𝑛𝑛→ 𝑛𝑛𝑛𝑛/2) y un acumulador por la derecha 𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚= (1, 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚(𝑚𝑚𝑚𝑚,𝑒𝑒𝑒𝑒)) cuya la función de acumulación es: 𝑚𝑚𝑚𝑚(𝑚𝑚𝑚𝑚,𝑛𝑛𝑛𝑛)=�𝑎𝑎𝑎𝑎𝑚𝑚𝑚𝑚2,𝑛𝑛𝑛𝑛%2 == 1 𝑚𝑚𝑚𝑚2,𝑛𝑛𝑛𝑛%2 == 0 El código equivalente es: Long pot(Long a, Integer n) { Long r = 1; if(n>0){ r = pot(a,n/2); r = r*r; if(n%2 == 1) r = r * a; } return r; } En este caso podemos encontrar una secuencia s’ y un acumulador a’ que acumulados por la izquierda dan el mismo resultado que la anterior secuencia y acumulador acumulados por la derecha. Estas secuencia y acumulador son: 𝑙𝑙𝑙𝑙1 = �(𝑛𝑛𝑛𝑛,𝑎𝑎𝑎𝑎),(𝑛𝑛𝑛𝑛,𝑒𝑒𝑒𝑒)→𝑛𝑛𝑛𝑛> 0, (𝑛𝑛𝑛𝑛,𝑒𝑒𝑒𝑒)→�𝑛𝑛𝑛𝑛2,𝑒𝑒𝑒𝑒∗𝑒𝑒𝑒𝑒�� 𝑙𝑙𝑙𝑙′=𝑙𝑙𝑙𝑙1. 𝑓𝑓𝑓𝑓𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑒𝑒𝑒𝑒𝑖𝑖𝑖𝑖((𝑛𝑛𝑛𝑛,𝑒𝑒𝑒𝑒)→𝑛𝑛𝑛𝑛%2 == 1) 𝑎𝑎𝑎𝑎′= (1, (𝑚𝑚𝑚𝑚, (𝑛𝑛𝑛𝑛,𝑒𝑒𝑒𝑒))→𝑚𝑚𝑚𝑚∗𝑒𝑒𝑒𝑒) Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Elproblemadelapotenciaentera
Problemas de algoritmos recursivos simples a iterativos 261 Y el algoritmo iterativo equivalente: Long pot(Long a, Integer n){ Long e = a; Long b = 1; while(n > 0){ if(n%2==1){ b = b * e; } e = e * e; n = n/2; } return b; } La razón de lo anterior es tener en cuenta que: 𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛= 𝑎𝑎𝑎𝑎∑𝑑𝑑𝑑𝑑𝑖𝑖𝑖𝑖2𝑖𝑖𝑖𝑖 𝑝𝑝𝑝𝑝 0=�𝑎𝑎𝑎𝑎𝑑𝑑𝑑𝑑𝑖𝑖𝑖𝑖2𝑖𝑖𝑖𝑖=�𝑎𝑎𝑎𝑎𝑑𝑑𝑑𝑑𝑖𝑖𝑖𝑖2𝑖𝑖𝑖𝑖 𝑝𝑝𝑝𝑝0 𝑝𝑝𝑝𝑝0 Podemos ver que la expresión de la derecha podemos considerarla como el producto (acumulador) de una secuencia cuyos elementos son: 𝑎𝑎𝑎𝑎𝑑𝑑𝑑𝑑𝑖𝑖𝑖𝑖2𝑖𝑖𝑖𝑖. Siendo 𝑑𝑑𝑑𝑑𝑖𝑖𝑖𝑖 la secuencia invertida de los dígitos binarios de 𝑛𝑛𝑛𝑛. Es decir lo valores 0, 1 por lo que los elementos de la secuencia son 1 si 𝑑𝑑𝑑𝑑𝑖𝑖𝑖𝑖= 0 y 𝑎𝑎𝑎𝑎2𝑖𝑖𝑖𝑖, si 𝑑𝑑𝑑𝑑𝑖𝑖𝑖𝑖= 1. Observemos que 𝑎𝑎𝑎𝑎2𝑖𝑖𝑖𝑖+1=𝑎𝑎𝑎𝑎(2𝑖𝑖𝑖𝑖∗2)= (𝑎𝑎𝑎𝑎2𝑖𝑖𝑖𝑖)2= 𝑎𝑎𝑎𝑎2𝑖𝑖𝑖𝑖∗𝑎𝑎𝑎𝑎2𝑖𝑖𝑖𝑖. La secuencia invertida de dígitos binarios podemos encontrarla mediante la secuencia: sd = (n,n->n>0,n/2).map(x->x%2); Reuniendo las ideas anteriores la secuencia de los factores de la expresión de la derecha puede ser descrita por: 𝑙𝑙𝑙𝑙=�(𝑛𝑛𝑛𝑛,𝑎𝑎𝑎𝑎),(𝑛𝑛𝑛𝑛,𝑒𝑒𝑒𝑒)→𝑛𝑛𝑛𝑛> 0, (𝑛𝑛𝑛𝑛,𝑒𝑒𝑒𝑒)→�𝑛𝑛𝑛𝑛2,𝑒𝑒𝑒𝑒∗𝑒𝑒𝑒𝑒�� .𝑓𝑓𝑓𝑓𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑒𝑒𝑒𝑒𝑖𝑖𝑖𝑖((𝑛𝑛𝑛𝑛,𝑒𝑒𝑒𝑒)→𝑛𝑛𝑛𝑛%2 == 1) El filtro es debido a que sólo debemos tener en cuenta los 𝑑𝑑𝑑𝑑𝑖𝑖𝑖𝑖= 1 ya que si 𝑑𝑑𝑑𝑑𝑖𝑖𝑖𝑖= 0 el factor se reduce a 1. Acumulando la secuencia anterior con el acumulador producto 𝑎𝑎𝑎𝑎= (1, (𝑏𝑏𝑏𝑏, (𝑛𝑛𝑛𝑛,𝑒𝑒𝑒𝑒))→𝑏𝑏𝑏𝑏∗𝑒𝑒𝑒𝑒) obtenemos el resultado buscado y el algoritmo iterativo. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
262 Problemas de algoritmos recursivos múltiples Suma y multiplicación de enteros grandes os números enteros solemos representarlos en los algoritmos como Integer o Long: pero estos tipos tienen un conjunto de valores limitado. Los valores de Integer van de -2^31= -2,147,483,648 a 2*31-1=2,147,483,647 que ocupan 4 bytes de memoria Los Long van de -2^63 = -9223372036854775808 a 2^63-1 = 9223372036854775807 que ocupan 8 bytes. Para usar valores enteros más grandes necesitamos un tipo de datos de tamaño variable que pueda representar cualquier valor entero. Java nos proporciona el tipo BigInteger. Las operaciones de suma y multiplicación se hacen con complejidad 𝛩𝛩𝛩𝛩(1) pero los de tipo BigInteger tienen unas complejidades que dependen de su número de dígitos. Un valor de tipo BigInteger, un entero largo 𝑛𝑛𝑛𝑛, lo podemos representar como una lista de dígitos 𝑑𝑑𝑑𝑑𝑟𝑟𝑟𝑟𝑑𝑑𝑑𝑑𝑟𝑟𝑟𝑟−1…𝑑𝑑𝑑𝑑0 en una base 𝑏𝑏𝑏𝑏. El número de dígitos, comovimos en problemas anteriores, es 𝑟𝑟𝑟𝑟=𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑏𝑏𝑏𝑏𝑛𝑛𝑛𝑛≅𝛩𝛩𝛩𝛩(𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑛𝑛𝑛𝑛). Queremos diseñar algoritmos de suma, reta, multiplicación, conciente, resto y potencia de enteros representados por listas de dígitos de tipo L Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Problemasdealgoritmosrecursivosmúltiples Sumaymultiplicacióndeenterosgrandes
Problemas de algoritmos recursivos múltiples 263 Long y de base 𝑏𝑏𝑏𝑏= 2^31. En el repositorio se ofrece el tipo LargeInteger que tiene una funcionalidad similar a BigInteger. La suma de valores de este tipo se puede hacer con el algoritmo clásico que se aprende en la escuela. Se van sumando los dígitos comenzando por los menos significativos y si se sobrepasa la base se anota una unidad, el acarreo, para acumularlo con el dígito siguiente. El algoritmo asumiendo que los dos sumandos tienen el mismo número de dígitos es: LargeInteger sum(LargeInteger x, LargeInteger y) { Integer n = x.size(); List<Long> r = new ArrayList<>(); Long ac = 0L; for(int i=n-1;i>=0;i--) { Long sm = ac+x.digit(i)+y.digit(i); Long d = sm%base; ac = sm/base; r.add(0,d); } r.add(0,ac); return LargeInteger.ofLong(r); } Como podemos ver la suma tiene complejidad 𝛩𝛩𝛩𝛩(𝑟𝑟𝑟𝑟). Es decir lineal en el número de dígitos y equivalentemente 𝛩𝛩𝛩𝛩(𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑛𝑛𝑛𝑛). Un algoritmo más completo para cuando el número de dígitos es diferente o algunos de los sumandos es cero está en el repositorio. La multiplicación también se podría diseñar con el algoritmo aprendido en la escuela que tiene complejidad 𝛩𝛩𝛩𝛩(𝑟𝑟𝑟𝑟2). En este caso podemos diseñar un algoritmo recursivo con una complejidad más baja. Es el algoritmo de Karatsuba. Sean 𝑛𝑛𝑛𝑛,𝑘𝑘𝑘𝑘 los valores a multiplicar. Asumamos que las listas de dígitos las dividimos por la mitad y sea 𝑚𝑚𝑚𝑚 el tamaño de la segunda mitad. Podemos observar que: 𝑛𝑛𝑛𝑛=𝑛𝑛𝑛𝑛1∗𝑏𝑏𝑏𝑏𝑚𝑚𝑚𝑚+𝑛𝑛𝑛𝑛0,𝑘𝑘𝑘𝑘=𝑘𝑘𝑘𝑘1∗𝑏𝑏𝑏𝑏𝑚𝑚𝑚𝑚+𝑘𝑘𝑘𝑘0 Y la multiplicación x∗y es: 𝑛𝑛𝑛𝑛∗𝑘𝑘𝑘𝑘=𝑠𝑠𝑠𝑠2∗𝑏𝑏𝑏𝑏2𝑚𝑚𝑚𝑚+𝑠𝑠𝑠𝑠1∗𝑏𝑏𝑏𝑏𝑚𝑚𝑚𝑚+𝑠𝑠𝑠𝑠0 𝑠𝑠𝑠𝑠2=𝑛𝑛𝑛𝑛1∗𝑘𝑘𝑘𝑘1, 𝑠𝑠𝑠𝑠1= (𝑛𝑛𝑛𝑛1+𝑘𝑘𝑘𝑘0)∗(𝑛𝑛𝑛𝑛0+𝑘𝑘𝑘𝑘1) , 𝑠𝑠𝑠𝑠0=𝑛𝑛𝑛𝑛0∗𝑘𝑘𝑘𝑘0 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de algoritmos recursivos múltiples 264 A partir de esas propiedades podemos deducir una definición recursiva. El caso base será cuando 𝑛𝑛𝑛𝑛,𝑘𝑘𝑘𝑘 tengan un dígito. Vemos que el tamaño del problema es el número de dígitos. Cada problema se divide en dos partes iguales, hay cuatro llamadas recursivas y la función de combinación es a suma la suma de complejidad 𝛩𝛩𝛩𝛩(𝑟𝑟𝑟𝑟). La recurrencia definida es: 𝑇𝑇𝑇𝑇(𝑟𝑟𝑟𝑟) = 4𝑇𝑇𝑇𝑇(𝑟𝑟𝑟𝑟/2) + 𝛩𝛩𝛩𝛩(𝑟𝑟𝑟𝑟) Cuya solución es 𝛩𝛩𝛩𝛩(𝑟𝑟𝑟𝑟2). Con este esquema recursivo no hemos ganado nada sobre el algortimo elemental. Pero podemos reordenar el cáculo de 𝑠𝑠𝑠𝑠1 aprovechando los cálculos ya hechos para 𝑠𝑠𝑠𝑠0, 𝑠𝑠𝑠𝑠2 en la forma: 𝑠𝑠𝑠𝑠1= (𝑛𝑛𝑛𝑛1+𝑛𝑛𝑛𝑛0)∗(𝑘𝑘𝑘𝑘0+𝑘𝑘𝑘𝑘1)− 𝑠𝑠𝑠𝑠2− 𝑠𝑠𝑠𝑠0 Ahora podemos observar que la ecuación de recurrencia es 𝑇𝑇𝑇𝑇(𝑟𝑟𝑟𝑟) = 3𝑇𝑇𝑇𝑇(𝑟𝑟𝑟𝑟/2) + 𝛩𝛩𝛩𝛩(𝑟𝑟𝑟𝑟) Cuya solución es 𝛩𝛩𝛩𝛩(𝑟𝑟𝑟𝑟log23) = 𝛩𝛩𝛩𝛩(𝑟𝑟𝑟𝑟1.58) . La potencia de enteros largos se puede implementar con el algoritmo de la potencia entera usando la suma y multiplicación anteriores. Observando el algoritmo de la potencia entera y teniendo en cuenta que los valores de 𝑛𝑛𝑛𝑛 siguen una progresión geométrica de razón 2, la complejidad de 𝑎𝑎𝑎𝑎𝑛𝑛𝑛𝑛, siendo 𝑎𝑎𝑎𝑎 un entero largo de 𝑟𝑟𝑟𝑟 dígitos y 𝑛𝑛𝑛𝑛 un entero conrto, será: �(𝑟𝑟𝑟𝑟∗2𝑖𝑖𝑖𝑖)1.58≅𝑓𝑓𝑓𝑓(𝑛𝑛𝑛𝑛)∗𝜃𝜃𝜃𝜃(𝑟𝑟𝑟𝑟1.58) 𝑙𝑙𝑙𝑙𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜2𝑛𝑛𝑛𝑛 𝑖𝑖𝑖𝑖=0 Con 𝑓𝑓𝑓𝑓(𝑛𝑛𝑛𝑛)=∑21.58 𝑖𝑖𝑖𝑖 𝑙𝑙𝑙𝑙𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜2𝑛𝑛𝑛𝑛 𝑖𝑖𝑖𝑖=0 . La explicación de lo anterior es que el número de pasos del algoritmo es 𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵2𝑛𝑛𝑛𝑛 y que los dígitos de un número se duplican al elevarse al cuadrado. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de algoritmos recursivos múltiples 265 Problemas de listas 1. Encontrar un conjunto con loe elementos de una lista en un rango Dada una lista ordenada de tipo genérico (List<E> lista), diseñar un algoritmo que devuelva un conjunto que incluya los elementos de dicha lista que se encuentren en un rango [a, b) dado (siendo a y b del mismo tipo que los elementos de la lista). Discutir los distintos algoritmos posibles y sus complejidades. • La primera posibilidad es usar una generalización sufija 𝑙𝑙𝑙𝑙(𝑖𝑖𝑖𝑖,𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙)=�{∅,𝑛𝑛𝑛𝑛−𝑖𝑖𝑖𝑖= 0 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑖𝑖𝑖𝑖]} ∪𝑙𝑙𝑙𝑙(𝑖𝑖𝑖𝑖+ 1, 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙), 𝑛𝑛𝑛𝑛−𝑖𝑖𝑖𝑖> 0 ∧𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑖𝑖𝑖𝑖]∈[𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏) 𝑙𝑙𝑙𝑙(𝑖𝑖𝑖𝑖+ 1, 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙), 𝑛𝑛𝑛𝑛−𝑖𝑖𝑖𝑖> 0 ∧𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑖𝑖𝑖𝑖]∉[𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏) Dadas las propiedades del operador ∪ podemos encontrar un algoritmo iterativo equivalente. La complejidad es Θ(𝑛𝑛𝑛𝑛) como puede comprobarse • La segunda posibilidad es usar una generalización central 𝑙𝑙𝑙𝑙(𝑖𝑖𝑖𝑖,𝑗𝑗𝑗𝑗,𝑘𝑘𝑘𝑘,𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙) = ⎩ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎧ ∅,𝑛𝑛𝑛𝑛−𝑖𝑖𝑖𝑖= 0 ∅,𝑛𝑛𝑛𝑛−𝑖𝑖𝑖𝑖= 1 ∧𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑖𝑖𝑖𝑖]∉[𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏) {𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑖𝑖𝑖𝑖]}, 𝑛𝑛𝑛𝑛−𝑖𝑖𝑖𝑖= 1 ∧𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑖𝑖𝑖𝑖]∈[𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏) 𝑙𝑙𝑙𝑙(𝑖𝑖𝑖𝑖,𝑘𝑘𝑘𝑘,𝑘𝑘𝑘𝑘+𝑖𝑖𝑖𝑖 2,𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙)∪𝑙𝑙𝑙𝑙(𝑘𝑘𝑘𝑘,𝑗𝑗𝑗𝑗,𝑗𝑗𝑗𝑗+𝑘𝑘𝑘𝑘 2,𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙), 𝑛𝑛𝑛𝑛−𝑖𝑖𝑖𝑖> 1 ∧𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑘𝑘𝑘𝑘]∈[𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏) 𝑙𝑙𝑙𝑙(𝑖𝑖𝑖𝑖,𝑘𝑘𝑘𝑘,𝑘𝑘𝑘𝑘+𝑖𝑖𝑖𝑖 2,𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙), 𝑛𝑛𝑛𝑛−𝑖𝑖𝑖𝑖> 0 ∧𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑘𝑘𝑘𝑘] > [𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏) 𝑙𝑙𝑙𝑙(𝑘𝑘𝑘𝑘,𝑗𝑗𝑗𝑗,𝑗𝑗𝑗𝑗+𝑘𝑘𝑘𝑘 2,𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙), 𝑛𝑛𝑛𝑛−𝑖𝑖𝑖𝑖> 0 ∧𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑘𝑘𝑘𝑘] < [𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏) La complejidad del caso peor es la solución de 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 2𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛/2)+ 1. Es decir Θ(𝑛𝑛𝑛𝑛). La del caso mejor 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)=𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛/2)+ 1. Es decir Θ(𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑛𝑛𝑛𝑛). La complejidad del caso medio depende de las probabilidades de 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑘𝑘𝑘𝑘]∈[𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏),𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑘𝑘𝑘𝑘]>[𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏),𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙[𝑘𝑘𝑘𝑘]<[𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏) Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Problemas de listas
Problemas de algoritmos recursivos múltiples 272 Una tercera aproximación al problema es enfocarlo de forma recursiva, generalizando el problema y dividiéndolo en dos partes iguales. SolH histograma2(List<Integer> ls){ Integer n = ls.size(); return histograma2(0,n,ls); } SolH histograma2(Integer i, Integer j, List<Integer> ls){ SolH rm; if(j-i>1){ Integer k = (j+i)/2; SolH r1 = histograma2(i,k,ls); SolH r2 = histograma2(k,j,ls); SolH r3 = centro(i,j,k,ls); rm = List.of(r1,r2,r3).stream() .max(Comparator.naturalOrder()).get(); } else if (j-i == 1) { rm = SolH.of(i,j,i,ls); } else { rm = SolH.zero(); } return rm; } Como vemos la solución del problema será la de mayor área de la parte izquierda, o de la parte derecha o la solución de área máxima centrada en k. Es decir, con i a la izquierda de k y j a la derecha. Para acabar de resolver el problema tenemos que diseñar el algoritmo que calcula la solución centrada. Una primera posibilidad es usar el algoritmo histograma1 anterior con i1, j1 moviéndose en los intervalos 𝑖𝑖𝑖𝑖1∈[𝑖𝑖𝑖𝑖,𝑘𝑘𝑘𝑘),𝑗𝑗𝑗𝑗1∈[𝑘𝑘𝑘𝑘+ 1, 𝑗𝑗𝑗𝑗].Pero al ser ℎ𝑖𝑖𝑖𝑖𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙1 de complejidad Θ(𝑛𝑛𝑛𝑛2) la ecuación de recurrencia asociada es: 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 2𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛/2)+𝑛𝑛𝑛𝑛2,Θ(𝑛𝑛𝑛𝑛2) Por esta vía no mejoramos en complejidad. Para que podamos mejorar la complejidad necesitamos que el algoritmo centro sea de complejidad Θ(𝑛𝑛𝑛𝑛) para que la ecuación de recurrencia asociada sea: 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 2𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛/2)+𝑛𝑛𝑛𝑛,Θ(𝑛𝑛𝑛𝑛log 𝑛𝑛𝑛𝑛) Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de algoritmos recursivos múltiples 273 Busquemos un algoritmo que calcule la solución centrada con complejidad Θ(𝑛𝑛𝑛𝑛). La idea es expandir la solución centrada más pequeña ubicada en los limites (𝑘𝑘𝑘𝑘−1, 𝑘𝑘𝑘𝑘+ 1) y el índice con valor mínimo en 𝑘𝑘𝑘𝑘−1. La idea es expandir esos límites hacia izquierda o derecha según el valor mayor de la nueva casilla y mantener la solución con mayor área. El algortimo resultante de complejidad Θ(𝑛𝑛𝑛𝑛) es: SolH centro(Integer i, Integer j, Integer k, List<Integer> ls) { Integer i1 = k-1, j1 = k+1; Integer min_index = minIndex(ls,i1,j1-1); SolH amax = SolH.zero(); while(i1 >= i && j1 <= j) { min_index = minIndex(ls,min_index,i1,j1-1); SolH r = SolH.of(i1,j1,min_index,ls); if(r.compareTo(amax) > 0) amax = r; if (i1 == i) j1++; else if (j1 == j) i1--; else { if (ls.get(i1-1) >= ls.get(j1)) i1--; else j1++; } } return amax; } El algoritmo anterior mantiene el invariante: min_index es el índice con menor valor en todo el intervalo [i1,j1) y amax es la solución con mayor área en el intervalo [i1,j1). Como podemos comprobar que el algoritmo no recorre todos los pares (i1,j1) posibles (eso daría complejidad de Θ(𝑛𝑛𝑛𝑛2)). Frente a eso amplia el intervalo a izquierda a derecha en la dirección que puede crecer el área. Esto lo consigue eligiendo el nuevo índice cuyo valor es mayor. Problemas de matrices 3. Obtener la suma de dos matrices: • De forma iterativa • De forma recursiva dividiéndolas en cuatro submatrices Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Problemas de matrices
Problemas de algoritmos recursivos múltiples 274 Para enfocar el problema proponemos un sistema de coordenadas para nombrar las casillas de la matriz. Nombremos las filas de arriba abajo por 𝑖𝑖𝑖𝑖 y las columnas por 𝑗𝑗𝑗𝑗 de tal forma que (0,0) es la casilla superior izquierda. Una matriz vendrá definida por su número de filas y columnas: 𝑛𝑛𝑛𝑛𝑓𝑓𝑓𝑓 × 𝑛𝑛𝑛𝑛𝑚𝑚𝑚𝑚. Una submatriz es una vista de una matriz definida por un vértice superior izquierdo y un tamaño de filas y columnas. Es decir dada una matriz 𝑚𝑚𝑚𝑚 una posible submatriz es 𝑙𝑙𝑙𝑙𝑚𝑚𝑚𝑚= (𝑚𝑚𝑚𝑚,𝑖𝑖𝑖𝑖0, 𝑛𝑛𝑛𝑛𝑓𝑓𝑓𝑓,𝑗𝑗𝑗𝑗0, 𝑛𝑛𝑛𝑛𝑚𝑚𝑚𝑚) con la restricciones adecuadas. Es una idea similar a sublist. Una matriz la podemos dividir en cuatro vistas que denominaremos m0, m1, m2, m3. La vista m0 vendrá definida (𝑚𝑚𝑚𝑚,0,𝑛𝑛𝑛𝑛𝑓𝑓𝑓𝑓/2,0, 𝑛𝑛𝑛𝑛𝑚𝑚𝑚𝑚/2) y de forma similar el resto. Cada submatriz tiene unas coordenadas locales tales que el vértice superior izquierdo es (0,0). Evidentemente una matriz se puede ver como una submatriz 𝑙𝑙𝑙𝑙𝑚𝑚𝑚𝑚=(𝑚𝑚𝑚𝑚,0,𝑛𝑛𝑛𝑛𝑓𝑓𝑓𝑓,0,𝑛𝑛𝑛𝑛𝑚𝑚𝑚𝑚). Llamemos Matrix<E> al tipo que representa una matriz o una vista de esta. Las funciones para operar con este tipo son: • Matrix<E> of(E[] datos, Integer nf, Integer nc): Una nueva matriz definida por un array de tamaño nf x nc. • E get(int i, int j): El valor de la casilla i, j • void set(int i, int j, E value): Actualización de la casilla i, j con el valor value. • View4<Matrix<E>> views4(): Las cuatro vistas de una matriz En primer lugar diseñamos la suma de las dos matrices cuadradas 𝑎𝑎𝑎𝑎,𝑏𝑏𝑏𝑏. �𝑎𝑎𝑎𝑎1𝑏𝑏𝑏𝑏1 𝑚𝑚𝑚𝑚1𝑑𝑑𝑑𝑑1�∗�𝑎𝑎𝑎𝑎2𝑏𝑏𝑏𝑏2 𝑚𝑚𝑚𝑚2𝑑𝑑𝑑𝑑2�=�𝑎𝑎𝑎𝑎1 + 𝑎𝑎𝑎𝑎2𝑏𝑏𝑏𝑏1 + 𝑏𝑏𝑏𝑏2 𝑚𝑚𝑚𝑚1 + 𝑚𝑚𝑚𝑚2𝑑𝑑𝑑𝑑1 + 𝑑𝑑𝑑𝑑2� Un primer algoritmo iterativo y otro recursivo son: Matrix<E> add(Matrix<E> m2){ Matrix<E> r = Matrix.zero(this.nf,m2.nc); for (int i = 0; i < this.nf; i++) { for (int j = 0; j < this.nc; j++) { E val = this.get(i,j).add(m2.get(i,j)); r.set(i,j,val); } } return r; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de algoritmos recursivos múltiples 275 Matrix<E> add_r(Matrix<E> m2){ Matrix<E> r; if(this.nc > 1 && this.nf > 1) { View4<Matrix<E>> v1 = this.views(); View4<Matrix<E>> v2 = m2.views(); Matrix<E> a = v1.a.add_r(v2.a); Matrix<E> b = v1.b.add_r(v2.b); Matrix<E> c = v1.c.add_r(v2.c); Matrix<E> d = v1.d.add_r(v2.d); r = Matrix.compose(a, b, c, d); } else { r = this.add(m2); } return r; } Como podemos comprobar ambos algoritmos tienen la complejidad Θ(𝑛𝑛𝑛𝑛2). El recursivo tiene asociada la ecuación de recurrencia y la solución: 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 4𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛/2)+ 1, Θ(𝑛𝑛𝑛𝑛2) 4. Obtener la multiplicación de dos matrices: • De forma iterativa • De forma recursiva dividiéndolas en cuatro submatrices según se indica �𝑎𝑎𝑎𝑎1𝑏𝑏𝑏𝑏1 𝑚𝑚𝑚𝑚1𝑑𝑑𝑑𝑑1�∗�𝑎𝑎𝑎𝑎2𝑏𝑏𝑏𝑏2 𝑚𝑚𝑚𝑚2𝑑𝑑𝑑𝑑2�=�𝑎𝑎𝑎𝑎1∗𝑎𝑎𝑎𝑎2 + 𝑏𝑏𝑏𝑏1∗𝑚𝑚𝑚𝑚2𝑎𝑎𝑎𝑎1∗𝑏𝑏𝑏𝑏2 + 𝑏𝑏𝑏𝑏1∗𝑑𝑑𝑑𝑑2 𝑚𝑚𝑚𝑚1∗𝑎𝑎𝑎𝑎2 + 𝑑𝑑𝑑𝑑1∗𝑑𝑑𝑑𝑑2𝑚𝑚𝑚𝑚1∗𝑏𝑏𝑏𝑏2 + 𝑑𝑑𝑑𝑑1∗𝑑𝑑𝑑𝑑2� Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de algoritmos recursivos múltiples 276 Una versión iterativa está en el algoritmo: Matrix<E> multiply(Matrix<E> in2){ Matrix<E> r = Matrix.zero(this.field,this.nf,in2.nc); for (int i = 0; i < this.nf; i++) { for (int j = 0; j < in2.nc; j++) { r.set(i,j,this.field.getZero()); for (int k = 0; k < this.nc; k++){ E val= (this.get(i,k).multiply(in2.get(k,j))) .add(r.get(i,j)); r.set(i,j,val); } } } return r; } Como podemos comprobar el algoritmo es de complejidad Θ(𝑛𝑛𝑛𝑛3). Una versión recursiva, con las ideas indicadas es: Matrix<E> multiply_r(Matrix<E> m2){ Matrix<E> r; if(this.nc < 2 || this.nf < 2 || m2.nf < 2 || m2.nc < 2) { r = this.multiply(m2); } else { View4<Matrix<E>> v1 = this.views(); View4<Matrix<E>> v2 = m2.views(); Matrix<E> a = v1.a.multiply_r(v2.a) .add(v1.b.multiply_r(v2.c)); Matrix<E> b = v1.a.multiply_r(v2.b) .add(v1.b.multiply_r(v2.d)); Matrix<E> c = v1.c.multiply_r(v2.a) .add(v1.d.multiply_r(v2.c)); Matrix<E> d = v1.c.multiply_r(v2.b) .add(v1.d.multiply_r(v2.d)); r = Matrix.compose(a, b, c, d); } return r; } Como podemos que también la multiplicación iterativa la recursiva tienen complejidad a Θ(𝑛𝑛𝑛𝑛3): 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 8𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛/2)+𝑛𝑛𝑛𝑛2,Θ(𝑛𝑛𝑛𝑛3) Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de algoritmos recursivos múltiples 277 Esta complejidad puede reducirse aún más reordenado el cálculo en la forma: 𝑝𝑝𝑝𝑝1 = 𝑎𝑎𝑎𝑎(𝑓𝑓𝑓𝑓−ℎ),𝑝𝑝𝑝𝑝2 = (𝑎𝑎𝑎𝑎+𝑏𝑏𝑏𝑏)ℎ,𝑝𝑝𝑝𝑝3 = (𝑚𝑚𝑚𝑚+𝑑𝑑𝑑𝑑)𝑒𝑒𝑒𝑒,𝑝𝑝𝑝𝑝4 = 𝑑𝑑𝑑𝑑(𝑔𝑔𝑔𝑔−𝑒𝑒𝑒𝑒) 𝑝𝑝𝑝𝑝5 = (𝑎𝑎𝑎𝑎+𝑑𝑑𝑑𝑑)(𝑒𝑒𝑒𝑒+ℎ),𝑝𝑝𝑝𝑝6 = (𝑏𝑏𝑏𝑏−𝑑𝑑𝑑𝑑)(𝑔𝑔𝑔𝑔+ℎ),𝑝𝑝𝑝𝑝7 = (𝑎𝑎𝑎𝑎−𝑚𝑚𝑚𝑚)(𝑒𝑒𝑒𝑒+𝑓𝑓𝑓𝑓) �𝑎𝑎𝑎𝑎1𝑏𝑏𝑏𝑏1 𝑚𝑚𝑚𝑚1𝑑𝑑𝑑𝑑1�∗�𝑎𝑎𝑎𝑎2𝑏𝑏𝑏𝑏2 𝑚𝑚𝑚𝑚2𝑑𝑑𝑑𝑑2�=�𝑝𝑝𝑝𝑝5 + 𝑝𝑝𝑝𝑝4−𝑝𝑝𝑝𝑝2 + 𝑝𝑝𝑝𝑝6𝑝𝑝𝑝𝑝1 + 𝑝𝑝𝑝𝑝2 𝑝𝑝𝑝𝑝3 + 𝑝𝑝𝑝𝑝4𝑝𝑝𝑝𝑝1 + 𝑝𝑝𝑝𝑝5−𝑝𝑝𝑝𝑝3−𝑝𝑝𝑝𝑝7� Que como podemos comprobar tendrá asociada la ecuación de recurrencia 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 7𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛/2)+𝑛𝑛𝑛𝑛2, Θ�𝑛𝑛𝑛𝑛log27�= Θ(𝑛𝑛𝑛𝑛2.8) 5. Dada una matriz comprobar si todos sus elementos cumplen una propiedad dada Este problema podemos resolver recorriendo todos los elementos de la matriz y comprobando si cumplen la propiedad Boolean allElements(Matrix<E> m, Predicate<E> pd) { return Stream2.allPairs(m.nf(),m.nc()) .map(p->m.get(p)) .allMatch(pd); } Igualmente se puede comprobar si algún elemento cumple la propiedad o ninguno la cumple. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de algoritmos recursivos múltiples 278 6. Dada una matriz de unos y ceros encontrar la mayor submatriz compuesta solo de unos Una manera de comenzar a enfocar el problema es recorrer todas las submatrices posibles, filtrar la que cumplan la propiedad y quedarse con la de mayor área. El código es: Stream<Matrix<E>> allSubMatrix(Matrix<E> m){ return Stream2.allQuartets(0,m.nf(),0,m.nc(), 1,m.nf(),1,m.nc()) .filter(q->q.third()<=m.nf()-q.first() && q.fourth()<=m.nc()-q.second()) .map(q->m.view(q.first(),q.second(), q.third(),q.fourth())); } Matrix<E> largeRectangle1(Matrix<E> m, Predicate<E> pd){ return allSubMatrix(m) .filter(mx->allElements(mx,pd)) .max(Comparator.comparing(my->my.area())) .get(); } El algoritmo anterior tiene complejidad, como puede comprobarse, de 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛6). Esto es debido a que para generar las submatrices debemos recorrer todas las combinaciones de (𝑓𝑓𝑓𝑓,𝑚𝑚𝑚𝑚,𝑛𝑛𝑛𝑛𝑓𝑓𝑓𝑓,𝑛𝑛𝑛𝑛𝑚𝑚𝑚𝑚), 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛4) y para cada matriz comprobar que todos sus elementos cumpen la propiedad, 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛2). Una posibilidad de reducir la complejidad es mediante un esquema recursivo. Para escoger el algoritmo adecuado debemos decidir si dividir la matriz en 2 o en 4. Estos algoritmos serán de la forma: Ilustración 21: Matriz binaria Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Ilustración21:Matrizbinaria
Problemas de algoritmos recursivos múltiples 279 Matrix<E> largeRectangle2(Matrix<E> m, Predicate<E> pd){ Matrix<E> r; if(m.nf()>2 && m.nc()>2) { View2<Matrix<E>> vx = m.views2F(); Matrix<E> ma = largeRectangle2(vx.left(),pd); Matrix<E> mb = largeRectangle2(vx.right(),pd); Matrix<E> ct = center2(m,pd); r = List.of(ma,mb,ct).stream() .max(Comparator.comparing(my->my.area())) .get(); } else { r = largeRectangle1(m,pd); } return r; } Matrix<E> largeRectangle4(Matrix<E> m, Predicate<E> pd){ Matrix<E> r; if(m.nf()>2 && m.nc()>2) { View4<Matrix<E>> vx = m.views4(); Matrix<E> ma = largeRectangle4(vx.a(),pd); Matrix<E> mb = largeRectangle4(vx.b(),pd); Matrix<E> mc = largeRectangle4(vx.c(),pd); Matrix<E> md = largeRectangle4(vx.d(),pd); Matrix<E> ct = center4(m,pd); r = List.of(ma,mb,mc,md,ct).stream() .max(Comparator.comparing(my->my.area())) .get(); } else { r = largeRectangle1(m,pd); } return r; } Para calcular la complejidad de este tipo de algoritmos recordemos que las ecuaciones de recurrencia del tipo 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)= 𝑎𝑎𝑎𝑎𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛/𝑏𝑏𝑏𝑏)+ 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑)𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑝𝑝𝑝𝑝𝑛𝑛𝑛𝑛 Solución 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)=�𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑙𝑙𝑙𝑙𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑏𝑏𝑏𝑏𝑎𝑎𝑎𝑎� 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑎𝑎𝑎𝑎>𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑 𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑝𝑝𝑝𝑝+1𝑛𝑛𝑛𝑛� 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑎𝑎𝑎𝑎=𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑 𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑝𝑝𝑝𝑝𝑛𝑛𝑛𝑛� 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑎𝑎𝑎𝑎<𝑏𝑏𝑏𝑏𝑑𝑑𝑑𝑑 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de algoritmos recursivos múltiples 280 Concretado para 𝑝𝑝𝑝𝑝= 0, 𝑎𝑎𝑎𝑎= 4, 𝑏𝑏𝑏𝑏= 2 las complejidades en función de 𝑑𝑑𝑑𝑑 son: 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)=�𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛2) 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑑𝑑𝑑𝑑< 2 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛2 𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑛𝑛𝑛𝑛) 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑑𝑑𝑑𝑑= 2 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑� 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑑𝑑𝑑𝑑> 2 Concretado para 𝑝𝑝𝑝𝑝= 0, 𝑎𝑎𝑎𝑎= 2, 𝑏𝑏𝑏𝑏= 2 las complejidades son en función de 𝑑𝑑𝑑𝑑: 𝑇𝑇𝑇𝑇(𝑛𝑛𝑛𝑛)=�𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛) 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑑𝑑𝑑𝑑< 1 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛 𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑛𝑛𝑛𝑛) 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑑𝑑𝑑𝑑= 1 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑� 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑑𝑑𝑑𝑑> 1 La complejidad depende, por tanto, de la complejidad de la función center (2 o 4). Observamos que si center tiene complejidad 𝛩𝛩𝛩𝛩�𝑛𝑛𝑛𝑛𝑑𝑑𝑑𝑑� el algoritmo diseñado 𝑎𝑎𝑎𝑎= 2, dividir en dos partes por filas o columnas, da complejidades mejores que para 𝑎𝑎𝑎𝑎= 4, dividir el cuatro partes. Escogemos dividir en dos partes. Buscamos para center un algoritmo de complejidad 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛). De esta forma conseguimos que nestro algoritmo de búsqueda del mayor bloque tenga una complejidad de 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛 𝑙𝑙𝑙𝑙𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝐵𝑛𝑛𝑛𝑛) más baja que 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛6) del algoritmo original. Si para center solo comseguimos 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛2) el algoritmo quedaría con complejidad 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛2) que sigue siendo mejor que 𝛩𝛩𝛩𝛩(𝑛𝑛𝑛𝑛6). El algoritmo center2 tiene como objetivo buscar la mayor matriz de unos que incluya casillas de las dos subpartes en las que dividimos la matriz original. Esto se puede conseguir en dos pasos que dejamos como ejercicio aunque la solución se puede encontrar en el repositorio: • Encontrar una lista de pares de enteros que delimiten los bloques de unos en la fila central ( o en la columna central si dividimos por columnas) • Por cada bloque de unos en la fila central encontrar la matriz de área mayor que incluyendo solo unos sea un subconjunto del bloque dado. La solución recuerda a la propuesta para el problema del histograma anterior Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de algoritmos recursivos múltiples 281 • Encontrar la mayor de las matrices asociadas a cada bloque. Si dividiéramos por cuatro el problema sería similar pero ahora tendríamos que recorrer la fila y la columna central para buscar los bloques de uno y luego la mayor matriz. Es debido a que tendríamos que buscar la mayor de todas las matrices que se solapan entre las cuatro partes. Dada una matriz de ceros y unos encontrar una submatriz rectangular número de filas y columnas mayor que 1, si la hay, que tenga todas sus esquinas iguales a 1 mat[][] = { 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 } Podemos abordar una solución enumerando las submatrices y comprobando si hay alguna que cumple la propiedad. Esto como dijimos antes se puede conseguir con complejidad Θ(n4 ). El código sería: Matrix<E> conPropiedad(Matriz<E> mt, Predicate<Matri<E)> pd){ return mt.allSubMatrix() .filter(m->m.nf()>1 && m.nc()>1) .filter(pd) .findFirst() .get(); } En este caso la propiedad sería Predicate<Matri<E)> pd = m->m.corners().stream() .allMatch(e->e.equals(1)) Una solución recursiva se puede conseguir con el mismo esquema que en el problema anterior. Pero ahora la función center, en el caso peor, tendría complejidad Θ(n4 ) con lo que no ganaríamos nada con la versión recursiva. La función center, en este caso, necesitaría enumerar los rectángulos que se solapen con las partes de la matriz y que tengan la propiedad pedida. Enumerar los rectángulos se puede hacer enumerando los posibles vértices superior izquierdo e inferior derecho. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
288 Problemas de implementación de tipos n esta sección se proponen implementaciones para tipos conocidos y ejercicios para ser resueltos Implementación de listas Las listas tienen dos implementaciones usuales: ArrayList y LinkedList. Los tipos siguientes, Alist y Llist, hacen este trabajo. Recordemos que un tipo se implementa mediante otro que tiene unas propiedades privadas, un invariante, unas operaciones y unos métodos de factoría. El tipo implementador ofrece como públicas las propiedades y operaciones que requiere el tipo a implementar. AList<E>: Mutable, Implementa List<E> Propiedades Privadas E[] data; int capacity; int size; // número de elementos Invariante: tam = data.lenght, size < tam, Operaciones privadas: E[] grow(E[] old, int newTam); E Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Problemas de implementación de tipos Implementacióndelistas
Problemas de implementación de tipos 289 En esta implementación los datos se guardan en un array que está parcialmente lleno. El número de datos es size. El primer detalle para tener en cuenta es que el tamaño del array de datos (data) debe ser suficiente para almacenar los datos. Es decir, size < tam. Esta restricción del invariante se puede mantener llamando a la operación grow al comienzo de la operación add. Con la implementación anterior se propone la implementación de las siguientes propiedades, operaciones y métodos de factoría del tipo List<E> discutiendo en cada caso la complejidad, las precondiciones y postcondiciones de cada uno de ellos. • int size() • Boolean contains(E e) • E get(int i) • boolean add(E e) • boolean remove(E e) • int indexOf(E e) • List<E> subList(int i, in j) Como ejemplo veamos los métodos grow y add. private AList(int capacity) { this.capacity = capacity; this.size = 0; this.data = null; } private void grow(){ if(size==capacity){ E[] oldElements = data; capacity = capacity*2; data = Arrays.copyOf(oldElements, capacity); } } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de implementación de tipos 290 public boolean add(E e) { if(this.data == null) this.data = (E[]) Array.newInstance(e.getClass(), capacity); grow(); data[size] = e; size++; return true; } En el repositorio se puede encontrar el código del resto de las operaciones. El tipo LList es la implementación de una lista enlazada. Como se ve abajo, también hay que mantener el invariante, size < tam, de forma similar a antes. Ahora, sin embargo, los datos no están indexados. Están enlazados en las distintas entradas del tipo Entry<E>. Ahora las complejidades de las operaciones básicas y del cálculo de las propiedades son diferentes. También es más compleja la implementación de sublist. LList<E>: Mutable, Implementa List<E> Propiedades Privadas Entry<E> first; Entry<E> last; int size; Invariante: … Propiedades privadas: Entry<E> entryInPos(int index); Tipos privados: Entry<K> Propiedades K key(); Entry<K> next(); Métodos de creación: Entry<K> of(K key, Entry<K> next); Como ejercicio se propone implementar las propiedades, operaciones y métodos de factoría de List<E>. Veamos como ejemplo algunos métodos privados y otros públicos. Algunas propiedades privadas son importantes como entryInPos que encuentra la tupla en la posición index o devuelve null si no la encuentra. Podemos ver que esta operación tiene en el caso peor complejidad del orden Θ(𝑛𝑛𝑛𝑛). Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de implementación de tipos 291 boolean add(E e){ Entry<E> e1 = new Entry<E>(e); if(last==null){ first = e1; last=e1; }else{ last.setNext(e1); last = e1; } size++; return true; } private Entry<E> entryInPos(int index){ Preconditions.checkElementIndex(index, size); Entry<E> pe = first; for(int p = 0 ; p < index; p++){ pe = pe.next(); } return pe; } public boolean add(int index, E e){ Preconditions.checkPositionIndex(index, size); Entry<E> ne = new Entry<E>(e); if(index==size){ add(e); } else if(index==0){ ne.setNext(first); first = ne; } else { Entry<E> pe = entryInPos(index-1); ne.setNext(pe.next()); pe.setNext(ne); } size++; return true; } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de implementación de tipos 292 Tablas hash El tipo HashTable es el adecuado para implementar el tipo Map<K,V>, Set<E>, Multiset<E>, etc. HashTable<K,V>: Mutable, Implementa Map<K,V> Propiedades Privadas: int groupsNumber; //número de grupos int capacity; //tamaño del array de datos int size; //número de pares clave valor AList<Integer> groups; //array de entradas a //grupos AList<EntryData<K,V>> data; //array de datos Integer firstFreeData; // primera tupla libre Integer group(K key); // grupo al que pertenece // la clave key EntryData<K,V> findEntry(K key); //tupla con la clave key o null si no //hay ninguna Invariante: size/capacity < loadFactorLimit; Operaciones privadas: void rehash(int newCapacity); Tipos privados: EntryData<K,V> Propiedades: K key(); V value(); Integer next(); Métodos de creación: EntryData<K,V> of( K key,V value,Integer next); Métodos de Creación: HashTable<K,V> empty(); Propiedades: … Operaciones … El invariante es el siguiente: • El grupo i está formado por la lista enlazada de tuplas (EntryData<K,V>) guardadas en data que comienza en groups.get(i). • Un par (key,value) está en el grupo i = key.hashCode()%groupsNumber o no está. • La primera casilla libre de data está en la posición firstFreeData. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Tablashash
Problemas de implementación de tipos 293 • Todas las casillas libres en data están enlazadas entre sí. • Debe cumplirse que size/capacity < loadFactorLimit. La operación privada rehash está diseñada para mantener esta relación si se intenta sobrepasar el factor de carga. • Cada tipo que actúe como clave debe tener un hashCode y un equals. El tipo usa una tupla de clave, valor y entero que denominamos EntryData y dos listas implementadas mediante arrays: una de enteros (groups) y otra de EntryData (data). Para implementar la búsqueda del grupo asociado a un par clave valor definimos los métodos privados: • Integer group(K key): Calcula el grupo asociado a la clave como el resto de la división entre el hashCode de la clave y el número de grupos. • EntryData<K,V> findEntry(K key): Busca dentro del grupo asociado a la clave, que como sabemos es una lista enlazada de EntryData la tupla con la clave igual a key. Devuelve null si no la encuentra. El método get(K key) se implementa fácilmente usando los dos métodos privados anteriores. El método put(K key, V value) se implementa con las siguientes ideas: • Se busca una EntryData que tenga una clave igual a key usando findEntry. o Si se encuentra se modifica el valor en esta tupla y se devuelve el antiguo valor o Si no se encuentra se busca primera EntryData en la lista de la que están vacías (que comienza en firstFreeData) y sus campos se actualizan con los valores de key, value. Posteriormente se actualiza firstFreeData a la siguiente tupla libre y se inserta al principio de la lista enlazada asociada al grupo group(key). Como ejercicio se propone implementar las propiedades, operaciones y métodos de factoría de Map<K,V>. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de implementación de tipos 294 El tipo Set<E> se implementa también mediante un pequeño ajuste al tipo HashTable<E,V>. Ahora no hace falta el tipo V y el tipo EntryData<E,V> se sustituye por EntryData<E> con propiedades key, next. Como ejercicio se propone implementar las propiedades, operaciones y métodos de factoría de Set<E>. El tipo Multiset<E> se implementa teniendo en cuenta que es equivalente a Map<E,Integer>. Como ejercicio se propone implementar las propiedades, operaciones y métodos de factoría de Set<E>. Conjuntos de enteros: IntegerSet El tipo IntegerSet es una implementación de Set<Integer> donde los valores enteros están por encima de un valor dado. El tipo es muy interesante porque ofrece operaciones con conjuntos de complejidad Θ(1). Para su implementación se usa un array de bits ya proporcionado por Java, El array de bits es un tipo, que ya ofrece Java como BitSet, muy adecuado para implementar conjuntos de enteros dentro de un rango. public class IntegerSet implements Set<Integer> { private final Integer infLimit; private final BitSet bits; … } La idea es reducir las operaciones sobre conjuntos (contains, unión, intersección, diferencia simétrica, complemento, …) a otras operaciones con bits (getBit, or, and, xor, complement, …). Se propone implementar las propiedades, operaciones y métodos de factoría de IntegerSet que implementan las de Set<E>. Como ejemplo la operación add es: Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Conjuntosdeenteros:IntegerSet
Problemas de implementación de tipos 295 @Override public boolean add(Integer e) { Preconditions.checkArgument(e>=infLimit, "Fuera de rango"); Integer ne = e-infLimit; Boolean c = this.bits.get(ne); this.bits.set(ne, true); return c != this.bits.get(ne); } Implementación de árboles El tipo Tree<E> se puede implementar mediante TreeImpl que mantiene un conjunto de propiedades privadas adecuadas. Se propone como ejercicio implementar las operaciones básicas del tipo Tree<E>. La implementación puede verse en el repositorio. TreeImpl<E>: Inmutable, Implementa Tree<E> Propiedades Privadas TreeType type; E label; List< TreeImpl<E>> children; TreeImpl<E> father; Invariante: (type == Nary && label !=null && children!=null) (type == Leaf && label !=null) || type == Empty; Métodos de creación: … Propiedades: … De la misma manera el tipo BinaryTree<E> se puede implementar mediante BinaryTreeImpl. Se propone como ejercicio implementar las operaciones básicas del tipo BinaryTree<E>. La implementación puede verse en el repositorio. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Implementacióndeárboles
Problemas de implementación de tipos 296 BinaryTreeImpl<E>: Inmutable, Implementa BinaryTree<E> Propiedades Privadas BinaryType type; E label; BinaryTreeImpl<E> left; BinaryTreeImpl<E> right; BinaryTreeImpl father; Invariante: (type == Binary && label !=null && left!=null && right!=null) || (type == Leaf && label !=null) || type == Empty; Métodos de creación: … Propiedades: … Para implementar conjuntos ordenados se suele usar un AVLTree. Este tipo se implementa reutilizando un BinaryTree que se mantiene equilibrado y ordenado. Se propone como ejercicio implementar las operaciones del tipo SortedSet<E>. AVLTree<E>: Mutable, Implementa SortedSet<E>. Propiedades privadas BinaryTree<E> tree; Comparator<E> comparator; Invariante: tree está ordenado con respecto a comparator y equilibrado Operaciones privadas: BinaryTree<E> addOrdered(BinaryTee<E> tree,Comparator<E> cmp); BinaryTree<E> removeOrdered(BinaryTee<E> tree,Comparator<E> cmp); BinaryTree<E> equilibrate(BinaryTee<E> tree); Métodos de creación: … Propiedades: … Operaciones: … Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
297 Problemas de árboles y expresiones os problemas sobre árboles son de tres tipos fundamentales: • Problemas iterativos sin tener en cuenta el nivel de cada subárbol. Estos se resuelven usando el stream, o el iterador, proporcionado por el árbol. Los algoritmos resultantes son similares a los algoritmos iterativos sobre un agregado de datos. • Problemas iterativos que tienen en cuenta el nivel de cada subárbol. Estos se resuelven usando el stream byLevel(), o el iterador equivalente, proporcionado por el árbol. Los algoritmos resultantes son similares a los algoritmos iterativos sobre un agregado de datos pero donde cada elemento incorpora su nivel dentro del árbol • Problemas recursivos. Todos los problemas de árboles pueden ser resueltos recursivamente. Aunque en muchos casos es más fácil y recomendable usar algoritmos iterativos hay otros algoritmos más fáciles desde el punto de vista recursivo. L Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Problemasdeárbolesyexpresiones
Problemas de Grafos 304 public Set<E> edgeSet() { return graph.edgeSet().stream() .filter(e->this.containsEdge(e)) .collect(Collectors.toSet()); } public Set<E> edgesOf(V v) { return graph.edgesOf(v).stream() .filter(e->this.containsEdge(e)) .collect(Collectors.toSet()); } … } 2. Dado un grafo con pesos obtener una vista que contenga los mismos vértices y sea completo. Las nuevas aristas tendrán un peso muy grande. Usamos la misma técnica de antes public class CompleteGraphView<V, E, G extends Graph<V,E>> implements Graph<V,E> { private G graph; private Supplier<E> edgeWeightFactory; private Double weightDefault; public E getEdge(V v0, V v1) { E edge = null; if (graph.containsEdge(v0, v1)) edge = graph.getEdge(v0, v1); else edge = this.edgeWeightFactory.get() return edge; } … Aquí se ha optado por construir una nueva arista cada vez que es necesario. Otra posibilidad es añadir las aristas nuevas que se construyen al grafo de partida cuando la necesitemos. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de Grafos 305 3. A partir de un grafo no dirigido con pesos obtener una vista que sea un grafo dirigido con los mismos vértices y que por cada arista original tenga dos dirigidas con los mismos pesos. Se usa la misma técnica que antes. Se deja como ejercicio. 4. Una red social imaginaria y pequeña, se representa con un grafo en el que los vértices modelan a los miembros de la red social y las aristas (sin etiqueta ni peso) modelan la amistad entre dos miembros. Desarrolle: • Un método que devuelva un conjunto con aquellos miembros que no tengan ningún amigo. • Un método que, dados dos miembros, devuelva la lista más corta de amigos que hay desde un miembro a otro miembro. <V> Set<V> sinAmigos(Graph<V,Integer> graph){ return graph.vertexSet().stream() .filter(v->graph.degreeOf(v)==0) .collect(Collectors.toSet()); } <V> List<V> listaMasCorta(Graph<V,Integer> graph, V e1, V e2){ ShortestPathAlgorithm<V,Integer> a = new DijkstraShortestPath<V,Integer>(graph); GraphPath<V,Integer> gp = a.getPath(e1,e2); return gp.getVertexList(); } 5. Lectura de grafos Dada una clase CV con los atributos: {a: String, b: Integer, c: Boolean}, una segunda clase CE con los siguientes atributos: {s: String, i: Integer} y un fichero datos.txt que contiene la información necesaria para representar Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de Grafos 306 un grafo en el que los vértices sean objetos CV y las aristas objetos CE, implemente un método, y todos los elementos auxiliares necesarios, que permita cargar dicho grafo desde el fichero. Asumimos que el tipo CV no define una propiedad que defina cada valor de manera unívoca. Cuando esto es así le añadimos un identificador de tipo entero que identifique cada vértice. El fichero es datos.txt es de la forma: #VERTEX# 1,A,2,true 2,B,3,false 3,C,10,true 4,D,21,true 5,E,4,false #EDGE# 1,3,v1,21 1,2,v2,2 2,5,v4,20 4,3,v5,3 2,4,v6,5 Los tipos CV, CE los diseñamos como records con un método de factoría que convierte una array de String en un valor. record CV(Integer id, String a, Integer b, Boolean c) { public static CV of(String[] formato) { return new CV( Integer.parseInt(formato[0]), formato[1], Integer.parseInt(formato[2]), toBoolean(formato[3])); } } record CE(String s, Integer i) { public static CE of(String[] formato) { return new CE(formato[2], Integer.parseInt(formato[3])); } } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de Grafos 307 Graph<CV, CE> leeGrafo(String file) { SimpleWeightedGraph<CV, CE> graph = GraphsReader.newGraph(file, CV::of, CE::of, Graphs2::simpleWeightedGraph, e->1.0); return graph; } 6. Rutas mínimas Una empresa de autobuses tiene andenes en algunas ciudades de un país. El mapa de carreteras de dicho país está modelado como un grafo en el que los vértices están etiquetados con el nombre de la ciudad y las aristas con la distancia entre dos ciudades. Desarrolle un método que permita calcular todas las rutas mínimas entre las diferentes ciudades, junto con su distancia. Una manera adecuada es usar el algoritmo de FloydWarshall: <V,E> Set<GraphPath<V,E>> distanciasMinimas(Graph<V,E> g){ List<V> vertices = g.vertexSet().stream().toList(); FloydWarshallShortestPaths<V,E> a = new FloydWarshallShortestPaths<>(g); Set<GraphPath<V,E>> s = new HashSet<>(); for(int i = 0; i<vertices.size();i++) { for(int j=i+1; j<vertices.size();j++) { s.add(a.getPath(vertices.get(i), vertices.get(j))); } } return s; } 7. Recubrimiento mínimo Se desea conectar un conjunto de ciudades mediante líneas telefónicas. La compañía telefónica cobra la cantidad 𝑝𝑝𝑝𝑝(𝑖𝑖𝑖𝑖,𝑗𝑗𝑗𝑗) por conectar la ciudad 𝑖𝑖𝑖𝑖 Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de Grafos 308 con la 𝑗𝑗𝑗𝑗. ¿Qué ciudades conectar para que todas estén conectadas entre sí al mínimo precio? El algoritmo de Kruskal nos resuelve el problema. Este algoritmo nos devuelve un SpanningTree<E> que no informa del conjunto de aristas elegidas y el peso del recubrimiento: <V,E> SpanningTree<E> recubrimientoMinimo(Graph<V,E> g){ KruskalMinimumSpanningTree<V,E> a = new KruskalMinimumSpanningTree<>(g); return a.getSpanningTree(); } 8. Recubrimiento de vértices Sea un grafo cuyas aristas representan carreteras y los vértices representan cruces entre ellas. Queremos colocar cámaras de seguridad en algunos cruces de tal manera que puedan ver todas las carreteras que acceden al cruce. ¿Si pretendemos colocar el mínimo número de cámaras, como podemos obtener la solución? Un algoritmo adecuado es el recubrimiento de vértices. Una implementación de este es RecursiveExactVCImpl. Este algoritmo devuelve un VertexCover<V> que es un conjunto de vértices y alguna información adicional como el peso del recubrimiento. <V,E> VertexCover<V> recubrimientoVertices(Graph<V,E> g){ VertexCoverAlgorithm<V> a = new RecursiveExactVCImpl<>(g); return a.getVertexCover(); } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de Grafos 309 9. Recorrido Una compañía de autopistas ha contratado a una empresa de seguridad para que patrulle la red de autopistas cuyo mapa está esquematizado en los siguientes grafos: La empresa de seguridad quiere realizar el servicio con un solo vehículo y quiere determinar la existencia de un recorrido de manera que se vigilen todos los tramos de la autopista una única vez. ¿Cuál es ese recorrido? Dado un grafo no dirigido implementar un algoritmo que nos proporcione una lista de aristas, si existe, con el recorrido a seguir. En cuál de los dos grafos existe el camino pedido. Un camino euleriano es un camino en un grafo que visita cada arista exactamente una vez (lo que permite volver a visitar los vértices). Es decir, en un camino euleriano pueden repetirse los vértices pero no las aristas. Alternativamente un camino hamiltoniano es un camino en un grafo que visita cada vértice exactamente una vez. En un camino hamiltoniano no se pueden repetir ni vértices ni aristas. El problema que se propone es encontrar un camino euleriano para ese grafo. Es conocido que para que exista un camino euleriano todos los vértices deben ser de grado par. Escribir un algoritmo para decidir si un grafo tiene un camino euleriano y si lo tiene encontrarlo. Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de Grafos 310 <V,E> Boolean esEuleriano(Graph<V,E> g){ return g.vertexSet().stream() .allMatch(v->g.degreeOf(v)%2==0); } <V,E> GraphPath<V,E> caminoEuleriano(Graph<V,E> g){ EulerianCycleAlgorithm<V,E> a = new HierholzerEulerianCycle<V,E>(); return a.getEulerianCycle(g); } Podemos comprobar que el grafo de la derecha no es euleriano. El de la izquierda si y un camino euleriano está definido por la secuencia de aristas: [K, J, I, H, G, C, D, E, F, B, A] 10. Plan de estudios Un plan de estudios está estructurado de tal forma que existen asignaturas que deben haberse cursado (y aprobado) anteriormente para que un alumno se pueda matricular de una asignatura dada. Así, los prerrequisitos de una asignatura pueden ser 0 o más asignaturas. Implemente un método que, dado el grafo que representa el plan de estudios, con las asignaturas y las restricciones de matriculación entre las mismas, y la lista de asignaturas que un alumno tiene aprobadas, devuelva una lista con las asignaturas que puede cursar el próximo año. Con la información proporcionada podemos representar el plan de estudios como un grafo dirigido acíclico. Debe ser acíclico porque si hubiera ciclos podríamos tener disponible una asignatura ya cursada. Se trata de encontrar las asignaturas vecinas hacia delante de las proporcionadas en la lista: Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Problemas de Grafos 311 Set<String> asignaturasPosibles( DirectedAcyclicGraph<String,String> g, List<String> as){ Set<String> r = new HashSet<>(); as.stream() .flatMap(a->g.outgoingEdgesOf(a).stream() .map(t->g.getEdgeTarget(t))) .filter(a->!as.contains(a)) .forEach(y->r.add(y)); return r; } 11. Problema de horarios Problema de horarios. Se deben impartir varias asignaturas y no se pueden programar a la misma hora dos asignaturas que tienen alumnos matriculados en ambas. En este caso los vértices representan asignaturas y una arista entre dos vértices significa que hay alumnos matriculados en las asignaturas que representan los vértices. Lo primero que queremos ver es la forma de leer un grafo cuando la información de la arista es irrelevante los vértices son de tipo String: Graph<String,DefaultEdge> leeAlumnosComunes(String file) { return GraphsReader.newGraph(file, s->s[0], s->new DefaultEdge(), Graphs2::simpleGraph); } Disponiendo del grafo este problema se puede resolver mediante coloreado de grafos. <V, E> Map<V, Integer> coloreado(Graph<V, E> g) { VertexColoringAlgorithm<V> vca = new GreedyColoring<V, E>(g); Coloring<V> vc = vca.getColoring(); return vc.getColors(); } Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla
Análisis y diseño de algoritmos y tipos de datos // Miguel Toro Bonilla Problemas de Grafos 312 El Map resultante asocia un color a cada asignatura. Las asignaturas con el mismo color pueden ser impartidas a la misma hora. Esto lo conseguimos con el código Graph<String,DefaultEdge> g = leeAlumnosComunes(String file); Map<String, Integer> m = coloreado(g); Map<Integer, List<String>> r = m.keySet().stream() .collect(Collectors.groupingBy(s->m.get(s))); El map r está formado por grupos cada uno de los cuales es una franja horaria. El número de franjas horarias es el número de colores diferentes que han hecho falta. ¿Se puede hacer un horario de n horas sin incompatibilidades?
MiguelToroesdoctorenIngenieroIndustrialporlaUniversidadde SevillaycatedráticodelDepartamentodeLenguajesySistemasInformáticosdelamismauniversidad. HasidodirectordelaOficinadeTransferenciadeResultadosde laInvestigación(OTRI)yDirectorGeneraldeInvestigación,TecnologíayEmpresadelaJuntadeAndalucía. HatenidounpapelactivoenlaAgenciaAndaluzadeEvaluación delaCalidadyAcreditaciónUniversitaria(AGAE),hasidomiembro delConsejoAsesordelaAgenciaNacionaldeEvaluacióndelaCalidadyAcreditación(ANECA)ycolaboraasiduamenteconvarias agenciasnacionalesdeevaluaciónuniversitaria. HasidoelPresidentedeSistedes(SociedadNacionaldeIngenieríadelSoftwareyTecnologíasdeDesarrollodeSoftware)yelPresidentedelaSociedadCientíficaInformáticadeEspaña(SCIE)que englobaalosinformáticosdelasuniversidadesespañolas. HarecibidoelPremioFamadelaUniversidaddeSevilla,elPremioSistedesdelaSociedadNacionaldeIngenieríadelSoftwarey TecnologíasdeDesarrollodeSoftwareenreconocimientoasulabor depromociónyconsolidacióndelaInformáticaenEspaña. HarecibidoelPremioNacionaldeInformáticaJoséGarcíaSantesmasesalatrayectoriaprofesionalotorgadoporlaSociedadCientíficaInformáticadeEspaña. ActualmenteesdirectordelInstitutodeIngenieríaInformática delaUniversidaddeSevilla. Biografía