Principios Básicos

Principio de Multiplicación (Regla del producto)

Sean A₁,A₂,…, A_n conjuntos finitos, entonces |A₁ x A₂ x … x A_n| = |A₁| . |A₂|  ….  . |A_n|

Ej:
Tomemos 2 conjuntos:
A = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } ; | A | = 10
B = { a, b, c, d, e, f } ; | B | = 5

Supongamos que quiero saber todos las posibles conjuntos formados por 1 elemento de A y otro de B, por ej: { 3, b }, { a, 2 }.

O visto desde lenguajes formales cual es la cantidad de posibles cadenas formadas por primero un elemento de A y después un elemento de B, Ej: “3b”, “2a”, “9c”, “3c".

Existen 10 elementos en A y 5 en B por lo que la solución es: | A | x | B |  = 50

Principio de Adición (Regla de la Suma)

Sean A₁,A₂,…, A_n conjuntos finitos y disjuntos, entonces |A₁ ∪ A₂ ∪ … ∪ A_n| = |A₁| + |A₂| +  ….  + |A_n|

Ej:

Supongamos que tengo que elegir un elemento de A o de B (del ejemplo anterior). Como |A| = 10 y |B| = 5 y A ∩ B = ∅ entonces |A ∪ B| = 15, o sea que existen 15 posibles elementos que puedo elegir.

Principio de Exclusión y Exclusión

Si A₁, A₂ son conjuntos finitos pero no disjuntos. Entonces |A ∪ B| = |A| + |B| - |A ∩ B|
Esto se generaliza para la unión de varios conjuntos.

Permutaciones

Permutaciones

Supongamos que quiero calcular la cardinalidad del conjunto G formado por las cadenas de 3 caracteres formadas por elementos de C= {n, m, p} tales que no se repita nunca ningún elemento: { “nmp”, “npm”, “mnp”, “mpn”, “pmn”, “pnm” }.
Por el principio de multiplicación, Existen 3 posibilidades para el primero, luego como no se repiten 2 para el segundo y 1 para el tercero.
| G | = 3! = 6

La forma de poner n objetos en ordén es: P(n, n) = n!

R-Permutaciones

Supongamos ahora que quiero saber la cardinalidad del conjunto H formado por todas las cadenas de 3 carácteres formadas por elementos de A= { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } sin que se repita nunca ningún elemento. Hay 10 posibilidades para el primer espacio, 9 para el segundo y 8 para el tercero, por lo que:

| H | = $\frac{10!}{7!}$

El número de permutaciones de r objetos de n en ordén pero sin repetición es: P(n, r) = $\frac{n!}{\left(n-r!\right)}$

Permutaciones con repetición

Supongamos que quiero saber la cardinalidad del conjunto formado por todas las cadenas de 3 caracteres formadas por elementos de A = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } en las que se puedan repetir los elementos. Por la regla del producto existen 10 posibilidades para el primer carácter, 10 para el segundo y 10 para el tercero, por lo que el resultado es 10³.

El número de permutaciones de r objetos de n en ordén con repetición es: n^r

Selecciones

r-combinaciones

Una r-combinación de elementos de un conjunto es una selección sin ordenar de r elementos del conjunto, es decir, de subconjuntos de r elementos.

El número de r-combinaciones de n elementos, donde n es un entero no negativo y r es un entero tal que 0 <= r <= n es: C(n, r) = $\left(\genfrac{}{}{0ex}{}{n}{r}\right)=$$\frac{n!}{r!.\left(n-r\right)!}$
Ej:

Supongamos que quiero calcular la cardinalidad del conjunto J formado por todos los posibles subconjuntos de 2 elementos que contienen elementos de D = {w, x, y, z},  C(4,2) = 6, ya que J = { {w, x}, {w,y} , {w,z}, {x, y}, {x, z}, {y, z}}.

Relación entre r-permutaciones y r-combinaciones

Las r-permutaciones de un conjunto de cardinalidad n se pueden obtener formando las C(n,r) r-combinaciones del conjunto ( o sea todas los posibles subconjuntos de tamaño r formados por los n elementos del conjunto ) y luego ordenando estos elementos de todas las formas posibles, como cada subconjunto tiene tamaño r esto puede hacerse de P(r, r) formas de lo que sigue que:

P(n, r) = C(n, r) . P(r, r)

Selecciones con repetición

En un conjunto con n elementos hay C(n + r - 1, r) combinaciones con repetición.

Ej:

Supongamos que en un grupo de monedas hay 3 tipos distintos de 1, 5 y 10 centavos y hay por lo menos 5 de cada una de ellas. Cuantos posibles combinaciones de 5 monedas es posible extraer de este grupo?  Es importante recalcar que las monedas de cada valor son indistinguibles entre si  y no importa el orden en que se seleccionan las monedas, por lo que hay 5 combinaciones con repetición de 3 elementos.
Supongamos que cuando elejimos las monedas las metemos en una caja con 3 compartimentos, 1 para cada  tipo de moneda, entre cada compartimento hay una barra que las separa, de esta manera algunas de las posibles combinaciones podrian representarse como:
** | * | **
* | | ****
|*****|
***|*|*
…. etc.
Se ve que el numero de seleccionar 5 monedas de entre 3 tipos distintos corresponde al numero de formas de colocar 2 barras y 5 asteriscos. Por lo que el número de formas de seleccionar las monedas es equivalente al número de formas de seleccionar 5 asteriscos de entre 7 posiciones posibles, que se puede hacer de C(7, 5) maneras.

Equivalencias de Números Combinatorios

$$\left(\genfrac{}{}{0ex}{}{0}{0}\right)=\frac{0!}{0!.0!}=1$$

$$\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\frac{n!}{0!.n!}=1$$

$$\left(\genfrac{}{}{0ex}{}{n}{1}\right)=\frac{n!}{1!.n!}=1$$

$$\left(\genfrac{}{}{0ex}{}{n}{n}\right)=\frac{n!}{0!.n!}=1$$

Números combinatorios complentarios

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!.\left(n-k\right)!}=\frac{n!}{\left(n-k\right)!.k!}=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$$

Permutaciones con Objetos Indistinguibles y Distribuciones de Objetos en Cajas

Ej 4.5.8 de MD
¿Cuantas permutaciones se pueden realizar con las letras de la palabra “PAPAYA¨? . No se puede usar la formula general de Permutaciones porque la letra “A” se repite 3 veces y la letra “P” se repite 2. Por lo que debe pensarse así: se pueden seleccionar las posiciones de las 3 letras “A” de C(6, 3) formas distintas, las “P” se pueden colocar en C(3,2) formas distinras quedando C(1, 1) para la “Y”. Por la regla del Producto queda:
C(6,3) . C(3, 2) . C(1,1) =  $\frac{6!}{3!.3!}$. $\frac{3!}{2!.1!}$. 1 = $\frac{6!}{3!.2!}$  = 60

El número de permutaciones diferentes de n objetos; donde hay n₁objetos indistinguibles de tipo 1, n₂ objetos indistinguibles de tipo 2, …, n_k objetos indistinguibles de tipo k; es:
$\frac{n!}{n_1!.n_2!\dots .n_k!}$

Ej 4.5.9 de MD
¿De cuántas formas se pueden distribuir a cuatro jugadores manos de 5 cartas usando una baraja de 5 cartas? . Observese que al primero se le pueden distribuir C(52, 5), al segundo C(47, 5), al terceso C(42, 5) y al cuarto C(37, 5) (Quedando 32 cartas en el maso como una 5ta clase posible). Por la regla del producto queda:
C(52, 5) . C(47, 5) . C(42, 5) . C(37, 5) = $\frac{52!}{47!.5!}$. $\frac{47!}{42!.5!}$$\frac{42!}{47!.5!}$. $\frac{37!}{32!.5!}$=  $\frac{52!}{5!.5!.5!.5!.32!}$

El número de formas de distribuir n objetos distinguibles en k cajas distinguibles de forma que en la caja i-ésima haya n_i objetos, i = 1,2, …, k; es:
$\frac{n!}{n_1!.n_2!\dots .n_k!}$

Referencias

Matemática Discreta y sus aplicaciones; Rosen, Kenneth H.; 5ª edición, Mc Graw Hill, 2004

Algebra I; Rojo, Armando; 21ª ed, Magister Eos; 2006

Uno de las cosas fascinantes del Mathematica y ( ahora del wolfram alpha ) es como resuelve y además simplifica expresiones matemáticas (por ejemplo: derivando funciones y dando cada uno de los pasos). Se usa de esta manera la computadora no para hacer cálculos numéricos ( que arrojen como resultado un número ) sino para computación simbólica ( cálculos que arrojan como resultado una expresión matemática ).

La pregunta es como una maquina que guarda resultados en memoria en forma de expresiones binarias ( esencialmente números, aunque pueden representar otra cosa ) para hacer esto. La respuesta es que la representación de formulas matemáticas puede ser realizada a través de diferentes estructuras de datos y es manipulando estas estructuras que se pueden realizar estos cómputos.

Como un ejemplo básico de esto acá va un ejemplo sacado de C & Data Structures sobre como se pueden hacer operaciones sobre polinomios.

Una estructura de datos para guardar un polinomio y las funciones para llenarlo y mostrarlo.

# include <stdio.h>

# include <stdlib.h>

struct pnode

   {

      int exp;

      int coeff;

      struct pnode *link;

   };

struct pnode *insert(struct pnode *p, int e,int c) {

   struct pnode *temp;

   temp = p;

   if(p==NULL) {

      p=(struct pnode *)malloc(sizeof(struct pnode));

      if(p==NULL) {

         printf("Error de alocación de memoria\n");

         exit(0);

      }

      p-> exp = e;

      p->coeff = c;

      p-> link = NULL;

   } else {

        //Si tienen el mismo exponente se suman los coeficientes en vez de agregar un nodo.

       if(p->exp == e) {

            p->coeff = p->coeff + c;

       } else {

            p->link = insert(p->link, e, c);

       }

   }

   return (p);

}



void printpoly ( struct pnode *p ) {

      printf("The polynomial is\n");

      while (p!= NULL) {

        if(p->exp != 1) {

            printf("%dx^%d\t", p->coeff, p-> exp);

        } else {

            printf("%dx\t", p->coeff);

        }

        p = p-> link;

      }

      printf("\n");

}

Nota: en la función de insertar si un nuevo termino tiene el mismo exponente que uno anterior se lo suma en vez de agregarlo. Esto es una de las modificaciones al código del libro.

Ordenando el polinomio

/* a function to sort a list */

struct pnode *sortpoly(struct pnode *p)

{

   struct pnode *temp1,*temp2,*max,*prev,*q;

   q = NULL;

   while(p != NULL) {

      prev = NULL;

      max = temp1 = p;

      temp2 = p -> link;

      while ( temp2 != NULL ) {

         if(max -> exp < temp2 -> exp) {

            max = temp2;

            prev = temp1;

         }

         temp1 = temp2;

         temp2 = temp2-> link;

      }

      if(prev == NULL) {

            p = max -> link;

       }  else {

            prev -> link = max -> link;

       }

       max -> link = NULL;

        if( q == NULL) {

            q = max;

        } else {

            temp1 = q;

            while( temp1 -> link != NULL) {

                temp1 = temp1 -> link;

            }

            temp1 -> link = max;

        }

    }

    return (q);

}

Una Función para sumar 2 polinomios

/* A function to add two polynomials */

   struct pnode *polyadd(struct pnode *p, struct pnode *q)

   {

      struct pnode *r = NULL;

      int e;

      int c;

      while((p!=NULL) && (q != NULL)) {

            //p mayor exponente que q

            if(p->exp > q->exp) {

                r = insert(r,p->exp,p->coeff);

                p = p->link;



            //q mayor exponenete que p

            } else if(p->exp < q->exp) {

                r = insert(r,q->exp,q->coeff);

                q = q->link;



            //mismo exponente

            } else {

                c = p->coeff + q->coeff;

                e = q->exp;

                r = insert( r, e,c);

                p = p->link;

                q = q->link;

            }

      }

   //Lo que quede de ambos polinomios

    while(p != NULL) {

        r = insert( r, p->exp,p->coeff);

        p = p->link;

    }

    while(q!=NULL) {

        r = insert( r, q->exp,q->coeff);

        q = q->link;

    }

   return(r);

}

Una función para multiplicar polinomios.

Teniendo una función insertar que sume los términos del mismo exponente y una función de suma es muy fácil agregar una función que multiplique polinomios.

struct pnode *polymult(struct pnode *p, struct pnode *q) {

    struct pnode *r, *r2, *temp;

    r = NULL;

    temp = q;

    while(p != NULL) {

        temp = q;

        while(temp != NULL) {

            r = insert(r, (temp->exp + p->exp), (temp->coeff * p->coeff));

            temp = temp->link;

        }

        p = p->link;

    }

    return r;

}

Probando el programa

int main()

   {

         int e;

         int n,i, c;

         struct pnode *poly1 = NULL ;

         struct pnode *poly2=NULL;

         struct pnode *result;

         printf("Enter the terms in the polynomial1 \n");

         scanf("%d",&n);

         i=1;

         while ( n-- > 0 )

         {

      printf( "Enter the exponent and coefficient of the term number %d\n",n);

               scanf("%d %d",&e,&c);

               poly1 = insert ( poly1,e,c);

         }

        printf("Enter the terms in the polynomial2 \n");

         scanf("%d",&n);

         i=1;

         while ( n-- > 0 )

         {

      printf( "Enter the exponent and coefficient of the term number %d\n",n);

               scanf("%d %d",&e,&c);

               poly2 = insert ( poly2,e,c);

         }

         poly1 = sortpoly(poly1);

         poly2 = sortpoly(poly2);

         printf("The polynomial 1 is\n");

         printpoly ( poly1 );

         printf("The polynomial 2 is\n");

         printpoly ( poly2 );

         result = polyadd(poly1,poly2);

         printf("The result of addition is\n");

         printpoly ( result );

         result = polymult(poly1, poly2);

         printf("The result of multiplication is\n");

         printpoly ( result );

         return 0;

   }

Resultados

Enter the terms in the polynomial1 
5
Enter the exponent and coefficient of the term number 4
5 5
Enter the exponent and coefficient of the term number 3
4 4
Enter the exponent and coefficient of the term number 2
3 3
Enter the exponent and coefficient of the term number 1
2 2
Enter the exponent and coefficient of the term number 0
1 1
Enter the terms in the polynomial2 
2
Enter the exponent and coefficient of the term number 1
2 2
Enter the exponent and coefficient of the term number 0
1 1
sdfsdfThe polynomial 1 is
The polynomial is
5x^5	4x^4	3x^3	2x^2	1x	
The polynomial 2 is
The polynomial is
2x^2	1x	
The result of addition is
The polynomial is
5x^5	4x^4	3x^3	4x^2	2x	
The result of multiplication is
The polynomial is
10x^7	13x^6	10x^5	7x^4	4x^3	1x^2	

Pensando en todo esto es interesante en como en MathML se usan estructuras arboreas ( MathML esta basado en XML ) para representar expresiones matematicas y las implicaciones que puede tener a futuro para la automatización de determinado tipo de calculos.

Referencias

C & Data Structures, Deshpande, Kakde; Charles River Media, 2004

Foldr y Foldl

foldr y foldl son funciones de plegado sobre la estructura recursiva de las listas.

Cumpliendose que:

foldr f z (x1 : (x2 : (… : (xn : []))))
= x1 ‘f’ (x2 ‘f’ (… ‘f’ (xn ‘f’ z))))

foldl f z (x1 : (x2 : (… : (xn : []))))
= ((((z ‘f’ x1) ‘f’ x2) … ‘f’ xn-1) ‘f’ xn)

En ambas se toma una función y se la aplica sucesivamente a cada miembre de una lista, hasta recibir un resultado final.

Ejemplos. Definición de una función and que devuelve True si todos los elementos de una lista de Bool son verdaderos y definición de una función or que devuelve True si alguno es verdadero.

and3 :: [Bool] -> Bool
and3 = foldr (&&) True

or3 :: [Bool] -> Bool
or3 = foldr (||) False

scanl y scanl, devuelven los pasos intermedios de una operación de foldl y foldr respectivamente. Los siguientes ejemplos demuestran que si una operación no es asociativa (como la resta en los naturales) foldr y foldl devuelven resultados distintos.

*Main> scanl (+) 0 [1..5]
[0,1,3,6,10,15]
*Main> scanr (+) 0 [1..5]
[15,14,12,9,5,0]

*Main> scanr (-) 0 [1..5]
[3,-2,4,-1,5,0]
*Main> scanl (-) 0 [1..5]
[0,-1,-3,-6,-10,-15]

El segundo argumento es el caso final o primero a aplicarse.

*Main> scanl (*) 10 [1..5]
[10,10,20,60,240,1200]
*Main> scanr (*) 10 [1..5]
[1200,1200,600,200,50,10]

Referencias

Razonando con Haskell;Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero y José E. Gallardo;Thomson Editores Spain;2004

Uno de los temas que es difícil de entender en C es el tema de los punteros y como se relacionan con las estructuras de datos. Lo difícil ( o por lo menos fue difícil para mi que venia de lenguajes dinámicos ) es entender que los punteros guardan direcciones a memoria y a que a partir de esto se puede hacer el entrelazamiento de diferentes estructuras apuntadas. Voy a usar los ejemplo de linked list de C & Data Structures para mostrar como se da esto.

Primero creamos la estructura y una función para insertar elementos en la misma:

struct node {

   int data;

   struct node *link;

};



/*Insert en versión recursiva */

struct node *insert(struct node *p, int n) {

   if(p==NULL) {

      p=(struct node *)malloc(sizeof(struct node));

      if(p==NULL) {

        printf("Allocation Error\n");

         exit(0);

      }

      p-> data = n;

      p-> link = NULL;

   } else {

       p->link = insert(p->link,n);

    }

      return(p);

}

Nota: Se hace la búsqueda del ultimo nodo para insertar en forma recursiva.

Luego hago una función para mostrar la lista:

void printnode( struct node *p) {

    printf("Memory Space: %p\t Value: %d \t Link: %p\t\n",p, p-> data, p-> link);

}



void printlist ( struct node *p ) {

      printf("The data values in the list are\n");

      while (p!= NULL) {

         printnode(p);

         p = p-> link;

      }

}

La función printnode, muestra primero la dirección de memoria de la estructura, después su valor y finalmente la dirección de memoria a la que apunta, de esta manera podemos ver como se enlazan los nodos dentro de la lista.

Agregando y borrando nodos.

   /* a function which inserts a newly created node after the specified

node */

    //node_no empieza en 0 como en los arrays

   struct node * newinsert ( struct node *p, int node_no, int value ) {

      struct node *temp, * temp1;

      int i;

      temp = p;



      for(i=0; i<node_no && temp->link != NULL; i++) {

            temp = temp->link;

      }

        if(i != node_no ) {

            printf("Se pide insertar en un nodo mayor a la cantidad existente, se agrega tras el ultimo nodo existente.\n");

        }

        temp1 = ( struct node * )malloc ( sizeof ( struct node ));

        if ( temp1 == NULL ) {

            printf( " Cannot allocate \n");

            exit (0);

        }

        temp1->data = value;

        temp1->link = temp->link;

        printf("The newly created node to be inserted is:\n");

        printnode(temp1);

        temp->link = temp1;

        return(p);

   }



   struct node * erasenode( struct node *p, int node_no) {

        struct node *temp, *prev;

        int i;

        temp = p;

        if(node_no == 0) {

            temp = p->link;

            free(p);

            p = temp;

        } else {

            i = 0;

            while(i<node_no && temp->link != NULL) {

                prev = temp;

                temp = temp->link;

                i++;

            }

            if(i != (node_no)) {

                printf("Se pide borrar un nodo que no existe.\n");

                exit(0);

            }

            prev->link = temp->link;

            free(temp);

        }

        return(p);

   }

Corriéndolo en el main:

int main()

{

      int n;

      int x;

      struct node *start = NULL ;

      printf("Enter the nodes to be created \n");

      scanf("%d",&n);

      while ( n-- > 0 )

      {

              printf( "Enter the data values to be placed in a node\n");

         scanf("%d",&x);

         start = insert ( start,x);

      }

      printf("The created list is\n");

      printlist ( start );

      start = newinsert(start, 2, 7);

      printlist (start);

      start = erasenode(start, 2);

      printlist ( start );

      return 0;

}

Resultado en pantalla:

Enter the nodes to be created 
5
Enter the data values to be placed in a node
5
Enter the data values to be placed in a node
4
Enter the data values to be placed in a node
3
Enter the data values to be placed in a node
2
Enter the data values to be placed in a node
1
The created list is
The data values in the list are
Memory Space: 0x81a5008	 Value: 5 	 Link: 0x81a5018	
Memory Space: 0x81a5018	 Value: 4 	 Link: 0x81a5028	
Memory Space: 0x81a5028	 Value: 3 	 Link: 0x81a5038	
Memory Space: 0x81a5038	 Value: 2 	 Link: 0x81a5048	
Memory Space: 0x81a5048	 Value: 1 	 Link: (nil)	
The newly created node to be inserted is:
Memory Space: 0x81a5058	 Value: 7 	 Link: 0x81a5038	
The data values in the list are
Memory Space: 0x81a5008	 Value: 5 	 Link: 0x81a5018	
Memory Space: 0x81a5018	 Value: 4 	 Link: 0x81a5028	
Memory Space: 0x81a5028	 Value: 3 	 Link: 0x81a5058	
Memory Space: 0x81a5058	 Value: 7 	 Link: 0x81a5038	
Memory Space: 0x81a5038	 Value: 2 	 Link: 0x81a5048	
Memory Space: 0x81a5048	 Value: 1 	 Link: (nil)	
The data values in the list are
Memory Space: 0x81a5008	 Value: 5 	 Link: 0x81a5018	
Memory Space: 0x81a5018	 Value: 4 	 Link: 0x81a5058	
Memory Space: 0x81a5058	 Value: 7 	 Link: 0x81a5038	
Memory Space: 0x81a5038	 Value: 2 	 Link: 0x81a5048	
Memory Space: 0x81a5048	 Value: 1 	 Link: (nil)	

Se ve aca como en la primera corrida los nodos estan ubicados uno tras otro en la memoria, pero al agregar un nuevo nodo se salta en el tercer nodo ( en este caso, Memory Space: 0x81a5028 Value: 3 Link: 0x81a5058 ) se salta al agregado ( Memory Space: 0x81a5058 Value: 7 Link: 0x81a5038 ) y del agregado al que antes existia contiguamente ( Memory Space: 0x81a5038 Value: 2 Link: 0x81a5048 ). Algo similar ocurre cuando se borra un nodo.

Revirtiendo y ordenando la lista.

/* a function to sort reverse list */

struct node *reverse(struct node *p) {

   struct node *prev, *curr;

   prev = NULL;

   curr = p;

   while (curr != NULL) {

      p = p-> link;

      curr-> link = prev;

      prev = curr;

      curr = p;

   }

   return(prev);

}



/* a function to sort a list */

struct node *sortlist(struct node *p)

{

   struct node *temp1,*temp2,*min,*prev,*q;

   q = NULL;

   while(p != NULL) {

      //Encontrar el menor de la lista p

      prev = NULL;

      min = temp1 = p;

      temp2 = p -> link;

      while ( temp2 != NULL ) {

              if(min -> data > temp2 -> data) {

                     min = temp2;

                     prev = temp1;

            }

         temp1 = temp2;

         temp2 = temp2-> link;

      }



      //Cambiar el link en la lista p del previo al menor al siguiente del menor

      if(prev == NULL) {

             p = min -> link;

      } else {

             prev -> link = min -> link;

      }



      //Agregar el menor a q

      min -> link = NULL;

      if( q == NULL){

            q = min; /* moves the node with lowest data value in the list pointed to by p to the list pointed to by q as a first node*/

       } else {

            temp1 = q;

            /* traverses the list pointed to by q to get pointer to its last node */

            while( temp1 -> link != NULL) {

                         temp1 = temp1 -> link;

            }

            temp1 -> link = min; /* moves the node with lowest data value in the list pointed to by p to the list pointed to by q at the end of list pointed by q*/

      }

   }

   return (q);

}

Vemos la impresión en pantalla de como quedan ordenados los nodos:

The sorted list is
The data values in the list are
Memory Space: 0x8c03048	 Value: 1 	 Link: 0x8c03038	
Memory Space: 0x8c03038	 Value: 2 	 Link: 0x8c03018	
Memory Space: 0x8c03018	 Value: 4 	 Link: 0x8c03008	
Memory Space: 0x8c03008	 Value: 5 	 Link: 0x8c03058	
Memory Space: 0x8c03058	 Value: 7 	 Link: (nil)	
The reversed list is
The data values in the list are
Memory Space: 0x8c03058	 Value: 7 	 Link: 0x8c03008	
Memory Space: 0x8c03008	 Value: 5 	 Link: 0x8c03018	
Memory Space: 0x8c03018	 Value: 4 	 Link: 0x8c03038	
Memory Space: 0x8c03038	 Value: 2 	 Link: 0x8c03048	
Memory Space: 0x8c03048	 Value: 1 	 Link: (nil)	

Referencias

C & Data Structures, Deshpande, Kakde; Charles River Media, 2004

Definición de Función.

Sea F una relación de A en B. F es una función si se cumple que:

F: A -> B <=> ∀a ∈ A( ∃b ∈ B ( (a, b) ∈ F ∧ ( (a, c) ∈ F => b = c)))

Coloquialmente para todo elemento de A existe un elemento de B tal que (a, b) ∈ F y este elemento es unico.

Considerando esto se suele expresar el valor de f  en a es b o en simbolos:

f(a) = b

Composición de Funciones

Sean f: A -> B y g: B -> C, entonces (g o f) (a) : A -> C es equivalente a g ( f (a) ) .

Funciones inyectivas (uno a uno)

f es inyectiva si se cumple que:

∀a₁ ∈ A ( ¬∃ a₂ ∈ A ( f(a₁) = f(a₂) )  

Funciones suryectivas

f : A -> B es suryectiva si se cumple que:

∀b ∈ B( ∃ a ∈ A( f(a) = b) )

Función inversa

Si f: A -> B es inyectiva y suryectiva se cumple que:

• f^-1: B -> A también es función.
• (f o f^-1) = I_A
• (f^-1 o f) = I_B

Donde I_C es la función identidad de C, I: C -> C tal que ∀ c ∈ C ( I(c) = c) ).

Referencias

How to Prove It: A Structured Approach; Velleman, Daniel; Cambridge University Press; 2006

A recursive data structure is a data structure that has the same form regardless of the size of the data.

Como ejemplo: linked list, arbol binario, etc.

P S Deshpande, O G Kakde: C & Data Structures

En otro ejercicio de la facultad se me pedía sumar todos los valores individuales de una matriz cuadrada a través de un algoritmo recursivo. Mi resolución en Java fue la siguiente:

	public static int sumaMatriz(int arr2[][], int m, int n) {
		if( (m == n) && (m == 0) ) return arr2[m][n];
		if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a
		if(m > n) {
			if(n > 0) {
				return arr2[m][n] + sumaMatriz(arr2, m, n-1); //Caso b
			} else {	
				return arr2[m][n];
			}
		} else { //n > m
			if(m > 0) {
				return arr2[m][n] + sumaMatriz(arr2, m-1, n); //Caso c
			} else {
				return arr2[m][n];
			}
		}
	}

Me interesa este ejercicio para pensar de otra forma sobre corrección de programas. La pregunta es si el algoritmo es correcto y después de pensarlo un poco llegue a la conclusión de que lo era. Por lo pronto para hacer una demostración formal debería usar inducción estructural pero este post trata más bien sobre trabajo previo a una demostración, lo que en How to Prove it llaman scratchwork. O sea el razonamiento a través del cual se llega a una demostración.

Primero que nada hagamos un poco de debugging con un caso simple de una matriz de 3×3. Para esto agregamos lo siguiente al código anterior:

	public static int sumaMatriz(int arr2[][], int m, int n) {
		if( (m == n) && (m == 0) ) return arr2[m][n];
		System.out.println(n + ” ” + m);
		if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a
		if(m > n) {
….
….

Y testeamos la función llamándola con:

public class TP4 {

	public static void main (String[] args) {
		int[][] arr2;
		arr2 = new int[3][3];
		arr2[0][0] = 1;
		arr2[0][1] = 2;
		arr2[0][2] = 2;
		arr2[1][0] = 4;
		arr2[1][1] = 2;
		arr2[1][2] = 3;
		arr2[2][0] = 4;
		arr2[2][1] = 7;
		arr2[2][2] = 8;
		System.out.println(”Ej9:”);
		System.out.println( TP4.sumaMatriz(arr2,2 ,2));
	}
}

Lo que muestra por consola es:

Ej9:

2 2
2 1
2 0
1 1
1 0
0 0
0 1
1 2
0 2

33

Podemos ver que todos los elementos de la matriz fueron accedidos y que el resultado es el correcto. Ahora imaginémonos el árbol de las llamadas de función.

Vemos que los elementos de la diagonal principal hacen 3 llamados más, al próximo elemento de la diagonal principal, y a los dos elementos con m o n decrementados en uno. Mientras que los elementos que no están en la diagonal principal hacen un solo llamado.

Razonamiento (Informal) sobre la corrección del Algoritmo

Consideremos una matriz cuadrada de grado m, tal que m sea mayor que 5 (esto es por claridad para hacer este ejercicio) y concentrémonos en los últimos 5×5 casilleros del limite inferior derecho, que es donde comienza el algoritmo.

Primer paso toma el elemento en m x m:

A partir de esto se realiza la llamada recursiva:

if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a

De la que se desprenden los siguientes 3 pasos.

El caso b:

return arr2[m][n] + sumaMatriz(arr2, m, n-1); //Caso b

De nuevo el caso a:

if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a

Y finalmente el caso c:

				return arr2[m][n] + sumaMatriz(arr2, m-1, n); //Caso c

Hemos llegado a llenar una matriz de 3×3, pero esto no nos demuestra nada, ahora lo interesante es saber que pasa cuando continua el algoritmo en los pasos siguientes y aquí es donde esta el truco.

Lo interesante es que las 3 posibles llamadas recursivas garantizan la siguiente:

• Por el caso a, desde una llamada de la función desde un casillero en la diagonal principal, no se llamara a la función en ningún casillero que este en la misma linea o columna de los elemento de donde han sido llamados por un casillero en la diagonal principal anterior.También por el caso a, la iteración a través de elementos de la diagonal principal eventualmente cubrirá todos los elementos de la diagonal principal de la matriz.

  

• Por el caso b, desde una llamada de la función desde un casillero en una columna que no sea en la diagonal principal, siempre continuara por esa misma columna hasta completarla.

  

• Por el caso c, desde una llamada de la función desde un casillero en la fila que no sea en la diagonal principal, siempre continuara por esa misma fila hasta completarla.

  

A partir de esto podemos inferir que el algoritmo pasa por todos los elementos de cualquier matriz cuadrada.

Importante

Quiero recalcar que esto es un razonamiento, a partir del cual por inducción estructural podría construirse una demostración, pero en términos de lógica formal no es una demostración. Igual, no deja de ser un razonamiento valido, lo cierto es que en la programación como practica es importante poder pensar si lo que se esta haciendo es correcto y si los programas que uno hace cumplen con las necesidades que uno tiene, pero también es cierto que sería completamente Overkill el tener que hacer una demostración formal de cada programa que uno hace. Lo importante es tener herramientas para poder razonar y pensar sobre como se programa.

En un ejercicio de la facultad me pidieron hacer un función recursiva que encuentre el Maximo común divisor entre dos números por medio de restas. Ahora, esto que parece un simple ejercicio en realidad se engancha con un montón de temas interesantes de la historia de la matemática. Bueno, lo primero que se me ocurrió fue factorizar los dos números y después buscar los factores comunes, obviamente esta idea no es lo que se dice fácil ( quizás hasta imposible ) de hacer recursivamente. Se me ocurrió investigar un poco y encontré el Algoritmo de Euclides. La implementación básica en Haskell es:

algEuclid :: Int -> Int -> Int
algEuclid a b	| c < 0 	= algEuclid b a
		| c == 0	= b
		| c >= b 	= algEuclid c b
		| c < b		= algEuclid b c
		where c = a - b

La versión en Haskell es super clara, pero se me pedía implementarla en Java y quedo así:

public class Ej {

	public static void main (String[] args) {
		//Ej8. Maximo Comun Divisor de 2 numeros
		System.out.println(”Ej8:”);
		System.out.println( TP4.algEuclid(64, 48));
	}


	public static int algEuclid( int a, int b) {
		int c = a - b;
		if ( c < 0) {
			return algEuclid(b, a);
		} else if (c == 0) {
			return b;
		} else if ( c >= b ) {
			return algEuclid(c, b);
		} //(c < b)
			return algEuclid(b, c);
	}
	
}

Lo interesante es que Euclides hace su demostración en términos puramente geométricos y en términos geométricos existen magnitudes a las que no es posible aplicarles esta formula. En particular raíz cuadrada de 2, es decir que no son conmensurables. Esto tuvo profundas implicancias en el desarrollo de la matemática, porque durante siglos al existir relaciones que no podían ser expresadas puramente en números (tal y como pretendían los pitagóricos) los griegos decidieron priorizar la geometría sobre otras formas de razonamiento matemático. Fue necesario un salto de paradigma, en el sentido de Kuhn, a saber la aceptación de los números irracionales como objetos matemáticos por derecho propio para poder continuar avanzando en diversas áreas de la matemática.

En definitiva, si la historia de las matemáticas demuestra algo, es que si hay algo que no podemos entender actualmente o que parece que nos lleva a un callejón sin salida, en algún momento quizás con un enfoque nuevo probablemente podremos integrarlo a un sistema explicativo de orden superior.

Referencias

Este es el primer programita en Haskell que hice por gusto propio, principalmente para afianzar un poco conceptos y además para probar tipos de datos y sobre todo de pensar desde Haskell. Lo fantástico es que estas cosas las hacia a mano, cuando tenía 17 años y estaba aprendiendo armonía (Por mi cuenta, obviamente).

Primero definí un tipo de datos Nota y una función sucesor cíclica (dado que estoy interesado en relaciones puramente armónicas).

data Nota = A | Bb | B | C | Db | D | Eb | E | F | Gb | G | Ab deriving (Eq)

suc :: Nota -> Nota
suc A = Bb; suc Bb = B; suc B = C; suc C = Db; suc Db = D; suc D = Eb; suc Eb = E; suc E = F; suc F = Gb; suc Gb = G; suc G = Ab; suc Ab = A;

Después hice que el tipo de datos Nota fuera instancia de la clase show, dando una definición especifica de la función show para mi tipo de datos para tratar los problemas del doble nombre de determinadas notas ( equivalencias enarmonicas ).

instance Show Nota where
	show A = show "A"
	show Bb = show "A#/Bb"
	show B = show "B"
	show C = show "C"
	show Db = show "C#/Db"
	show D = show "D"
	show Eb = show "D#/Eb"
	show E = show "E"
	show F = show "F"
	show Gb = show "F#/Gb"
	show G = show "G"
	show Ab = show "G#/Ab"

A partir de esto puedo definir la función intervalo, que toma un número natural (de 0 a 11, aunque se puede considerar al tipo Nota y a la función intervalo como compartiendo propiedades con la aritmética mod(12), por lo que n puede tomar valores mayores a 11 y los resultados van a ser los mismos a intervalo _ (n mod (12))). En un principio había pensado que se podía pensar como un isomorfismo, pero no estoy convencido, aunque si tomamos aplicación parcial de intervalo x como una función en si misma, ahí si podría serlo.

intervalo :: Nota -> Integer -> Nota
intervalo a 0 = a
intervalo a 1 = suc(a)
intervalo a n = suc( intervalo a (n-1))

No intente definir los intervalos a partir de sus nombres usuales sino simplemente desde su distancia (ascendente) a partir de la nota base. O sea, se sobreentiende que si le doy un valor de uno representa a una segunda menor, de 4 a una tercera mayor, etc. (Por otro lado es como siempre me acerque al concepto de intervalo).

Paso siguiente construir funciones para definir las cuatro triadas básicas.

type Triada = (Nota, Nota, Nota) 

maj :: Nota -> Triada
maj a = (a, intervalo a 4, intervalo a 7)

men :: Nota -> Triada
men a = (a, intervalo a 3, intervalo a 7)

aug :: Nota -> Triada
aug a = (a, intervalo a 4, intervalo a 8 )

dim :: Nota -> Triada
dim a = (a, intervalo a 3, intervalo a 6)

Y luego definir las escalas y modos básicos.

escala :: Nota -> [Integer] -> [Nota]
escala a [] = []
escala a (x:xs) = intervalo a x : escala a xs

escala_cromatica :: Nota -> [Nota]
escala_cromatica a = escala a [0..11]

escala_mayor :: Nota -> [Nota]
escala_mayor a = escala a [0,2,4,5,7,9,11]

escala_menor :: Nota -> [Nota]
escala_menor a = escala a [0,2,3,5,7,8,10]

escala_menor_armonica :: Nota -> [Nota]
escala_menor_armonica a = escala a [0,2,3,5,7,8,11]

escala_menor_melodica :: Nota -> [Nota]
escala_menor_melodica a = escala a [0,2,3,5,7,9,11]

modo_dorico :: Nota -> [Nota]
modo_dorico a = escala a [0,2,3,5,7,9,10]

modo_frigio :: Nota -> [Nota]
modo_frigio a = escala a [0,1,3,5,7,8,10]

modo_lidio :: Nota -> [Nota]
modo_lidio a = escala a [0,2,4,6,7,9,11]

modo_mixolidio :: Nota -> [Nota]
modo_mixolidio a = escala a [0,2,4,5,7,9,10]

modo_locrio :: Nota -> [Nota]
modo_locrio a = escala a [0,1,3,5,6,8,10]

escala_disminuida :: Nota -> [Nota]
escala_disminuida a = escala a [0,2,3,5,6,8,9,11]

escala_aumentada :: Nota -> [Nota]
escala_aumentada a = escala a [0,2,4,6,8,10]

Dado que voy a intentar hacer reconocimiento de acordes, se vuelve necesario definir la función distancia (que es distancia ascendente).

distancia :: Nota -> Nota -> Integer
distancia a b 	| (intervalo a 0) == b 	= 0
		| otherwise 		= 1 + (distancia (suc a) b)

Probar de Reconocer Acordes.

es_triada_mayor :: Triada -> Bool
es_triada_mayor (a,b,c) | (distancia a b) == 4 && (distancia a c) == 7 = True
			| otherwise = False

es_triada_menor :: Triada -> Bool
es_triada_menor (a,b,c) | (distancia a b) == 3 && (distancia a c) == 7 = True
			| otherwise = False

es_triada_disminuida :: Triada -> Bool
es_triada_disminuida (a,b,c) 	| (distancia a b) == 3 && (distancia a c) == 6 = True
				| otherwise = False

es_triada_aumentada :: Triada -> Bool
es_triada_aumentada (a,b,c) 	| (distancia a b) == 4 && (distancia a c) == 8 = True
				| otherwise = False

Ejemplo de uso:

*Main> es_triada_mayor (A,Db,E)
True
*Main> es_triada_mayor (A,C,E)
False

Aclaración: Como el tipo de datos es cíclico a partir de la función suc y estamos trabajando con triadas básicas, no importan las diferentes inversiones de los acordes.

Ver si una triada existe en una escala:

esta_triada_en_escala :: [Nota] -> Triada -> Bool
esta_triada_en_escala xs (a,b,c)	| elem a xs && elem b xs && elem c xs = True
					| otherwise = False
{- 
*Main> esta_triada_en_escala (men A) (modo_dorico A)
True
-}

Ahora ya puedo armonizar escalas por un método de Brute Force, no muy elegante, pero por lo pronto efectivo. Primero creo todas las posibles triadas (4*12 = 48) y después filtro las que corresponden a la escala, además de crear una función que muestre los resultados de una forma visualmente más agradable.

show_triada :: Triada -> String
show_triada (a,b,c) 	| es_triada_mayor (a,b,c) = strip_slashes(show a) ++ " maj"
			| es_triada_menor (a,b,c) = strip_slashes(show a) ++ " min"
			| es_triada_aumentada (a,b,c) = strip_slashes(show a) ++ " aug"
			| es_triada_disminuida (a,b,c) = strip_slashes(show a) ++ " dim"
			| otherwise = strip_slashes(show (a,b,c)) ++ " No es Triada"
			where 
				strip_slashes :: [Char] -> [Char]
				strip_slashes [] = []
				strip_slashes (x:xs) 	| x == ‘\”‘ = strip_slashes xs
							| otherwise = x : strip_slashes xs		

todas_las_triadas :: Nota -> [Triada]
todas_las_triadas a = concat( map hacer_triadas_de (escala_cromatica a))
			where
			hacer_triadas_de :: Nota -> [Triada]
			hacer_triadas_de a = [(dim a),(men a),(maj a),(aug a)]
armonizar_escala :: [Nota] -> [String]
armonizar_escala (x:xs) = map show_triada (filter (esta_triada_en_escala (x:xs)) (todas_las_triadas x))

{-
*Main> armonizar_escala (modo_dorico A)
["A min","B min","C maj","D maj","E min","F#/Gb dim","G maj"]
*Main> armonizar_escala (escala_menor_armonica E)
["E min","F#/Gb dim","G aug","A dim","A min","B maj","B aug","C dim","C min","C maj","D#/Eb dim","D#/Eb aug"]
*Main> armonizar_escala (escala_aumentada E)
["E aug","F#/Gb aug","G#/Ab aug","A#/Bb aug","C aug","D aug"]
*Main> armonizar_escala (escala_disminuida E)
["E dim","F#/Gb dim","F#/Gb min","F#/Gb maj","G dim","A dim","A min","A maj","A#/Bb dim","C dim","C min","C maj","C#/Db dim","D#/Eb dim","D#/Eb min","D#/Eb maj"]
-}

Detalle: otro ejemplo de currying en esta_triada_en_escala (x:xs).

Obviamente esto un principio y hay un montón de ideas que se me ocurrieron mientras hacia esto. Así que, sera continuado.

Una función de orden superior es una función que devuelve otra función.

Un Combinador es un función de orden superior que encapsula un determinado comportamiento de una clase de funciones y provee un template para la creación de estas. Ej:

iter :: (Integer -> Integer -> Integer) -> Integer -> ( Integer -> Integer )
iter op e = fun
	where 
	fun 0	= e
	fun m@(n + 1) = op m (fun n)

factorial :: Integer -> Integer
factorial = iter (*) 1

sumatorio :: Integer -> Integer
sumatorio = iter (+) 0

Referencias

Razonando con Haskell;Blas C. Ruiz, Francisco Gutiérrez, Pablo Guerrero y José E. Gallardo;Thomson Editores Spain;2004