LSO Práctica 1. Soluciones.

> mkdir $HOME/help $HOME/downloads

>mkdir $HOME/downloads/lost

>cd /
>cat $HOME/downloads/lost/index.txt

>man ls

>man ls>$HOME/help/ls.txt

>rm -r $HOME/help/ $HOME/downloads

Centro del universo (Nodo central de redes)

Ejercicio:

El número Bacon (por el actor Kevin Bacon) se define como la distancia mínima entre un actor y Kevin Bacon; dos actores que han trabajado juntos en la misma película tienen distancia uno; dos que no han trabajado juntos pero que han trabajado junto con un tercer actor tienen distancia dos, etc.

Este problema se puede modelar mediante un grafo dirigido (con una arista en cada sentido, puesto que “haber trabajado con” es, evidentemente, una relación conmutativa) y ponderado. El peso de todas las aristas es 1. Cada vértice es una cadena con el nombre del actor o actriz. Cuando existe arista entre dos vértices quiere decir que ambos han actuado juntos en al menos una película. En lo que sigue consideraremos que el grafo es no dirigido. De la misma forma que se define el número Bacon podría haberse definido cualquier otro; por ejemplo, el número Yola de un actor sería la distancia más corta (en el sentido enunciado anteriormente) entre Yola Berrocal y ese actor. Por ejemplo, Santiago Segura tiene número Yola 1 por haber trabajado junto a Yola Berrocal en “Torrente 2”. En este problema vamos a tratar de averiguar quién es el “Centro del Universo”. Para ello vamos a definir un nuevo concepto: se define la media de un actor x como la media de los números x de todos los demás actores y actrices. Por ejemplo, la media Bacon es la media de los números Bacon de todos los demás actores y actrices. Se puede suponer que cuanto más baja es la media de un actor, tanto más céntrico es (en el sentido Hollywood). De modo que se define el “Centro del Universo” como aquel actor o actriz con media más pequeña (puede haber varios). Esto es lo que queremos encontrar. Para ello escríbase un algoritmo que

a) convierta el grafo no dirigido etiquetado (ponderado) de entrada en la matriz de costes equivalente, creando dos Maps (funciones) auxiliares: una, que llamaremos indice que a cada nombre de actor/actriz le asocia el índice de la fila/columna que lo representa dentro de la matriz de costes; la otra la llamaremos nombre y hace corresponder a cada índice en la matriz el nombre correspondiente.

b) a partir de las funciones indice y nombre y de la matriz, encuentre y devuelva un conjunto con los nombres de los actores/actrices de menor media.

Notas:
- Supóngase que disponemos de métodos que implementan los algoritmos vistos en el tema Grafos; si hubiera varios con el mismo nombre, explíquese en un comentario cuál es el que se utiliza.
- Supóngase que el grafo es conexo.
Comentarios anecdóticos e intrascendentes: el día 27 de febrero de 2002 (estos números fluctúan con cada película que se estrena), Kevin Bacon tiene número Yola 3 (actuó con John Malkovich en “Queens Logic“ que a su vez actuó con Inés Sastre en “Beyond the clouds” que ha actuado con Yola Berrocal en “Torrente 2”). La media Bacon actual es 2,917; la media Yola es 3,780. El centro del universo es realmente el actor Christopher Lee (el mítico Drácula). Su media es 2,622940. En este momento se cuentan 498.374 actores/actrices enlazables (omitiendo los que trabajan exclusivamente en televisión) en la base de datos International Movie Data Base (imdb.com), por lo que la matriz de costes tendría 248.376.643.876 elementos: difícilmente se podría resolver por el método propuesto.

Una posible solución:

func centroDelUniverso(g:Graph) dev(actores:Set)
indice, nombre:Map
q: Entero[][]
i,j,k,m, min:Entero
itA,itB:Iterator
vVert,adj:Object

alg
nombre:=Map()
indice:=Map()
actores:=Set()
q:=< crea una matríz de Entero[0...g.size()-1,0...g.size()-1] inicializada a inf>

// Pasar de grafo a matriz de adyacencias
i:=0
j:=0
k:=0
itA:=g.vertices().iterator()
mientras itA.hasNext() //Recorremos todos los vertices del grafo
vVert:=itA.next()
si NO indice.containsKey(vVert) // Si no está en los maps añade al actor
indice.put(vVert,j)
nombre.put(j,Vvert)
j:=j+1
fsi
i:=indice.get(vVert)
q[i][i]:=0 // Del actor a si mismo 0 para que no influya en la media
itB:=g.getAdjacents(vVert).iterator() //Para todos los adyacentes hacer:
mientras itB.hasNext()
adj:=itB.next()
si NO indice.containsKey(adj) // Si no está en los maps añade al actor
indice.put(adj,j)
nombre.put(j,adj)
j:=j+1
fsi
k:=indice.get(adj)
q[i][k]:=1; //Poner distancia 1
fmientras
fmientras


//Algoritmo de Floyd
m := c.length -1
desde k := 0 hasta m
desde i := 0 hasta m
desde j := 0 hasta m
si q[i, k] + q[k, j] < q[i, j]:
q[i, j] := q[i, k] + q[k, j]
fsi
fdesde
fdesde
fdesde

// Resolucion problema

min:=inf
desde i:=0 hasta m //Para todos los actores
desde j:=0 hasta m //suma de las distancias al resto de actores
k:=k + q[i,j]
fdesde
si k < min // si las distancias son menores, es que la media es menor, por tanto elimina la lista
actores:=Set() // y empieza una con el actor que posee el mínimo hasta este momento.
actores.add(nombre.get(i))
min:=k // actualizamos k
| k=min
actores.add(nombre.get(i)) // Si tienen igual media, lo añadimos a la lista
fsi
fdesde
fin

Salida de un laberinto por búsqueda en profundidad

Ejercicio:

El problema del laberinto puede verse como una serie de habitaciones con puertas por las que se puede pasar a habitaciones adyacentes. La idea es que empezando por una habitación de entrada, hay que encontrar el camino que nos lleva a la habitación de salida. Para ello, de una habitación a otra sólo se puede pasar si hay una puerta entre las dos habitaciones. Todo esto se puede representar mediante un grafo. a) Indíquese cuáles serán los vértices, las aristas y qué tipo de grafo necesitaremos.

b) Escríbase un procedimiento que, tomando una habitación de entrada, otra de salida y el grafo representando el laberinto, escriba, si existe, las habitaciones que componen el camino desde la entrada a la salida. ¿En qué algoritmo se basa la solución propuesta?

Notas:
1. Si se usan estructuras auxiliares, justifíquese su uso.
2. Úsense todas las estructuras necesarias manipulándolas como TAD.
3. El camino resultante, si existe, se puede escribir tanto desde la entrada a la salida, como desde la salida a la entrada.
4. En el caso de que exista más de un camino desde la entrada a la salida, sólo se escribirá el primero que se encuentre.
5. Los vértices no tienen ningún tipo de información asociada, y no se puede modificar su estructura.

Una posible solución en pseudocódigo:

Los nodos son las habitaciones y las puertas las arístas. Necesitaremos un grafo no dirigido y no etiquetado ya que las puertas suponemos que se pueden abrir desde los dos lados.

clase SalidaLaberinto

proc SalidaLaberinto(u,dest: Object, g:Graph)
sol:List
visitados: Set
alg
sol:=List()
visitados:=Set()
si depthFirstSearchModified(u,dest,g,visitados,sol)
mostrar(sol)
| otros:
mostrar("No hay camino hacia la salida")
fsi
fin

func depthFirstSearchModified(u: Object, dest:Object, g: Graph; ent/sal visitados: Set, sol:List) dev(b:Boolean)
v: Object
adyacentes: Set
itd: Iterator
alg
b:=false
sol.add(u)
si u.equals(dest)
b:=true
|otros:
visitados.add(u)
adyacentes := g.getAdjacents(u)
itd := adyacentes.iterator()
mientras itd.hasNext() y no b
v := itd.next()
si no visitados.contains(v):// Equivalente a “si no visitado”
b:=depthFirstSearch(v, g, visitados, sol)
fsi
fmientras
si no b
sol.remove(u)
fsi
fsi
fin
finClase

Altura y Tipo de arbol (java)

El problema es el siguente:

Realizar una función recursiva que reciba como parámetro de entrada un BinaryTree y que devuelva la altura del árbol y un String que podrá tomar cuatro valores: “V” (Vacío), “CO” (Completo), “CA” (Casi Completo) u “O” (Otros), en función del tipo del árbol.
Notas:
El árbol sólo se puede recorrer una vez.
Se definirá la altura de un árbol vacío como - 1, y la de un árbol con un elemento como 0.
Se supone implementada una función max(intege, integer) que devuelve el máximo entre los enteros que se le pasan como parámetros de entrada.

Una posible solucion en java es la siguente:


public doble alturaYTipodeArbol2(Nodo b){
doble izq=new doble(),der=new doble(),res=new doble();

if(b.isEmpty()){
res.a=-1;
res.tipo="V";
} else if(b.isLeaf()){
res.a=0;
res.tipo="CO";
}else{
if(b.left()!=null){
izq=alturaYTipodeArbol(b.left());}
if(b.right()!=null){
der=alturaYTipodeArbol(b.right());}
res.a=max(izq.a,der.a)+1;
if(b.left()==null){
res.tipo="O";}
else if(b.right()==null){
if(izq.a==0){
res.tipo="CA";}
else{
res.tipo="O";}}
else if(izq.a==der.a && izq.tipo.equals("CO") && der.tipo.equals("CO")){
res.tipo="CO";}
else if((izq.tipo.equals("CO") && der.tipo.equals("CA") && izq.a==der.a)|| ((izq.tipo.equals("CO") || izq.tipo.equals("CA"))&& der.tipo.equals("CO") && izq.a==der.a+1)){
res.tipo="CA";{
else {
res.tipo="O";}
}
return res;
}
public int max(int a, int b){
int aux;
if(a < b){
aux=b;}
else{
aux=a;}
return aux;
}


Monticulo de máximos a lista en orden inverso (java)

El problema es el siguiente:


Realice un algoritmo que partiendo de un montículo de máximos, representado con un BinaryTree, devuelva una lista de los elementos de dicho montículo ordenados de mayor a menor. Los elementos del montículo son enteros.
NOTA: Se pueden utilizar estructuras auxiliares.

Para quién llame al montículo de máximos de otra forma, decir que es un árbol (binario en éste caso) en el que cada nodo es mayor o igual que sus hijos.

Dicho esto pondré la primera solucion en JAVA:


public LinkedList monticuloAlistaOrdenInverso2(BinaryTree b){
LinkedList sol = new LinkedList();
LinkedList laux = new LinkedList();
BinaryTree a;
int max, imax=0;
if(!b.isEmpty()){
laux.add(b);
a=b;
while(laux.size() > 0){
sol.add(a.getRoot());
laux.remove(imax);
if(a.left()!= null){
laux.add(a.left());}
if(a.right()!= null){
laux.add(a.right());}
max=Integer.MIN_VALUE;

for(int i=0; i < laux.size();i++){
if(max < laux.get(i).getRoot()){
max=laux.get(i).getRoot();
imax=i;
}
}
if(!laux.isEmpty()){
a=laux.get(imax);}
}
}
return sol;
}


Otra solución para montículos que no tengan valores repetidos es la siguiente:


public LinkedList monticuloAlistaOrdenInverso(BinaryTree b){
LinkedList l = new LinkedList();
TreeSet s = new TreeSet();
Object o;
Iterator i=b.iterator();
while(i.hasNext()){
s.add(i.next());
}
while(!s.isEmpty()){
o=s.last();
l.add(o);
s.remove(o);
}
return l;
}


Practica 5 ASPP

.386
.MODEL flat
OPTION CASEMAP:N
.CODE
PUBLIC _int2fp
_int2fp PROC
; Cuerpo del pro
push ebp
mov ebp,esp
push eax
push ebx
push ecx
push edx

xor eax,eax
xor ebx,ebx
xor ecx,ecx
xor edx,edx

mov ecx, [ ebp
mov eax, [ ebp

cmp eax,0
je Cero

cmp eax,0
jge Bucle
mov dh,1
neg eax

Bucle: cmp eax
je Fb
shrd ebx,eax,1
shr eax,1
add dl,1
jmp Bucle

Cero: mov eax,
jmp Fin

Fb:add dl,127
xor eax,eax
mov ax,dx
shld eax,ebx,

Fin:mov [ ecx]

pop edx
pop ecx
pop ebx
pop eax
pop ebp

ret



_int2fp ENDP
END

Problema 6 Practica 2

public class Practi02E6 {
public static void main(String[ ] args) {
int [ ] size = {10000, 100000, 1000000, 10000000};
long [ ] tiempos= new long [ 3*size.length];
Temporizador t = new Temporizador(5);
CronometraMetodoBinarySearch CMBN = new CronometraMetodoBinarySearch(1,1);

for(int i=0;i < size.length;i++){
CMBN.setTamaño(size[ i]);
for(int j=0;j<3;j++){
CMBN.setCaso(j);
t.cronometra(CMBN);
tiempos[ 3*i+j]=t.getTiempoMinimo();
}
}
for(int i=0;i < size.length;i++){
System.out.println("Caso: EP, Tamaño: "+size[ i]+" \tTiempo: "+tiempos[ 3*i]+" ns");
System.out.println("Caso: EM, Tamaño: "+size[ i]+" \tTiempo: "+tiempos[ 3*i+1]+" ns");
System.out.println("Caso: EF, Tamaño: "+size[ i]+" \tTiempo: "+tiempos[ 3*i+2]+" ns");
}
}
}


public class CronometraMetodoBinarySearch implements EstrategiaSolucion{

public static final int EXITO_PRINCIPIO = 0;
public static final int EXITO_MITAD = 1;
public static final int EXITO_FINAL = 2;
public static final int SIN_EXITO_PRINCIPIO = 3;
public static final int SIN_EXITO_MITAD = 4;
public static final int SIN_EXITO_FINAL = 5;

private int numElem;
private int casoDeBusqueda;
private int [] datos;
private int numBuscado;

public CronometraMetodoBinarySearch(int numElem, int casoDeBusqueda) {

// TODO
this.numElem=numElem;
this.casoDeBusqueda=casoDeBusqueda;
this.datos= new int[this.numElem];
this.inicializaDatos();
this.generaNumBuscado();

}

public void setTamaño(int tam){
this.numElem=tam;
this.datos= new int[this.numElem];
this.inicializaDatos();
}

public void setCaso(int casoBusqueda) {

// TODO
this.casoDeBusqueda=casoBusqueda;
this.generaNumBuscado();
}

private void generaNumBuscado() {
switch(casoDeBusqueda) {
case EXITO_PRINCIPIO:
numBuscado = datos[0];
break;
case EXITO_MITAD:
numBuscado = datos[(numElem - 1) / 2];
break;
case EXITO_FINAL:
numBuscado = datos[numElem - 1];
break;
case SIN_EXITO_PRINCIPIO:
numBuscado = datos[0] - 1;
break;
case SIN_EXITO_MITAD:
numBuscado = datos[numElem / 2] - 1;
break;
case SIN_EXITO_FINAL:
numBuscado = datos[numElem - 1] + 1;
break;
default:
// no puede darse ningún otro caso
}
}

private void inicializaDatos() {
for(int i = 0; i < numElem; i++) {
// tomando pares dejamos sitio para las búsquedas fallidas
datos[i] = 2 * (i + 1);
}
}

public void procesamientoFinal() {

}

public void procesamientoInicial() {

}

public void solucion() {
Arrays.binarySearch(this.datos, this.numBuscado);

}

}