BD I - Capítulo 1. Introducción

Base de Datos I

Damos inicio al estudio de una nueva asignatura. No es la intención del curso focalizarse en conceptos teóricos, preferimos dejarle ese aspecto a autores como Date, Elmasri y Navathe.

Solamente a modo de introducción diremos que una Base de Datos es un conjunto de datos almacenados entre los que existen relaciones lógicas y que ha sido diseñada para satisfacer los requerimientos de información de una determinada empresa u organización.

Todos los contenidos que estudiaremos en los capítulos siguientes corresponderán al modelo de datos relacional. Cuando decimos modelo de datos nos referimos a que deben describirse:

• Estructuras de datos: Son los tipos de datos que existen en la base y la forma en que se relacionan.
• Restricciones de integridad: Condiciones que deben cumplir los datos para reflejar correctamente la realidad.
• Operaciones de manipulación de datos: Básicamente operaciones de inserción, eliminación, modificación y recuperación de datos.

En particular, las Bases de datos relacionales modelan la realidad utilizando relaciones. Estas relaciones pueden considerarse en forma lógica como conjuntos de datos. Pensamos cada relación como tablas compuestas por registros (las filas de la tabla) y campos (las columnas de la tabla).

Los temas que iremos abordando en los próximos capítulos son:

• Álgebra Relacional
• SQL
• Dependencias Funcionales
• Normalización de Base de Datos 

Capítulo 21. Algoritmos Greedy: Ejemplo de la mochila (Parte III)

Realizamos una ligera modificación al pseudocódigo del algoritmo de la mochila para poder almacenar los elementos que forman parte de la solución y devolverlos como resultado

Pseudocódigo

Análisis de Complejidad Temporal

El análisis es idéntico al realizado para el algoritmo del capítulo previo. La complejidad queda en el orden O(n*log(n)) si utilizamos MergeSort para ordenar la cadena por la razón Beneficio/Peso.

Capítulo 20. Algoritmos Greedy: Ejemplo de la mochila (Parte II)

Presentamos el pseudocódigo del ejemplo que resolvimos manualmente en el capítulo anterior.

Pseudocódigo

Análisis de Complejidad Temporal

Cabe señalar una importante diferencia respecto del análisis temporal para el ejemplo del cambio. Fijemos nuestra atención en el bloque 'mientras' y las condiciones:

i <= longitud(S) y capacidadParcial < P

En el peor de los casos, el bloque se ejecutará 'n' veces, siendo 'n' la cantidad de elementos en la secuencia S. Es decir, tiene mayor peso la condición i <= longitud(S) que la condición capacidadParcial < P.

Esto es así debido a que los objetos son finitos y no pueden repetirse en el armado de la solución final. Distinto era el caso en el ejemplo del cambio donde teníamos instancias infinitas de cada moneda y el objetivo era cubrir un importe P.

 

Las sentencias contenidas en el bloque 'mientras' tienen una complejidad constante dando un costo de O(n) para todo el bloque por lo explicado anteriormente.

Se observa entonces que la complejidad temporal del algoritmo dependerá del método de ordenamiento elegido para "ordenarPorBeneficioPeso". Si utilizamos MergeSort la complejidad temporal de MOCHILA_GREEDY nos queda en O(n*log(n)).

No debe sorprendernos que la complejidad en algoritmos Greedy venga dada por el método de ordenamiento utilizado ya que es la forma más eficiente que encontramos para implementar la estrategia de selección.

En el próximo capítulo haremos una ligera modificación al pseudocódigo de forma que nos permita guardar los elementos que serán almacenados en la mochila.

Fuentes:

Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda

Capítulo 19. Algoritmos Greedy: Ejemplo de la mochila (Parte I)

Continuando con los Algoritmos Greedy, centraremos nuestra atención en el ejemplo de la mochila. La descripción del problema es la siguiente:

Se tienen n objetos y una mochila con capacidad P. Cada uno de los n objetos tiene dos propiedades: peso y beneficio. Para i = 1, 2, ..., n, el objeto i tiene un peso p_i y un beneficio b_i. Tanto el peso como el beneficio son siempre positivos.

Además, los objetos pueden ser fraccionados, esto quiere decir que puedo llevar 1/2, 1/3 o cualquier otra fracción de un objeto.

Matemáticamente si una fracción x_i (0<x_i<1) del objeto i es colocada en la mochila, esta fracción contribuye en un peso x_i*p_i y en un beneficio x_i*b_i.

Para dejar en claro esto último, si tengo un objeto i cuyo peso es 12 y beneficio es 9, si decido llevar 1/3 del objeto, la contribución de este objeto al problema sería:

Peso = x_i*p_i = 1/3*12 = 4. 
Benefición = x_i*b_i = 1/3*9 = 3. 

Aclarado todo esto, el objetivo del problema es llenar la mochila de forma tal que se maximice el beneficio de los objetos transportados sin exceder la capacidad P (peso total) de la mochila.

Vamos a resolver un ejemplo de este problema en forma manual y en el siguiente capítulo lo haremos a través del pseudocódigo. Supongamos entonces que tenemos la siguiente instancia del problema:

La capacidad P de la mochila es 12 y poseemos el conjunto de elementos:

Elementos = { (p = 5; b = 4) , (p = 7; b = 5), (p = 2; b = 3), (p = 6; b = 3), (p = 4; b = 5) }

Con el fin de abreviar la nomenclatura representaremos a cada elemento e_i con el par (p_i, b_i). De esta forma, el conjunto anterior es simplemente:

Elementos = { (5,4), (7,5), (2,3), (6,3), (4,5) }

Recordemos que en los algoritmos Greedy podía identificarse una función selección, muchas veces asociada a la forma de ordenar el conjunto de elementos candidatos. En forma intuitiva, ya que el objetivo es maximizar el beneficio y los objetos pueden fraccionarse, convendría ordenar los elementos por su relación beneficio/peso en forma decreciente. Así, el conjunto de elementos ordenado por b/p nos queda:

Elementos = { (2,3), (4,5), (5,4), (7/5), (6, 3) }

Ahora, deberíamos ir tomando cada uno de estos elementos y verificar que no nos excedamos de la capacidad P de la mochila. Llamaremos W al peso parcial y B al beneficio parcial tras la elección de cada elemento (actúan como contadores).

Empecemos entonces tomando el primer elemento del conjunto ordenado, el (2,3). Nuestros contadores quedan:

W = 2
B = 3

Ya que no nos excedimos de la capacidad P, procedemos a elegir el siguiente elemento (4, 5):

W = 2 + 4 = 6
B = 3 + 5 = 8

Siendo que 6 es menor a P = 12 elegimos un tercer elemento, el (5,4):

W = 6 + 5 = 11
B = 8 + 4 = 12

El peso parcial acumulado aún no excede la capacidad de nuestra mochila, es por ello que podemos elegir un nuevo elemento: el (7,5).

W = 11 + 7 = 18 
B = 12 + 5 = 17

¿Qué ha pasado? Hemos superado la capacidad total P de la mochila. Siendo que el peso acumulado W del paso anterior era igual a 11, sólo necesitábamos contribuir en 1 para alcanzar la capacidad total. Aquí es cuando debemos fraccionar el elemento.

Es fácil ver que con la fracción 1/7 cumpliremos nuestro cometido y los acumuladores quedarán:

W = 11 + 1/7*7 = 12
B = 12 + 1/7*5 = 89/7

Todo esto realizado en forma intuitiva deriva en la solución óptima. Vale aclarar que debería demostrarse matemáticamente, cosa que excede el alcance de nuestro curso.

Esto mismo que hemos hecho manualmente, se verá plasmado en pseudocódigo en el siguiente capítulo.

Capítulo 18. Algoritmos Greedy: Ejemplo del cambio

En este y capítulos posteriores iremos analizando distintos ejemplos de aplicación de la técnica de algoritmos Greedy. Comenzaremos con estudiar el más sencillo de todos: el problema del cambio.

Se desea encontrar la forma de devolver un vuelto de valor 'v' con monedas de denominaciones d₁, d₂, ..., d_n considerando que existe una cantidad infinita de monedas de cada denominación.

Por ejemplo, queremos devolver $1.83 y disponemos de monedas de 1, 5, 10, 25, 50 centavos y 1 peso. La forma más sencilla e intuitiva de hacerlo es con una moneda de 1 peso, una moneda de 50 centavos, una moneda de 25 centavos, una moneda de 5 centavos y tres monedas de 1 centavo.

Esto que hacemos en forma intuitiva (devolver la cantidad pedida con la menor cantidad posible de monedas) puede expresarse en el siguiente algoritmo:

Cómo se estudió en el capítulo 16, debería ser posible identificar las 4 funciones que caracterizan a los algoritmos Greedy.

Así, el conjunto de candidatos es el conjunto de monedas disponibles y se dispone de infinitas monedas de cada denominación. El conjunto de candidatos pendientes viene dado por las posiciones mayores o iguales a i en la cadena 'monedas'.

La función selección es la que elige el elemento de la posición i sumado a que las monedas están ordenadas de mayor a menor (se indicó como 100 la moneda de 1 peso para diferenciarla de la moneda de 1 centavo).

La función de factibilidad es la que pregunta si s + monedas[i] < v (es decir, está preguntando si al sumarle el candidato elegido en ese momento al vuelto parcial 's', no nos estamos pasando del valor v a devolver).

La función solución es la que evalúa s < v y la función objetivo, implícita, es la que minimiza la cantidad de monedas.

Debemos tener en cuenta que este algoritmo es correcto para las denominaciones de monedas utilizadas. Para otras instancias del problema el algoritmo deja de ser óptimo y es necesario emplear otra técnica distinta que estudiaremos más avanzado el curso.

Para ilustrar este hecho supongamos que nuestra cadena de monedas es = [6, 4, 1] y se nos pide devolver un cambio de 8.

El algoritmo presentado en este capítulo nos daría el vuelto con una moneda de 6 y dos monedas de 1 (totalizando 3 monedas) cuando intuitivamente podemos apreciar que la manera más óptima sería devolver dos monedas de 4.

Fuentes:

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.