Primer Parcial 22/4/2013 (2014)

Examen Español
Universidad Universidad Politécnica de Valencia (UPV)
Grado Ingeniería Informática - 2º curso
Asignatura Estructura de Datos y Algoritmos
Año del apunte 2014
Páginas 5
Fecha de subida 27/11/2014
Descargas 4
Subido por

Descripción

Resolución del Primer Parcial de EDA (22 de Abril de 2013)

Vista previa del texto

Resolución del Primer Parcial de EDA (22 de Abril de 2013) 1.- En el paquete lineales, se ha diseñado la clase LPIMap que figura a continuación para implementar la interfaz genérica Map mediante una ListaConPI (ver en el Anexo la definición de estas interfaces). Se pide concluir su diseño, completando los huecos que aparecen en su código.
(2.25 puntos) public class LPIMap V> implements Map<C, V> { LPIMap<C, Map class EntradaMap V> { EntradaMap<C, Map protected C clave; protected V valor; EntradaMap c, V v){ this.clave = c; this.valor = v; } EntradaMap(C Map public String toString(){ return "("+this.clave+", "+this.valor+")\n"; } toString } protected ListaConPI<EntradaMap ListaConPI<EntradaMap<C, Map<C, V>> lpi; public LPIMap this.lpi = new LEGListaConPI<EntradaMap<C,V>>(); } LPIMap(){ Map /** si no existe, inserta la Entrada (c, v) en un Map y devuelve null; si ya existe, * devuelve su valor y lo substituye por v, i.e. actualiza la Entrada de Clave c */ (1.25 puntos) public V insertar(C insertar c, V v){ V valorAntinguo = null; EntradaMap<C, V> nueva = new EntradaMap<C, V>(c, v); // buscar primero en la Lista lpi una Entrada con la misma Clave c que nueva for ( lpi.inicio(); !lpi.esFin() && !lpi.recuperar().clave.equals(c); lpi.siguiente() ); // Resolución de la Búsqueda: Búsqueda: si ya existe una Entrada con Clave c, recuperar su valor y // actualizarlo (o bien, insertar nueva y eliminar la ya existente de Clave c); sino, // insertar nueva en fin de Lista if ( !lpi.esFin() ){ valorAntiguo = lpi.recuperar().valor; lpi.recuperar().valor = v; //o //o bien: bien: lpi.insertar(nueva); lpi.eliminar(); } else lpi.insertar(nueva); return valorAntiguo;; } /** si existe, elimina la Entrada con Clave c de un Map y devuelve su valor asociado, * null si no existe una Entrada con dicha clave */ (0.7 puntos) public V eliminar(C c){ eliminar V valor = null; // buscar primero en la Lista lpi una Entrada con la Clave c for ( lpi.inicio(); !lpi.esFin() && !lpi.recuperar().clave.equals(c); lpi.siguiente() ); // Resolución de la Búsqueda: si existe la Entrada de Clave c, devolver su valor y eliminarla; si // no existe, devolver null if ( !lpi.esFin() ){ valor = lpi.recuperar().valor; lpi.eliminar(); } lpireturn valor;;eliminar(); } /** comprueba si un Map está vacío */ public boolean esVacio(){ return esVacio (0.1 puntos) lpi.esVacia(); } /** devuelve la talla, o número de Entradas, de un Map */ (0.1 puntos) public int talla() talla(){ () return lpi.talla(); } /** devuelve un String con todas las Entradas de un Map */ public String toString(){ toString() return lpi.toString() ; } … } (0.1 puntos) 2.- Sea v un array de Integer que se ajustan al perfil de una curva continua y monótona creciente, tal que v[0]<0 y v[v.length-1]>0. Existe una única posición k de v, 0≤k<v.length-1, tal que entre v[k] y v[k+1] la función vale 0.
Ejemplo: 0 -3 1 -2 2 -1 3 1 4 4 5 5 Se pide diseñar el método recursivo que más eficientemente calcule dicha posición k.
(2.25 puntos) //SII v.length>1 && v[0]<0 && v[v.length v[v.length-1]>0 public static int indiceDelCero(Integer[] (Integer[] v){ v) return indiceDelCero(v, (v, 0, v.length-1); v.length } private static int indiceDelCero(Integer[] indiceDelCero v, int ini, int fin){ // Búqueda con garantía de éxito del índice del cero en el subArray ordendado // ascendendentemente v[ini...
v[ini...fin ...fin] fin] con estrategia DyV, se divide en 2 el problema int mitad = (ini+fin)/2; // Para que mitad sea el índice del cero, como mínimo v[mitad]<=0 if ( v[mitad]<=0 ){ // si v[mitad]<=0 y v[mitad+1]>0, entonces mitad es el índice del cero if ( v[mitad+1]>0 ) return mitad; // sino, si v[mitad]<=0 pero v[mitad+1]<=0, el índice del cero NO es v[mitad] y, // además, solo puede estar “detrás” de mitad, i.e. en el subArray v[mitad+1...
v[mitad+1...fin] ...fin] else return indiceDelCero(v, mitad+1, mitad+ fin); } // Si v[mitad]>0, v[mitad]>0, el índice del cero NO es v[mitad] y, además, solo puede estar // “antes” antes” de mitad, i.e. en el subArray v[ini...
v[ini...mitad ...mitad] mitad] else return indiceDelCero(v, (v, ini, mitad); }lpi.esFin() ) throw new ElementoNoEncontrado(“La Entrada a eliminar no existe”); 3.- Se ha cambiado la función de dispersión de una Tabla Hash que contenía ontenía varias entradas, entradas por lo que puede ser que alguna de ellas ya no esté en la cubeta que debiera.
debiera Se pide diseñar en la clase TablaHash (ver Anexo) un método esOK que, con el mínimo coste posible, compruebe si todas tod las entradas de una Tabla Hash están en la cubeta que les corresponde.
(2.5 puntos) Problema de Búsqueda de la 1ª Entrada de la Tabla situada en la cubeta incorrecta: en el Peor de los Casos, si todas las entradas están donde deben, el coste es lineal con la talla de la Tabla; en el Mejor de los casos, si la 1ª Entrada de la 1ª cubeta no está en la cubeta correcta, correcta, el coste es independiente de la talla.
• Suponiendo que las cubetas se implementan mediante Listas Directas ...
public boolean esO esOk(){ for ( int i=0; i<elArray.length; i++ ) for ( EntradaHash<C,V> e = elArray[i]; e!=null; e=e.siguiente ) if ( indiceHash(e.clave)!=i ) return false; return true; } • Alternativamente, suponiendo que las cubetas se implementan mediante Listas Con Punto de Interés ...
public boolean esOk(){ esOk for ( int i=0; i<elArray.length; i++ ) for ( elArray[i].inicio(); !elArray[i].esFin(); !elArray[i].esFin() elArray[i].siguiente() () ) if ( indiceHash(elArray[i] elArray[i].recuperar().clave)!=i ) return false; return true; } 4.- Se dispone de un ABB en el que se admiten elementos repetidos, de forma que los datos del subárbol izquierdo de un nodo son menores o iguales que el elemento de dicho nodo, mientras que los del subárbol derecho son siempre mayores.
En la clase que lo representa (ver Anexo) figura el siguiente método, que permite comprobar si un elemento e dado está repetido en el ABB: (3 puntos) public boolean repetido(E repetido e){ return repetido(e, this.raiz, false); false) } protected boolean repetido(E e, NodoABB<E> actual, boolean encontrado){ repetido if ( actual==null ) return false; if ( actual.dato.compareTo(e)==0){ if ( encontrado ) return true; else encontrado = true; } return repetido(e, actual.izq, encontrado) || repetido(e, actual.der, encontrado); repetido repetido } Suponiendo que el ABB está equilibrado, se pide: (a) Indicar el tamaño del problema, x, que resuelve el método protected recursivo.
el tx es el tamaño del nodo actual odo actual (0.25 puntos) maño del n this.lpi.eliminar(); (b) Indicar si existen instancias significativas y, en caso afirmativo, describir cada una de ellas: (0.5 puntos) Es un problema de Búsqueda y, por lo tanto, sí hay instancias significativas. En concreto: **Caso Mejor: ya en la primera llamada, e ocupa el nodo actual y el primer nodo de su hijo izquierdo.
**Caso Peor: e no está en el nodo actual, o no está repetido en él, por lo que hay que recorrer todos sus caminos para constatarlo antes de devolver false.
this.lpi.eliminar(); (c) En función de la respuesta dada en el apartado anterior, escribir las Relaciones de Recurrencia que expresan la Complejidad Temporal de dicho método recursivo.
(0.5 puntos) TMrepetido(x) = k2 si x>0 TPrepetido(x) = 2 * TPrepetido(x /2 ) + k3 si x>0; TPrepetido(x) = k1 si x=0; (d) En función de las respuestas anteriores, y aplicando los teoremas de coste (ver Anexo), indicar el coste Temporal Asintótico de dicho método recursivo.
(0.25 puntos) ( Trepetido(x) ∈ Ω(1) y Trepetido(x) ∈ O(x) (e) Modificar el método recursivo analizado para hacerlo lo más eficiente posible; indicar también cuál es la mejora de coste conseguida y el motivo por el que se logra.
(1.5 puntos) protected boolean repetido(E e, NodoABB<E> actual, boolean encontrado){ if ( actual==null ) return false; int resC = actual.dato.compareTo(e); if ( resC>=0 ){ if ( resC==0 ){ if ( encontrado ) return true; else encontrado = true; } return repetido(e, actual.izq, encontrado); } else return repetido(e, actual.der, encontrado); } En el Peor de los Casos se busca e en un Camino del ABB en vez de en todos, i.e. se realiza una llamada en el caso general en vez de dos, por lo que el coste es logarítmico en lugar de lineal.
ANEXO Las interfaces ListaConPI y Map del paquete modelos.
public interface ListaConPI<E> ListaConPI { void insertar(E e); /** SII !esFin() */ void eliminar(); void inicio(); /** SII !esFin() */ void siguiente(); void fin(); /** SII !esFin() */ E recuperar(); boolean esFin(); boolean esVacia(); int talla(); } public interface Map<C, V> { Map V insertar(C c, V v); V eliminar(C c); V recuperar(C c); boolean esVacio(); int talla(); ListaConPI<C> claves(); } Teorema 1: f(x) = a·f(x - c) + b, con b ≥ 1 • si a=1, f(x) ∈ Θ(x); • si a>1, f(x) ∈ Θ(ax/c) ; Teorema 3: f(x) = a·f(x/c) + b, con b ≥ 1 • si a=1, f(x) ∈ Θ(logcx); • si a>1, f(x) ∈ Θ(xlogca); Teoremas de coste Teorema 2: f(x) = a·f(x - c) + b·x + d, con b y d≥1 • si a=1, f(x) ∈ Θ(x2); • si a>1, f(x) ∈ Θ(ax/c); Teorema 4: f(x) = a·f(x/c) + b·x + d, con b y d≥1 • si a<c, f(x) ∈ Θ(x); • si a=c, f(x) ∈ Θ(x·logcx); • si a>c, f(x) ∈ Θ(xlogca); Teoremas maestros Teorema para recurrencia divisora: la solución a la ecuación T(n) = a· T(n/b) + Θ(nk), con a≥1 y b>1 es: • T(n) = O(nlogba) si a>bk; k • T(n) = O(n ·log n) si a=bk; si a<bk; • T(n) = O(nk) Teorema para recurrencia sustractora: la solución a la ecuación T(n) = a· T(n-c) + Θ(nk) es: • T(n) = Θ(nk) si a<1; k+1 • T(n) = Θ (n ) si a=1; • T(n) = Θ (an/c) si a>1; Implementación de cubetas con Listas Con Punto de Interés: TablaHash y EntradaHash del paquete deDispersion.
class EntradaHash<C, V> { EntradaHash C clave; V valor; public EntradaHash(C clave, V valor){ this.clave = clave; this.valor = valor; } } public class TablaHash V> implements Map<C, V> { TablaHash<C, laHash protected ListaConPI<EntradaHash<C,V>>[] elArray; protected int talla; protected int indeHash(C c){…} public TablaHash(int tallaMaximaEstimada){…} protected static final int siguientePrimo(int n){…} protected static final boolean esPrimo(int n){…} public V recuperar(C c){…} public V eliminar(C c){…} public V insertar(C c, V v){…} protected final void rehashing(){…} public final double factorCarga(){…} public final boolean esVacio(){…} public final int talla(){…} public final ListaConPI<C> claves(){…} … } Implementación de cubetas con Listas Directas: TablaHash y EntradaHash del paquete deDispersion.
class EntradaHash<C, V> { EntradaHash C clave; V valor; EntradaHash<C, V> siguiente; public EntradaHash(C clave, V valor, EntradaHash<C, V> siguiente){ this.clave = clave; this.valor = valor; this.siguiente = siguiente; } } public class TablaHash V> implements Map<C, V> { TablaHash<C, laHash protected EntradaHash<C,V>>[] elArray; protected int talla; protected int indeHash(C c){…} public TablaHash(int tallaMaximaEstimada){…} protected static final int siguientePrimo(int n){…} protected static final boolean esPrimo(int n){…} public V recuperar(C c){…} public V eliminar(C c){…} public V insertar(C c, V v){…} protected final void rehashing(){…} public final double factorCarga(){…} public final boolean esVacio(){…} public final int talla(){…} public final ListaConPI<C> claves(){…} … } Las clases NodoABB y ABB del paquete jerarquicos class NodoABB<E> { NodoABB E dato; NodoABB<E> izq, der; NodoABB(E dato){ this.dato = dato; this.izq = null; this.der = null; } NodoABB(E dato, NodoABB<E> izq, NodoABB<E> der){ this.dato = dato; this.izq = izq; this.der = der; } } public class ABB<E extends Comparable<E>> { ABB protected NodoAB<E> raiz; protected int talla; public ABB(){…} public boolean esVacio(){…} public int tamanyo(){…} public public public public public /* SII public E recuperar(E e){…} void insertar(E e){…} E actualizar(E e){…} E eliminar(E e){…} E eliminarMin(){…} actual != null */ protected NodoABB<E> eliminarMin(NodoABB<E> actual){…} E recuperarMin(){…} public int altura(){…} protected int altura(NodoABB<E> actual){…} public String toStringPreOrden() /* SII actual != null */ protected String toStringPreOrden(NodoABB<E> actual){…} public String toStringInOrden() /* SII actual != null */ protected String toStringInOrden(NodoABB<E> actual){…} public String toStringPostOrden() /* SII actual != null */ protected String toStringPostOrden(NodoABB<E> actual){…} public String toStringPorNiveles() /* SII actual != null */ protected String toStringPorNiveles(NodoABB<E> actual){…} … } ...