CC30A Algoritmos y Estructuras de Datos

Benjamin Bustos (bebustos@dcc.uchile.cl)
Patricio Poblete (ppoblete@dcc.uchile.cl)

Nociones básicas de programación

En esta sección se revisarán los elementos básicos que se van a utilizar para escribir programas. Esto supone que los alumnos ya saben programar, y es sólo un resumen y una ordenación de conceptos. La notación utilizada es la del lenguaje Java, pero los conceptos son más generales y se aplican a muchos otros lenguajes similares.

Datos

Los programas representan la información que manejan mediante valores llamados "constantes", y dichos valores se almacenan en "variables".

Variables

int k; // entero

float x; // real

double prom; // real de doble precisión

boolean condicion; // verdadero o falso

char c; // un carácter

String nombre; // secuencia de caracteres

Nótese que la secuencia "//" indica el comienzo de un comentario, el cual se extiende hasta el final de la línea.

Constantes

3 // int

4.50 // float

1e-6 // float

'a' // char

"hola" // String

Instrucciones Elementales

Asignación

Esta es la instrucción más simple, que permite modificar el valor de una variable:

a = E; // asigna a la variable 'a' el valor de la expresión 'E'

Ejemplos:

k = 0;

k = k+1;

k += 1;

++k;

k++;

Las tres últimas son abreviaturas. La notación "+=" permite evitar repetir el lado izquierdo de la asignación. Las dos últimas incrementan el valor de la variable en 1, pero difieren respecto del valor retornado. En el primer caso (preincremento) se incrementa primero y luego se retorna el valor resultante. El el segundo caso (postincremento) se incrementa después, y se retorna el valor previo de la variable.

Salida

System.out.println("¡Hola!");

Instrucciones Compuestas

Estas instrucciones se forman agrupando a otras instrucciones, ya sean elementales o compuestas, usando las reglas de secuencia, alternación (if) e iteración (while).

Secuencia de instrucciones

Un grupo de instrucciones escritas una a continuación de la otra se ejecutan en ese mismo orden:

instrucción1;

instrucción2;

. . .

También es posible agrupar las instrucciones entre llaves para que sean equivalentes a una sola instrucción:

    instrucción1;

    instrucción2;

    . . .

Ejemplo:

// Intercambiar dos valores a y b

    int aux = a;

    a = b;

    b = aux;

Instrucciones condicionales

Forma 1:

if( condición )

    instrucción1;

else

    instrucción2;

Forma 2:

if( condición )

    instrucción;

Nota: No existe el "endif". Si lo que se desea ejecutar en cada caso es más de una instrucción, hay que escribirlas encerradas entre llaves.

Ejemplo:

// m = max(a,b)

if( a>b )

    m = a;

else

    m = b;

Ejemplo:

// a = abs(a)

if( a<0 )

    a = -a;  // se omite el "else" si es vacío

Ejemplo:

// Ordenar a, b (borrador)

if( a>b )

    intercambiar a, b;

La línea destacada no es una instrucción real del lenguaje, es sólo una forma de dejar pendiente esa parte del programa. Más adelante se podrá "refinar" esa seudo-instrucción definiendo:

intercambiar a, b =>

  int aux = a;

  a = b;

  b = aux;

Si se efectúa la sustitución del texto refinado en lugar del que se había escrito originalmente, resulta un texto de programa refinado que cumple con las reglas del lenguaje. Para ayudar a la auto-documentación del programa, se puede conservar la seudo-instrucción como comentario:

// Ordenar a, b

if( a>b )

{ // intercambiar a, b

  int aux = a;

  a = b;

  b = aux;

Ejemplo: Encontrar el máximo entre un conjunto de variables

// m = max(a,b,c)

// Solución 1 (borrador)

if( a>b )

  m = max(a,c);

else

  m = max(b,c);

Realizando las sustituciones respectivas, se obtiene la siguiente versión "refinada":

// m = max(a,b,c)

// Solución 1 (versión refinada)

if( a>b )

  if( a>c )

    m = a;

  else

    m = c;

else

  if( b>c )

    m = b;

  else

    m = c;

Nota: En este caso, las llaves no son realmente necesarias, pero pueden utiizarse si ayudan a la claridad del programa.

Este enfoque de solución tiene la desventaja que es difícil de generalizar. Por ejemplo, el programa que encuentra el máximo de cuatro variables tiene aproximadamente el doble de líneas que éste, y por lo tanto el tamaño del programa va creciendo exponencialmente. Además no hay forma de escribir un programa para un número de variables que no sea conocido a priori.

// m = max(a,b,c)

// Solución 2 (borrador)

m = a;

m = max(m,b);

m = max(m,c);

Sustituyendo las seudo-instrucciones, resulta:

// m = max(a,b,c)

// Solución 2 (versión refinada)

m = a;

if( b>m )

  m = b;

if( c>m )

  m = c;

Con cada instrucción que se ejecuta, el estado del proceso cambia. Para entender lo que está sucediendo en el programa, puede resultar útil intercalar comentarios que describan lo que sabemos que se cumple después de cada instrucción:

// m = max(a,b,c)

// Solución 2 (versión refinada y con afirmaciones)

m = a;

// m == max(a)

if( b>m )

  m = b;

// m == max(a,b)

if( c>m )

  m = c;

// m == max(a,b,c)

Ese tipo de comentarios se llaman afirmaciones (assertions), y en casos más complejos son fundamentales para entender lo que está sucediendo en un proceso.

La generalización para encontrar el máximo de cuatro o más variables es directa, y en cada caso requiere sólo agregar dos líneas al programa. Más adelante se verá una versión para un número variable de datos.

Instrucción iterativa

La forma general es:

while( condición )

    instrucción;

La instrucción se ejecuta en forma reiterada mientras la condición sea verdadera.

Cada vez que se intenta iniciar una nueva iteración (incluyendo la primera vez que ello ocurre) el programa se encuentra en un estado I llamado el invariante del ciclo.

En general, al escribir un ciclo, se debe establecer la validez inicial del invariante, a través de una inicialización. El objetivo del ciclo es llegar a un estado final F. En cada iteración se debe, además, preservar la validez del invariante.

Ejemplo:

Considere el problema de encontrar el máximo de un número variable de datos, almacenados en un arreglo a[1], ..., a[n]. Para verlo en forma iterativa, imagine un proceso en que los datos se van examinando uno a uno, comparándolos con el máximo encontrado hasta el momento. De esta manera, si en un instante dado ya se han examinado los datos hasta a[k], entonces se conoce el máximo hasta esa variable.

// m = max(a[1],...,a[n]);

k = 1;

m = a[1];

// m == max(a[1])

// De esta manera trivial se incializa el siguiente invariante:

// Invariante: k<=n && m == max(a[1],...,a[k])

while( k<n )

    ++k;

    // k<=n && m == max(a[1],...,a[k-1])

    if( a[k]>m )

        m = a[k];

    // k<=n && m == max(a[1],...,a[k])

// m = max(a[1],...,a[n])

Esta última afirmación se deduce del hecho que al terminar el ciclo se sabe que el invariante sigue siendo verdadero, pero la condición del ciclo es falsa. En estricto rigor, la afirmación que podríamos hacer ahí es

// k>=n && k<=n && m == max(a[1],,,a[k])

de la cual se deduce la señalada al final del programa.

Desarrollo de Programas iterativos usando invariante

¿Cómo escribir un ciclo (y asegurarse que hace lo que uno quiere)?

El punto de partida es el INVARIANTE: una condición que se cumple durante todo el ciclo y que refleja de alguna manera la estrategia que se usa para resolver el problema. Lo importante: se debe cumplir al principio, durante cada ejecución del ciclo y al final. Veamos un ejemplo con la búsqueda de mayor de n números:

1. Encontrar un invariante adecuado. Para esto, a menudo es conveniente "relajar" la meta (estado final) al que se desea llegar. Por ejemplo, si se desea obtener:

// m == max(a[1].,,,.a[n])

se puede re-escribir esta condición separándola en dos condiciones que se puedan satisfacer independientemente:

// m == max(a[1].,,,.a[k]) && k==n

Esto, que puede parecer ocioso, es muy útil, porque a continuación se relaja la exigencia de esta condición, haciendo que se cumpla la primera parte, pero dejando que la segunda se satisfaga con "k<=n".

2. Escribir la inicialización, la cual debe asegurar que el invariante se cumpla antes de empezar a iterar.

3. Encontrar la condición de término. Esto se obtiene de comparar "qué le falta" al invariante para ser igual al estado final.

4. Escribir el cuerpo del ciclo, el cual debe:

o conseguir que el proceso avance, de modo que termine algún día, y

preservar el invariante.

Estos dos últimos objetivos suelen ser contrapuestos. Al efectuar un avance en el proceso, los valores de las variables cambian, con el resultado que a menudo se deja de satisfacer el invariante. Por lo tanto, el resto del cuerpo del ciclo se suele dedicar a tratar de recuperar la validez del invariante.

Ejemplos de programas iterativos abordados con invariante

Algoritmos simples de ordenación

Considere el problema de poner los elementos de un arreglo a[0],...,a[n-1] en orden ascendente.

Se estudiarán varias soluciones, todas ellas consistentes en algoritmos sencillos, pero no muy eficientes. Estas distintas soluciones van a provenir de escoger distintos invariantes, o distintas maneras de preservarlos.

Ordenación por inserción

Este algoritmo va construyendo un trozo ordenado del arreglo al extremo izquierdo, y en cada iteración le agrega un nuevo elemento a ese grupo.

Invariante:

Esto es: los k primeros elementos ya están ordenados.

// Ordenar a[0],...,a[n-1] por inserción (borrador)

k = 0; // inicialmente no hay elementos ordenados (k=1 también funcionaría)

while( k<n )

    Insertar a[k] entre a[0],...,a[k-1];

    ++k;

Si la inserción se efectúa correctamente, es evidente que el programa anterior ordena correctamente al conjunto.

El siguiente problema es ver cómo se realiza la inserción:

Insertar a[k] entre a[0],...,a[k-1] =>

for( j=k; j>0 && a[j-1]>a[j]; --j )

    // intercambiar a[j-1] con a[j]

    t = a[j];

    a[j] = a[j-1];

    a[j-1] = t;

Al seguir el proceso de la inserción, se puede observar que la variable t toma siempre el mismo valor: el del elemento que se está insertando. Por lo tanto, se puede optimizar el programa realizando una única asignación a t antes de comenzar el ciclo. Otra observación es que la mayoría de las asignaciones a a[j-1] son inútiles, porque esa variable va a ser sobre-escrita en la iteración siguiente. Luego, se puede evitar esas asignaciones, reemplazándolas por una sola al final del ciclo:

Insertar a[k] entre a[0],...,a[k-1] =>

// versión optimizada

t = a[k];

for( j=k; j>0 && a[j-1]>t; --j )

    a[j] = a[j-1];

a[j] = t;

Efectuando la sustitución de esta versión, se obtiene la siguiente versión final para el algoritmo de ordenación:

// Ordenar a[0],...,a[n-1] por inserción

k = 0; // inicialmente no hay elementos ordenados (k=1 también funcionaría)

while( k<n )

    // Insertar a[k] entre a[0],...,a[k-1]

    t = a[k];

    for( j=k; j>0 && a[j-1]>t; --j )

        a[j] = a[j-1];

    a[j] = t;

    ++k;

El tiempo que demora este algoritmo en el peor caso es del orden de n², lo que se denotará O(n²).Se puede demostrar que esto mismo es cierto si se considera el caso promedio.

Ordenación por Selección

Este algoritmo se basa en hacer pasadas sucesivas sobre los datos. En cada pasada, se encuentra el máximo del arreglo, y se lo lleva al extremo derecho. Una vez hecho esto, ese elemento deja de ser considerado, porque se encuentra ya en su posición definitiva. Esto conduce al siguiente invariante:

En palabras: "Los elementos desde k hasta n-1 ya están ordenados y son mayores que los primeros k".

// Ordenar a[0], ..., a[n-1] por selección

k = n; // inicialmente los n primeros están desordenados

while( k>=2 )

    Llevar el max de a[0], ..., a[k-1] hacia a[k-1];

    --k;

Donde

Llevar el max de a[0], ..., a[k-1] hacia a[k-1] =>

i = 0; // a[i] es el max hasta el momento

for( j=1; j<=k-1; ++j )

    if( a[j]>a[i] )

        i = j;

// ahora intercambiamos a[i] con a[k-1]

t = a[i];

a[i] = a[k-1];

a[k-1] = t;

El tiempo que demora este algoritmo es O(n²), y no hay diferencia entre el peor caso y el caso promedio.

Más adelante se verá una forma diferente de realizar el proceso de encontrar el máximo, que permitirá que ese proceso sea más eficiente. Básicamente, se trata que al encontrar el máximo una vez, es posible obtener información adicional que facilite encontrar luego el segundo máximo, y así sucesivamente.

Una forma de hacer esto es construir un torneo balanceado, al estilo de los torneos de tenis. Una vez que se han jugado todos los partidos del torneo, con n jugadores, si se desea encontrar al (verdadero) sub-campeón, basta con sustituir imaginariamente al campeón por un jugador pésimo, y jugar de nuevo los log n partidos en que estuvo involucrado el campeón. El resultado es un método de ordenación que demora tiempo O(n log n).

Ordenación de la Burbuja

Este método se basa en hacer pasadas de izquierda a derecha sobre los datos, intercambiando pares de elementos adyacentes que estén fuera de orden. Al final de cada pasada, en forma natural el máximo estará en la posición de más a la derecha (que es su posición final) y puede por lo tanto ser excluido en pasadas sucesivas.

Esto conduce al siguiente invariante (idéntico al de ordenación por selección):

El borrador del programa es:

// Ordenar a[0], ..., a[n-1] por la burbuja (borrador)

k = n;

while( k>1 )

    Hacer una pasada sobre a[0], ..., a[k-1];

    Disminuir k;

Donde

Hacer una pasada sobre a[0], ..., a[k-1] =>

for( j=0; j<=k-2; ++j )

    if( a[j]>a[j+1] )

      { // Intercambiar a[j] con a[j+1]

        t = a[j];

        a[j] = a[j+1];

        a[j+1] = t;

Disminuir k =>

--k;

Esto último puede parecer ocioso, pero pronto se verá que el expresarlo de esta manera da una flexibilidad que resulta útil.

Un problema que presenta este programa es que si el archivo está incialmente ordenado, el programa igual hace n pasadas, cuando después de la primera ya podría haberse dado cuenta que el archivo ya estaba ordenado.

Para aprovechar cualquier posible orden que pueda haber en el archivo, se puede hacer que el programa anote ("recuerde") el lugar en donde se produjo el último intercambio. Si la variable i se define de manera que el último intercambio en una pasada dada fue entre a[i-1] y a[i], entonces todos los elementos desde a[i] en adelante están ya ordenados (de lo contrario habría habido intercambios más hacia la derecha), y por lo tanto k se puede disminuir haciendo que sea igual a i:

Hacer una pasada sobre a[0], ..., a[k-1] =>

i=0;

for( j=0; j<=k-2; ++j )

    if( a[j]>a[j+1] )

      { // Intercambiar a[j] con a[j+1]

        t = a[j];

        a[j] = a[j+1];

        a[j+1] = t;

        //Recordar el lugar del último intercambio

        i = j+1;

Disminuir k =>

k=i;

El tiempo que demora este algoritmo tanto en el peor caso como en promedio es O(n²).

Cálculo de `xⁿ`

Un algoritmo simple consiste en multiplicar n veces:

// Algoritmo simple

y = 1;

for( j=n; j>0; --j )

    y = y*x;

Este algoritmo evidentemente toma tiempo O(n), y su invariante se puede escribir como

        y * x^j == xⁿ

Es posible encontrar un algoritmo sustancialmente más eficiente de la siguiente manera. Primero se desvinculan las dos ocurrencias de x en el invariante:

y = 1;

z = x;

for( j=n; j>0; --j )

    y = y*z;

con invariante

        y * z^j == xⁿ

Esto podría parecer ocioso, pero permite hacer una optimización al observar que está permitido modificar la variable z al inicio del ciclo siempre que se mantenga la validez del invariante. En particular, si j resulta ser par, podemos elevar z al cuadrado si al mismo tiempo dividimos j por 2. De esta manera, el invariante sigue igual, pero j disminuye mucho más rápido.

Mejor todavía, si esto se puede hacer una vez, entonces se puede hacer muchas veces siempre que j siga siendo par:

y = 1;

z = x;

for( j=n; j>0; --j ) // Invariante: y * z^j == xⁿ

    while( j es par )

        z = z*z;

        j = j/2;

    y = y*z;

La detección que j es par se puede implementar como

j es par =>

j&1 == 0

Este algoritmo demora tiempo O(log n), lo cual se debe a que j sólo se puede dividir log n veces por 2 antes de llegar a 1. Es cierto que j sólo se divide cuando es par, pero si es impar en una iteración del for, está garantizado que será par a la siguiente.

Diagramas de Estados

Un diagrama de estados nos permite visualizar los diferentes estados por los que va pasando un programa. Las transiciones de un estado a otro se realizan ya sea incondicionalmente o bajo una condición. Además, pueden ir acompañadas de una acción que se realiza junto con la transición.

Ejemplo: Contar palabras en una frase.

Para simplificar, supongamos que la frase está almacenada en un string s, y supongamos que la frase termina con un punto. Por ejemplo,

     String s = "Este es un ejemplo.";

Para los fines de este ejemplo, diremos que una "palabra" es cualquier secuencia de caracteres consecutivos distintos de blanco (y punto).

Para resolver este problema, examinaremos los caracteres del string de izquierda a derecha, usando charAt(k), y lo que se haga con cada caracter depende si estábamos dentro o fuera de una palabra. Esto último correspnde al estado del programa.

Veremos dos formas distintas de llevar este diagrama de transición a un programa. A pesar que ambos se ven muy distintos, en realidad representan exactamente el mismo proceso:

// Version 1

np = 0;

estado = FUERA;

for( k=0; (c=s.charAt(k))!='.'; ++k )

    if( estado==FUERA )

        if( c!=' ' )

            ++np;

            estado = DENTRO;

    else  // estado==DENTRO

        if( c==' ' )

            estado = FUERA;

// Version 2

k = 0;

np = 0;

while( s.charAt(k)!='.' )

  { // estado==FUERA

    while( s.charAt(k)==' ' )

        ++k;

    if( s.charAt(k)=='.' )

        break;

    ++np;

    ++k;

    // estado==DENTRO

    while( s.charAt(k)!=' ' && s.charAt(k)!='.' )

        ++k;

    if( s.charAt(k)=='.' )

        break;

    ++k;

Problema

Reordenar los elementos de a[0], ..., a[n] dejando a la izquierda los <0 y a la derecha los >=0.

Solución 1:

Invariante:

// Version 1

i = 0;

j = n;

while( i<j )

    if( a[i]<0 )

        ++i;

    else if( a[j]>=0 )

        --j;

    else

        a[i] <-> a[j];

        ++i;

        --j;

// Version 2

i = 0;

j = n;

while( i<j )

    while( i<j && a[i]<0 )

        ++i;

    while( i<j && a[j]>=0 )

        --j;

    if( i<j )

        a[i] <-> a[j];

        ++i;

        --j;

Solución 2:

Invariante:

i = 0;

for( j=0; j<=n; ++j )

    if( a[j]<0 )

        a[i] <-> a[j];

        ++i;

Problema

Escribir una función con encabezado pubic static double valor(String s) que recibe como parámetro un string que contiene un número real terminado con un ; y entregue su valor. Si el número está ma escrito debe retornar Math.MAXDOUBLE (el máximo double que puede guardar java).

Esto se puede abordar con ayuda de un diagrama de estados:

// Version 1

double valor = 0;

int n;

int final ENTERO =1, DECIMAL =2, ERROR =3, FIN =0;
estado = ENTERO;
for( k=0; k < s.length() && estado != FIN && estado != ERROR; ++k ){

if( estado== ENTERO)
if( s.charAt(k) <= '9' && s.charAt(k) >= '0' )

valor = valor*10 + s.charAt(k)-'0';

else if (s.charAt(k) == ';')

estado = FIN;

else if (s.charAt(k) == '.') {

n = 10;

estado = DECIMAL;

else estado = ERROR;

else if(estado == DECIMAL)

if( s.charAt(k) <= '9' && s.charAt(k) >= '0' ) {

valor = valor + (s.charAt(k)-'0')/n;

n = n*10;

}

else if (s.charAt(k) == ';')

estado = FIN;

else estado = ERROR;

}

if (estado == FIN)return valor else return Math.MAXDOUBLE;

// Version 2

double valor = 0;

k = 0;
while(k < s.length() && s.charAt(k) <= '9' && s.charAt(k) >= '0') {

valor = valor*10 + s.charAt(k)-'0';

k++;

}

if (s.charAt(k) == ';') return valor

else if (s.charAt(k) != '.') return Math.MAXDOUBLE;

int n = 10;

while (k < s.length() && s.charAt(k) <= '9' && s.charAt(k) >= '0') {

valor = valor + (s.charAt(k)-'0')/n;

n = n*10;

k++;

}

if (s.charAt(k) == ';') return valor

else return Math.MAXDOUBLE;

Problema Propuesto (traer solución el Miércoles 24 de Septiembre)

escribir una función que tenga el encabezado public static true valido(String s) que retorna true si el string s empieza con uno o más caracteres 'a' seguidos por uno o más caraceters 'b' y terminados con uno o más caracteres 'c' seguido por un carácter ';'. Además debe imprimir (con System.out.println(....) ) la cantidad de caracteres a, b y c que venían en la secuencia.

por ejemplo: aabbbbcc; , abbbbc; , abc;, aaabc; son secuencias válidas. bbbccc; , axbbccc; , aaaccc; , aabcc  (no tiene ';' al final) son inválidas.

Recursividad

Al programar en forma recursiva, buscamos dentro de un problema otro subproblema que posea su misma estructura.

Ejemplo: Calcular xⁿ.

// Version 1

public static float elevar( float x, int n )

    if( n==0 )

        return 1;

    else

        return x * elevar(x, n-1);

// Version 2

public static float elevar( float x, int n )

    if( n==0 )

        return 1;

    else if( n es impar )

        return x * elevar( x, n-1 );

    else

        return elevar( x*x, n/2 );

Ejemplo: Torres de Hanoi.

public class TorresDeHanoi

    static void Hanoi( int n, int a, int b, int c )

        if( n>0 )

            Hanoi( n-1, a, c, b );

            System.out.println( a + " --> " + c );

            Hanoi( n-1, b, a, c );

        public static void main( String[] args )

            Hanoi( Integer.parseInt(args[0]), 1, 2, 3 );

"Dividir para reinar"

Este es un método de diseño de algoritmos que se basa en subdividir el problema en sub-problemas, resolverlos recursivamente, y luego combinar las soluciones de los sub-problemas para construir la solución del problema original.

Ejemplo: Multiplicación de Polinomios.

Supongamos que tenemos dos polinomios con n coeficientes, o sea, de grado n-1:

A(x) = a₀+a₁*x+ ... +a_n-1*x^n-1

B(x) = b₀+b₁*x+ ... +b_n_-1*xⁿ^-1

representados por arreglos a[0], ..., a[n-1] y b[0], ..., b[n-1]. Queremos calcular los coeficientes del polinomio C(x) tal que C(x) = A(x)*B(x).

Un algoritmo simple para calcular esto es:

// Multiplicación de polinomios

for( k=0; k<=2*n-2; ++k )

    c[k] = 0;

for( i=0; i<n; ++i)

    for( j=0; j<n; ++j)

        c[i+j] += a[i]*b[j];

Evidentemente, este algoritmo requiere tiempo O(n²). ¿Se puede hacer más rápido?

Supongamos que n es par, y dividamos los polinomios en dos partes. Por ejemplo, si

A(x) = 2 + 3*x - 6*x² + x³

entonces se puede reescribir como

A(x) = (2+3*x) + (-6+x)*x²

y en general

A(x) = A'(x) + A"(x) * xⁿ^/2

B(x) = B'(x) + B"(x) * xⁿ^/2

Entonces

C = (A' + A"*x^n/2) * (B' + B"*x^n/2)

  = A'*B' + (A'*B" + A"*B') * x^n/2 + A"*B" * xⁿ

Esto se puede implementar con 4 multiplicaciones recursivas, cada una involucrando polinomios de la mitad del tamaño que el polinomio original. Si llamamos T(n) al número total de operaciones, éste obedece la ecuación de recurrencia

T(n) = 4*T(n/2) + K*n

donde K es alguna constante cuyo valor exacto no es importante.

Teorema

Las ecuaciones de la forma

T(n) = p*T(n/q) + K*n

con tienen solución

T(n) = O(n^log_q^p)       (p>q)

T(n) = O(n)           (p<q)

T(n) = O(n log n)     (p=q)

Por lo tanto la solución del problema planteado (p=4, q=2) es

T(n) = O(n^log₂⁴) = O(n²)

lo cual no mejora al algoritmo visto inicialmente.

Pero... hay una forma más eficiente de calcular C(x). Si calculamos:

D = (A'+A") * (B'+B")

E = A'*B'

F = A"*B"

entonces

C = E + (D-E-F)*xⁿ^/2 + F*xⁿ

Lo cual utiliza sólo 3 multiplicaciones recursivas, en lugar de 4. Esto implica que

T(n) = O(n^log₂³) = O(n^1.59)

Recursividad y Tabulación (Programación Dinámica)

A veces la simple recursividad no es eficiente.

Ejemplo: Números de Fibonacci.

Los números de Fibonacci se definen mediante la recurrencia

f_n = f_n_-1+f_n_-2   (n>=2)

f₀ = 0

f₁ = 1

cuyos primeros valores son

n  0  1  2  3  4  5  6  7  8  9 10 11 . . .

f_n  0  1  1  2  3  5  8 13 21 34 55 89 . . .

Se puede demostrar que los números de Fibonacci crecen exponencialmente, como una función O(øⁿ) donde ø=1.618....

El problema que se desea resolver es calcular f_n para un n dado.

La definición de la recurrencia conduce inmediatamente a una solución recursiva:

public static int F( int n )

    if( n<= 1)

        return n;

    else

        return F(n-1)+F(n-2);

Lamentablemente, este método resulta muy ineficiente. En efecto, si llamamos T(n) al número de operaciones de suma ejecutadas para calcular f_n, tenemos que

T(0) = 0

T(1) = 0

T(n) = 1 + T(n-1) + T(n-2)

La siguiente tabla mustra los valores de T(n) para valores pequeños de n:

 n    0  1  2  3  4  5  6  7  8  9 10 ...

T(n)  0  0  1  2  4  7 12 20 33 54 88 ...

Ejercicio: Demostrar que T(n) = f_n₊₁-1.

Por lo tanto, el tiempo que demora el cálculo de F(n) crece exponencialmente con n, lo cual hace que este método sea inútil excepto para valores muy pequeños de n.

El origen de esta ineficiencia es que la recursividad calcula una y otra vez los mismos valores, porque no guarda memoria de haberlos calculado antes.

Una forma de evitarlo es utilizar un arreglo auxiliar fib[], para anotar los valores ya calculados. Un método general es inicializar los elementos de fib con algún valor especial "nulo". Al llamar a F(n), primero se consulta el valor de fib[n]. Si éste no es "nulo", se retorna el valor almacenado en el arreglo. En caso contrario, se hace el cálculo recursivo y luego se anota en fib[n] el resultado, antes de retornarlo. De esta manera, se asegura que cada valor será calculado recursivamente sólo una vez.

En casos particulares, es posible organizar el cálculo de los valores de modo de poder ir llenando el arreglo en un orden tal que, al llegar a fib[n], ya está garantizado que los valores que se necesitan (fib[n-1] y fib[n-2]) ya hayan sido llenados previamente. En este caso, esto es muy sencillo, y se logra simplemente llenando el arreglo en orden ascendente de subíndices:

fib[0] = 0;

fib[1] = 1;

for( j=2; j<=n; ++j )

    fib[j] = fib[j-1]+fib[j-2];

El tiempo total que esto demora es O(n).

Esta idea se llama programación dinámica cuando se la utiliza para resolver problemas de optimización, y veremos algunas aplicaciones importantes de ella a lo largo del curso.

¿Es posible calcular f_n más rápido que O(n)? Si bien podría parecer que para calcular f_n sería necesario haber calculado todos los valores anteriores, esto no es cierto, y existe un método mucho más eficiente.

Tenemos

f_n = f_n_-1+f_n_-2

f₀ = 0

f₁ = 1

Esta es una ecuación de recurrencia de segundo orden, porque f_n depende de los dos valores inmediatamente anteriores. Definamos una función auxiliar

g_n = f_n_-1

Con esto, podemos re-escribir la ecuación para f_n como un sistema de dos ecuaciones de primer orden:

f_n = f_n-1+g_n-1

g_n = f_n-1

f₁ = 1

g₁ = 0

Lo anterior se puede escribir como la ecuación vectorial

f_n = A*f_n_-1

donde

f_n = [ f_n ]       A = [ 1 1 ]

    [ g_n ]           [ 1 0 ]

con la condición inicial

f₁ = [ 1 ]

    [ 0 ]

La solución de esta ecuación es

f_n = Aⁿ^-1*f₁

lo cual puede calcularse en tiempo O(log n) usando el método rápido de elevación a potencia visto anteriormente.

Backtraking (resolver por prueba y error)

Problema: se tiene una matriz de caracteres de dimensiones M+1xN+1 que representa un laberinto. En los elementos donde hay un caracter ‘*’ significa que hay una pared y no se puede pasar por esa posición y por donde hay un espacio ‘ ‘ se puede pasar. Un ejemplo sería:

* * * * * * * * *

* * * *

* * * * * *

* * *

* * * *

* * * * * * * * *

Se le pide escribir un método public static boolean salida(char[][] x, int i, int j, int M, int N) que retorne true si a desde la posición i,j se puede encontrar una salida.

Recursivamente esto se puede programar de la siguiente manera probando todos los caminos posibles:

1- si en la posición donde estoy (i,j) hay un ‘*’ no hay salida y retorno false.

2- si estoy en una posición (i,N) o (M,j) y hay un ‘ ‘ entonces estoy fuera y retorno true.

3- si estoy en posición (i,j) y hay un espacio, pruebo recursivamente si hay salida por alguna de las 4 vecinas (i+1,j), (i-1,j), (i,j+1), (i,j-1).

si alguna de las llamadas retorna true, yo retorno true (suponemos que no se puede mover en diagonal). Si todas retornan false, retorno false.

if (i == M || j == N) return true;

if (salida1(x, i+1, j, M, N)) return true;

if (salida1(x, i-1, j ,M, N)) return true;

if (salida1(x, i, j+1, M, N)) return true;

if (salida1(x, i, j-1, M, N)) return true;

return false;

Esta solución tiene el problema que puede generar llamadas infinitas. Por ejemplo, si llamamos a salida(x, a, b, M,N) y esá vacía pero no es salida, esta llamará a salida(x,a+1,b,M,N). Si la celda (a+1,b) está vacía y no es salida, llamará a salida(x, a+1-1,b,M,N), generandose así un ciclo infinito. Para evitar esto podemos ir “marcando” (por ejemplo, con una x) los lugares por donde hemos pasado para no pasar de nuevo por ahí:

if (i == M || j == N) return true;

if (x[i][j] == '*' || x[i][j] == '+') return false;

x[i][j] = '+';

if (salida1(x, i+1, j, M, N)) return true;

if (salida1(x, i-1, j ,M, N)) return true;

if (salida1(x, i, j+1, M, N)) return true;

if (salida1(x, i, j-1, M, N)) return true;

return false;

Y ahora, ¿ como podemos “rescatar” el camino? Podemos retornar un string que contenga la secuencia de (i,j) por donde hay que pasar para llegar a la salida. Para eso debemos modificar el encabezado:

public static String sailda(char[][] x, int i, int j, int M, int N) {

if (i == M || j == N) return "("+i+","+j+")";

String l = s.nextLine();

if (x[i][j] == '*' || x[i][j] == '+') return null;

x[i][j] = '+';

String camino = (salida2(x, i+1, j, M, N));

if (camino != null) return "("+i+","+j+")"+camino;

camino = (salida2(x, i-1, j ,M, N));

if (camino != null) return "("+i+","+j+")"+camino;

camino = (salida2(x, i, j+1, M, N));

if (camino != null) return "("+i+","+j+")"+camino;

camino = (salida2(x, i, j-1, M, N));

if (camino != null) return "("+i+","+j+")"+camino;

return null;

}

Finalmente, queremos saber cuánto mide el camino (de existir) entre la celda i,j y la salida más próxima. Para esto tenemos que probar todas las posibilidades y nos quedamos con la mejor (más corta):

public static int sailda(char[][] x, int i, int j, int M, int N) {

if (i == M || j == N) return 0;

String l = s.nextLine();

if (x[i][j] == '*' || x[i][j] == '+') return -1;

int mascorto = M*N+1;

x[i][j] = '+';

int camino = (salida3(x, i+1, j, M, N));

if (camino != -1 && camino < mascorto) mascorto = camino;

camino = (salida3(x, i-1, j ,M, N));

if (camino != -1 && camino < mascorto) mascorto = camino;

camino = (salida3(x, i, j+1, M, N));

if (camino != -1 && camino < mascorto) mascorto = camino;

camino = (salida3(x, i, j-1, M, N));

if (camino != -1 && camino < mascorto) mascorto = camino;

x[i][j] = ' ';

if (mascorto == M*N+1) return -1;

return mascorto +1;

}

Hagamos una función que me ayuda a evaluar qué tan buena es una jugada en el gato. Esto suponiendo que tanto mi contrincante como yo vamos a seguir escogiendo la mejor jugada posible en cada etapa.

//retorno 1 si gano con la jugada x,y, 0 si empato, -1 si pierdo

//suponiendo que el contrincante hace su mejor jugada

int gato(char[][] t, int x, int y, char z) {

t[x][y] = z;

//si gano retorno 1

if (gano(t, z))

return 1;

if (empate(t,x,y,z))

return 0;

char contrincante = 'O';

if (z == 'O')

contrincante = 'X';

int mejorCont = -1;

for (int i = 0; i <= 2; i++)

for (int j = 0; j <= 2; j++)

if (t[i][j] == ' ') {

int c = gana(t,i,j,contrincante);

if (c > mejorCont)

mejorCont = c;

}

return -mejorCont:

}

boolean gano(char[][] t, char z) {

boolean gane = false;

if (t[0][0] == z && t[0][1] == z && t[0][2] == z)

gane = true;

if (t[1][0] == z && t[1][1] == z && t[1][2] == z)

gane = true;

if (t[2][0] == z && t[2][1] == z && t[2][2] == z)

gane = true;

if (t[0][0] == z && t[0][1] == z && t[0][2] == z)

gane = true;

if (t[1][0] == z && t[1][1] == z && t[1][2] == z)

gane = true;

if (t[1][1] == z && t[1][2] == z && t[1][3] == z)

gane = true;

if (t[2][0] == z && t[2][1] == z && t[2][2] == z)

gane = true;

if (t[0][0] == z && t[1][1] == z && t[2][2] == z)

gane = true;

if (t[2][0] == z && t[1][1] == z && t[0][2] == z)

gane = true;

return gane;

}

boolean empate(char[][] t) {

//se empata cuando el tamblero esta lleno

for (int i = 0; i <= 2; i++)

for (int j = 0; j <= 2; j++)

if (t[i][j] != ' ')

return false;

return true;

}

Conceptos de Programación Orientada al Objeto (OOP)

Un objeto combina datos y operaciones (métodos).

El principio básico es el de encapsulamiento (ocultamiento de información). Esto permite separar el "qué" (especificación funcional, pública) del "cómo" (implementación, privada).

Conceptos asociados a la programación orientada a objetos, para apoyar la reutilización de codigo:

Código genérico: la lógica de un algoritmo debe poder escribirse independientemente del tipo de los datos.

Herencia: permite extender la funcionalidad de un objeto.

Polimorfismo: permite que se seleccione automáticamente la operación apropiada según el tipo y número de los parámetros.

Clases

En Java un objeto es una instancia de una clase.

Ejemplo:

// Clase Entero, que permite leer y

// guardar un valor en una variable entera

public class Entero

    // Datos privados

    private int valor;

    // Métodos públicos

    public int leer()

        return valor;

    public void guardar( int x )

        valor = x;

// Ejemplo de programa principal

public class Prueba

    public static void main( String[] args )

        Entero m = new Entero();

        m.guardar( 5 );

        System.out.println( "m=" + m.leer() );

Tipos de métodos

Constructores

Permiten inicializar el objeto. Puede haber varios constructores con distinto número y tipos de parámetros.

Si no hay un constructor definido, los campos se inicializan automáticamente con valores nulos.

El constructor debe tener el mismo nombre que la clase.

Ejemplo: Clase para almacenar fechas:

public class Fecha

    private int a;

    private int m;

    private int d;

    // Constructor con parámetros

    public Fecha( int aa, int mm, int dd )

        a = aa;

        m = mm;

        d = dd;

    // Constructor sin parámetros

    public Fecha()

        a = 2001;

        m = 1;

        d = 1;

Ejemplos de uso:

Fecha f1 = new Fecha();

Fecha f2 = new Fecha( 2001, 4, 11 );

"Mutators" y "accessors"

Las variables de una clase tipicamente son privadas. Para mirar su valor, o para modificarlo, hay que utilizar métodos ad hoc (como leer y guardar en el ejemplo de la clase Entero).

Esto es un mayor grado de burocracia, pero aisla a los usuarios de una clase de los detalles de implementación de ella, y evita que se vean afectados por eventuales cambios en dicha implementación.

toString

Al imprimir un objeto a usando println, automáticamente se invoca a

         a.toString()

para convertirlo a una forma imprimible. Esto mismo ocurre cada vez que se utiliza a en un contexto de String.

En el ejemplo, si vamos a imprimir objetos de tipo Fecha, debemos proveer una implementación de toString dentro de esa clase:

public String toString()

    return d + "/" + m + "/" + a;

equals

El método equals se utiliza para ver si dos objetos tienen el mismo valor. Se invoca

        if( x.equals(y) )

y se declara como

        public boolean equals( Object b )

El tipo Object usado aquí es un tipo de objeto "universal" del cual se derivan todos los otros. El siguiente ejemplo muestra una implementación de equals para la clase Fecha:

public boolean equals( Object b )

    if( !(b instanceof Fecha) )

        return false; // el otro objeto no era de tipo Fecha

    Fecha f = (Fecha) b; // para verlo como una Fecha

    return a==f.a && m==f.m && d==f.d;

this

La referencia this identifica al objeto actual. Permite desde dentro de la clase accesar los campos propios diciendo, por ejemplo, this.a. Esto en realidad es redundante, porque significa lo mismo que decir simplemente a, pero puede ser más claro en la lectura.

También permite comparar si este objeto es el mismo que otro (no sólo si tienen el mismo contenido, sino si ambas referencias apuntan al mismo objeto).

El otro uso de this es como constructor, para llamar a otro constructor de la misma clase. Por ejemplo, el constructor sin parámetros de la clase Fecha podría haber sido declarado como:

public Fecha()

    this( 2001, 1, 1 );

Campos estáticos

Hay dos tipos de campos estáticos:

public final static double PI = 3.14159; // constante

private static int precioActual = 1300; // variable compartida

                         // por todos los objetos de esa clase

Métodos estáticos

Los métodos estáticos están asociados a una clase, no a objetos particulares dentro de ella.

Ejemplos:

       Math.sin

       Integer.parseInt

Los métodos estáticos no pueden hacer uso de la referencia this.

Packages

Las clases se pueden agrupar en "paquetes". Para esto, cada clase debe precederse de

package P;

class C

    . . .

Cuando a una variable no se le pone public ni private, es visible sólo dentro del mismo package.

La clase C se denomina P.C, pero si antes decimos import P.C; o bien import P.*;, entonces podemos referirnos a la clase simplemente como C;

Herencia

Principio que permite reutilizar trabajo ya hecho. Se basa en la relación is-a.

Ejemplo:

Círculo is-a Figura
Auto is-a Vehículo

Las clases forman una jerarquía en base a la relación de herencia.

Otro tipo de relación distinta es has-a. Por ejemplo:

Auto has-a Manubrio

Este tipo de relación se llama agregación y a menudo es más importante que la herencia.

Clase base:

La clase de la cual se derivan otras

Clase derivada:

Hereda todas las propiedades de la clase base. Luego puede agregar campos y métodos, o redefinir métodos.

Los cambios que se hagan en la clase derivada no afectan a la clase base.

Sintaxis:

public class Derivada extends Base

    . . .

· Los campos adicionales generalmente son privados.

· Los métodos de la clase base que no se redefinen en la clase derivada se heredan sin cambio, excepto por el constructor.

· Los métodos que se redefinen tienen prioridad.

· Se pueden agregar nuevos métodos.

· Los métodos públicos se pueden redefinir como privados.

Visibilidad

Los campos privados de la clase base no se ven desde las clases derivadas. Para que un campo de este tipo sea visible debe declararse como protected. Esta posibilidad debe usarse con mucho cuidado.

Constructores

Cada clase define su propio constructor, el cual lleva el mismo nombre que la clase.

Si no se define un constructor, se genera automáticamente un constructor sin parámetros que:

· llama al constructor con cero parámetros de la clase base, para la parte heredada, y luego

· inicializa con valores nulos los campos restantes.

Si se escribe un constructor, su primera instrucción puede ser una llamada a

           super( ... );

lo cual invoca al constructor de la clase base.

final

Si un método se declara como final, entonces no puede ser redefinido en las clases derivadas.

Análogamente, una clase declarada como final no puede ser extendida.

Métodos abstractos

Un método abstracto declara funcionalidad, pero no la implementa. Las clases derivadas deben proveer implementaciones para estos métodos.

Una clase abstracta es una clase que tiene al menos un método abstracto. No se puede crear objetos pertenecientes a una clase abstracta (no se puede ejecutar new).

Ejemplo:

abstract class Figura

    private String nombre;

    abstract public double area();

    public Figura( String n )

        nombre = n;

    // Este constructor no puede ser invocado directamente,

    // sólo lo usan las clases derivadas

    final public double compArea( Figura b )

        return area() - b.area();

    final public String toString()

        return nombre + " de area " + area();

// Clases derivadas

public class Circulo extends Figura

    static final private double PI = 3.141592653;

    private double radio;

    public Circulo( double r )

        super( "circulo" );

        radio = r;

    public double area()

        return PI*radio*radio;

public class Rectangulo extends Figura

    private double largo;

    private double ancho;

    public Rectangulo( double l, double a )

        super( "rectangulo" );

        largo = l;

        ancho = a;

    public double area()

        return largo*ancho;

public class Cuadrado extends Rectangulo

    public Cuadrado( double lado )

        super( lado, lado );

Herencia múltiple

En algunos lenguajes, una clase puede heredar de más de una clase base. En Java esto no se permite, lo cual evita los conflictos que se podrían producir al heredarse definiciones incompatibles de métodos y variables.

Interfaz

Una interfaz es un mecanismo que permite lograr algunos de los efectos de la herencia múltiple, sin sus problemas.

Una interfaz es una clase que sólo tiene métodos públicos abstractos y campos públicos estáticos finales.

Se dice que una clase implementa a la interfaz si provee definiciones para todos los métodos abstractos de la interfaz.

Una clase puede extender sólo a una clase base, pero puede implementar muchas interfaces.

Ejemplo:

package Definiciones;

public interface Comparable

    public int Compare( Comparable b );

final public class Entero implements Comparable

    private int valor;

    public Entero( int x )

        valor = x;

    public String toString()

        return Integer.toString( valor );

    public int valorEntero()

        return valor;

    public int Compare( Comparable b )

        return valor - ((Entero) b).valor;

Uso de interfaces para implementar componentes genéricas

Ejemplo: Ordenación por inserción que ordena objetos de cualquier tipo.

package Ordenacion;

import Definiciones.*;

public static void insercion( Comparable[] a )

    for( int k=0; k<a.length; ++k )

        int j;

        Comparable t = a[k];

        for( j=k; j>0 &&

              t.Compare(a[j-1])<0; --j)

            a[j] = a[j-1];

        a[j] = t;

Ejemplo de uso: Ordenar enteros entregados como argumentos.

import Definiciones.*;

public class PruebaOrdenacion

    public static void main( String[] args )

        Entero[] a = new Entero[args.length];

        for( int i=0; i<args.length; ++i )

            a[i] = new Entero( Integer.parseInt(args[i]) );

        Ordenacion.insercion( a );

        for( int i=0; i<a.length; ++i )

            System.out.println( a[i] );

Nociones básicas de programación

Datos

Variables

Constantes

Instrucciones Elementales

Asignación

Salida

Instrucciones Compuestas

Secuencia de instrucciones

Instrucciones condicionales

Instrucción iterativa

Desarrollo de Programas iterativos usando invariante

¿Cómo escribir un ciclo (y asegurarse que hace lo que uno quiere)?

Ejemplos de programas iterativos abordados con invariante

Algoritmos simples de ordenación

Ordenación por inserción

Ordenación por Selección

Ordenación de la Burbuja

Cálculo de xn

Diagramas de Estados

Problema

Problema

Problema Propuesto (traer solución el Miércoles 24 de Septiembre)

Recursividad

"Dividir para reinar"

Recursividad y Tabulación (Programación Dinámica)

Backtraking (resolver por prueba y error)

Conceptos de Programación Orientada al Objeto (OOP)

Clases

Tipos de métodos

Constructores

"Mutators" y "accessors"

toString

equals

this

Campos estáticos

Métodos estáticos

Packages

Herencia

Visibilidad

Constructores

final

Métodos abstractos

Herencia múltiple

Interfaz

Uso de interfaces para implementar componentes genéricas

Cálculo de `xⁿ`