RECURSIVIDAD 1
1.1 Introducción 1
1.2 Propiedades de una recursividad 7
1.3 Ejemplos de programas recursivos 10
1.4 Ejemplos de recursividades de cola 25
1.5 Ejercicios 29
2 RELACIONES DE RECURRENCIA 33
2.1 Introducción 33
2.2 Resolución de relaciones de recurrencia 44
2.2.1 Método iterativo 45
2.2.2 Relaciones de recurrencia homogéneas lineales 54
2.3 Ejercicios 70
3 ANÁLISIS DE ALGORITMOS 73
3.1 Introducción 73
3.2 Enfoque experimental 74
3.3 Enfoque teórico: notación asintótica O grande 84
3.4 Enfoque teórico: otras notaciones asintóticas 110
3.5 Ejercicios 120
4 RELACIONES B INARIAS 123
4.1 Introducción 123
4.2 Representaciones de una relación binaria 139
4.3 Operaciones con relaciones binarias 145
4.4 Tipos de relaciones 162
4.5 Ejercicios 179
5 TEORÍA DE GRAFOS 183
5.1 Introducción 183
5.2 Representaciones para un grafo 210
5.3 Circuitos en un grafo 236
5.4 Algoritmo del camino más corto 270
5.5 Ejercicios 290
6 TEORÍA DE ÁRBOLES 295
6.1 Introducción 295
6.2 Árboles binarios de búsqueda 327
6.3 Recorridos en un árbol binario 340
6.4 Árboles generadores 378
6.5 Árboles de expansión mínima 393
6.6 Ejercicios 417
7 MÁQUINAS DE ESTADO FINITO Y AUTÓMATAS 421
7.1 Introducción 421
7.2 Máquinas de estado finito 421
7.3 Autómatas de estado finito determinísticos 436
7.4 Autómatas no determinísticos 462
7.5 Ejercicios 481
8 LENGUAJES Y GRAMÁTICAS 487
8.1 Introducción 487
8.2 Lenguajes formales y gramáticas 487
8.3 Gramáticas regulares y autómatas 502
8.4 Ejercicios 512
Solución de los ejercicios 517
Bibliografía 571
Apéndice 1: Comandos del paquete VilCretas 573
Apéndice 2: Tipos de grafos 603
Si desea conocer una serie de contenidos esenciales relacionados con el campo de la matemática discreta, ha llegado al libro indicado. Esta obra cubre los temas de recursividad, relaciones de recurrencia, análisis de algoritmos, relaciones binarias, teoría de grafos, teoría de árboles, máquinas y autómatas de estado finito, y lenguajes y gramáticas. Después de muchos años de experiencia en el aula, el autor brinda en este libro una exposición disruptiva al incorporar una combinación propicia entre la teoría clásica, el desarrollo de una cantidad relevante de ejemplos y el uso de software como un recurso didáctico fundamental. El programa empleado se sustenta en un paquete de uso libre diseñado por el autor, llamado VilCretas, que añade 232 comandos de uso especializado en el área de la matemática discreta al conocido software comercial Wolfram Mathematica. En este sentido, el paquete VilCretas le ofrece distintas herramientas de exploración conceptual y procedimental, lo que le posibilitará la interacción con objetos matemáticos y le favorecerá los procesos de aula basados en la experimentación y el análisis, bajo la premisa de un tratamiento didáctico guiado que le conducirá al autoaprendizaje. También encontrará en esta obra distintos apoyos de mediación multimedial creados por el autor, que buscan mejorar los procesos educativos en un campo científico muchas veces considerado como árido por los estudiante
