Semana 1 Cartilla ETC V1

Cartilla Elementos de Teor´ıa en la Computaci´
on
M´onica Mar´ıa Lozano Romero
Polit´ecnico Grancolombiano

2010

Cartilla Elementos de Teor´ıa en la Computaci´
on

Este libro est´a sujeto a derechos de autor. Todos estos derechos son reservados para el autor del libro
en su reproducci´on parcial o completa, en especial los derechos de traducci´on, distribuci´on, uso de las
ilustraciones ycopia. Cualquier infracci´on a estos derechos esta legislada por la ley colombiana de derechos
de autor.

i

Cartilla Elementos de Teor´ıa en la Computaci´
on

ii

´Indice general

1. Conteo
1.1. Introducci´on . . . . . . . . . . . . . . . . . . .
1.2. Principios de Conteo . . . . . . . . . . . . . .
1.2.1. Regla de la suma y el producto . . .
1.2.2. Permutaciones . . . . . . . . . . . . .
1.2.3.Combinaciones . . . . . . . . . . . . .
1.2.4. Principio de las casillas . . . . . . . .
1.2.5. Ejemplos . . . . . . . . . . . . . . . .
1.3. Teorema del binomio y sus aplicaciones . .
1.3.1. Triangulo de pascal y el teorema del
1.4. Conteo y conjuntos . . . . . . . . . . . . . . .
1.5. Ejercicios . . . . . . . . . . . . . . . . . . . .

. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. .. . . .
. . . . . .
. . . . . .
binomio
. . . . . .
. . . . . .

2. Inducci´
on
2.1. Introducci´on . . . . . . . . . . . . . . . . . . . . . . .
2.2. Inducci´on sobre los naturales . . . . . . . . . . . . .
2.2.1. Inducci´on con inicio en enteros distintos de
2.3. Principio del buen orden . . . . . . . . . . . . . . .
2.3.1. Inducci´on y el principio del buen orden . .
2.4. Definicionesinductivas . . . . . . . . . . . . . . . .
2.4.1. Inducci´on sobre definiciones inductivas . .
2.4.2. Arboles binarios . . . . . . . . . . . . . . . .
2.5. Inducci´on y el an´alisis de algoritmos . . . . . . . .
2.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . .
3. Especificaci´
on y correci´
on de algoritmos
3.1. Introducci´on . . . . . . . . . . . . . . . . . .
3.2. Especificaci´on dealgoritmos . . . . . . . .
3.3. Correci´on de asignaci´on y condicionales .
3.3.1. Correci´on de asignaciones . . . . .
3.3.2. Correcci´on de condicionales . . . .
3.4. Correcci´on de ciclos . . . . . . . . . . . . .
3.5. Ejercicios . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

4. Ecuaciones de recurrencia
4.1. Introducci´on . . . . . .. . . . . . . . . . . . . . . . .
4.2. Definiciones b´asicas . . . . . . . . . . . . . . . . . .
4.2.1. Tipos de ecuaciones de recurrencia . . . . .
4.3. Ecuaciones de recurrencia lineales y homog´eneas .
4.3.1. Ecuaciones de primer orden . . . . . . . . .
4.3.2. Ecuaciones de segundo orden . . . . . . . .
4.4. Ecuaciones de recurrencia lineales no Homog´eneas
4.5. Ejercicios . . . . . . . . . .. . . . . . . . . . . . . .
iii

.
.
.
.
.
.
.
.
.
.
.

. . .
. . .
cero
. . .
. . .
. . .
. . .
. . .
. . .
. . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
..
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
..

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
....