Examen IIC1103 ENUNCIADO 2013 2

´ lica de Chile
Pontificia Universidad Cato
Escuela de Ingenier´ıa
´n
Departamento de Ciencia de la Computacio
Segundo Semestre de 2013

IIC 1103

Introducci´
on a la Programaci´
on
Examen

Instrucciones
Debes marcar tu n´
umero de alumno y el n´
umero de pregunta correctamente y con un l´apiz
NOTORIAMENTE OSCURO en cada una de las hojas de respuesta. Si tu n´
umero de alumno
no se lee bien oest´a mal marcado en una hoja, tendr´as UN PUNTO MENOS en la pregunta
correspondiente.
Los ejercicios deben ser respondidos en HOJAS SEPARADAS. No se aceptar´an hojas de respuesta que contengan respuestas a dos ejercicios distintos.
Puedes utilizar m´as de una hoja para responder una misma pregunta, pero tu n´
umero de alumno
y el n´
umero de pregunta deben estar marcados correctamente en TODAS LASHOJAS.
Marca tu n´
umero de alumno por filas de arriba hacia abajo. Si tu n´
umero de alumno termina
en j, deja la u
´ltima fila en blanco.
El tiempo disponible para realizar la evaluaci´on es estrictamente de 3 horas, no se dar´a tiempo
adicional.
Durante la evaluaci´on NO est´a permitido utilizar apuntes.
NO est´a permitido el uso de aparatos electr´onicos, los celulares deben estar apagados y nopueden ser consultados en ning´
un momento (ni siquiera para ver la hora). El tiempo restante
se informar´a oportunamente.
El puntaje de las preguntas se distribuye uniformemente, a menos que se indique lo contrario.

1

1. [10 puntos] La red social Pajaritos se basa en una lista de usuarios de la red, y relaciones entre
estos usuarios, especificadas a trav´es de la relaci´on seguir. Cuando unusuario a est´a relacionado
con un usuario b, se dice que el usuario a sigue al usuario b.
La relaci´on seguir no es necesariamente sim´etrica, lo que significa que es posible que el usuario
a siga al usuario b, pero que el usuario b no siga al usuario a. Adem´as ning´
un usuario se sigue
a s´ı mismo.
Estas caracter´ısticas permiten identificar algunos perfiles interesantes como el perfil estrella.´
Este
es un tipo de usuario que tiene muchos seguidores, al menos el 50 % de la red, pero sin
embargo ´el sigue a muy pocas personas (menos del 20 % de la cantidad que lo sigue a ´el). Estos
usuarios provocan una alta carga en la red cada vez que publican un mensaje.
Adem´as existen categor´ıas definidas por relaciones entre grupos de usuarios. Por ejemplo:
Amigos. Dos usuarios son amigos, si sesiguen mutuamente.
Tri´angulos. Tres usuarios forman un tri´angulo cuando el primer usuario sigue al segundo,
el segundo sigue a un tercero, y ´este a su vez sigue al primero.
Comunidad. Tres o m´as usuarios forman una comunidad cuando todos son amigos entre s´ı.
Note que una comunidad de tres amigos tambi´en forma un tri´angulo, pero no todo tri´angulo
forma una comunidad de tres amigos.
Consideraque en la red hay N usuarios, y que cada usuario es representado por un n´
umero entre
0 y N-1. Los desarrolladores de la red social representan la relaci´on de seguir utilizando una
matriz de 1’s y 0’s de nombre sigue y dimensi´on N×N. Un usuario a sigue a otro usuario b
cuando el valor sigue[a][b] es 1. En caso contrario, el valor es 0.
Tu tarea ser´a programar algunas funciones que permitan alos mantenedores de la red identificar
a todos los usuarios o grupos de usuarios que cumplan alguna condici´on:
a) [1 punto] seguidos(sigue,a). Retorna una lista con todos los usuarios que son seguidos
por el usuario a.
b) [1 punto] seguidores(sigue, a). Retorna una lista con todos los usuarios que siguen al
usuario a.
c) [1 punto] estrellas(sigue). Retorna una lista con todos los usuariosestrella de la red
social.
d ) [1 punto] amigos(sigue,a,b). Retorna True si los usuarios a y b son amigos, y False en
caso contrario.
e) [2 puntos] triangulo(sigue,a,b,c). Retorna True si los usuarios a, b y c forma un triangulo. Note que el orden en que los usuarios forman el tri´angulo puede ser cualquiera, no
necesariamente a, b, c.
f ) [2 puntos] triangulos(sigue). Retorna la cantidad de...