Bloque de Colores

Algunas demostraciones simples cuya estructura me llamo la atención

Icono de Post May 23 2008 :: Algebra, Lógica ::

Demostrar que si a es par <=> a2 es par

Como es doble implicación tengo que demostrar: 1) a es par => a2 es par ∧  2) a2 es par => a es par

1) a es par => a2 es par

a es par => a = 2k; k ∈ Z => a2 = ( 2k )2 => a2 = 4k2 => a2 = 2( 2k2 )
Como ( 2k2 ) ∈ Z => a2 es par.

2) a2 es par => a es par

Para esta parte de la demostración se usa el contrareciproco. ( p => q ≡ ¬q => ¬p )

a2 es par => a es par ≡ a es impar => a2 es impar

a es impar => a = 2k +1; k ∈ Z => a2 = ( 2k+ 1 )2 => a2 = 4k2 + 4k + 1 => a2 = 2( 2k2 + 2k ) + 1
Como ( 2k2 + 2k ) ∈ Z => a2 es impar y la proposición queda demostrada.

Demostrar que el producto de 2 números consecutivos es par.

El producto de dos números consecutivos puede escribirse como a.( a+1 ). La demostración es por exhaustación de casos.

1) Supongamos que a es par

a es par => a = 2k; k ∈ Z => a. ( a + 1) = 2k . ( 2k + 1)
Como k . ( 2k  + 1 ) ∈ Z => a. ( a + 1)  es par.

2) Supongamos que a es impar

a es impar => a = 2k + 1; k ∈ Z => a. ( a + 1) => 2k + 1. ( 2k + 1 + 1) = 2k +1 . ( 2k + 2 ) = ( 2k + 1) . 2 (k + 1) = 2 ( 2k + 1) . (k + 1)
Como ( 2k + 1) . (k + 1) ∈ Z => a. ( a + 1)  es par.

Demostrar que si p es primo y p / a.b => p/a ∨ p/b

Es una implicación que tiene una disyunción en la conclusión.

Supongamos que p/a, entonces listo no queda nada que demostrar.

Ahora si ¬(p/a) => p y a son coprimos o sea que ( p ; a ) = 1 => ∃ n; s ∈ Z / p.n + a.s = 1

Como p/a.b => a.b = pk; k ∈ Z
Tomamos:
p.n + a.s = 1

Multiplicamos ambos terminos por b:
b.p.n + a.b.s = b

Sustituimos a.b por p.k:
b.p.n + p.k.b.s = b

Despejamos p:
p (bn + kbs) = b

Como (bn + kbs) ∈ Z, queda demostrado que p/b y por exhaustación de casos queda demostrado que si p es primo y p / a.b => p/a ∨ p/b .

Referencias

Apuntes de Clase de Algebra y Matemática Discreta cursada con Marcela Wilder en ella Universidad de Palermo, el segundo cuatrimestre de 2007

Autor: Emiliano Martínez Luque.

Comments Off on Algunas demostraciones simples cuya estructura me llamo la atención

Probabilidad – Formulas Básicas

Icono de Post May 14 2008 :: Estadística, Probabilidad ::

Definiciones Básicas

Experimento Aleatorio: Experimento cuyo resultado no puede predecirse con exactitud.

S: Espacio Muestral: Conjunto de todos los resultados posibles de un experimento aleatorio.

EJ: Experimento: arrojar 2 veces una moneda de 2 caras

E = {(c,c), (c,s), (s,c), (c,c)}

Punto Muestral: cada uno de los resultados posibles de un experimento aleatorio.

Suceso o Evento: subconjunto de puntos del espacio muestral.

Suceso Imposible o nulo: no ocurrirá con total seguridad.

Probabilidad de Laplace

Es a priori, no experimental.

Si un experimento admite N resultados posibles, todos ellos equiprobables entonces:

P(A) = F N = Casos Favorables Casos Posibles

Desventajas:

  • Resultados pueden no ser equiprobables
  • Numero de casos debe ser finito
  • No siempre se conocen los casos favorables

Probabilidad de Von Misses o de la Probabilidad Frecuencial

Es a posteriori, luego de un experimento.

EJ: Se toma un dado cargado y buscamos la probabilidad de que salga el número 2. Se realiza el experimento un número n de veces y observamos la cantidad de resultados favorables fr (Frecuencia absoluta del suceso).

f r = f i n = número de exitos número de pruebas

Ley de los grandes números o convergencia estocástica de las frecuencias relativas

Al aumentar las pruebas las frecuencias relativas tenderán a estabilizarse alrededor de un determinado valor.

P(A) = lim n f r = lim n f a n

Clasificación de Sucesos

Sucesos mutuamente excluyentes: La ocurrencia de uno impide la ocurrencia del otro.
P(A ∩ B) = 0
Sucesos no excluyentes o conjuntos: pueden ocurrir simultaneamente.
P(A ∩ B) != 0
Sucesos exhaustivos: Su unión es equivalente a S
P(A) + P(B) + … = P(S) = 1
A ∪ B ∪ … =

Definición Axiomatica de Probabilidad

Sean:
S espacio muestral
E un experimento aleatorio
A un suceso ∈ S en E

entonces P(A) es una función del tipo P(A): A -> (0,1)

Caracteristicas

0 <= P(A) <= 1
P(S) = 1
Sean A, B dos sucesos mutuamente excluyentes => P(A ∪ B) = P(A) + P(B)

Teorema de la suma de Probabilidades

P( A ∪ B ) = P(A) + P(B) – P(A ∩ B) = 1 – P( A _ B _ )
NOTA: Pensar en Cardinalidad de conjuntos cuando se piensa P( A ∪ B).
Nota: ∪ puede pensarse en este caso como ⊻ y ∩ como ∧, si se utiliza la notación P(A o B) = P(A) + P(B) – P(A y B)

EJ: Probabilidad de sacar una carta de un maso que sea o un 4 o un oro = P(4) + P(oro) – P(4 de oros)

P( A ∪ B ∪ C) = P(A) + P(B) + P(C) – P(A ∩ B) – P(A ∩ C) – P(B ∩ C) + P(A ∩ B ∩ C)

Teorema del Producto de Probabilidades

Sea S un espacio muestral y A,B dos sucesos pertenecientes a S. La probabilidad de que ocurran A y B simultanea o sucesivamente en 2 REPETICIONES de un experimento es.

P(A ∩ B) = P(A) . P(B/A) = P(B) . P(B/A)

Probabilidad condicional: P(A/B) = Probabilidad de que ocurra A dado la ocurrencia previa (o simultanea) de B

P(A/B) = P ( A B ) ) P ( B )

EJ: Se tira un dado 2 veces,

a) cual es la probabilidad de que la suma sea 8.

Evento(suma 8 ) = {(2,6), (3,5), (4,4), (5,3), (6,2)} = 5 posibilidades.

Total de combinacines de 2 dados = 62= 36

P(suma 8 ) = 5 36

Hasta aqui nos manejamos con los conceptos de Laplace.

b) Cuál es la probabilidad de que si la suma dio 8 que el primer resultado haya sido 3?

A ojo se puede ver que solamente una (3,5).

P(3 en la primer tirada) = 1 5

Pero lo vamos a hacer correctamente:

Evento(suma 8 ) = {(2,6), (3,5), (4,4), (5,3), (6,2)}
Evento(primer resultado fue 3) = {(3,1), (3,2), (3,3), (3,4), (3,5), (3,6) }
E(suma 8 ) ∩ E(primer 3) = {(3,5)}

Para sucesos independientes

Si los sucesos son independientes, la formula se reduce a:

P(A ∩ B) = P(A) . P(B)

Diagramas de Carol

A A _ TOTAL
BA ∩ B A _ ∩ BB
B _ A ∩ B _ A _ B _ B _
TOTALA A _

EJ: Sea A y B dos eventos sobre un expacio muestral con los siguientes valores

A A _ TOTAL
B101838
B _ 30342362
TOTAL40360400

P(A) = 40/400 = 1/10

P(B/A) = 10/40 = 1/4
desarrollando la formula
P(B/A) = P ( A B ) P ( A ) = 10 400 40 400 = 1/4

P(A ∩ B) = P(A) . P(B/A) = 40 400 . 10 40 = 10 400 = 1/40

Nota: los valores surgen directamente de la tabla.

Muestras sin reposición

Supongamos un conjunto U de tamaño 50. Este esta dividido en 2 subconjuntos mutuamente excluyentes y exhaustivos sobre U que llamaremos A y B, La cardinalidad de A=10 y la de B=40. O lo que es lo mismo sea E el evento de seleccionar un elemento de U => P(A) = 1/5 y P(B) = 4/5 tal que P(S) = P(A) + P(B) = 1.

Consideraremos ahora una serie de eventos: E1, E2 , E3, E en el que en cada evento se toma un elemento de U pero no se lo repone. De esta manera la cardinalidad de U decrece en 1 por cada evento realizado y se modifica el espacio muestral y tambien se modifican luego de cada evento P(A) y P(B).

Por ejemplo: supongamos que E1toma un elemento de A entonces Para E2: P(A) 9/49 y P(B) = 40/49

que posibilidad hay de que el proximo evento E2sea de nuevo A. En simbolos:

P(E2 / E1) = 10 50 . 9 49

P(ABBA) = 10 50 . 40 49 . 39 48 . 9 47

Teorema de la Probabilidad Total

Sea un espacio muestral S dividido en 2 sucesos A1 y A2 tal que: P(A1 ∩ A2) = 0 (Son mutuamente excluyentes), P ( A i ) = 1 ( forman un sistema exhaustivo ) .

Conjuntamente sobre S puede darse un suceso D conjuntamente con A1 o A2. Es evidente que P(A1 ∩ D) y P(A2 ∩ D) son mutuamente excluyentes.

P(D) = P ( A i ) . P( D / Ai)

Ej: A,B,C forman un sistema exhaustivo sobre el espacio muestra S y son mutuamente excluyentes.

P(A)=45%, P(B)=32%, P(C)=23%

Para A, D=4%, para B, D=6% y para C, D=2,5%

P(D) = P(A) . P(D/A) + P(B) . P(D/B) + P(C) . P(D/C)

P(D) = 0.45 x 0.04 + 0.32 x 0.06 + 0.23 x 2.5 = 0.043 o 0.43%

Nota: Se puede plantear con arboles

Teorema de Bayes o Teorema de la probabilidad de las causas

Sean Aisucesos excluyentes y exhaustivos, D un suceso tal que P(D) > 0 y se conocen P(D/Ai) y P(Ai).

P(Ak/D) = P ( A k D ) P ( D ) = P ( A k ) . P ( D / A k ) i P ( A i ) . P ( D / A i )

Esperanza Matematica

En una distribución de probabilidades del tipo:

Xi P( Xi )
0 P( 0 )
1 P( 1 )
2 P( 2 )
…..…….
TOTAL1 o 100%

Donde la sumatoria de todas las P( X i ) = 1 o 100%.
Se define la esperanza matematica como:

E = X i P ( X i )

Referencias

Apuntes de clase de Estadí­stica 1, Conceptos Teóricos y Ejemplos. M. Cattaneo, S. Diez, Universidad de Palermo, 2007.

Haskell: Sintaxis Básica

Icono de Post May 10 2008 :: Haskell, Programación Funcional ::

Tipos y Funciones

:t Muestra el tipo de datos

Las funciones son tipos de datos (pensar en definición matematica)


mas2 a = a+2

:t mas2
mas2 :: (Num a) => a -> a

Debe leerse como si a es numérico, entonces, mas2 es una función de a en a. Pensar en f: A -> A

Para forzar un tipo, lo declaro al principio:


multiploDe2 :: Int -> Bool
multiploDe2 a = rem a 2 == 0

Funciones con mas de una variable.


multiplo :: (Integral a) => a -> a ->
Boolmultiplo a b = rem a b == 0

Para comprender mejor:


:t multiplo 10
multiplo 10 :: (Integral t) => t -> Bool

(O sea que al llenar la primer variable se retorna una función de el tipo de la segunda variable al tipo de retorno.)

Sintaxis de Funciones

Función definida en diferentes casos:


fibonacci :: Int -> Int
fibonacci a		| a < 1				= error "Indefinida para ese valor"
			| a == 1 || a == 2 		= 1
			| otherwise			= fibonacci (a-1) + fibonacci (a-2)

Otra forma es:


prefix :: String -> String -> Bool
prefix [] ys			= True
prefix (x:xs) []		= False
prefix   (x:xs) (y:ys)		= (x==y) && prefix xs ys

O una combinación


substring :: String -> String -> Bool
substring xs []	= False
substring xs (y:ys)		| prefix xs (y:ys) = True
				| otherwise = substring xs ys

Construcción de Conjuntos a partir de listas

Un ejemplo, el conjunto de los pares. x = 2k; k ∈ N


pares = map (*2) [1..]

Otro ejemplo Primos y compuestos (del libro)


prime :: Integer -> Bool
prime n			| n < 1		= error "not positive integer"
			| n == 1		= False
			| otherwise		= ldp n == n

ldp :: Integer -> Integer
ldp = ldpf primes

ldpf :: [Integer] -> Integer -> Integer
ldpf (p:ps) n				| rem n p == 0			= p
					| p^2 > n 			= n
					| otherwise			= ldpf ps n

primes :: [Integer]
primes = 2 : filter prime [3..]

composite :: Integer -> Bool
composite n = not (prime n)

composites :: [Integer]
composites = 4 : filter composite [5..]

Operadores Infix


(-) 5 3 ≡ 5 - 3
rem 10 3 ≡ 10 `rem` 3

Definición de un operador Infix ( “|” y “/” ya están definidos en prelude por eso use “//” )


divide :: Int -> Int -> Bool
divide a b = rem b a == 0

infix 1 //
(//) :: Int -> Int -> Bool
a // b = divide a b

Funciones auxiliares dentro de funciones


solveQdr :: Float -> Float -> Float -> (Float, Float)
solveQdr a b c		| a == 0		= error "No es Quadratica"
			| d<0			= error "No hay solucion en los Reales"
			| otherwise 		= ( (-b + sqrt d ) / 2*a, (-b - sqrt d ) / 2*a)
					where d = (b^2)-(4*a*c)

Otra opcion (let … in)


solveQdr :: Float -> Float -> Float -> (Float, Float)
solveQdr a b c     = if a == 0 then error "No es Quadratica"
          else let d = b^2 - 4*a*c in
		  if d<0 then error "No hay solucion en los reales"
		  else ( (-b + sqrt d ) / 2*a, (-b - sqrt d ) / 2*a)

Expresiones Lambda

Uso Básico


por2 :: Integer -> Integer
por2 = ( x -> x*2 )
(x -> x+1) 8
9

Pasaje de una expresión Lambda como parámetro a una función (es como pasar una función)


infix 1 ==>
(==>) :: Bool -> Bool -> Bool
True ==> x = x;
False ==> x = True;

infix 1 <=>
(<=>) :: Bool -> Bool -> Bool
x <=> y = x == y
infixr 2 <+>
(<+>) :: Bool -> Bool -> Bool
x <+> y = x /= y

{- Equivalencias logicas -}
logEquiv1 :: (Bool -> Bool) -> (Bool -> Bool) -> Bool
logEquiv1 bf1 bf2 = (bf1 True <=> bf2 True) && (bf1 False <=> bf2 False)

logEquiv2 :: (Bool -> Bool -> Bool) -> (Bool -> Bool -> Bool) -> Bool
logEquiv2 bf1 bf2 = and [(bf1 p q <=> bf2 p q) |    p <- [True, False],
                            q <- [True, False]]

logEquiv3 :: (Bool -> Bool -> Bool -> Bool) -> (Bool -> Bool -> Bool -> Bool) -> Bool
logEquiv3 bf1 bf2 = and [(bf1 p q r <=> bf2 p q r) |    p <- [True, False],
                            q <- [True, False],
                            r <- [True, False]]

{- Idempotencia -}
logEquiv1 (p -> p) (p -> p || p)
True

{- Doble Negación -}
logEquiv1 (p -> p)  (p -> not (not p))
True

{- De Morgan -}
logEquiv2 (p q -> not (p && q)) (p q -> not p || not q)
True

{- Contrareciproco -}
logEquiv2 (p q -> p ==> q) (p q -> not q ==> not p)
True

{- Distributiva -}
logEquiv3 (p q r -> (p || q) && r) (p q r -> (p && r) || (q && r))
True

Expresiones mas complejas


every , some :: [a] -> (a -> Bool) -> Bool
every xs p = all p xs
some xs p = any p xs

(x -> some [1,2,3] (y -> x==y^2)) {-  Verifica si un numero es el cuadrado de 1, 2 o 3 -}
(x -> some [1,2,3] (y -> x==y^2)) 4
True

:t (x -> some [1,2,3] (y -> x==y^2))
(x -> some [1,2,3] (y -> x==y^2)) :: (Num a) => a -> Bool

every [1,4,9] (x -> some [1,2,3] (y -> x==y^2))
True

List comprehension, And, Or


{- valid 3 por List comprehension -}
valid3 :: (Bool -> Bool -> Bool -> Bool) -> Bool
valid3 bf = and [ bf p q r |    p <- [True, False],
                q <- [True, False],
                r <- [True, False] ]
{- and es Conjuncion generalizada sobre una lista (Retorna True si todos son True),
p <- Es List Comprehension

:t and
and :: [Bool] -> Bool

Existe tambien or que es Disyunción generalizada sobre la lista. (Retorna True si al menos uno es True)
-}

Otra forma.


[ x | x <- [1..10], prime (x+5)]
[2,6,8]

Composición de Funciones


por3 :: Int -> Int
por3 x = x*3

divisiblePor2 :: Int -> Bool
divisiblePor2 x = rem x  2 == 0

:t (divisiblePor2 . por3)
(divisiblePor2 . por3) :: Int -> Bool

(divisiblePor2 . por3) 4
True

(divisiblePor2 . por3) 5
False

Referencias

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

Autor: Emiliano Martínez Luque.

Comments Off on Haskell: Sintaxis Básica

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

Walk don´t run

Icono de Post May 4 2008 :: Uncategorized ::

Mi nuevo blog de apuntes y machetes y proyectos de CS. Pero esta vez en cristiano, coÑo. Que el otro es de trabajo y este es por deporte.

Y como esto da para rato… empiezo con un video emblematico que es la guía espiritual de este blog.

Un beso para todos los que no me conocen.