Bloque de Colores

Recuento: Permutaciones y Selecciones ( Formulas básicas)

Icono de Post August 26 2009 :: Apuntes, Combinatoria ::

Principios Básicos

Principio de Multiplicación (Regla del producto)

Sean A1,A2,…, An conjuntos finitos, entonces |A1 x A2 x … x An| = |A1| . |A2|  ….  . |An|

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 A1,A2,…, An conjuntos finitos y disjuntos, entonces |A1 ∪ A2 ∪ … ∪ An| = |A1| + |A2| +  ….  + |An|

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 A1, A2 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 | = 10!7!

El número de permutaciones de r objetos de n en ordén pero sin repetición es: P(n, r) = n!(nr!)

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 103.

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

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) = (nr)=n!r! . (nr)!
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

(00)=0!0! . 0! =1

( n 0 ) = n ! 0 ! . n ! = 1

( n 1 ) = n ! 1 ! . n ! = 1

( n n ) = n ! 0 ! . n ! = 1

Números combinatorios complentarios

( n k ) = n ! k ! . ( n k ) ! = n ! ( n k ) ! . k ! = ( n n k )

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) =   6 ! 3 ! . 3 ! . 3 ! 2 ! . 1 ! . 1 = 6 ! 3 ! . 2 !   = 60

El número de permutaciones diferentes de n objetos; donde hay n1objetos indistinguibles de tipo 1, n2 objetos indistinguibles de tipo 2, …, nk objetos indistinguibles de tipo k; es:
n ! n 1 ! . n 2 ! . 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) = 52 ! 47 ! . 5 ! . 47 ! 42 ! . 5 ! 42 ! 47 ! . 5 ! . 37 ! 32 ! . 5 ! =   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 ni objetos, i = 1,2, …, k; es:
n ! n 1 ! . n 2 ! . 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

Autor: Emiliano Martínez Luque.

Comments Off on Recuento: Permutaciones y Selecciones ( Formulas básicas)

Usando linked lists para trabajar con polinomios

Icono de Post August 13 2009 :: c, Estructuras de datos ::

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 memorian");

         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 isn");

      while (p!= NULL) {

        if(p->exp != 1) {

            printf("%dx^%dt", p->coeff, p-> exp);

        } else {

            printf("%dxt", 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 %dn",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 %dn",n);

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

               poly2 = insert ( poly2,e,c);

         }

         poly1 = sortpoly(poly1);

         poly2 = sortpoly(poly2);

         printf("The polynomial 1 isn");

         printpoly ( poly1 );

         printf("The polynomial 2 isn");

         printpoly ( poly2 );

         result = polyadd(poly1,poly2);

         printf("The result of addition isn");

         printpoly ( result );

         result = polymult(poly1, poly2);

         printf("The result of multiplication isn");

         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

Autor: Emiliano Martínez Luque.

Comments Off on Usando linked lists para trabajar con polinomios

foldr, foldl, scanl, scanr

Icono de Post August 13 2009 :: Haskell, Programación Funcional ::

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

Autor: Emiliano Martínez Luque.

Comments Off on foldr, foldl, scanl, scanr

Analizando los punteros de una linked list

Icono de Post August 10 2009 :: c, Estructuras de datos ::

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 Errorn");

         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: %pt Value: %d t Link: %ptn",p, p-> data, p-> link);

}



void printlist ( struct node *p ) {

      printf("The data values in the list aren");

      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 noden");

         scanf("%d",&x);

         start = insert ( start,x);

      }

      printf("The created list isn");

      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

Autor: Emiliano Martínez Luque.

Comments Off on Analizando los punteros de una linked list

Funciones (Definiciones Básicas)

Icono de Post August 10 2009 :: Apuntes, Teoría de Conjuntos ::

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:

∀a1 ∈ A ( ¬∃ a2 ∈ A ( f(a1) = f(a2) )  

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) = IA
  • (f-1 o f) = IB

Donde IC 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

Autor: Emiliano Martínez Luque.

Comments Off on Funciones (Definiciones Básicas)

Definición de estructura de datos recursiva

Icono de Post August 10 2009 :: Estructuras de datos ::

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