Matemática Discreta

Título: Matemática Discreta Autores: Violeta Migallón y José Penadés Edita: Puntero y Chip, 2004 Localización: Reprografía EPS
	PRÓLOGO Este libro va dirigido a aquellos que estén interesados en conocer una parte de la matemática finita y, más concretamente, al alumnado de cualquier ingeniería informática. No hemos tratado de ser exhaustivos en los temas tratados, si bien, el planteamiento del contenido seleccionado en este libro se ha intentado realizar de forma rigurosa a la vez que sencilla para el lector. Las actuales recomendaciones curriculares en informática señalan que, la presencia de parte de las matemáticas necesarias para el ingeniero informático ha sufrido un proceso de redireccionamiento hacia las estructuras discretas. Así, aunque no existe total coincidencia en el papel que debe jugar la matemática tradicional, todos coinciden en resaltar la importancia que en ciencia de la computación tienen las estructuras discretas. En ese sentido podríamos decir que las estructuras discretas son las matemáticas de la informática, aunque no las únicas. De hecho, la matemática discreta, considerada como disciplina independiente, ha nacido hace muy pocos años como consecuencia de la aparición del computador que, al fin y al cabo, es una máquina finita.
Son muchos los tópicos que pueden clasificarse dentro de la materia de matemática discreta. Podemos considerar, por ejemplo, los tópicos relacionados con la teoría de conjuntos, la lógica básica, las técnicas de demostración, los fundamentos de conteo, la aritmética entera y modular, los grafos, los árboles o la probabilidad discreta. De entre ellos, existen ciertos tópicos que por sus características pueden, también, englobarse dentro de otras disciplinas o materias. Por ejemplo, los conceptos relacionados con la teoría de conjuntos pueden formar parte del álgebra, la lógica básica y las técnicas de demostración formarían parte de la lógica considerada como materia, y lo mismo ocurre con la probabilidad discreta que ya por sí misma puede considerarse una disciplina. Todo ello nos ha llevado a considerar en este libro conceptos relacionados con los grafos, la aritmética entera y modular, y los fundamentos de conteo. Así, este libro está dividido en tres grandes bloques o partes con características propias en sus contenidos. La primera parte está dedicada a realizar una introducción a la teoría de grafos, el estudio de la aritmética entera y modular se realiza en la segunda parte, y por último, dedicamos un bloque a diversas técnicas de conteo. En cada uno de los capítulos incluidos en cada bloque se realiza una breve introducción donde intentamos motivar la inclusión de los distintos conceptos, a la vez que planteamos el esquema del capítulo en sí mismo; los distintos conceptos y resultados se ilustran con numerosos ejemplos y ejercicios resueltos que figuran intercalados entre el desarrollo teórico hasta un total de 295; finalizamos cada capítulo con una serie de ejercicios propuestos que pueden ayudar a afianzar los conocimientos adquiridos en la lectura del capítulo en cuestión. Las soluciones a los 201 ejercicios propuestos se incluyen en un apéndice final; en dichas soluciones no sólo se indica el resultado final sino que, cuando se ha creído conveniente, se ha realizado una indicación para su correcta resolución. Hay que tener en cuenta, además, que el lector puede ayudarse, para la resolución de los problemas de los dos primeros bloques, de dos herramientas informáticas de libre distribución; éstas son la herramienta MaGraDa (Grafos para Matemática Discreta) y ArtEM (Aritmética Entera y Modular). Esperamos, pues, que este libro sea de interés tanto para el alumnado de una ingeniería informática o cualquier otro estudio relacionado, como para la comunidad académica en general.
ÍNDICE Prólogo Parte I. Introducción a la teoría de grafos Capítulo 1. Fundamentos de grafos 1.1 Introducción 1.2 Definición y conceptos básicos 1.3 Tipos particulares de grafos 1.4 Subgrafos 1.5 Grado de un vértice 1.6 Caminos y conexión 1.7 Isomorfismos de grafos 1.8 Representación matricial 1.9 Problemas propuestos Capítulo 2. Accesibilidad y conectividad 2.1 Introducción 2.2 Accesibilidad 2.3 Cálculo de las componentes conexas 2.4 Conectividad en grafos no dirigidos 2.5 Problemas de recorrido de aristas 2.6 Sucesiones de deBruijn 2.7 Problemas de recorrido de vértices 2.8 Códigos de Gray 2.9 Problemas propuestos Capítulo 3. Árboles 3.1 Introducción 3.2 Definición, propiedades y ejemplos 3.3 Árboles con raíz o enraizados 3.4 Árboles binarios 3.5 Códigos binarios 3.6 Árboles binarios de búsqueda 3.7 Algoritmos de búsqueda de primera profundidad 3.8 Notación polaca 3.9 Problemas propuestos Capítulo 4. Grafos ponderados 4.1 Introducción 4.2 Definición y ejemplos 4.3 Caminos más cortos 4.4 Grafos acíclicos. Método del camino crítico 4.5 Algoritmo de Dijkstra 4.6 Caminos más cortos entre todos los pares de vértices 4.7 Árboles generadores de mínimo peso 4.8 Problemas propuestos Parte II. Aritmética entera y modular Capítulo 5. Los números enteros 5.1 Introducción 5.2 Los enteros. Principio de la buena ordenación 5.3 Divisibilidad 5.4 Máximo común divisor y mínimo común múltiplo 5.5 Números primos. Factorización 5.6 Problemas propuestos Capítulo 6. Congruencias en los enteros. Aritmética modular 6.1 Introducción 6.2 Congruencias 6.3 Los enteros modulo n. Aritmética en Z_n 6.4 Elementos invertibles en Z_n. Teoremas de Euler y Fermat 6.5 Aritmética computacional con enteros grandes 6.6 Aplicación a la criptografía 6.6.1 Criptosistemas de clave privada 6.6.2 Criptosistemas de clave pública 6.7 Problemas propuestos Parte III. Análisis combinatorio Capítulo 7. Fundamentos del análisis combinatorio 7.1 Introducción 7.2 Principios básicos de conteo 7.3 Variaciones sin repetición 7.4 Variaciones con repetición 7.5 Permutaciones sin repetición 7.6 Permutaciones con repetición 7.7 Combinaciones sin repetición 7.8 Combinaciones con repetición 7.9 Problemas propuestos Capítulo 8. Funciones generadoras 8.1 Introducción 8.2 Función generadora ordinaria de una sucesión 8.3 Técnicas de cálculo de los coeficientes de las funciones generadoras ordinarias 8.4 Tratamiento de las funciones generadoras ordinarias para los problemas combinatorios de selección 8.5 Partición de un entero positivo 8.6 Función generadora exponencial. Aplicación a los problemas combinatorios de ordenación 8.7 Problemas propuestos Capítulo 9. Relaciones de recurrencia 9.1 Introducción 9.2 Relaciones de recurrencia lineales con coeficientes constantes 9.3 Solución general de una relación de recurrencia lineal homogénea y con coeficientes constantes 9.4 Relaciones de recurrencia no homogéneas 9.5 Otros métodos de resolución de relaciones de recurrencia 9.6 Problemas propuestos Soluciones a los problemas propuestos Bibliografía Índice terminológico