Complejidad de algoritmos a través de sus tiempos de ejecución

Práctica propuesta en la UPM para la asignatura “Algorítmica y Complejidad” en el curso 2012-2013:

Link al enunciado de la práctica en formato pdf

Fichero de ejemplo de entradas en formato pdf

Aquí dejo la solución propuesta por un compañero:

with Text_IO;
use Text_IO;
 
with ada.numerics.generic_elementary_functions;
with Ada.Exceptions;
use Ada.Exceptions;
use ada.numerics;
 
 
procedure pb is
   --Tipos definidos
   type coma_fija is delta 0.0000001 digits 18;
   type datos is array (1..20) of coma_fija;
 
   --Packages
   package coma_fija_IO is new decimal_IO (coma_fija);
   package funciones is new generic_elementary_functions (float);
   package enteros is new integer_IO (integer);
   use enteros;
   use funciones;
 
   --Declaración de variables
   D : datos;
   valor : coma_fija;
   fichero_entrada, fichero_salida : File_Type;
   ultimo : Integer := 20;
   error_prc : coma_fija := 0.01;
 
   --Funciones
 
   --------------------------------------------------------
 
   --Lee 20 datos del fichero. Retorna falso si no se han podido leer
   --20 o si el fichero ha acabado.
   function leer_bloque return boolean is
      n : integer := 1;
   begin
      ultimo := 20;
      while n <= 20 and not End_Of_File(fichero_entrada) loop
         coma_fija_IO.Get(File => fichero_entrada, Item => valor);
         D(n) := coma_fija(valor);
         n := n + 1;
      end loop;
      return n = 21;
   end leer_bloque;
 
   --------------------------------------------------------
 
   --Test de igualdad
   function igual(a, b, error : coma_fija) return boolean is
      r : boolean;
   begin
      r := abs(a - b) < abs(a * error);
      return r;
   end igual;
 
   --------------------------------------------------------
 
   --Función para hacer debug
   procedure print is
   begin
      for n in D'Range loop
         coma_fija_IO.Put(D(n));
         new_line;
      end loop;
   end print;
 
   --------------------------------------------------------
 
   --Deriva los datos actuales invalidando el último dato.
   procedure derivar is
   begin
      for n in D'First..D'Last - 1 loop
         D(n) := D(n + 1) - D(n);
      end loop;
      ultimo := ultimo - 1;
   end derivar;
 
   --------------------------------------------------------
 
   --Test constante
   function test_const return boolean is
      n : Integer := 1;
   begin
      while n <= ultimo and then igual(D(n), D(D'First), error_prc) loop
         n := n + 1;
      end loop;
      return n = ultimo + 1;
   end test_const;
 
   --------------------------------------------------------
 
   --Test exponencial
   function test_exp return boolean is
      n : Integer := 1;
      a, b, log2 : coma_fija;
 
   begin
      log2 := 0.6931472;
 
      if D(1) > D(2) then
         return false;
      end if;
 
      a := coma_fija(log(float(0.5 * (D(2)-D(1))))) / log2;
      b := D(1) - coma_fija((2.0)**(float(a + 1.0)));
 
      while n <= ultimo
      and then igual(D(n), coma_fija((2.0)**(float(a + coma_fija(n)))) + b, 3 * error_prc) loop
         n := n + 1;
      end loop;
 
      return n = ultimo + 1;
 
      exception
      when Error : others =>
         return false;
 
   end test_exp;
 
   --------------------------------------------------------
 
   --Test logaritmo
   function test_log return boolean is
      n : Integer := 1;
      a : coma_fija;
   begin
      if D(1) = 0.0 then
         return false;
      end if;
 
      a := (1.0/D(1)) - 1.0;
      while n <= ultimo and then igual(D(n), 1.0/(coma_fija(n) + a), 2.0 * error_prc) loop
         n := n + 1;
      end loop;
 
      return n = ultimo + 1;
 
      exception
      when Error : others =>
         return false;
 
   end test_log;
 
   --------------------------------------------------------
 
   --Calcular el orden
   function calcular_orden return Integer is
   begin
 
      if test_const then
         return 9;
      elsif test_exp then
         return 8;
      end if;
 
      derivar;
 
      if test_log then
         return 7;
      end if;
 
      for orden in 1..6 loop
         if test_const then
            return orden;
         else
            derivar;
         end if;
      end loop;
 
      return 0;
 
   exception
      when Error : others =>
         return 0;
 
   end calcular_orden;
 
   --------------------------------------------------------
 
   --ENTRADA DEL PROGRAMA
begin
   Open(File => fichero_entrada, Mode => In_File, Name => "f1.txt");
   Create(File => fichero_salida, Mode => Out_file, Name => "f2.txt");
 
   while leer_bloque loop
      Put(FILE => fichero_salida, ITEM => Integer'Image(calcular_orden));
   end loop;
 
   Close (File => fichero_salida);
   Close (File => fichero_entrada);
 
   exception
   when Error : others =>
      Close (File => fichero_salida);
      Close (File => fichero_entrada);
      return;
 
end Pb;
Tagged with: , , ,
7 comments on “Complejidad de algoritmos a través de sus tiempos de ejecución
  1. Reaper says:

    Muchísimas gracias Alejandro por tu tiempo y esfuerza,has salvado muchas vidas jajaja te debemos una XD

  2. AlejandroMoran says:

    De nada Reaper, un saludo.

  3. Daniel says:

    Pues sí Alejandro, muchas gracias por tu ayuda, aunque me da a mi que va a haber més ceros en estas prácticas… porque dijeron que tenían un “anticopia” y me parece que muchos de nosotros no vamos a cambiar mucho de la práctica…

    Aún así ya sabes, eres un crack por ayudarnos tanto, y además desinteresadamente.

    • Javivi says:

      Pues si…

      • AlejandroMoran says:

        No sé que decir… el año pasado también nos metieron miedo con el anticopia pero no lo tenían pq pasaron muchas copiadas, y… siendo tan vagos como para no cambiar las prácticas del año anterior pues me cuesta un poco creer que han trabajado más de lo normal (nada), eso si, si pueden cambien la práctica por evitar problemas 🙂 un saludoo!

  4. Miguel says:

    Estaría bien que en esta asignatura dieran unas “nociones básicas” de la verificación empírica de las cotas superiores de complejidad temporal, como hacen en otras universidades, y no hablarle en chino mandarino a los alumnos. Para que os ilustréis un poco: http://www.madsgroup.org/docencia/alg/T1_VerificacionEmpirica.pdf

    • AlejandroMoran says:

      Si, estaría bien, pero… estas practicas son de hace dos años y mira, siguen con las mismas, si estudias en la EUI y esperas algo de trabajo por parte de los dos inútiles que imparten la asignatura de Algorítmica y Complejidad estás jodido, son unos vagos y su nivel docente deja mucho que desear, es triste, pero es lo que hay por desgracia con esos dos.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.