Metonymie.com :: Apuntes » Apuntes
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)

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)

Equivalencias Básicas de Sumatorias

Icono de Post May 7 2009 :: Algebra, Apuntes ::

Sumatoria de una constante    

Sea k constante se cumple que:

n = 1 m k = mk

Sumatoria de un polinomio

n = 1 m 2 a + b 2 c = n = 1 m 2 a + n = 1 m b 2 n = 1 m c

Sumatoria de un producto

Sea c constante, se cumple que:

n = 0 m ck = c . n = 0 m k

Sumatoria de una potencia ( Progresión geometrica )

Sea | r | > 1:
n = 1 m r n = r n + 1 1 r 1

Equivalencias

n = 0 m n = n ( n + 1 ) 2

n = 0 m n 2 = n ( n + 1 ) ( 2 n + 1 ) 6

n = 0 m n 3 = n 2 ( n + 1 ) 2 4

Estas equivalencias pueden demostrarse facilmente por inducción, hay más para diversos grados de n en esta pagína: PlanetMath: Summation.

Cambio de Limites

n = a b f ( k ) = n = a + r b + r f ( k r )

Autor: Emiliano Martínez Luque.

Comments Off on Equivalencias Básicas de Sumatorias

Relaciones sobre conjuntos (Definiciones y Propiedades Básicas)

Icono de Post May 7 2009 :: Apuntes, Teoría de Conjuntos ::

Definiciones Iniciales

Producto Cartesiano de A × B
A × B = {(a, b) | a ∈ A ∧ b ∈ B }
En particular, si A = B, se escribe A2 = {(a, b) | a ∈ A ∧ b ∈ A}

Relación
Sean A, B Conjuntos entonces R ⊆ A × B es una relación de A a B.

Dominio de R
Dom(R) = {a ∈ A | ∃b ∈ B((a, b) ∈ R)}

Rango de R
Ran(R) = {b ∈ B | ∃a ∈ A((a, b) ∈ R)}

Inversa de R
R-1 = {(b, a) ∈ B × A | (a, b) ∈ R}

Composición de S con R
S o R = {(a, c) ∈ A × C | (a, b) ∈ R ∧ (b, c) ∈ S}

Propiedades Posibles de las relaciones

Reflexiva
∀x ∈ R (x R x )

Simétrica
∀x, y ∈ R ( x R y -> y R x)

Transitiva
∀x,y,z ∈ R ( x R y ∧ y R z -> x R z)

Antisimetrica
∀x,y ∈ R ( x R y ∧ y R x -> x = y)

Irreflexiva
∀x ∈ A ((x, x) ∉ R)

Tricotomia
∀x ∈ A, ∀y ∈ A ( x R y ∨ y R x ∨ x = y)

Relaciones de Orden

Sea R una relación sobre un conjunto A, si R es Reflexiva, Transitiva y Antisimétrica se dice que R es un orden parcial sobre A.
Sera un orden total si ademas cumple que:
∀x,y ∈ A( x R y ∨ y R x)

Si R es irreflexiva y transitiva, se la llama un orden parcial estricto. Si ademas cumple Tricotomia, es un orden total estricto.

Elementos menores y mínimos

Sea R un Orden parcial en un conjunto A, B ⊆ A y b ∈ B. b es el elemento menor en B para R si ∀x ∈ B(b R x ). b es un elemento mínimo en B para R si ∀x ∈ B( x R b -> x = b ).

Nota: Sea R es un orden parcial sobre A y B ⊆ A. Se cumple que si B tiene un elemento menor, entonces este elemento es único, es mínimo y es el único mínimo. ( Sin embargo un elemento puede ser mínimo pero no ser menor. ) Si R es un orden total se cumple que si b es un elemento mínimo de B entonces es el menor elemento de B.

Cotas Inferiores y Superiores

Sea R un orden parcial en A, B ⊆ A y a ∈ A. a es una cota inferior de B si ∀b ∈ B( a R b ). Es una cota superior si ∀b ∈ B( b R a).

Sea U el conjunto de todas las cotas superiores de A, Si U tiene un elemento menor entonces este elemento es la cota superior menor de B.
Sea U el conjunto de todas las cotas inferiores de A, Si U tiene un elemento mayor entonces este elemento es la cota inferior mayor de B.

Cerraduras ( Closures )

Sea R una Relación en A. Sea S ⊆ A x A, si se cumple que: R ⊆ S,  S es reflexiva, ∀T ⊆ A x A( R ⊆ T ∧ T es reflexiva -> S ⊆ T) entonces S es la cerradura reflexiva de R.
De forma equivalente se definen las cerraduras Transitiva y Simétrica..

Relaciones de Equivalencia

Sea R una relación en A. Si R es reflexiva, simétrica y transitiva, se la llama una relación de equivalencia en A.  

Supongamos que A es un conjunto y F ∈ P(A), si se cumple que ∀X ∈ F, Y ∈ F( X ≠ Y -> X ∩ Y = ∅ ) se dice que F es disjunto en pares (pairwise disjoint). Si F cumple que: ∪F = A, F es disjunto en pares, ∀X ∈ F( X ≠ ∅ ), entonces F es una partición de A.

Toda relación de equivalencia establece una partición sobre el conjunto sobre el que esta definida.

Sea R una relación de equivalencia sobre A, x ∈ A. La clase de equivalencia de x respecto a R es el conjunto:
[x]R = { y ∈ A | y R x}
Se define entonces el conjunto de todas las clases de equivalencia sobre A determinados por R como A / R ( A modulo R ) tal que:
A / R = { [x]R | x ∈ A } = { X ⊆ A | ∃x ∈ A(X = [x]R)}

Referencias

The Haskell Road To Logic, Math and Programming; Doets, Van Eijck; King´s College London Publications; 2004

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

Autor: Emiliano Martínez Luque.

Comments Off on Relaciones sobre conjuntos (Definiciones y Propiedades Básicas)

Resumen de Sintaxis de Estructuras en C

Icono de Post December 31 2008 :: Apuntes, c ::

Declaración de estructuras y acceso a miembros.


#include <string.h>
#include <stdio.h>

struct ejemplo {
	int miembro1;
	char miembro2[30];
};

main () {

	struct ejemplo var1;

	var1.miembro1 = 10;
	strcpy(var1.miembro2, "Hola que Tal.");
	printf("miembro 1: %d t miembro 2: %sn", var1.miembro1, var1.miembro2);
}

Usando Typedef para simplificar la declaración de estructuras.


#include <string.h>
#include <stdio.h>

struct ejemplo {
	int miembro1;
	char miembro2[30];
};
typedef struct ejemplo ejemp;

main () {

	ejemp var2;

	var2.miembro1 = 20;
	strcpy(var2.miembro2, "Otro string.");
	printf("miembro 1: %d t miembro 2: %sn", var2.miembro1, var2.miembro2); 

}

Se puede hacer la misma declaración del typedef de la siguiente manera:


typedef struct ejemplo {
	int miembro1;
	char miembro2[30];
} ejemp;

Punteros a estructuras


#include <string.h>
#include <stdio.h>

struct ejemplo {
	int miembro1;
	char miembro2[30];
};

main () {

	struct ejemplo var1, *var2;

	//var2 es un puntero a var1
	var2 = &var1;

	var1.miembro1 = 10;
	strcpy(var1.miembro2, "Hola que Tal.");

	printf("miembro 1: %d t miembro 2: %sn", (*var2).miembro1, (*var2).miembro2);
	//O lo que es equivalente y mas usual
	printf("miembro 1: %d t miembro 2: %sn", var2->miembro1, var2->miembro2); 

}

Nota: (*var2).miembro1 es equivalente a var2->miembro1

Asignar memoria para un puntero a estructura.


#include <string.h>
#include <stdio.h>
#include <stdlib.h>

struct ejemplo {
	int miembro1;
	char miembro2[30];
};

main () {

	struct ejemplo *var1;

	var1 = (struct ejemplo*)malloc( sizeof(struct ejemplo));

	var1->miembro1 = 10;
	strcpy(var1->miembro2, "Hola que Tal.");

	printf("miembro 1: %d t miembro 2: %sn", var1->miembro1, var1->miembro2); 		

}

Estructuras dentro de estructuras.



#include <string.h>
#include <stdio.h>
#include <stdlib.h>

struct ejemplo {
	int miembro1;
	char miembro2[30];
};

struct ejemplo2 {
	struct ejemplo ej;
}

main () {

	struct ejemplo2 var1, *var2;

	var1.ej.miembro1 = 10;
	strcpy(var1.ej.miembro2, "Hola que Tal.");

	printf("miembro 1: %d t miembro 2: %sn", var1.ej.miembro1, var1.ej.miembro2); 		

	//var2 es puntero a var1
	var2 = &var1;

	printf("miembro 1: %d t miembro 2: %sn", var2->ej.miembro1, var2->ej.miembro2); 		

}

Espacio de memoria ocupado por una estructura.


#include <string.h>
#include <stdio.h>

struct ejemplo {
	int miembro1;
	int miembro2;
	int miembro3;
	char miembro4[30];
	char miembro5[30];
};

main () {

	struct ejemplo var1;

	var1.miembro1 = 10;
	printf("Dirección de miembro 1: %u t Dirección de miembro 2: %u t Dirección de miembro 3: %un", &var1.miembro1, &var1.miembro2, &var1.miembro3);
	printf("Dirección de miembro 4: %u t Dirección de miembro 5: %un", &var1.miembro4, &var1.miembro5);
}

Resultados


Dirección de miembro 1: 3219667864 	 Dirección de miembro 2: 3219667868 	 Dirección de miembro 3: 3219667872
Dirección de miembro 4: 3219667876 	 Dirección de miembro 5: 3219667906

Explicación: Las direcciones utilizadas por una estructura son continuas. En este caso tomo una dirección especifica 3219667864 para el comienzo de la misma, la dirección del primer miembro. Como los ints en mi implementación de C en Ubuntu tienen como tamaño 4 bytes, el segundo, tercer y cuarto miembro tienen las direcciones 3219667868, 3219667872, 3219667876 respectivamente. Como el cuarto miembro es un array de chars y los chars tiene tamaño de 1 byte, el quinto miembro tiene dirección 30 bytes luego del cuarto en 3219667906.

Referencias

The C Programming Language, Segunda Edición; Kernighan, Ritchie; Prentice Hall Hispanoamerica, 1991

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

Autor: Emiliano Martínez Luque.

Comments Off on Resumen de Sintaxis de Estructuras en C

Resumen de sintaxis de Punteros en C

Icono de Post October 15 2008 :: Apuntes, c ::

Copiado directamente de K & R.


	int x = 1, y = 2, z[10];
	int *ip; /* ip es un puntero a int */

	//Se usa &var para referenciar a la dirección de la variable a la que se quiere apuntar
	ip = &x; /* ip apunta a x */

	//Se usa *puntero para referenciar el valor de la dirección a la que apunta el puntero
	y = *ip; /* y es ahora 1 ( el valor de x) */

	*ip = 0; /* x es ahora 0 */

	ip = &z[0]; /* ip ahora apunta a z[0] */

Un ejemplo de una función que toma punteros como parámetros


void swap( int *px, int *py) {
	int temp;

	temp = *px;

	*px = *py;

	*py = temp;
}

Llamando a la función y pasando los valores por referencia


	swap(&x, &y);

	printf("n");
	printf("%d %dn", x, y);
	//Imprime 1, 0

Que pasa si imprimo un puntero directamente sin usar * ?


....
test1(&x, &y);
....

void test1( int *px, int *py) {
	//Imprime 1 0
	printf("%d %dn", *px, *py);
	//Imprime la dirección de x y casteada a Int
	printf("%d %dn", px, py);
}

Arreglos, Punteros y aritmética de punteros


#include 

int main() {
	int a[10], x;
	int *pa;
	//Relleno el array a con [0-9]
	for( x=0; x<10; x++ ) {
		a[x] = x;
		printf("%dn", a[x]);
	}

	pa = &a[0];
	//pa es ahora un puntero que apunta a la primer dirección del arreglo

	printf("%d %dn", a[7], *(pa+7) );
	//Imprime 7 7.. porque luego de pa= &a[0], a[i] es igual a *(pa + i)
}

Punteros y funciones


//Toma como parámetro 2 punteros a char
int strlen( char *s, char *t) {
	while((*s++ = *t++) != '');
}
....

//Función que devuelve un apuntador a int
int *f();

Referencias

The C Programming Language, Segunda Edición; Kernighan, Ritchie; Prentice Hall Hispanoamerica, 1991

Autor: Emiliano Martínez Luque.

Comments Off on Resumen de sintaxis de Punteros en C

Operadores Bitwise ( a nivel del Bit ) en C

Icono de Post September 12 2008 :: Apuntes, c ::

Una de las cosas nuevas que aprendí en los primeros capítulos de K & R, es la explicación de operaciones Bitwise. Lo cierto es que si bien sabia que existían como nunca había tenido la necesidad de utilizarlas, nunca les preste atención. Este es un pequeño resumen por si las necesito a futuro.

Operaciones & , | , ~ y ^

& ( conjunción Lógica o multiplicación Booleana a nivel del bit )
Sean a, b dos cadenas de bits del mismo tamaño ( por ejemplo integer ). La operación a & b realiza una operación de Conjunción Lógica sobre cada uno de los bits de ambas cadenas, devolviendo una nueva cadena de bits de tamaño equivalente a a,b con un 1 en la posición donde tanto a como b tenian un 1 y un 0 en cualquier otro caso. Ej:

a     = 10010101 
b     = 00110100
a & b = 00010100
| ( disyunción Lógica o suma Booleana a nivel del bit )
La operación a | b devuelve un 1 en la posición donde a o b ( o ambos ) tienen un 1 y un 0 cuando ambas tienen cero. Ej:

a     = 10010101 
b     = 00110100
a | b = 10110101
~ ( negación Lógica a nivel del bit )
Sea a una cadena de bits. La operación ~a invierte los 1s y 0s de a. Ej:


a  = 10010101 
~a = 01101010
^ ( Disyunción exclusiva Lógica a nivel del bit )
La operación a ^ b devuelve un 1 en la posición donde a o b ( pero no ambos ) tienen un 1 y un 0 cuando ambas tienen 0 o ambas tienen 1. Ej:

a     = 10010101 
b     = 00110100
a ^ b = 10100001

Operaciones << y >>

Operación <<
Sea a una cadena de bits, n un entero, a << n, devuelve la misma cádena movida n bits a la izquierda ( perdiendose los primeros n bits de la cadena ) y reemplazando las n posiciones a la derecha por 0. Ej:

a      = 10010101 
a << 2 = 01010100
Operación >>
Sea a una cadena de bits, n un entero, a >> n, devuelve la misma cadena movida n bits a la derecha ( perdiéndose los últimos n bits de la cadena ) y reemplazando las n posiciones a la izquierda por 0. Ej:

a      = 10010101 
a >> 3 = 00010010

Algunos Usos y Ejemplos

Multiplicación por 2n

Por propiedades de los números binarios, se cumple que agregando n 0s a la derecha es equivalente a multiplicar este mismo número por 2n. Ej:


int function multiplicar_por_exponente_de_2( int a, int power ) {
	return a << power;
}

Nota: Hay que cuidar el overflow de los datos considerando el tamaño de ints en nuestro sistema. Pero este no es un post sobre implementaciones de C.

Cociente de dividir por 2n


int function cociente_de_exponente_de_2( int a, int power ) {
	return a >> power;
}

Nota: Desde ya que esta función devuelve el cociente pero no el resto.

Cociente y resto de dividir por 2n


unsigned int a, cociente, resto;
a = 757;
cociente = a >> 3;
resto =  (~((~0) << 3)) & a

Nota: ~0 devuelve un int del tamaño del sistema con todos sus bits pasados a 1, al moverlo 3 posiciones a la izquierda se tiene todos 1s salvo los 3 últimos bits, al negar esto se obtiene todos 0s salvo los 3 últimos bits que nos sirven para obtener los valores que son el resto de la división.

Representación en cadena binaria de un número


void show_as_binary( int a, char str[]) {
	int x, size;
	size = (int)sizeof(b) * 8;
	for(x=0; x<size; x++) {

		//This is necesary for a%2 might return -1 if a < 0. 
		str[x] = '0' + ((a%2) < 0 ? 1: (a%2) );
		a = a >> 1;
	}
	reverse(str);
}

Representación en Octal de un número


void show_as_octal( int a, char str[]) {
	int x, size;
	size = (int)sizeof(b) * 8;
	for(x=0; x<size && a!=0; x++) {
		str[ x ] = '0' + (a%8);
		a = a >> 3;
	}
	str[ x ] = '0';
	reverse(str, (x+1));	

} 

Uso de un int para múltiples flags

Es una práctica común en Unix usar ints para pasar múltiples flags a funciones. Supongamos que necesito 4 flags distintos para una función o para lo que sea. Lo que puedo hacer es lo siguiente:


#define FLAG_A 1;
#define FLAG_B 2;
#define FLAG_C 4;
#define FLAG_D 8;

//Llamar a la función con FLAG_A y FLAG_D
call_function( FLAG_A | FLAG_D );

//Comparar si una variable tiene FLAG_B seteado
if( ( a & FLAG_B ) == FLAG_B ) { ...

//Comparar si una variable no tiene FLAG_C seteado
if( ( ( a | FLAG_C ) != a ) { ... 

Lo interesante de esto es que al abstraernos de los ints y pensarlos como cadenas de bits, se pueden hacer operaciones de algebra de boole, donde cada bit toma un valor verdadero o falso, que nos sirve para evaluar colecciones de flags como colecciones de proposiciones booleanas. Ahorrándonos así de pasar un valor como argumento a la función para cada una. Ej:


//Comparar contra FLAG_A, FLAG_B y no FLAG_D
if ( ( ( a & (FLAG_A | FLAG_B) ) == ( FLAG_A | FLAG_B ) ) && ( ( a | FLAG_D ) != a ) ) { ...

Un ejemplo concreto es el uso de los permisos de archivos en linux.

chmod toma un valor en octal que puede representarse así:



0012 = 18 = x

0102 = 28 = w

1002 = 48 = r

De donde surgen sus relativas combinaciones, por ej:



0112 = 38 = wx

1102 = 68 = rw

1112 = 78 = rwx

Bonús. Ejercicios 2.6, 2.7 y 2.8 de K & R

Ej 2.6

Escriba una función setbits( x,p,n,y ) que regresa x con los n bits que principian en la posición p iguales a los n bits más a la derecha de y, dejando los otros bits sin cambio.


//Ej 2.6
unsigned setbits(unsigned x, int p, int n, int y) {
	unsigned t, z;
	if(y < n) { 
		perror("Error");
	} else {
		//All 0s except for the space that starts at y and has size n
		t = ~(~0<<n)<<(y-n);
		//Get the value of x in this position
		t = x & t;
		//move the distance that p has from y
		t = t << (p-y);
		//Set that same space to 0s in x, starting on p and with size n
		z = ~(~0<<n)<<(p-n);		
		x = x & (~ z);
		//merge them
		t = x | t;
	}
	return t;
}

Ej 2.7

Escriba una función invert( x,p,n ) que regresa x con los n bits que principian en la posición p invertidos, dejando los otros sin cambio.


//Ej 2.7
unsigned invert(unsigned x, int p, int n) {
	unsigned t, z;
	//All 0s except for the space that starts at p and has size n
	t = ~(~0<<n)<<(p-n);
	//Get the inverted value of x in this position
	z = (~x & t);
	//merge them (first clean up x in the space that starts at p and has size n then merge with z)
	t = (~t & x) | z;
	return t;
}

Ej 2.8

Escriba una función rightrot( x,n ) que regresa x rotado a la derecha n posiciones de bits.


//Ej 2.8
unsigned rightrot( unsigned a, int n) {
	unsigned t, mascara, x;
	t = 0;
	mascara = 1;
	for(x=0; x<n; x++) {
		t = t << 1;
		t = t | (mascara & a);
		a = a >> 1;
	}
	return t;
}

Autor: Emiliano Martínez Luque.

Comments Off on Operadores Bitwise ( a nivel del Bit ) en C

Teoría de Conjuntos ( Definiciones y Formulas Básicas )

Icono de Post September 10 2008 :: Apuntes, Teoría de Conjuntos ::

Definiciones

Conjunto: Colección de Objetos. A, B, C..
Elemento: Objeto dentro de un conjunto. a, b, c.
Representación por extensión.
A = {a, b, c, d}
Representación por comprensión.
A = {x | x < 10 ∧ x > -100}
A = {x | Φ(x) }
∈ pertenece a, es elemento de

∪ Union
A ∪ B = {x | x ∈ A ∨ x ∈ B}
∩ Intersección
A ∩ B = {x | x ∈ A ∧ x ∈ B}
Ac Complemento
Ac = {x | x ∉ A}

Equivalencias Basicas

Doble negación
A = (Ac)c

Idempotencia
A ∪ A = A
A ∩ A = A

De morgan
(A ∪ B)c = (Ac ∪ Bc)
(A ∩ B)c = (Ac ∩ Bc)

Conmutativa
(A ∪ B) = (B ∪ A)
(A ∩ B) = (B ∩ A)

Asociativa
(A ∪ B) ∪ C = A ∪ (B ∪ C)
(A ∩ B) ∩ C = A ∩ (B ∩ C)

Distributiva
A ∩ (B ∪ C) = (A ∪ B) ∩ (A ∪ C)
A ∪ (B ∩ C) = (A ∩ B) ∪ (A ∩ C)

Absorción
A ∩ (A ∪ B) = A
A ∪ (A ∩ B) = A

Universo, Conjunto Vacio

U Universo
∅ Conjunto Vacio

c = U
Uc = ∅

Dominancia
U ∪ A = U
∅ ∩ A = ∅

Identidad
U ∩ A = A
∅ ∪ A = A

Ley del medio excluido
A ∪ Ac = U

Contradicción
A ∩ Ac = ∅

Inclusión, Inclusión estricta, Equivalencia, Resta, Diferencia simetrica

Definiciones

⊆ Inclusión
A ⊆ B = {x | x ∈ A => x ∈ B}
⊂ Inclusión Estricta
A ⊂ B <=> ∀x (x ∈ A => x ∈ B) ∧ ∃y (y ∈ B ∧ y ∉ A)
= Equivalencia
A = B <=> A ⊆ B ∧ B ⊆ A
– Resta
A – B = {x | x ∈ A ∧ x ∉ B}
Δ Diferencia Simetrica
A Δ B = {x | x ∈ A ∨ x ∈ B ∧ ¬ (x ∈ A ∧ x ∈ B) } = A ∪ B -(A ∩ B)

A, B son Disjuntos <=> A ∩ B = ∅

Ac = U – A

Conjunto de Partes y Familias de Conjuntos

Definiciónes

P(A) Conjunto de Partes
X ∈ P(A) <=> X ⊆ A
P(A) = {X | X ⊆ A}

Nota: ∀A( {∅} ∈ P(A) )

F, G Se usan para representar Familias de Conjuntos o o Colecciones de Conjuntos
∪F = ∀x ( ∃y ( y ∈ F ∧ x ∈ y ) )
∩F = ∀x ( ∀y ( y ∈ F -> x ∈ y ) )

Referencias

The Haskell Road To Logic, Math and Programming; Doets, Van Eijck; King´s College London Publications; 2004

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

Autor: Emiliano Martínez Luque.

Comments Off on Teoría de Conjuntos ( Definiciones y Formulas Básicas )

Alfabetos, Lenguajes y Gramáticas (Definiciones Básicas)

Icono de Post September 6 2008 :: Apuntes, Lenguajes Formales ::

Alfabetos

Σ : alfabeto, Conjunto finito, no vacio de símbolos.

Cadena: sucesión de símbolos concatenados.

Σ1 = Σ

Σn+1 = { xy / x ∈ Σ, y ∈ Σn } ; donde x, y son cadenas formadas por símbolos de Σ.
Aclaración: en este caso x representa una cadena formada por un solo símbolo de Σ.

Ejs:
Σ = {a,b,c} => Σ2 = {aa, ab, ac, ba, bb, bc, ca, cb, cc }
aab ∈ Σ
3

Cardinalidad de un Alfabeto

| Σ | = 3  => | Σ2| = 32

Generalizando:

| Σ | = t  => | Σn| = tn

Cadena Vacia

λ: Cadena o palabra vacia. Elemento neutro para la concatenación de cadenas.

Importante: ∀Σ:  Σ0= { λ }

Conjunto infinito de todas las cadenas que pueden formarse con un alfabeto

Σ* = n = 0 Σ n   
| Σ | = ∞

Cadenas y Concatenación

Se puede definir una cadena W sobre el alfabeto Σ como: W = x1x2…..xn ; xi ∈ Σ

Longitud de una cadena

|| w || = n

Concatenación

Sean:
X = x1x2…..xn ; xi ∈ Σ
Y = y
1y2…..ym ; yi ∈ Σ
=>
XY = x
1x2…..xny1y2…..ym; ∧ XY ∈ Σn + m

Propiedades de la Concatenación

1. Cerrada sobre si misma (Ley de Composición Interna)
Σ* -> Σ* : Σ*

2. Asociativa
X(YZ) = (XY)Z

3. No Conmutativa
XY ≠ YX

Longitud de una Concatenación

|| XY || = || X || + || Y ||; ∀ X, Y ∈ Σ*

Potencias de una cadena

∀ X ∈ Σ*:
X
0 = λ
X
1 = X
X
2 = XX
X
n = XXn – 1
|| X
n|| = n . || X ||

Prefijos, Sufijos

sea W ∈ Σ* ∧ W = XY entonces X es prefijo de W, Y es sufijo de W.
Si adémas:
Y ≠ λ => X es prefijo propio de W
X ≠ λ => Y es prefijo propio de W  

Subcadenas

sea W ∈ Σ* ∧ W = XZY entonces Z es subcadena de W.

Lenguajes

Sea Σ ≠ φ, L ⊆ Σ* es un lenguaje sobre Σ

Importante: φ ⊂ Σ . φ es un lenguaje, llamado lenguaje Vacio.

Gramática

G = (V, T, S, P) es una gramática donde:
V  es un Alfabeto
T ⊂ V, son los elementos terminales
S ⊂ V, es el Start Symbol. O Simbolo de Comienzo.
P, son las reglas de Producción.

Lenguaje generado por una gramática

Todas las cadenas de elementos pertenecientes a T, que pueden formarse a partir de las reglas de Producción P. Se lo suele representar com L( G ) .

Ejemplos

1) L = { 1111n0n / n ∈ N}. Lenguaje formado por todas las cadenas con prefijo 111 y luego una suseción de 10.


G = ( V,T,S0,P )
V = {1,0,S}
T = {1,0}
S
0 = S
P:
S -> S10

S -> 111S

2) L = Lenguaje formado por todas las cadenas con prefijo 111 y luego  al menos un 1 o un 0 y luego una sucesión de 1s y 0s en cualquier orden. = {1110, 1111, 11101, 11100, 11110, 11111, …. }

G = ( V,T,S0,P )
V = {1,0,S,A,B}
T = {1,0}
S
0 = S
P:

AB -> BA
BA -> AB
A -> 0
B -> 1
S -> SA
S -> SB
S -> 111S

3) L = Lenguaje que tiene la misma cantidad de 0s y 1s. = { λ, 01, 10, 0011, 0110, 1100, 0101, 1010, …. }

G = ( V,T,S0,P )
V = {1,0,S, A, B}
T = {1,0}
S
0 = S
P:

AB -> BA
BA -> AB
A -> 0
B -> 1
S -> SAB
S -> λ

Referencias

Apuntes de Clase de Algebra y Matemática Discreta cursada en el segundo cuatrimestre de 2007 en la Universidad de Palermo dictada por Marcela Wilder.
Algebra Y Matenática Discreta, Gabriela Esperón, Marcela Wilder, UP, 2007.

Autor: Emiliano Martínez Luque.

Comments Off on Alfabetos, Lenguajes y Gramáticas (Definiciones Básicas)

1er Parcial de Sistemas Operativos

Icono de Post May 10 2008 :: Apuntes ::

Ayer dí el primer parcial de Sistemas Operativos. Además de estudiar los primeros 3 capítulos de Sistemas Operativos Modernos de Tanenbaum, que trata muy bien la teoría. Para la práctica y para afianzar conceptos, me sirvieron los siguientes apuntes:

Semaforos

Un muy buen apunte sobre Semáforos es el de Salvador Sánchez-Alonso de la Universidad de Alcala que se puede encontrar acá

Procesos, Threads y Calendarización de Procesos

Un muy buen resumén de Procesos y Threads de la página de Cristofer Reyes
de la Universidad Técnica Federico Santa María

Y un excelente resumén de Calendarización de Procesos lo encontre en la página de Maribel Castillo Catalán de la Universidad Jaume I

Autor: Emiliano Martínez Luque.

Comments Off on 1er Parcial de Sistemas Operativos