INF-221 Algoritmos y Complejidad, 2020-1
Tarea 1
Profesor: Diego Arroyuelo
Ayudantes: Tomás Berrios, Gabriel Carmona
[Link]@[Link],
[Link]@[Link]
Fecha de Entrega: 24 de junio, 2020
Plazo máximo de entrega: 5 dı́as.
Reglas del Juego
La presente tarea debe hacerse en grupos de 3 personas. Toda excepción a esta regla debe ser conversada
con los ayudantes ANTES de comenzar la tarea. No se permiten de ninguna manera grupos de más de 3
personas. Pueden usarse los lenguajes de programación C, C++, Python, y Java.
1. Joins en Bases de Datos [35 %]
En bases de datos relacionales, la operación join (denotada con ./) permite combinar tuplas de distintas
relaciones, formando tuplas más grandes. Dado que la normalización en bases de datos relacionales genera
varias relaciones, la operacion join permite (entre otras cosas) obtener la información original (es decir, antes
de la normalización). Esto hace a los joins una de las operaciones más tı́picas y empleadas en bases de datos
relacionales. Por ejemplo, si tenemos las relaciones R(A, B) (es decir, que tiene atributos A y B) y S(B, C)
(con atributos B y C), la operación R(A, B) ./ S(B, C) produce como resultado una relación T (A, B, C). En
este caso, el atributo B es conocido como atributo de join: es ese atributo el que se usa para combinar tuplas
de R y S. Vamos a considerar únicamente el caso de join natural en esta tarea. Esto eso, un join que se
realiza sólo teniendo en cuenta la igualdad de los valores de los atributos de join. Por cada tupla (ai , bj ) ∈ R
y (bj , ck ) ∈ S, el join produce la tupla (ai , bj , ck ) en T . Considere el siguiente ejemplo de join:
R (A B)
1 2 T (A B C)
2 4 S (B C)
1 2 3
4 1 3 1
= 5 2 3
5 2 ./ 2 3
4 5 3
4 5 5 3
3 5 3
3 4
3 5
La operación join está definida no sólo para relaciones binarias (como lo hemos explicado), sino que puede
extenderse a relaciones de cualquier aridad, y cualquier cantidad de atributos de join. Por ejemplo, podemos
tener R(A, B, C) ./ S(A, C, D), que producirá la relación T (A, B, C, D). La tarea consiste en implementar un
algoritmo de fuerza bruta para resolver la operación join. Los atributos de cada relación serán representados
por números enteros.
1
Formato de Entrada
La entrada de datos será a través de la entrada estándar (stdin). La primera lı́nea de la entrada contiene
un único número entero N, indicando la cantidad de atributos de la relación R. Puede asumir que 1 ≤ N ≤ 100.
La siguiente lı́nea de la entrada contiene N valores enteros, separados entre si por un único espacio en blanco,
indicando los atributos de la relación R. Los valores están ordenados de forma creciente. La siguiente lı́nea
contiene un valor entero NR, tal que 1 ≤ NR ≤ 10, 000, e indica la cantidad de tuplas de la relación R. Luego,
le siguen NR lı́neas, cada una con N valores enteros (separados entre sı́ por un único espacio), correspondientes
a las tuplas de la relación R. A continuación, le sigue una lı́nea que contiene un único número entero M,
indicando la cantidad de atributos de la relación S. Puede asumir que 1 ≤ M ≤ 100. La siguiente lı́nea de la
entrada contiene M valores enteros, separados entre si por un único espacio en blanco, indicando los atributos
de la relación S. Los valores están ordenados de forma creciente. La siguiente lı́nea contiene un valor entero NS,
tal que 1 ≤ NS ≤ 10, 000, e indica la cantidad de tuplas de la relación S. Luego, le siguen NS lı́neas, cada una
con M valores enteros (separados entre sı́ por un único espacio), correspondientes a las tuplas de la relación S.
Un ejemplo (que replica el ejemplo mostrado anteriormente) es el siguiente:
2
0 1
7
1 2
2 4
4 1
5 2
4 5
3 4
3 5
2
1 2
3
3 1
2 3
5 3
Formato de Salida
La salida se hará a través de la salida estándar (stdout). Debe mostrar el resultado de la operación join
sobre las dos relaciones dadas en la entrada. El formato es el siguiente: la primera lı́nea debe contener un
valor P, indicando la cantidad de atributos de la relación resultante del join. Luego, le sigue una lı́nea que
contiene P valores enteros, separados entre si por un único espacio, y ordenados de forma creciente. Esos
valores indican los atributos de la relación resultante. Luego, le sigue una lı́nea que contiene un único valor
entero NT, que es la cantidad de tuplas del join. Finalmente, se tienen NT lı́neas, cada una con P valores
enteros separados por un único espacio, correspondientes a las tuplas del join.
La salida correspondiente al ejemplo mostrado anteriormente es:
3
0 1 2
4
1 2 3
5 2 3
4 5 3
3 5 3
2
2. Contando Triángulos en Grafos [15 %]
Sea G = (V, E) un grafo dirigido con conjunto de vértices V y aristas E. En esta parte, debe implementar
un algoritmo que use el algoritmo de join de la sección anterior para contar la cantidad de triángulos que
tiene G. Esto es una aplicación importante en muchas aplicaciones, como por ejemplo redes sociales y biologı́a.
Un triángulo es un patrón del siguiente tipo:
B C
Suponga que los arcos del grafo estarán representado por una relación binaria E(A, B), en donde por cada
arco a → b en el grafo, tenemos la tupla (a, b) ∈ E.
La entrada de datos se hará mediante la entrada estándar (stdin). Cada lı́nea contiene dos valores enteros,
que representan un arco (dirigido) del grafo. la entrada es terminada con EOF. La salida se hará a través de la
salida estándar (stdout). Se debe imprimir una única lı́nea que contiene la cantidad de triángulos del grafo
dado en la entrada.
3. Algoritmo de Multiplicación de Matrices [50 %]
Dadas dos matrices A y B, ambas de dimensión n × n, el algoritmo del tipo Dividir y Conquistar de
Strassen permite calcular A × B en tiempo Θ(n2,81 ), mientras que el algoritmo tradicional de multiplicación
de matrices es de tiempo Θ(n3 ). El objetivo de esta parte de la tarea es estudiar e implementar el algoritmo
de Strassen, para poder aplicarlo en las siguientes situaciones:
Problema 1: Suponga que quiere multiplicar dos matrices X e Y , de dimensiones kn × n y n × kn,
respectivamente. Implemente un algoritmo para llevar a cabo dicha multiplicación, usando el algoritmo
de Strassen como subrutina.
Problema 2: Idem al problema anterior, pero ahora asumiendo que las matrices tienen dimensión n × kn y
kn × n, respectivamente.
Escriba un informe (idealmente usando LATEX, aunque no es obligatorio su uso) en el que muestre la
comparación del algoritmo de Strassen y el tradicional para multiplicar matrices, para diferentes valores de k
y n. Resuma sus experimentos en unos pocos gráficos (su informe no deberı́a tener más de 2 páginas). Agregue
observaciones y conclusiones de sus experimentos, ası́ como una explicación clara de cómo se realizaron los
experimentos (quien lea su informe, deberı́a ser capaz de replicar sus experimentos sin problemas).
Formato de Entrada
La entrada de datos será a través de la entrada estándar (stdin). Para estos dos problemas, la entrada
comienza con una lı́nea que contiene dos números enteros, N y k. Luego le siguen los valores que componen a
las dos matrices, escritos por filas y los valores separados entre si por un único espacio (primero las filas de la
matriz A, y a continuación las de la matriz B). Asuma que las matrices están formadas por valores enteros.
Formato de Salida
La salida se hará a través de la salida estándar (stdout). La primera lı́nea de la salida contiene dos
números, N y M , indicando las dimensiones de la matriz resultante de la multiplicación de las dos matrices
de la entrada. Le siguen N lı́neas, cada una conteniendo M valores enteros. Cada una de esas lı́neas es una
fila de la matriz.
3
4. Entrega de la Tarea
La entrega de la tarea debe realizarse enviando un archivo comprimido llamado
[Link]
(reemplazando sus apellidos según corresponda), o alternativamente usando formato zip, en el sitio Aula USM
del curso, a más tardar el dı́a 24 de junio, 2020, a las [Link] hrs (Chile Continental), el cual contenga:
Los archivos con el código fuente necesarios para el funcionamiento de la tarea.
[Link], Nombre y ROL de cada integrante del grupo.
[Link], Instrucciones de compilación en caso de ser necesarias.
Makefile, Instrucciones para compilación automática.
