Estructura de Datos : Introducción


Definiciones

Estudio de Algoritmos ( Study of Algorithms )

Estudio de Datos ( Study of Data )

Estructura de Datos ( Data Structures )

Especificación ( Specification )

Implementación ( Implementation )


Ejemplo de Estructura de Datos

Supongamos que se desea definir la modesta estructura de datos numero natural, abreviada natno, donde natno = { 0, 1, 2, 3, ... }, y con dos operaciones, la que pregunta por cero y la que adiciona.

structure NATNO

        declare ZERO()                     ----> natno
                ISZERO(natno)              ----> boolean             Conjunto de funciones F
                SUCC(natno)                ----> natno               Conjunto de funciones F
                ADD(natno, natno)          ----> natno               Conjunto de funciones F

        for all x, y perteneciente a natno

        let
                ISZERO(ZERO)             ====> true                  Conjunto de axiomas A
                ISZERO(SUCC(x))          ====> false                 Conjunto de axiomas A
                ADD(ZERO, y)             ====> y                     Conjunto de axiomas A
                ADD(SUCC(x), y)          ====> SUCC(ADD(x, y))       Conjunto de axiomas A
        end

end NATNO

Conjunto de dominios D = { natno, boolean }

Dominio designado de D = natno


Terminos de Estructuras de Datos.


Implementacion de una Estructura de Datos.


Un lenguaje para la descripción de algoritmos.

Para presentar o describir un algoritmo puede usarse :

  • Los argumentos para usar un lenguaje especial para la descripción de algoritmos son : Los componentes del lenguaje especial para la descripcion de algoritmos son : La traducción desde este lenguaje especial para la descripción de algoritmos a un lenguaje existente puede ser hecha según lo que muestra la siguiente figura :
                              +----------------+
                              |                |
                         +--->| Pre Procesador |---+
    +----------------+   |    |                |   |    +----------------+        +----------------+        +----------------+
    |    Lenguaje    |---+    +----------------+   +--->|    Programa    |        |   Compilador   |        |     Codigo     |
    |                |                                  |    Lenguaje    |------->|    Lenguaje    |------->|                |
    |    Especial    |---+    +----------------+   +--->|    Existente   |        |   Existente    |        |     Maquina    |
    +----------------+   |    |   Traducción   |   |    +----------------+        +----------------+        +----------------+
                         +--->|                |---+
                              |    a   Mano    |
                              +----------------+
    
    Nosotros utilizaremos el lenguaje especial enunciado para la descripción de muchos ejemplos de algoritmos del curso, y para otros tantos, utilizaremos el lenguaje existente Java.


    Tiempos de Computación de un Algoritmo

    Terminologia

    1. Bloque
      Los bloques son conjuntos de sentencias que se ejecutan en conjunto y en un tiempo que puede considerarse constante.
    2. n
      El parámetro n es el valor que caracteriza las entradas y/o salidas que debe procesar el algorítmo. Puede observarse, que aunque deban procesarse n elementos de entrada o salida, el tiempo de procesamiento, puede no depender de n.
    3. Costo
      Entendemos por costo, el tiempo que requiere un bloque para ser procesado. El costo del algoritmo, sera entonces, la sumatoria de los bloques que lo componen, ajustado a las veces que se ejecutan.
    4. g(n)
      Funcion en { 1, 2, 3, ... }, que determina el tiempo de ejecución de un algoritmo en función de n.
    5. f(n)
      Funcion en { 1, 2, 3, ... }. Si consideramos f(n) = O(g(n)) obtenemos la siguiente definición matemática precisa de f(n). Es f(n) = O(g(n)), sí y solo sí, existen dos constantes c y n0 tal que el valor absoluto de f(n) es menor o igual que c por el valor absoluto de g(n) para todo n >= n0. Así |f(n)| =< c * |g(n)|, para todos los enteros positivos n, excepto un numero finito de ellos.
    6. O(g(n))
      Denota el órden de magnitud del tiempo de ejecución de un algoritmo. Es una cota superior que tiene en cuenta los parametros de ejecucion de un algoritmo. Por ejemplo, O(n), denota que el órden de magnitud del tiempo de ejecución de un algoritmo es proporcional a n. La notación O(g(n)) significa que el órden de magnitud del tiempo de ejecución de un algorítmo no tarda más que una constante por g(n), donde n es un parámetro que caracteriza las entradas y/o salidas que debe procesar el algorítmo.

    Tiempos de Computación Constantes - O(1) - K * 1

    Algoritmo 1
        -----------;
        -----------;
        -----------;         Bloque A         Tiempo Algoritmo 1 = A                                                                        1
        -----------;
        -----------;                                        g(n) = K * 1
    
    Algoritmo 2                                             g(n) = O(1) ( Constante )
        -----------;
        -----------;         Bloque B                                                                                                       1
        -----------;
        if ( ......... )
        {
            -----------;                      Tiempo Algoritmo 2 = B + C + E
            -----------;     Bloque C                                                                                                       1
            -----------;                                    g(n) = K * 1
        }
        else                                                g(n) = O(1) ( Constante )
        {
            -----------;                      Tiempo Algoritmo 2 = B + D + E
            -----------;     Bloque D                                                                                                       1
            -----------;                                    g(n) = K * 1
        }
        -----------;                                        g(n) = O(1) ( Constante )
        -----------;         Bloque E                                                                                                       1
        -----------;
    
    Un ejemplo es el acceso a un elemento de un arreglo de n elementos.

    Tiempos de Computación Lineal - O(n) - K * n

    Algoritmo 1
        -----------;
        -----------;         Bloque A                                                                                                       1
        -----------;
        while ( ........ )
        {
            -----------;
            -----------;     Bloque B         Tiempo Algoritmo 1 = A + B * n + C                                                            100
            -----------;
        }                                                        = R + S * n =< R * n + S * n = K * n
        -----------;
        -----------;         Bloque C                       g(n) = O(n) ( Lineal )                                                          1
        -----------;
    
    Un ejemplo es la recuperación de todos los elementos de un arreglo de n elementos.

    Tiempos de Computación Cuadrático - O(n**2) - K * n**2

    Algoritmo 1
        -----------;
        -----------;         Bloque A                                                                                                       1
        -----------;
        while ( ........ )
        {
            -----------;
            -----------;     Bloque B                                                                                                       100
            -----------;
            while ( ........ )
            {
                -----------;
                -----------; Bloque C         Tiempo Algoritmo 1 = A + ( B +  C * n + D ) * n + E                                           10000
                -----------;
            }                                                    = A + B * n + C * n**2 + D * n + E
            -----------;
            -----------;     Bloque D                            = R + S * n + T * n**2 =< R * n**2 + S * n**2 + T * n**2 = K * n**2        100
            -----------;
        }                                                   g(n) = O(n**2) ( Cuadratico )
        -----------;
        -----------;         Bloque E                                                                                                       1
        -----------;
    

    Tiempos de Computación Cúbico - O(n**3) - K * n**3

    Algoritmo 1
        -----------;
        -----------;             Bloque A                                                                                                   1
        -----------;
        while ( ........ )
        {
            -----------;
            -----------;         Bloque B                                                                                                   100
            -----------;
            while ( ........ )
            {
                -----------;
                -----------;     Bloque C                                                                                                   10000
                -----------;
                while ( ........ )
                {
                    -----------;
                    -----------; Bloque D     Tiempo Algoritmo 1 = A + ( B + ( C +  D * n + E ) * n + F ) * n + G                           1000000
                    -----------;
                }                                                = A + ( B + C * n + D * n**2 + E * n + F ) * n + G
                -----------;
                -----------;     Bloque E                        = A + B * n + C * n**2 + D * n**3 + E * n**2 + F * n + G                   10000
                -----------;
            }                                                    = R + S * n + T * n**2 + U * n**3
            -----------;
            -----------;         Bloque F                        =< R * n**3 + S * n**3 + T * n**3 + U * n**3 = K * n**3                    100
            -----------;
        }                                                   g(n) = O(n**3) ( Cubico )
        -----------;
        -----------;             Bloque G                                                                                                   1
        -----------;
    

    Tiempos de Computación Exponencial - O(2**n) - K * 2**n

    Algoritmo 1
        -----------;
        -----------;         Bloque A                                                                                                       1
        -----------;
        while ( ........ )
        {
            -----------;
            -----------;     Bloque B         Tiempo Algoritmo 1 = A + B * 2**n + C                                                         2**100
            -----------;
        }                                                        = R + S * 2**n =< R * 2**n + S * 2**n = K * 2**n
        -----------;
        -----------;         Bloque C                       g(n) = O(2**n) ( Exponencial )                                                  1
        -----------;
    

    Tiempos de Computación Logarítmico - O(log2 n) - K * log2 n

    Algoritmo 1
        -----------;
        -----------;         Bloque A                                                                                                       1
        -----------;
        while ( ........ )
        {
            -----------;
            -----------;     Bloque B         Tiempo Algoritmo 1 = A + B * log n + C                                                        log2 100
            -----------;
        }                                                        = R + S * log2 n =< R * log2 n + S * log2 n = K * log 2 n
        -----------;
        -----------;         Bloque C                       g(n) = O(log2 n) ( Logaritmico )                                                1
        -----------;
    

    Tiempos de Computación Compuesto - O(n log n) - K * n * log2 n

    Algoritmo 1
        -----------;
        -----------;         Bloque A                                                                                                       1
        -----------;
        while ( ........ )
        {
            -----------;
            -----------;     Bloque B                                                                                                       100
            -----------;
            while ( ........ )
            {
                -----------;
                -----------; Bloque C         Tiempo Algoritmo 1 = A + ( B +  C * log2 n + D ) * n + E                                      100 * log2 100
                -----------;
            }                                                    = A + B * n + C * n * log2 n + D * n + E
            -----------;
            -----------;     Bloque D                            = R + S * n + T * n * log2 n                                               100
            -----------;
        }                                                        =< R * n * log2 n + S * n * log2 n + T * n * log2 n = K * n * log2 n
        -----------;
        -----------;         Bloque E                       g(n) = O(n * log2 n ) ( Compuesto )                                             1
        -----------;
    

    Comparación de las funciones de tiempo de computación

    *-----------------------------------------------------------------------------*
    |   log2 n   |     n      |  n log2 n  |    n**2    |    n**3    |    2**n    |
    |------------+------------+------------+------------+------------+------------|
    |     0      |     1      |     0      |    1       |    1       | 2          |
    |     1      |     2      |     2      |    4       |    8       | 4          |
    |     2      |     4      |     8      |    16      |    64      | 16         |
    |     3      |     8      |     24     |    64      |    512     | 256        |
    |     4      |     16     |     64     |    256     |    4096    | 65536      |
    |     5      |     32     |     160    |    1024    |    32768   | 2147483648 |
    *-----------------------------------------------------------------------------*
    
    Para grandes archivos de datos, algoritmos más complejos que n * log2 n, son a menudo imprácticos.


    Selección de un algoritmo

    Al analizar dos algoritmos que realizan la misma tarea normalmente se toma como superior el que tenga una O(g(n)) mejor para valores altos de n. Supongamos dos algoritmos, que cumplen con la misma tarea, con las siguiente funciones :

    *--------------------------------------*
    |     n      |   10 * n   |    n**2    |
    |------------+------------+------------|
    |     1      |     10     |      0,5   |
    |     5      |     50     |     12,5   |
    |     10     |     100    |     50     |
    |     15     |     150    |    112,5   |
    |     20     |     200    |    200     |
    |     25     |     250    |    312,5   |
    |     30     |     300    |    400     |
    *--------------------------------------*
    
    Para n < 20 el algoritmo 1 es mejor que el algoritmo 2.
    Para n = 20 el algoritmo 1 es igual que el algoritmo 2.
    Para n > 20 el algoritmo 2 es mejor que el algoritmo 1.
    Para valores de n chicos, las constantes deben determinarse precisamente, ya que dependen del lenguaje y la máquina en que corren, entre muchas otras variables. Quizas, en este caso, hasta haya que medir en la práctica el comportamiento de los algoritmos.
     450 *                             *              /
         |                                           /
         |                                          /
         |                                         /
         |                                        /
     400 *                                       *
         |                                      /
         |                                     /
         |                                    /
         |                                   /
     350 *                                  *
         |                                 /
         |                                /
         |                        *      /
         |                              /
     300 *                             *
         |                            /
         |                           /
         |                          /
         |                         /
     250 *                        *
         |                       /
         |                      /
         |                     /
         |                    /
     200 *                   *
         |                  /
         |                 /
         |                /
         |               /
     150 *              *
         |             /
         |            /
         |           /  *
         |          /
     100 *         *
         |        /
         |       /
         |      /
         |     /
      50 *    *    *
         |   /
         |  /
         | /  *
         |/
    -----|----*----*----*----*----*----*----*-------------------------------> n
              5   10   15   20   25   30   35
    
          <------------------><------------------ .....
    
              Algortimo 1         Algortimo 2
    


    Espacios de Computación de un Algoritmo

    Un algoritmo debe ser analizado en función de :

    El segundo punto es el tema de este curso de Estructuras de Datos. En todos los casos comprometeremos tiempo por espacio o espacio por tiempo.


    Bibliografía