Curso Informtica III 2016
EJERCICIOS RESUELTOS
UNIDAD I
1) Utilizando el Principio de Induccin Matemtica (PIM), demuestre que la
suma de los cubos de los n primeros nmeros naturales es igual al
cuadrado de la suma de ellos.
Solucin:
Se vuelve a enunciar el problema de la siguiente manera:
Demuestre que
n
nN; i i
i 0
i 0
n
En el presente captulo se demostr por PIM que:
nN;
i
i 0
n(n 1) ,
2
entonces, al utilizar esto para rescribir el enunciado:
nN;
n 2 (n 1) 2
n(n 1)
3
,
i
4
2
i 0
n
y ahora se procede a demostrar por induccin matemtica:
I.
Caso Base: para n = 0, se verifica:
0 2 (0 1) 2
0
i 0 0
4
i 0
Por lo tanto, la frmula se cumple en el caso base.
0
II.
Se define la hiptesis inductiva y la tesis:
k 2 (k 1) 2
4
i 0
2
2
K 1
Tesis: i 3 (k 1) (k 2)
4
i 0
K
H.I.:
Al utilizar la H.I. y propiedades de sumatorias:
K 1
i i
3
i 0
i 0
K 1
i K 1
k 2 (k 1) 2
k 2 (k 1) 2 4(k 1) 3
(k 1) 3
4
4
Curso Informtica III 2016
(k 1) 2 (k 2 4(k 1)) (k 1) 2 (k 2 4k 4) (k 1) 2 (k 2)
4
4
4
se cumple tambin la tesis y, por el PIM, la frmula es vlida para todos
los nmeros naturales
2) Usando PIM demuestre que n N:
n
i(i 2) 1* 3 2 * 4 3 * 5 ... n(n 2)
i 0
n(n 1)(2n 7)
6
Solucin:
i. Se verifica para n = 0 (caso base):
0
i (i + 2) = 0 (0 + 2) = 0 =
i 0
0(0 1)(2(0) 7)
=0
6
ii. Se formula la H.I. y la tesis:
Para algn k N,
H.I.:
i (i + 2) =
i 0
k 1
Tesis:
i (i + 2) =
i 0
k 1
i (i + 2) =
i 0
i(i 2)
i 0
k (k 1)(2k 7)
6
(k 1)((k 1) 1)(2(k 1) 7)
6
k 1
i(i 2)
por propiedad de sumatorias
i k 1
i (i + 2) + (k+1)((k+1)+2)
i 0
k (k 1)(2k 7) 6(k 1)((k 1) 2)
por H.I.
6
(k 1)[k (2k 7) 6((k 1) 2)]
=
6
2
(k 1)(2k 7k 6k 6 2)
=
6
2
(k 1)(2k 13k 8)
=
6
Curso Informtica III 2016
(k 1)(k 2)(2k 9)
6
(k 1)((k 1) 1)(2(k 1) 7)
=
6
Q.E.D.
3) Demuestre por PIM que n 1;
n
i(i!) (n 1)!1
i 1
Solucin:
Se procede a demostrar por induccin matemtica:
i.
Caso base: para n = 1, se verifica que:
1
i(i!) 1.(1)! 1
i 1
, y por otra parte, (1+1)! 1 = 2! 1 = 1
Por lo que la frmula se cumple para el caso base.
ii.
Caso inductivo:
Se plantea la hiptesis inductiva para el nmero k N, y se asume
verdadera:
k
H.I. :
i(i!) (k 1)!1
i 1
Se probar para el caso k + 1, es decir, se demostrar la tesis:
k 1
Tesis:
i(i!) ((k 1) 1)!1
i 1
Prueba:
k 1
k 1
i 1
i 1
i k 1
i(i!) i(i!) i(i!)
; por propiedad de sumatorias,
Curso Informtica III 2016
k
i(i!) (k 1)(k 1)!
i 1
(k 1)!1 (k 1)(k 1)! ; por sustitucin de la H.I.
(k 1)!1 (k 1) 1
; al factorizar (k+1)!
(k 2)(k 1)!1
(k 2)!1
; por la definicin recursiva de un
nmero factorial, n! = n x (n-1)!
(k 2)!1
((k 1) 1)!1
Se cumple tambin la tesis y, por el PIM, la frmula es vlida n 1.
4)
Demuestre por PIM que n N;
n
2 n 1 1
i 0
Solucin:
Se procede a demostrar por induccin matemtica:
i.
Caso base: para n = 0, se verifica que:
0
20 1
i 0
01
, y por otra parte, 2 1 1
Por lo que la frmula se cumple para el caso base.
iii.
Caso inductivo:
Se plantea la hiptesis inductiva para el nmero k N, y se asume
verdadera:
k
H.I. :
2 k 1 1
i 0
Se probar el caso para k + 1, es decir, deber demostrarse la tesis:
k 1
Tesis:
2 ( k 1)1 1
i 0
Curso Informtica III 2016
Prueba:
k 1
2 2
i
i 0
i 0
k 1
i k 1
2 ( k 1) 1 2 ( k 1)
; por propiedad de sumatorias
; por sustitucin de H.I.
2(2 ( k 1) ) 1
2 ( k 2) 1 2 ( k 1)1 1
Se cumple tambin la tesis y, por el PIM, la frmula es vlida n N.
5) Demuestre por PIM que n 1, 6n es un nmero que acaba en 6.
Puede utilizar lo siguiente: Un nmero que termine en el dgito 6 puede
escribirse como 10a + 6 donde a N.
Solucin:
Se procede a demostrar por induccin matemtica:
i.
Caso base: Obviamente el caso para n = 1 es cierto porque 61 = 6.
ii.
Caso inductivo:
Se plantea la hiptesis inductiva para el nmero n N, y se asume
verdadera:
H.I.: 6n = 10a + 6, donde a N,
y deber probarse para el caso n + 1, es decir, deber demostrarse la
tesis:
n
Entonces: 6n+1 = 6 x6 = 6(10a + 6)
; por sustitucin de la H.I.
= 60a + 36 = 60a + 30 + 6 = 10(6a + 3) + 6
= 10c + 6
; con c=6a + 3 entero
Por lo que 6n+1 termina en 6, es decir que la tesis queda comprobada, y
luego se afirma por PIM que la proposicin es vlida n 1.
Curso Informtica III 2016
6) Se define el producto de matrices reales 22 de la siguiente manera:
a b e
c d g
f ae bg
h ce dg
af bh
; a, b, c, d R.
cf dh
Sea Fk el k-simo nmero de Fibonacci, al usar el PIM demuestre que:
k
F
1 1
k 1
1 0
Fk
Fk
Fk 1
Por el P.I.M.
i. Se verifica para k=1, es decir, para el caso base:
1
F1
F0
1 1
1 1 F2
=
=
1
0
1
0
F1
ii. Se formulan la H.I. y la tesis:
k
H.I.
F
1 1
= k 1
1 0
Fk
1 1
Tesis
1 0
k 1
Fk
Fk 1
F( k 1)1
=
F( k 1)
k
F( k 1)
F( k 1)1
1
1 1 1 1
usando la H.I.
=
1 0 1 0
1
Fk 1 Fk 1 1
=
Fk Fk 1 1 0
Fk 1 FK Fk 1
de la definicin de nmeros de Fibonacci
=
F
F
F
K 1
K
k
F( k 1)1
=
F( k 1)
F( k 1)
Q.E.D.
F( k 1)1
Curso Informtica III 2016
7) Definamos un nmero triangular de la siguiente manera:
Tn =
n(n 1)
; n N. Demuestre las siguientes proposiciones:
2
i) Tn+1 = Tn + n + 1
ii) 2Tn n = n2
Solucin:
i)
Tn+1 = Tn + n + 1
De la formula demostrada en el tema 1.
Tn =
n(n 1)
=
2
n 1
Tn+1 =
k =
k 0
k , se obtiene,
k 0
+ (n+1),
k 0
= Tn + n + 1
Q.E.D.
ii)
ii.1) 2Tn n = n2
Por PIM, se verifica para n=0 ( caso Base)
2T0 0 = 2(o) 0 = 0 = 02
Se formula la H.I. y la tesis:
H.I.
Para algn k ; 2Tk k = k2
Tesis:
2Tk+1 (k+1) = (k+1) 2
2(T + k + 1) (K + 1) = k2 + 2k + 1 que se obtiene al
k
sustituir Tk+1 = Tk + k + 1
2T + k + 1 = k2 + 2k + 1 2T k = k2
k
k
Curso Informtica III 2016
Usando la H.I. se demuestra la proposicin, y por lo tanto Q.E.D.
ii.2) 2Tn n = n2
De la H.I.
2Tk k = k2
Sumando 2k + 1 a ambos lados, se tiene que:
2Tk + k + 1 = k2 + 2k + 1 = (k+1) 2
2Tk + k + 1 = 2Tk + 2k k + 1 que se obtiene al sustituir k por: 2k k
= 2Tk + 2k k + 2 1 que se obtiene al sustituir 1 por: 2 - 1
= 2(Tk + k + 1) (k + 1) = (k + 1) 2
Usando la H.I. se demuestra la proposicin, y por lo tanto Q.E.D.
8) Escriba un programa en lenguaje Pascal que implemente la funcin de
Ackerman, definida anteriormente.
Solucin:
public class Mayle{
public longint a(int n, int m){
if (n == 0) { return m+1; }
if (m == 0) { return a(n-1,1); }
if ((n != 0) && (m != 0)) { return (n-1,a(n,m-1)); }
}
public static void main (String args[]) {
[Link](Sumar nmeros);
[Link](Ackerman de nmeros);
int resultado = a(x,y);
[Link](El Ackerman es: + resultado);
}
}
9) Utilizando el PIM, demuestre que para todo nmero natural n:
A(3,n) = 2 n+3 3, en donde A (n,m) es la funcin de Ackerman
Solucin:
8
Curso Informtica III 2016
Para resolver este ejercicio, se utilizarn los resultados, ya
demostrados en el presente captulo, relacionados con la funcin
de Ackerman, que fueron desarrollados al utilizar el PIM:
I.
yN, A(1,y) = y + 2
yN, A(2,y) = 2y + 3
Caso Base: se verifica para el caso y = 0:
A(3,0) = A(2,1)
= 2(1) + 3
=5
por el caso 2 de la definicin
suposicin ii
2 0+3 3 = 2 3 3 = 8 3 = 5
II.
la frmula es vlida para y=0
Se construye la hiptesis inductiva y la tesis:
H.I:
A(3, k ) 2 k 3 3
Tesis:
A(3, k 1) 2 ( k 1)3 3
Se calcula:
A (3,k+1) = A (2, A(3,k))
por el caso 3 de la definicin
A (2, A(3,k)) = 2 A(3,k) + 3 suposicin ii
= 2 ( 2k+3 3) + 3
= 2k+4 6 + 3
= 2k+4 3 = 2(k+1) + 3 - 3
La tesis se cumple tambin al asumir la H.I., por lo que el PIM
nos permite afirmar que se verifica para todos los nmeros
naturales.
10) Utilizando el principio de reduccin al absurdo, demuestre que el
conjunto de nmeros primos es infinito.
Solucin:
Suponga que el conjunto de nmeros primos es finito, es decir,
supngase que existe nicamente un nmero n de nmeros primos:
P = {pjj : 1.n}.
Formamos, entonces, un nmero entero positivo, llamado B, tal que:
B = p1p2pkpn + 1 producto de todos los primos de P ms 1.
9
Curso Informtica III 2016
De esta construccin se sabe que B> [Link] y, con mayor razn,
B>pn, es decir, segn nuestra hiptesis, B es mayor que el mayor
nmero primo y, por lo tanto, B no podra ser un nmero primo.
Del teorema fundamental de la aritmtica1 se sabe que si B no es
primo, entonces debe existir un primo pk P, tal que pk divide a B,
por definicin de divisibilidad se sabe que existe un m N tal que:
B p1 p2 ... pk ... pn 1 pk m .
Al restar p1p2pkpn de ambos lados tenemos que:
1 p k m - p1p 2 ...p k ...p n p k (m p1p 2 ...p k-1p k 1 ...p n )
Sabemos que si pk es primo, entonces pk > 1, por lo tanto:
p k (m p1p 2 ...p k-1p k 1 ...p n ) 1 ;
pero esto es imposible, lo que conlleva a una contradiccin, de
manera que B es nmero primo y esto implica que p n no es el mayor
nmero primo, por lo tanto, los nmeros primos no son finitos.
Entonces se ha demostrado por Reduccin al Absurdo que el
conjunto de nmeros primos no puede ser finito y por lo tanto es
infinito.
11) Demuestre por el mtodo de Reduccin al Absurdo que 2 es un
nmero irracional, es decir, que no es racional pues no puede ser
expresado como una fraccin de nmeros enteros.
Solucin:
2 es un nmero racional. Sin prdida de
Suponga que
generalidad, se puede suponer que existen enteros m, n primos
relativos2, tales que:
2
1
m
.
n
El teorema fundamental de la aritmtica establece que todo nmero entero positivo es primo o
producto de primos.
2
Con primos relativos se implica que no tienen ningn divisor comn. Adems, es un hecho
conocido que todo nmero racional puede ser expresado como una fraccin en la que el
numerador y el denominador son nmeros primos relativos.
10
Curso Informtica III 2016
Al elevar al cuadrado ambos lados de la igualdad anterior se
obtiene:
m2
m
2 2 .
n
n
Al multiplicar ambos lados de la ecuacin por n2 se tiene que:
2n 2 m 2
Por lo tanto, 2 divide a m2 y es, por lo tanto, un nmero par. Sin
embargo, esto implica que m tambin debe ser un nmero par (la
multiplicacin de dos nmeros impares es impar). As, 2 divide
tambin a m.
De esto se concluye que existe un entero k, tal que:
4k2 = m2
Al sustituir esto en la igualdad anterior, se deduce que:
2n2 = 4k2
O lo que es equivalente:
n2 = 2k2
Por lo anterior, n2 es par, pero, como se haba sealado
anteriormente, esto implica que n tambin es par. Esto resultara en
que tanto n como m son pares lo cual contradice la hiptesis
planteada al principio en la que se estableca que n y m eran
nmeros primos relativos. Se produjo un absurdo, lo cual nos
obliga a aceptar que la hiptesis planteada no puede ser
verdadera. Por lo tanto 2 no puede ser racional. A estos nmeros
se les denomina irracionales.
12) La suma de nmeros naturales puede ser definida en forma recursiva de
modo que para cualesquiera enteros n y m:
a.
b.
sum (n,0) = n
sum (n, suc(m)) = suc(sum(n, m))
(Base)
(Induccin)
donde suc(n) es el nmero natural ms pequeo mayor que n (su
sucesor).
Al basarse en la definicin anterior:
11
Curso Informtica III 2016
a. D una definicin recursiva de la multiplicacin de nmeros
enteros:
Solucin:
Defina la multiplicacin de esta manera:
mult (n, 0) = 0
(Base)
mult (n, suc(m)) = sum (n, mult (n, m)) (Induccin)
Note que la base comienza desde cero porque estamos
trabajando con multiplicacin entre nmeros naturales.
Adems, esta es una de las formas en que se puede definir,
pero no la nica.
b. Utilizando las definiciones recursivas anteriores, demuestre que:
i. 3 + 4 = 7
Solucin:
sum (3, 4) = suc (sum(3,3)) = suc (suc (sum (3,2)))
= suc (suc (suc (sum (3,1))))
= suc (suc (suc (suc (sum (3,0)))))
= suc (suc (suc (suc (3))))
= suc (suc (suc (4)))
= suc (suc (5))
= suc (6)
=7
ii. 2 * 3 = 6
Solucin:
mult (2, 3)
mult (2, suc(2))
= sum (2, mult (2, 2))
= sum(2, sum(2,mult(2, 1)))
= sum(2, sum(2, sum(2,mult(2, 0))))
= sum(2, sum(2, sum(2,0)))
= sum(2, sum(2, 2))
= sum(2, suc(sum(2,1))
= sum(2, suc(suc(sum(2,0))))
= sum(2, suc(suc(2)))
= sum(2, suc(3))
12
Curso Informtica III 2016
= sum(2, 4)
= suc(sum(2, 3))
= suc(suc(sum(2, 2)))
= suc(suc(suc(sum(2, 1))))
= suc(suc(suc(suc(sum(2, 0)))))
= suc(suc(suc(suc(2))))
= suc(suc(suc(3)))
= suc(suc(4))
= suc(5)
=6
c. Escriba un programa en lenguaje Pascal, que implemente las tres
operaciones: sucesor, suma y multiplicacin.
Solucin:
public class Mayle{
int suc(int m){
return m+1;
}
int sum(int n, int m){
if (m == 0) { return n; }
else { return (suc(sum(n,m-1))); }
}
int mult(int n, int m){
if (m== 0) { return 0; }
else { return (sum(n,sum(n,m-1))); }
}
void main (String args[]) {
[Link](Sumar numeros: );
int result = sum(x,y);
[Link](La suma de numeros es : + result);
result = mult(x,y);
[Link](La mult de numeros es: + result);
}
}
13) D una definicin recursiva de las siguientes frmulas:
a. Cn = 7n (1)
Solucin:
C0 = 0;
Cn+1 = 7(n+1) = 7n + 7 (3)
Al utilizar la ecuacin (1) y sustituir en la ecuacin (3), obtenemos:
13
Curso Informtica III 2016
Cn+1 = Cn + 7.
Por lo tanto la definicin recursiva ser:
i.
ii.
C0 = 0;
Cn+1 = Cn + 7
b. Cn = 3n + 7 (1)
Solucin:
C0 = 7;
Cn+1 = 3(n+1) + 7= (3n + 7) + 3
(3)
Al utilizar la ecuacin (1) y sustituir en la ecuacin (3), obtenemos:
Cn+1 = Cn + 3.
Por lo tanto la definicin recursiva ser:
i. C0 = 7;
ii. Cn+1 = Cn + 3
c. Cn = 11n - 8 (1)
Solucin:
C0 = 8;
Cn+1 = 11(n+1) 8 = (11n - 8) + 11 (3)
Al utilizar la ecuacin (1) y sustituir en la ecuacin (3), obtenemos:
Cn+1 = Cn + 11.
Por lo tanto la definicin recursiva ser:
i. C0 = 8;
ii. Cn+1 = Cn + 11
14
Induccin y recursin
UNIDAD I
Agenda
1.
2.
3.
4.
5.
6.
Matemtica discreta vs Matemtica continua.
Principio de induccin matemtica (PIM).
Definiciones recursivas.
Ejemplo 1, Nmeros de Fibonacci.
Ejemplo 2, funcin de Ackerman.
Reduccin al absurdo.
Parte 1
Matemtica Discreta versus Matemtica Continua
Matemtica Discreta
Algunos temas que abarca la matemtica discreta:
1. Teora de conjuntos.
2. Lgica matemtica.
3. Relaciones y clases de equivalencia.
4. Teora de grafos.
5. Teora de nmeros.
6. Estructuras lgicas.
Matemtica Continua
La matemtica continua comprende temas como:
1.
2.
3.
Continuidad y lmites de funciones.
Clculo diferencial e integral.
Ecuaciones diferenciales.
Herramientas para el curso
Dada la naturaleza de los temas que sern tratados durante el
curso, estas herramientas sern de gran utilidad:
1.
2.
Principio de Induccin Matemtica (PIM).
Funciones Recursivas.
Parte 2
Principio de Induccin Matemtica (PIM)
Ilustracin intuitiva sobre el PIM
De qu color es la bola en cada
una de las urnas?
Principio de induccin matemtica
(PIM)
El PIM se basa en dos ideas subyacentes:
1.
2.
Una afirmacin de tipo inductivo.
Una comprobacin de tipo llamado caso base.
Ejemplo: PIM
Utilizar PIM para demostrar que la frmula utilizada para
calcular la suma de todos los nmeros naturales iguales o
menores a un nmero dado n, se cumple para todos los
nmeros naturales.
n(n + 1)
Sn = i =
2
i =0
Ejemplo: PIM
Caso Base
Ejemplo: PIM
Caso Base
Probaremos que la frmula se cumple para el caso en el que
n = 0.
Ejemplo: PIM
Caso Base
Probaremos que la frmula se cumple para el caso en el que
n = 0.
0
S0 = i
i =0
Ejemplo: PIM
Caso Base
Probaremos que la frmula se cumple para el caso en el que
n = 0.
0
S0 = i = 0
i =0
Ejemplo: PIM
Caso Base
Probaremos que la frmula se cumple para el caso en el que
n = 0.
0
0(0 + 1)
S0 = i = 0 =
2
i =0
Ejemplo: PIM
Caso Base
Probaremos que la frmula se cumple para el caso en el que
n = 0.
0
S0 = i = 0 =
i =0
0(0 + 1)
2
Por lo tanto la frmula se cumple para el caso base, cuando
n = 0.
Ejemplo: PIM
Hiptesis inductiva
Ejemplo: PIM
Hiptesis inductiva
Para esto asumimos que la frmula es valida para el caso n.
n
n(n + 1)
Sn = i =
2
i =0
Ejemplo: PIM
Hiptesis inductiva
Para esto asumimos que la frmula es valida para el caso n.
n
Tesis
n(n + 1)
Sn = i =
2
i =0
Ahora debemos demostrar que la frmula anterior conserva el
mismo patrn en el caso n+1
n +1
S n +1 = i =
i =0
(n + 1)((n + 1) + 1) ?
2
Ejemplo: PIM
Demostracin
Ejemplo: PIM
n +1
S n +1 = i
i =0
Explicacin: Tesis
Ejemplo: PIM
n +1
i =0
i =0
S n +1 = i = i + (n + 1)
Explicacin: Propiedad de las sumatorias
Ejemplo: PIM
n(n + 1)
S n +1 = i = i + (n + 1) =
+ (n + 1)
2
i =0
i =0
n +1
Explicacin: Por hiptesis inductiva.
Ejemplo: PIM
n(n + 1)
+ (n + 1)
2
Explicacin: Ahora desarrollemos el trmino
anterior
Ejemplo: PIM
n(n + 1)
n(n + 1) + 2(n + 1)
+ (n + 1) =
2
2
Explicacin: Factorizacin
Ejemplo: PIM
(
n(n + 1)
n + 1)(n + 2)
+ (n + 1) =
2
2
Explicacin: Mediante factorizacin
Ejemplo: PIM
(
n(n + 1)
n + 1)(n + 2 ) (n + 1)(n + 1 + 1)
+ (n + 1) =
=
2
2
2
Explicacin: Se puede escribir de esta manera
Ejemplo: PIM
(
n(n + 1)
n + 1)(n + 2 ) (n + 1)(n + 1 + 1)
+ (n + 1) =
=
2
2
2
Que es lo queramos demostrar!!
Ejemplo: PIM
Por lo tanto mediante PIM hemos demostrado que:
n
n(n + 1)
Sn = i =
2
i =0
Para todo nmero n que pertenezca a los nmeros naturales.
Ejemplo: PIM
Por lo tanto mediante PIM hemos demostrado que:
n
n(n + 1)
Sn = i =
2
i =0
Para todo nmero n que pertenezca a los nmeros
naturales.
Q Q.E.D.
Parte 3
Definiciones Recursivas
Definiciones Recursivas
Para definir recursivamente necesitamos dos casos:
1. Un caso base.
2. Un caso inductivo.
Factorial
Un ejemplo simple de recursin, factorial de un nmero n.
Base:
0! = 1
Induccin: n! = n*(n-1)!, para n 1
Ejemplo de factorial
Utilizando al definicin recursiva anterior, calculemos el
factorial de 4 (4!).
Ejemplo de factorial
Definicin recursiva de factorial
0! = 1
n! = n*(n-1)!
4!=?
-> Base
-> Induccin
Ejemplo de factorial
Definicin recursiva de factorial
0! = 1
n! = n*(n-1)!
4!=?
Explicacin: Usamos la definicin, caso
inductivo.
-> Base
-> Induccin
Ejemplo de factorial
Definicin recursiva de factorial
0! = 1
n! = n*(n-1)!
4!=4*(3)!
Explicacin: Usamos la definicin, caso
inductivo.
-> Base
-> Induccin
Ejemplo de factorial
Definicin recursiva de factorial
0! = 1
n! = n*(n-1)!
4!=4*(3)!
Explicacin: Aplicamos nuevamente el caso
inductivo
-> Base
-> Induccin
Ejemplo de factorial
Definicin recursiva de factorial
0! = 1
n! = n*(n-1)!
4!=4*(3)!=4*(3*(2)!)
Explicacin: Aplicamos nuevamente el caso
inductivo
-> Base
-> Induccin
Ejemplo de factorial
Definicin recursiva de factorial
0! = 1
n! = n*(n-1)!
4!=4*(3)!=4*(3*(2)!)
Explicacin: Aplicamos nuevamente el caso
inductivo
-> Base
-> Induccin
Ejemplo de factorial
Definicin recursiva de factorial
0! = 1
n! = n*(n-1)!
-> Base
-> Induccin
4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!))
Explicacin: Aplicamos nuevamente el caso
inductivo
Ejemplo de factorial
Definicin recursiva de factorial
0! = 1
n! = n*(n-1)!
-> Base
-> Induccin
4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!))
Explicacin: Continuamos aplicando el caso
inductivo.
Ejemplo de factorial
Definicin recursiva de factorial
0! = 1
n! = n*(n-1)!
-> Base
-> Induccin
4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!))=4*(3*(2*1*(0)!))
Explicacin: Continuamos aplicando el caso
inductivo.
Ejemplo de factorial
Definicin recursiva de factorial
0! = 1
n! = n*(n-1)!
-> Base
-> Induccin
4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!))=4*(3*(2*1*(0)!))
Explicacin: Ahora aplicamos el caso base.
Ejemplo de factorial
Definicin recursiva de factorial
0! = 1
n! = n*(n-1)!
-> Base
-> Induccin
4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!))=4*(3*(2*1*1))
Explicacin: Ahora aplicamos el caso base.
Ejemplo de factorial
Definicin recursiva de factorial
0! = 1
n! = n*(n-1)!
-> Base
-> Induccin
4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!))=4*(3*(2*1*1))
4*3*2*1
Explicacin: Ahora solo debemos operar.
Ejemplo de factorial
Definicin recursiva de factorial
0! = 1
n! = n*(n-1)!
-> Base
-> Induccin
4!=4*(3)!=4*(3*(2)!)=4*(3*(2*(1)!))=4*(3*(2*1*1))
4*3*2*1 = 24
Explicacin: Ahora solo debemos operar.
Parte 4
Nmeros de Fibonacci
Ejemplo: Nmeros de Fibonacci
1.
2.
3.
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2
-> Base, parte 1
-> Base, parte 2
-> Induccin
Ejemplo: Nmeros de Fibonacci
Veamos algunos ejemplos de la funcin de Fibonacci:
F0 = 0
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
Ejemplo: Nmeros de Fibonacci
Frmula para calcular fibonacci:
En donde:
Fn =
n n
5
1+ 5
1 5
=
; =
2
2
Ejemplo: Nmeros de Fibonacci
Demostracin por medio de PIM:
1.
2.
3.
Caso Base.
Hiptesis Inductiva
Tesis
Ejemplo: Nmeros de Fibonacci
Casos Base
F0 =
0 0
5
Para n = 0
Ejemplo: Nmeros de Fibonacci
Casos Base
F0 =
0 0
5
Para n = 0
Por definicin:
F0 = 0
Ejemplo: Nmeros de Fibonacci
Casos Base
0
1 1
F0 =
=
5
5
Ejemplo: Nmeros de Fibonacci
Casos Base
F0 =
0 0
5
1 1
=
=0
5
Ejemplo: Nmeros de Fibonacci
Casos Base
F0 =
F1 =
0 0
5
1 1
5
11
=
=0
5
Para n = 1
Ejemplo: Nmeros de Fibonacci
Casos Base
F0 =
F1 =
0 0
5
1 1
5
11
=
=0
5
Para n = 1
Por definicin:
F1 = 1
Ejemplo: Nmeros de Fibonacci
Casos Base
F0 =
F1 =
0 0
5
1 1
5
11
=
=0
5
Ejemplo: Nmeros de Fibonacci
Casos Base
F0 =
0 0
5
11
=
=0
5
1+ 5 1 5
1 1
2
F1 =
=
= 2
5
5
5
Ejemplo: Nmeros de Fibonacci
Casos Base
F0 =
0 0
5
11
=
=0
5
1+ 5 1 5
1
1
1+ 5 1 5
2
2
F1 =
=
=
=
5
5
5
2 5
) (
Ejemplo: Nmeros de Fibonacci
Casos Base
F0 =
0 0
5
11
=
=0
5
1+ 5 1 5
1
1
1+ 5 1 5 2 5
2
2
F1 =
=
=
=
=
5
5
5
2 5
2 5
) (
Ejemplo: Nmeros de Fibonacci
Casos Base
F0 =
0 0
5
11
=
=0
5
1+ 5 1 5
1 1
1+ 5 1 5
2
2
F1 =
=
=
=
=1
5
5
5
2 5
) (
Ejemplo: Nmeros de Fibonacci
Hiptesis Inductivas
Fn =
n n
5
Fn 1 =
n 1 n 1
5
Ejemplo: Nmeros de Fibonacci
Hiptesis Inductivas
Fn =
Tesis:
n n
5
Fn +1 =
Fn 1 =
n +1 n +1
5
n 1 n 1
5
?
Ejemplo: Nmeros de Fibonacci
Por definicin
Fn +1 = Fn + Fn 1
Ejemplo: Nmeros de Fibonacci
n n n 1 n 1
Fn +1 =
+
5
5
Explicacin: Por hiptesis inductivas
Ejemplo: Nmeros de Fibonacci
n n + n 1 n 1
Fn +1 =
5
Explicacin: Por comn denominador.
Ejemplo: Nmeros de Fibonacci
n n 1 ( n + n 1 )
Fn +1 =
5
Explicacin: Reordenando y agrupando.
Ejemplo: Nmeros de Fibonacci
n 1 ( + 1) n 1 ( + 1)
Fn +1 =
5
Explicacin: Por factorizacin.
Ejemplo: Nmeros de Fibonacci
n 1 ( + 1) n 1 ( + 1)
Fn +1 =
5
OJO!
2
1+ 5 1+ 2 5 + 5 3
5 1+ 5
=
=
= +
=
+1 = +1
4
2 2
2
2
2
Ejemplo: Nmeros de Fibonacci
n 1 ( + 1) n 1 ( + 1)
Fn +1 =
5
OJO!
2
1+ 5 1+ 2 5 + 5 3
5 1+ 5
=
=
= +
=
+1 = +1
4
2 2
2
2
2
1 5 1 2 5 + 5 3
5 1 5
2
=
=
=
=
+ 1 = + 1
4
2 2
2
2
Ejemplo: Nmeros de Fibonacci
n 1 2 n 1 2
Fn +1 =
5
Explicacin: Por resultados anteriores
Ejemplo: Nmeros de Fibonacci
n +1 n +1
Fn +1 =
5
Explicacin: Por suma de exponentes
Ejemplo: Nmeros de Fibonacci
n +1 n +1
Fn +1 =
5
Q Q.E.D.
Parte 5
Funcin de Ackerman
Ejemplo: Funcin de Ackerman
1.
A(0,y) = y+1
2.
A(x,0) = A(x-1,1)
-> Induccin, parte 1
A(x,y) = A(x-1,A(x,y-1)) -> Induccin, parte 2
3.
-> Base
Para todo x, y N
Ejemplo: Funcin de Ackerman
A(2,1)=?
Ejemplo: Funcin de Ackerman
A(2,1)=?
Caso 3:
A(x,y) = A(x-1,A(x,y-1))
Ejemplo: Funcin de Ackerman
A(2,1)=?
Caso 3:
A(x,y) = A(x-1,A(x,y-1))
x=2
-> x-1 = 1
y=1
-> y = 0
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
Caso 3:
A(x,y) = A(x-1,A(x,y-1))
x=2
-> x-1 = 1
y=1
-> y = 0
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) = ?
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) = ?
Caso 2:
A(x,0) = A(x-1,1)
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) = ?
Caso 2:
A(x,0) = A(x-1,1)
x=2
-> x-1 = 1
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
Caso 2:
A(x,0) = A(x-1,1)
x=2
-> x-1 = 1
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = ?
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = ?
Caso 3
A(x,y) = A(x-1,A(x,y-1))
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = A(0,A(1,0))
A(1,0) = ?
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = A(0,A(1,0))
A(1,0) = ?
Caso 2:
A(x,0) = A(x-1,1)
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = A(0,A(1,0))
A(1,0) = A(0,1)
Caso 2:
A(x,0) = A(x-1,1)
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = A(0,A(1,0))
A(1,0) = A(0,1)
A(0,1) = ?
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = A(0,A(1,0))
A(1,0) = A(0,1)
A(0,1) = ?
Caso 1:
A(0,y) = y+1
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = A(0,A(1,0))
A(1,0) = A(0,1)
A(0,1) = ?
Caso 1:
A(0,y) = y+1
y=1
-> y+1 = 2
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = A(0,A(1,0))
A(1,0) = A(0,1)
A(0,1) = 2
Caso 1:
A(0,y) = y+1
y=1
-> y+1 = 2
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = A(0,A(1,0))
A(1,0) = 2
Por resultado anterior
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = A(0,2)
Por resultado anterior
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = A(0,2)
A(0,2) = ?
Caso 1:
A(0,y) = y+1
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = A(0,2)
A(0,2) = ?
Caso 1:
A(0,y) = y+1
y=2
-> y+1 = 2
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = A(0,2)
A(0,2) = 3
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) =A(1,1)
A(1,1) = 3
Por resultado anterior
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,A(2,0))
A(2,0) = 3
Por resultado anterior
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
Por resultado anterior
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = ?
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = ?
Caso 3
A(x,y) = A(x-1,A(x,y-1))
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = A(0,A(1,2))
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = A(0,A(1,2))
A(1,2) = ?
Caso 3
A(x,y) = A(x-1,A(x,y-1))
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = A(0,A(1,2))
A(1,2) = A(0,A(1,1))
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = A(0,A(1,2))
A(1,2) = A(0,A(1,1))
A(1,1) = 3
Por resultado anterior
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = A(0,A(1,2))
A(1,2) = A(0,3)
Por resultado anterior
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = A(0,A(1,2))
A(1,2) = A(0,3)
A(0,3) = ?
Caso 1:
A(0,y) = y+1
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = A(0,A(1,2))
A(1,2) = A(0,3)
A(0,3) = 4
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = A(0,A(1,2))
A(1,2) = 4
Por resultado anterior
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = A(0,4)
Por resultado anterior
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = A(0,4)
A(0,4) = ?
Caso 1:
A(0,y) = y+1
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = A(0,4)
A(0,4) = 5
Ejemplo: Funcin de Ackerman
A(2,1)=A(1,3)
A(1,3) = 5
Por resultado anterior
Ejemplo: Funcin de Ackerman
A(2,1)=5
Por resultado anterior
Ejemplo: Funcin de Ackerman
A(2,1)=5
Que es el resultado final
Funcin de Ackerman: propiedades
Primera Propiedad
Demostracin por medio de PIM.
A(1, y ) = y + 2;
para todo entero " y".
Funcin de Ackerman:
propiedades
Caso Base
A(1,0) = A(0,1);
por caso 2 : A(x,0 ) = A(x 1,1)
Funcin de Ackerman:
propiedades
Caso Base
A(1,0) = A(0,1);
A(0,1) = 1 + 1 = 2;
por caso 2 : A(x,0 ) = A(x 1,1)
por caso 1 : A( 0,y) = y + 1
Funcin de Ackerman:
propiedades
Caso Base
A(1,0) = A(0,1);
por caso 2 : A(x,0 ) = A(x 1,1)
A(0,1) = 1 + 1 = 2; por caso 1 : A( 0 ,y) = y + 1
Por lo que se cumple el caso base
Funcin de Ackerman:
propiedades
Hiptesis Inductiva
A(1, y ) = y + 2
Tesis
A(1, y + 1) = ( y + 1) + 2 ?
Funcin de Ackerman: propiedades
Demostracin
Funcin de Ackerman:
propiedades
Demostracin
A(1, y + 1) = A(0, A(1, y ))
caso 3 : A( x,y ) = A(x 1,A(x,y 1 ))
Funcin de Ackerman:
propiedades
Demostracin
A(1, y + 1) = A(0, A(1, y )) caso 3 : A(x,y) = A(x 1,A(x,y 1 ))
A(0, A(1, y )) = A(0, y + 2)) H.I.
Funcin de Ackerman:
propiedades
Demostracin
A(1, y + 1) = A(0, A(1, y ))
caso 3 : A(x,y) = A(x 1,A(x,y 1 ))
A(0, A(1, y )) = A(0, y + 2)) H.I.
A( 0 ,y + 2 ) = (y + 1 ) + 2 lgebra y caso 1 : A( 0 ,y) = y + 1
Funcin de Ackerman:
propiedades
Demostracin
A(1, y + 1) = A(0, A(1, y ))
caso 3 : A(x,y) = A(x 1,A(x,y 1 ))
A(0, A(1, y )) = A(0, y + 2)) H.I.
A( 0 ,y + 2 ) = (y + 1 ) + 2
lgebra y caso 1 : A( 0 ,y) = y + 1
Q Q.E.D.
Funcin de Ackerman: propiedades
Segunda Propiedad
Demostracin por medio de PIM.
A(2, y ) = 2 y + 3;
para todo entero " y".
Funcin de Ackerman: propiedades
Caso Base
A(2,0) = A(1,1);
por caso 2 : A(x,0 ) = A(x 1,1)
Funcin de Ackerman:
propiedades
Caso Base
A(2,0) = A(1,1);
A(1,1) = 1 + 2 = 3;
por caso 2 : A(x,0 ) = A(x 1,1)
por propiedad 1 : A( 1,y) = y + 2
Por lo que se cumple el caso base
Funcin de Ackerman:
propiedades
Hiptesis Inductiva
A(2, y ) = 2 y + 3
Tesis
A(2, y + 1) = 2( y + 1) + 3 ?
Funcin de Ackerman:
propiedades
Demostracin
Funcin de Ackerman:
propiedades
Demostracin
A(2, y + 1) = A(1, A(2, y ))
caso 3 : A( x,y ) = A(x 1,A(x,y 1 ))
Funcin de Ackerman:
propiedades
Demostracin
A(2, y + 1) = A(1, A(2, y )) caso 3 : A(x,y) = A(x 1,A(x,y 1 ))
A(1, A(2, y )) = A(1,2 y + 3)) H.I.
Funcin de Ackerman:
propiedades
Demostracin
A(2, y + 1) = A(1, A(2, y )) caso 3 : A(x,y) = A(x 1,A(x,y 1 ))
A(1, A(2, y )) = A(1,2 y + 3)) H.I.
A( 1,2 y + 3 ) = ( 2 y + 3 ) + 2
por propiedad 1 : A( 1,y) = y + 2
Funcin de Ackerman:
propiedades
Demostracin
A(2, y + 1) = A(1, A(2, y )) caso 3 : A(x,y) = A(x 1,A(x,y 1 ))
A(1, A(2, y )) = A(1,2 y + 3)) H.I.
A( 1,2 y + 3 ) = ( 2 y + 3 ) + 2
( 2 y + 3 ) + 2 = 2(y + 1 ) + 3
por propiedad 1 : A( 1,y) = y + 2
por lgebra
Funcin de Ackerman:
propiedades
Demostracin
A(2, y + 1) = A(1, A(2, y )) caso 3 : A(x,y) = A(x 1,A(x,y 1 ))
A(1, A(2, y )) = A(1,2 y + 3)) H.I.
A( 1,2 y + 3 ) = ( 2 y + 3 ) + 2
( 2 y + 3 ) + 2 = 2(y + 1 ) + 3
por propiedad 1 : A( 1,y) = y + 2
por lgebra
Q Q.E.D.
Parte 6
Reduccin al Absurdo
Ejemplo: Reduccin al absurdo
Demostremos que es un nmero irracional, es decir, que
no puede ser representado como una fraccin de nmeros
enteros, por medio de Reduccin al Absurdo.
2
Ejemplo: Reduccin al absurdo
Solucin
Supongamos que
es un nmero racional.
Ejemplo: Reduccin al absurdo
Solucin
Supongamos que 2 es un nmero racional.
Esto significa que existen dos nmeros m y n
(primos relativos) tales que:
m
2=
n
Ejemplo: Reduccin al absurdo
m
2 =
n
( )
Explicacin: Elevemos ambos lados de la igualdad
anterior al cuadrado.
Ejemplo: Reduccin al absurdo
Explicacin: Lo cual podemos escribir
Ejemplo: Reduccin al absurdo
m
2= 2
n
Explicacin: Lo cual podemos escribir
Ejemplo: Reduccin al absurdo
Explicacin: Multiplicando ambos lados de la
ecuacin por n2.
Ejemplo: Reduccin al absurdo
2n = m
Explicacin: Multiplicando ambos lados de la
ecuacin por n2.
Ejemplo: Reduccin al absurdo
2
2n = m
Por lo que m2 es un nmero par y tambin m lo es. Recuerde
que la multiplicacin de dos nmeros impares es siempre impar,
por lo que m no podra ser impar sin caer en una contradiccin.
Ejemplo: Reduccin al absurdo
De lo anterior podemos concluir que existe un nmero k, tal
que:
2k = m
Ejemplo: Reduccin al absurdo
De lo anterior podemos concluir que existe un nmero
k, tal que:
2
4k = m
2
Sustituimos en la ecuacin
Ejemplo: Reduccin al absurdo
De lo anterior podemos concluir que existe un nmero
k, tal que:
2
4k = m
2
Sustituimos en la ecuacin
2n = m
Ejemplo: Reduccin al absurdo
De lo anterior podemos concluir que existe un nmero
k, tal que:
2
4k = m
2
Sustituimos en la ecuacin
2n = m
Ejemplo: Reduccin al absurdo
4k = m
2
Y tenemos
2n = m
Ejemplo: Reduccin al absurdo
Y tenemos
2n = 4k
Ejemplo: Reduccin al absurdo
Por lo anterior n2 es par y n tambin lo es.
De esto resulta que n y m son pares, lo cual contradice la
hiptesis (acerca de que n y m son primos), y as se produce un
absurdo, lo cual nos obliga a aceptar que la hiptesis planteada
no es verdadera.
Ejemplo: Reduccin al absurdo
Por lo anterior n2 es par y n tambin lo es.
De esto resulta que n y m son pares, lo cual contradice
la hiptesis (acerca de que n y m son primos), y as se
produce un absurdo, lo cual nos obliga a aceptar que la
hiptesis planteada no es verdadera.
Q Q.E.D.
Ejercicio 1
Sea Fn el n-simo nmero de Fibonacci. Usando el PIM demuestre
la validez de la siguiente proposicin:
n
1+
i =1
F =F
2i
2 n +1
, n 1
Ejercicio 1
Caso Base
1
1 +
i =1
2i
? Para n = 1
Por una parte:
1 + F2i = 1 + F2 = 1 + 1 = 2
i =1
Por otra parte:
F3 = 2
Con lo que se comprueba el caso base.
Ejercicio 1
Hiptesis Inductiva
k
1 + F2 i = F2 k +1 , k N
i =1
Tesis
k +1
1 + F2 i = F2 ( k +1) +1 ?
i =1
Ejercicio 1
k +1
Tesis
1 + F2 i = F2 ( k +1) +1 ?
i =1
Demostracin
k +1
1+
i =1
2i
= 1+ (
i =1
k +1
2i
2i
i = k +1
Explicacin: por propiedades de sumatorias
Ejercicio 1
k +1
Tesis
1 + F2 i = F2 ( k +1) +1 ?
i =1
Demostracin
k +1
1+
i =1
2i
= (1 +
i =1
k +1
2i
)+
2i
i = k +1
Explicacin: por asociatividad de la suma
Ejercicio 1
k +1
Tesis
1 + F2 i = F2 ( k +1) +1 ?
i =1
Demostracin
k +1
1+
i =1
k +1
2i
2 k +1
2i
i = k +1
Explicacin: sustituyendo Hiptesis Inductiva
Ejercicio 1
Tesis
k +1
1 + F2 i = F2 ( k +1) +1 ?
i =1
Demostracin
F
=F
=F
=F
=
2 k +1
+ F 2 ( k +1)
2 k +1
+ F 2k +2
2 k +3
2 ( k +1) +1
Explicacin: por definicin recursiva de los nmeros de Fibonacci
Q Q.E.D.
Informtica III
Lenguajes
Agenda
1. Lenguajes, un poco de historia.
2. Alfabetos.
3. Cuerdas.
4. Operaciones entre cuerdas.
5. Lenguajes.
6. Ejemplos.
Lenguajes
Un poco de historia
Un poco de historia
Inicios de la computacin: conexin de alambres
Salto cuntico con el concepto de programa
almacenado, sin embargo los lenguajes eran de bajo
nivel
Desarrollo de lenguajes de alto nivel unido a la
formalizacin de la Teora de Lenguajes
Bases de la Teora de Lenguajes: Teoras de
Matemtica Discreta y Lgica Matemtica
Un poco de historia
Paralelamente se construyeron mquinas que
interpretaran estos lenguajes y los tradujeran a
lenguaje mquina.
Este es un de los AVANCES ms importantes en la
computacin
Elementos de la teora de
lenguajes
Los lenguajes estn presentes cuando se necesita:
Comunicacin entre agentes
Codificacin de informacin
Elementos bsicos de la teora de lenguajes:
Un lenguaje
Una mquina para leer y analizar el lenguaje
Correspondencia entre
mquinas y lenguajes
LENGUAJES
Lenguajes de
alto nivel
LCL, Lenguajes
de Contexto
Libre
Lenguajes de
bajo nivel LR,
Lenguajes
regulares
MQUINAS
(Compiladores)
Mquinas de
Turing
APD,
Autmata
Push Down
AFD, Autmata
finito
determinstico
PROPSITOS
(Lenguaje
mquina)
Qu es un lenguaje?
Todo lenguaje posee dos dimensiones
Sintaxis
Semntica
Alfabetos
Alfabeto
Normalmente identificado por
Conjunto finito y no vaco de smbolos
Por lo general se representan por letras
minsculas
Ej. alfabetos: abecedario, alfabeto binario
Cuerdas
Cuerdas
Dado un alfabeto , una cuerda se define
como una secuencia de letras sobre el
alfabeto
Su representacin usual son las ltimas
letras del abecedario: v, w, x, y, z
Conocidas
tambin
como
palabras,
oraciones, strings
Se postula la existencia de la cuerda nula
Cuerdas
Dado un alfabeto , se definen dos conjuntos
de cuerdas:
El conjunto clausura de Kleene, *
* = Universo de cuerdas o todas las cuerdas
de longitud arbitraria
* incluye la cuerda nula
Y el conjunto + = * - { }
Operaciones con cuerdas
Concatenacin
La concatenacin de dos o ms cuerdas se define como la
cuerda formada yuxtaponindolas, en orden indicado.
Puede considerarse como una operacin binaria sobre *,
asociativa, no conmutativa y con elemento neutro la cuerda
nula
Lo anterior constituye un semi-grupo tambin llamado
monoide.
Ejemplo: Concatenacin
Si w = a1a2an; y v = b1b2bm
wv sera: a1a2anb1b2bm,
mientras que vw sera: b1b2bma1a2an
No es conmutativa - S es asociativa
Para toda cuerda w: w = w = w
Imagen inversa
La imagen inversa de una cuerda w, wR se
define como:
w *, a
R =
(wa)R = awR
caso base
caso recursivo
Ejemplo: Imagen inversa
Supongan la cuerda w = abca, su imagen
inversa wR segn la definicin recursiva sera:
Ejemplo: Imagen inversa
Supongan la cuerda w = abca, su imagen
inversa wR segn la definicin recursiva sera:
wR
Ejemplo: Imagen inversa
Supongan la cuerda w = abca, su imagen
inversa wR segn la definicin recursiva sera:
wR = (abca)R
Ejemplo: Imagen inversa
Supongan la cuerda w = abca, su imagen
inversa wR segn la definicin recursiva sera:
wR = (abca)R = a(abc)R
Ejemplo: Imagen inversa
Supongan la cuerda w = abca, su imagen
inversa wR segn la definicin recursiva sera:
wR = (abca)R = a(abc)R
= ac(ab)R
Ejemplo: Imagen inversa
Supongan la cuerda w = abca, su imagen
inversa wR segn la definicin recursiva sera:
wR = (abca)R = a(abc)R
= ac(ab)R
= acb(a)R
Ejemplo: Imagen inversa
Supongan la cuerda w = abca, su imagen
inversa wR segn la definicin recursiva sera:
wR = (abca)R = a(abc)R
= ac(ab)R
= acb(a)R
= acba()R
Ejemplo: Imagen inversa
Supongan la cuerda w = abca, su imagen
inversa wR segn la definicin recursiva sera:
wR = (abca)R = a(abc)R
= ac(ab)R
= acb(a)R
= acba()R
= acba
Ejemplo: Imagen inversa
Supongan la cuerda w = abca, su imagen
inversa wR segn la definicin recursiva sera:
wR = (abca)R = a(abc)R
= ac(ab)R
= acb(a)R
= acba()R
= acba
wR = acba
Longitud o largo de una cuerda
Denotado por |w| y es el nmero de letras
que w contiene.
Se define recursivamente:
w *, a
|| = 0
|aw| = |w| +1
caso base
caso recursivo
Ejemplo: Longitud de una cuerda
Supongan la cuerda w = abca, calculemos su
largo, |w|, mediante la definicin recursiva.
|w| = |abca| = |bca| + 1
Ejemplo: Longitud de una cuerda
Supongan la cuerda w = abca, calculemos su
largo, |w|, mediante la definicin recursiva.
|w| = |abca| = |bca| + 1
= |ca| + 1 + 1
Ejemplo: Longitud de una cuerda
Supongan la cuerda w = abca, calculemos su
largo, |w|, mediante la definicin recursiva.
|w| = |abca| = |bca| + 1
= |ca| + 1 + 1
= |a| + 2 + 1
Ejemplo: Longitud de una cuerda
Supongan la cuerda w = abca, calculemos su
largo, |w|, mediante la definicin recursiva.
|w| = |abca| = |bca| + 1
= |ca| + 1 + 1
= |a| + 2 + 1
= || + 3 + 1
Ejemplo: Longitud de una cuerda
Supongan la cuerda w = abca, calculemos su
largo, |w|, mediante la definicin recursiva.
|w| = |abca| = |bca| + 1
= |ca| + 1 + 1
= |a| + 2 + 1
= || + 3 + 1
=4+0=4
Palndromos
Son cuerdas que se leen igual hacia adelante como hacia
atrs, es decir:
R = w
,
w
es
palndromo
ssi
w
w *
Existen palndromos de longitud par e impar
Ejemplos de palndromos
Considere el alfabeto = {a,b} y la cuerda
w = aabbaa
wR = (aabbaa)R = aabbaa = w
La cuerda nula tambin es un palndromo
RADAR construida sobre el abecedario tambin es un
palndromo
Potencia
Definicin recursiva:
w *
w0 =
wn+1 = wnw
caso base
caso recursivo
Ejemplo: Potencia
Suponga la cuerda w = acb, calculemos algunas potencias.
w0 =
Ejemplo: Potencia
Suponga la cuerda w = acb, calculemos
algunas potencias.
w0 =
w1 = acb
Ejemplo: Potencia
Suponga la cuerda w = acb, calculemos
algunas potencias.
w0 =
w1 = acb
w2 = acbacb
Ejemplo: Potencia
Suponga la cuerda w = acb, calculemos
algunas potencias.
w0 =
w1 = acb
w2 = acbacb
w3 = acbacbacb
Prefijos
Sea w = abcba, veamos algunos ejemplos de
prefijos de w
a
ab
abc
abcb
w
Prefijos propios
Sea w = abcba, veamos algunos ejemplos de
prefijos de w
a
ab
abc
abcb
Sufijos
Sea w = abcba, veamos algunos ejemplos de
sufijos de w.
a
ba
cba
bcba
abcba
Sufijos propios
Sea w = abcba, veamos algunos ejemplos de
sufijos propios de w.
a
ba
cba
bcba
Subcuerda
Sea w = abcba, veamos algunos ejemplos de
subcuerdas de w.
abc
(subcuerda propia)
bcb
(subcuerda propia)
bcba
(subcuerda propia)
(no
es
subcuerda
propia)
w
(no es subcuerda propia)
Subsecuencia
Sea w = a1b2cb4a5 algunas subsecuencias de w:
cb4
a1b4
a1a5
b2a5
Lenguajes
Definicin Formal de un Lenguaje
Un lenguaje es un subconjunto de la clausura de
Kleene *
Ejemplo de lenguajes
el conjunto vaco es un lenguaje del alfabeto
*, la clausura de Kleene es un lenguaje
, el alfabeto mismo es tambin un lenguaje
{ } es un lenguaje cuyo nico elemento es la
cuerda nula
Caractersticas
Los lenguajes pueden ser finitos o infinitos
Pueden definirse en forma enumerativa, descriptiva o
mediante mtodos que se explicarn ms adelante
Ejemplos
Si ={a, b}, entonces:
L = {aba, bbbaaa, aaa} es un lenguaje finito
definido en forma enumerativa
L = {anbn; donde n es un nmero natural} es
un lenguaje infinito definido en forma
descriptiva
L = {w * tal que |w| = 5}, es el lenguaje de
todas las cuerdas cuya longitud es 5
Unin entre lenguajes
L U M (tambin denotado por L+M), es el
lenguaje
formado
por
cuerdas
que
pertenecen al lenguaje L o bien al lenguaje
M
Ejemplo de Unin entre lenguajes
Si L={A, B, C, , Z, a, b, c, , z} y D={0,1,,9}
L+D es el conjunto de palabras de longitud 1
(letras o dgitos) como:
A, z, C, b, 9, 8
Notacin
En notacin de conjuntos:
L M w * | w L w M
Concatenacin entre lenguajes
Escrita por LM, es el lenguaje constituido por
cuerdas que se forman concatenando una
cuerda del lenguaje L con una cuerda del
lenguaje M (en ese orden)
Ejemplo de concatenacin entre
lenguajes
Si L={A, B, C, , Z, a, b, c, , z} y D={0,1,,9}
LD es el conjunto de cuerdas que consisten
en un letra seguida de un dgito. Ejs:
A1, B9, Z3, z9, b5
Notacin
En notacin de conjuntos:
LM w | x L y M w xy
*
Potencia de un lenguaje
Si n es un nmero natural, Ln es el lenguaje
formado por L concatenado consigo mismo n
veces
Si n es cero, Ln = {}
Ejemplo de potencia de un lenguaje
Si L={A, B, C, , Z, a, b, c, , z} y D={0,1,,9}
L4 es el conjunto de palabras que contienen
exactamente cuatro letras. Ejs:
AazZ, aaaa, Czwb, Hola
Notacin
En notacin de conjuntos:
Ln w * | w1 , w2, ..., wn L wn w1w2 ...wn
Ejemplo de Clausura de Kleene de
un lenguaje
Si L={A, B, C, , Z, a, b, c, , z}
L* es el conjunto de todas las palabras de
longitud arbitraria formadas nicamente por
letras, incluyendo tambin la cuerda nula. Ejs:
, A, a, z, da, zz, AKD, EIEIEIEI
Clausura de Klenee de un
lenguaje
Se denota por L*
L* Li
i 0
Clausura positiva de un lenguaje
La clausura positiva L* se define como la
clausura de Kleene anterior, pero excluyendo la
cuerda nula
L L*
Otros ejemplos
Si L={A, B, C, , Z, a, b, c, , z} y D={0,1,,9}
L(L+D)* es el conjunto de palabras que
empiezan con una letra seguida de cero o ms
letras o dgitos. Ejs:
A, z, AbdZ45, Dw383, t99595
D+ es el conjunto de palabras con uno o ms
dgitos. Ejs:
0, 1000, 494949
EJERCICIOS
Ejercicio 1
Utilizando
el
PIM
demuestre
que:
El nmero de subsecuencias de una cuerda w
de longitud n es 2n.
Ejercicio 2
Si L={A, B, C, , Z, a, b, c, , z} y D={0,1,,9}
Determine si las siguientes cuerdas pertenecen a (L*D*
LD)+
a123aab
3159abdd
Ejercicio 3, parte I
Dado el alfabeto = {a, b}, una cuerda de Finobacci se
define recursivamente como:
f1 = a;
f2 = b
fn = fn-1fn-2, para todo natural n3
Dada la definicin anterior:
Liste las 9 primeras cuerdas Fibonacci
Ejercicio 3, parte II
La longitud de las cuerdas de Fibonacci tienen relacin
directa con los nmeros de Fibonacci, de la siguiente
manera:
fn= Fn
siendo Fn el ensimo nmero de Fibonacci.
Demuestre esta afirmacin utilizando el PIM.
Ejercicio 4
Usando el PIM demuestre que:
|wn| = n|w|
Para toda cuerda w y para todo nmero natural n
Ejercicio 5
Demuestre por Induccin Matemtica que:
w, x*, wx=w+x
