Algoritmos y Estructuras de Datos (VJ1215)

Complementa las clases estudiando los siguientes apartados del capítulo 5 "Análisis de Algoritmos" del libro "Estructuras de datos en Java" (2000) de M. A. Weiss:

• 5.1 ¿Qué es el análisis de algoritmos?
• 5.2 Ejemplos de tiempo de ejecución de algoritmos
• 5.4 Reglas generales para la notación O
• 5.5 Logaritmos
• 5.6 Problema de la búsqueda estática
  • 5.6.1 Búsqueda secuencial
  • 5.6.2 Búsqueda binaria
• 5.7 Comprobar el análisis de un algoritmo
• 5.8 Limitaciones del análisis O

La edición en castellano "Estructuras de datos en Java" (2013) contiene erratas que nos hacen descartarla.

La sección "Ejercicios" contendrá en cada tema una propuesta de ejercicios a completar en el tiempo de trabajo de clase más el tiempo de trabajo no presencial de la asignatura.

No es obligatorio entregar las soluciones y no son puntuables, pero puedes pedir al profesor que revise lo que quieras y que te aclare cualquier duda, con el objetivo de aprender.

Puedes trabajar en pareja o en grupo si lo deseas, siempre que el objetivo sea que todos aprendáis a escribir las soluciones. Puedes pedir ayuda a otros estudiantes y comparar tu solución con las suyas.

Es importante no ver las soluciones antes de haber intentado resolver los ejercicios, porque debes aprender a escribirlas, no a leerlas.

Dedicaremos las primeras sesiones de laboratorio a adaptarnos a un nuevo lenguaje de programación (C++) y seguiremos introduciendo características de C++ poco a poco a lo largo del curso. Las soluciones en C++ que se proporcionan son también una ayuda para ir conociendo mejor el lenguaje.

Cada estudiante podrá decidir libremente con qué herramienta realizar todas las prácticas del curso. En clase veremos cómo trabajar usando Linux, empleando el compilador g++ y cualquier editor. También veremos cómo trabajar con Online GDB.

En los ejercicios 2 y 3 veremos también cómo realizar comparaciones experimentales de diferentes soluciones algorítmicas a un mismo problema, midiendo tiempos de ejecución para diferentes tallas del problema y observando cómo crece el tiempo de ejecución cuando crece la talla.

Algunos de los siguientes ejercicios requieren que sepas que existen algoritmos que permiten ordenar un vector en tiempo O(n log n). A lo largo del curso estudiaremos algunos de esos algoritmos:

• heapsort (en el tema "Colas de prioridad mediante montículos"),
• AVL sort (en el tema "Conjuntos y diccionarios mediante árboles de búsqueda") y
• mergesort (en el tema "Técnicas algorítmicas").

De momento no necesitas saber más de ellos.

Opcionalmente, en tu tiempo de trabajo no presencial puedes resolver también los ejercicios del siguiente apartado Refuerzo de conceptos básicos: recursión. Te interesa mucho aprender a resolver esos ejercicios cuanto antes, si no sabes hacerlo ya.

1. Clase de prácticas LA2 13/09, LA1 y LA3 15/09

   Asegúrate de que entiendes estos tres ejemplos iniciales de C++, explicados en la primera sesión de prácticas.

   Prueba esto en un terminal tras guardarlos, para compilarlos y ejecutarlos:

   g++ ejemplo_for.cpp && ./a.out

g++ ejemplo_vector.cpp && ./a.out

g++ ejemplo_funcion.cpp && ./a.out

   En el tercer ejemplo se hace uso de C++11 para inicializar el vector. Si en tu ordenador tienes una versión de g++ más antigua que la que tenemos este curso en las aulas, es posible que tengas que informarle de que usas C++11:

   
g++ ejemplo_funcion.cpp -std=c++11 && ./a.out


   Pueba a compilar los mismos ejemplos con Online GDB. En el resto del curso puedes seguir trabajando con él si lo prefieres.

2. 1. Clase de prácticas LA2 13/09, LA1 y LA3 15/09

      Implementa una función recursiva que calcule y devuelva el n-ésimo número de Fibonacci, pasándole n. Haz una primera versión aplicando directamente esta definición recursiva. Utilízala para calcular desde f₀ hasta f₅₀ y observa el tiempo que tarda en calcular cada nuevo número (en el apartado b veremos cómo cronometrar ese tiempo con precisión). Compáralo con una función iterativa que obtenga cada número a partir de los dos anteriores. Observa la importante diferencia práctica entre ambas (de lo cual no puede deducirse que sea malo utilizar funciones recursivas).

      Solución recursiva

      Solución iterativa

   2. Clase de teoría TE1 15/09

      Utilizando estos ejemplos se verá en clase de teoría el resultado de comparar experimentalmente las dos soluciones anteriores midiendo sus tiempos de ejecución.

      Para representar gráficamente los resultados utilizaremos Gnuplot online: basta copiarlos en el panel "Data" y, si quieres, adaptar el contenido del panel "Plot script".

      Nota sobre evaluación: Medir experimentalmente tiempos de ejecución no será materia de examen, aunque éste es un ejercicio importante para convencerte de la importancia práctica del contenido de la asignatura. Si no estás convencido de eso, lo puedes pasar mal estudiándola. Por otra parte, la comparación experimental de algoritmos te resultará útil cuando el análisis teórico no baste para elegir uno.

3. 1. Clase de prácticas LA2 13/09, LA1 y LA3 15/09

      Implementa en C++ una función que reciba como argumentos un vector de enteros y un dato que queremos buscar en dicho vector. La función debe "devolver" (no lo confundas con "mostrar") la posición del dato si lo encuentra y -1 en caso contrario. Si el dato aparece más de una vez, debe devolver una (cualquiera) de las posiciones en que aparece.

      Hazlo empleando el algoritmo de búsqueda secuencial de forma no recursiva.

      Solución

      Busca errores

   2. Clase de prácticas LA2 13/09, LA1 y LA3 15/09

      Resuelve de nuevo el problema anterior empleando esta vez el algoritmo de búsqueda binaria de forma no recursiva (suponiendo que es un vector ordenado).

      Solución

   3. Clase de teoría TE1 15/09
      Clase de prácticas LA2 20/09, LA1 y LA3 22/09

      Después mira con detalle esta comparación experimental midiendo tiempos, que se analizará también en clase de teoría y permitirá ver la importancia práctica de pasar los vectores por referencia.

4. 1. Clase de teoría TE1 29/09

      Analiza el coste temporal, en el mejor y en el peor caso, de este algoritmo para buscar la posición de un dato en un vector de talla n (es la solución del ejercicio 3.a). Indica cuándo se dan el mejor y el peor caso.

      int busquedaSecuencial(const vector<int> & v, int dato) {
         for (int i = 0; i < v.size(); i++)
            if (v[i] == dato)
               return i;
         return -1;
      }
      		

      Solución

   2. Clase de teoría TE1 29/09

      Analiza el coste temporal, en el mejor y en el peor caso, de este algoritmo para sumar los datos de un vector de talla n. ¿Coinciden los resultados con los del apartado anterior? ¿Por qué?

      int sumar(const vector<int> & v) {
         int suma = 0;
         for (int i = 0; i < v.size(); i++)
            suma += v[i];
         return suma;
      }
      		

      ¿Cambiaría alguno de esos costes si implementásemos así el algoritmo?

      int sumar(const vector<int> & v) {
         if (v.size() == 0)
            return 0;
         if (v.size() == 1)
            return v[0};
         int suma = v[0];
         for (int i = 1; i < v.size(); i++)
            suma += v[i];
         return suma;
      }
      		

      Solución

   3. Clase de prácticas LA2 20/09, LA1 y LA3 22/09

      ¿Conoces algún algoritmo, entre los que has estudiado en primer curso, que tenga coste temporal O(log n) en el peor caso? ¿Cuál es su coste temporal en el mejor caso?

   4. Clase de teoría TE1 29/09

      Analiza el coste temporal, en el mejor y en el peor caso, del algoritmo de ordenación por inserción.

   5. Analiza el coste temporal, en el mejor y en el peor caso, del algoritmo de ordenación por selección.

   6. Resuelve este ejercicio sobre costes temporales de bucles (incluye las soluciones).

5. Clase de teoría TE1 29/09

   Averigua, consultando por ejemplo la página Sumatorio de la Wikipedia, cómo calcular estos sumatorios, que no debes confundir entre sí (en estos sumatorios se usa MathML, para verlos correctamente es recomendable utilizar alguna versión reciente de Firefox).

   $$\sum _{i=1}^{n}i=1+2+\dots +n$$ $$\sum _{i=0}^n{2}^i=2^0+2^1+\dots +2^n$$

6. Clase de teoría TE1 29/09

   Tenemos n ≥ 2 datos de tipo real almacenados en un vector y queremos encontrar, entre todos los posibles pares de datos, un par tal que la diferencia entre los dos valores del par sea mínima (por ejemplo, para emparejar a los dos jugadores que tienen la puntuación más similar en un videojuego). ¿Cómo resolverías el problema, y qué coste tendría, sin ordenar el vector? ¿Sería mejor ordenar primero el vector con un algoritmo de coste O(n²) y aprovechar después esa ordenación? ¿Sería mejor ordenarlo con un algoritmo de coste O(n log n) y aprovechar después esa ordenación? ¿Qué harías si no fuese posible modificar el vector y cómo afectaría eso al coste temporal?

   Solución

7. Propón un algoritmo para averiguar en tiempo O(n log n) si dos vectores contienen los mismos datos y en las mismas cantidades, sabiendo que ambos son de talla n y no están necesariamente ordenados,

   Ayuda

   Solución

8. Propón un algoritmo para averiguar en tiempo O(n log n) si un vector de talla n contiene elementos duplicados.

   Ayuda

   Solución

9. Clase de prácticas LA2 20/09, LA1 y LA3 22/09

   Implementa una función que reciba un valor real x y un valor entero n y devuelva el resultado de calcular xⁿ. Contempla la posibilidad de que el exponente sea negativo. Tu solución debe ejecutarse en tiempo O(log |n|).

   Ayuda

   Solución

   También es válida esta solución de M. A. Weiss (aunque en ella no trabaja con valores de tipo real). Puedes encontrar una explicación en el apartado 2.4.4 "Logarithms in the Running Time" (páginas 87-88) de su libro "Data Structures and Algorithm Analysis in C++" (2014). Puedes encontrar una explicación alternativa en el apartado 1.6 "Un ejemplo elaborado: exponenciación" del libro "Estructuras de datos, algoritmos y programación orientada a objetos" (1998) de G. L. Heileman y en la página "Exponenciación binaria" de la Wikipedia.

10. Clase de prácticas LA2 20/09, LA1 y LA3 22/09

    En un vector v1 tenemos números ordenados de menor a mayor sin repetidos. En otro vector v2 tenemos números con esas mismas condiciones. Queremos contar cuántos números comunes tienen v1 y v2.

    1. Diseña un algoritmo eficiente para resolver ese problema e impleméntalo en C++, suponiendo que no puedes utilizar llamadas recursivas.

       Ayuda (mírala después de pensar la solución)

       Solución

       Busca errores

    2. Resuelve de nuevo el mismo problema recursivamente, sin utilizar ningún bucle.

       Solución

       Busca errores

11. Clase de prácticas LA2 20/09, LA1 y LA3 22/09

    Sustituye la implementación no recursiva del algoritmo de búsqueda binaria del ejercicio 3.b por una implementación recursiva.

    Solución

    Busca errores

12. Tras completar el ejercicio 10, diseña un algoritmo eficiente para resolver el problema de mezclar dos vectores ordenados. Su entrada serán dos vectores de números reales, cada uno de los cuales estará ordenado de menor a mayor y podrá contener elementos repetidos. Su salida debe ser un nuevo vector que contenga todos los elementos de ambos vectores ordenados también de menor a mayor.

    Por ejemplo, si los vectores de entrada son [11, 22, 33.3, 33.3, 35] y [10, 33.3, 40] el resultado debe ser [10, 11, 22, 33.3, 33.3, 33.3, 35, 40].

    La solución de este problema será una subrutina del algoritmo de ordenación por mezcla mergesort, como veremos en el tema 5.2.

    1. Resuelve el problema sin utilizar recursión.

       Analiza el tiempo de ejecución de tu solución en el peor caso y exprésalo en notación O.

       Solución

    2. Resuelve el mismo problema sin utilizar ningún bucle, con el mismo coste temporal.

       Solución

13. Tras completar el ejercicio 12 y entender las soluciones propuestas, indica qué problema resuelve el algoritmo siguiente y analiza su coste temporal en el peor caso.

    vector<float> misterio(const vector<float> & a, const vector<float> & b) {
       vector<float> c(a.size() + b.size());
       int i = 0, j = 0, k = 0;
       while ( i < a.size() ) {
          while ( j < b.size() && b[j] <= a[i] ) {
             c[k] = b[j];
             k++;
             j++;
          }
          c[k] = a[i];
          k++;
          i++;
       }
       while ( j < b.size() ) {
          c[k] = b[j];
          k++;
          j++;
       }
       return c;
    }
    	    

    Solución

14. Supongamos que en un vector de cadenas A tienes los DNI de los clientes de tu empresa de videojuegos y en otro vector B tienes los DNI de los clientes que ya han comprado el último videojuego lanzado al mercado. En una campaña de marketing quieres obtener a partir de ellos un vector con los DNI de los clientes que no han comprado ese videojuego. Propón un algoritmo para resolver el problema y analiza su coste computacional en cada uno de los casos siguientes:

    1. si ninguno de los dos vectores está ordenado;

    2. si el vector A ya está ordenado y el B no;

    3. si el vector B ya está ordenado y el A no; y

    4. si ambos están ordenados.

    ¿Vale la pena invertir tiempo en ordenar los vectores inicialmente para resolver el problema cuando no están ordenados?

    Solución

15. Tienes que encontrar un número secreto n que es entero positivo y no sabes en qué rango se encuentra. Cada vez que hagas un intento fallido te dirán si el número secreto es mayor o menor que el que has propuesto. Propón un algoritmo para encontrar el número secreto realizando O(log n) intentos.

    Solución

16. Tienes n monedas, siendo n potencia de 2, y sabes que una de ellas es falsa y pesa menos que las demás. Para encontrarla dispones de una balanza de dos platillos, en los que puedes poner tantas monedas como quieras. Diseña un procedimiento que te permita encontrar la moneda falsa realizando O(log n) pesadas (la única operación cuyo coste nos interesa, por tanto, es la de usar la balanza para pesar; es lo que pasaría, por ejemplo, si hubiera que pagar una cantidad fija por cada pesada). Después modifícalo, si hace falta, para evitar la necesidad de que n sea potencia de 2.

    

    Solución

Opcionalmente, en los exámenes de cursos pasados puedes encontrar más ejercicios de análisis de costes, si quieres seguir practicando.