Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 5 vistas

    Clase Repaso

    Cargado por

    TorneoLol Murcia

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Clase Repaso

    Cargado por

    TorneoLol Murcia
    5 vistas2 páginas

    Título original

    clase repaso

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    5 vistas2 páginas

    Clase Repaso

    Cargado por

    TorneoLol Murcia

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 2

    Algoritmos y Estructuras de Datos II – 2º Grado Hoja 1/2

    Ejercicios tipo examen para clase de repaso


    No entregar esta hoja con el examen.
    La primera pregunta cuenta un 32% de la nota de teoría.
    El resto de preguntas valen el 68% (1,7 puntos cada una).

    1. a) Calcular el tiempo de ejecución de este algoritmo y expresarlo son las notaciones O, Ω y Q:


    función pass (A: array; n: entero)
    para i = 1..n hacer
    para j = 1..n hacer
    M[i,j]=rand();
    finpara
    finpara
    i = 1;
    mientras i<=n hacer
    si par(M[i,i]) entonces
    M[i,i] = M[n-i+1,n-i+1];
    si no
    acum=0; j=1;
    mientras impar(M[i,j]) Y j<=n hacer
    acum=acum + M[i,j];
    j = j+1;
    finmientras
    M[i,i] = acum;
    finsi
    i=i+1;
    finmientras

    b) Resolver la siguiente ecuación de recurrencia e indicar el orden exacto. No hace falta obtener
    las constantes, pero sí indicar los valores de n para calcularlas.
    t(n) = n^2 si n < 5
    t(n) = 4t(n/2) + 5 t(n/4) + n si n ≥ 5

    2. Divide y vencerás

    Subsecuencia de dobles. Nos piden encontrar, dentro de una secuencia S de n números indexados
    por i=1..n, cuál es la subsecuencia más larga que cumple la condición de que sus elementos son uno
    el doble del anterior.

    Por ejemplo, si

    S = [ 1 2 4 8 16 32 7 8 9 10 12 6],

    el resultado sería la subsecuencia [1 2 4 8 16 32], entre los índices 1 y 6, con longitud 6.


    Algoritmos y Estructuras de Datos II – 2º Grado Hoja 2/2
    Ejercicios tipo examen para clase de repaso

    ENUNCIADO DE PROBLEMA para las preguntas 3 a 5:

    Fondo de armario. Para celebrar que nos vamos a graduar tus padres te dan un presupuesto P para
    gastar en ropa. Vamos a una tienda donde hay T prendas diferentes, cada una con un precio pi. Para
    una vez que se estiran, quieres gastar lo máximo posible, sin superar P.

    3. Diseñar un algoritmo voraz que encuentre una buena forma de resolver el problema. Hay que
    ajustarse al esquema y desarrollar sus funciones. ¿Garantiza ese algoritmo la solución óptima?
    Razonarlo.

    4. Resolver este problema mediante programación dinámica indicando la ecuación de recurrencia


    utilizada, los casos base, las tablas necesarias, la forma de rellenar las tablas, la forma de reconstruir
    la solución y el resto de pasos vistos en clase. Indicar cómo se sabe si hay varias soluciones óptimas
    distintas.

    5. Resolver el problema de forma óptima por backtracking. Se deberán utilizar los esquemas vistos
    en clase. Definir la forma de representar la solución, el tipo de árbol usado, el esquema y las
    funciones genéricas del esquema. Seguir los pasos de desarrollo vistos en clase. Se valorarán
    posibles optimizaciones.

    También podría gustarte