¿Cuál es el mejor libro para estudiar matemáticas discretas?

Matemáticas concretas: una base para la informática, ¡por el propio Donald Knuth!

Se necesita conocimiento matemático discreto para volverse experto en probar la corrección y derivar la complejidad de los algoritmos y las estructuras de datos. Se le enseñarán esos en los libros de Algo/DS, pero solo puede obtener la competencia matemática practicando solo matemáticas discretas.

El libro de Knuth es muy bueno para eso. Pero en mi humilde opinión, solo lo necesitará si desea realizar pruebas avanzadas en DS/Algorithms.

Para un principiante, sería genial repasar "Grimaldi" http://www.amazon.com/Discrete-Combinatorial-Mathematics-Applied-Introduction/dp/0201199122 y luego pasar rápidamente a Algorithms.

De lo contrario, continuará profundizando en Matemáticas discretas y nunca llegará a Algorithms/DS.

Recuerde, Matemáticas discretas no le enseña cómo diseñar algoritmos o estructuras de datos. Eso vendrá solo practicando problemas de algoritmos @ topcoder, acm icpc, spoj, etc. y leyendo libros sobre Algos/DS o cursos sobre esos.

Mis 2 centavos.

Un muy buen libro de texto para matemáticas discretas a nivel de pregrado es el libro de Kenneth Rosen titulado Matemáticas discretas y sus aplicaciones .

El libro proporciona soluciones a la mitad de los problemas. También puede comprar la Guía de soluciones para estudiantes . No lo tengo, pero sospecho que proporciona las respuestas a la otra mitad de las preguntas o proporciona una guía paso a paso para resolver los problemas (el libro solo proporciona respuestas finales con explicaciones mínimas de esas respuestas ).

Se usa para la secuencia de dos cuartos en Matemática discreta que toman los estudiantes de ingeniería de software y ciencias de la computación, así como una serie de programas de matemáticas en mi universidad. Conservé este libro incluso después de tomar el curso, y actualmente lo estoy usando para repasar mis habilidades matemáticas discretas para mi examen de Asociado Certificado en Desarrollo de Software.

Hay muchas áreas diferentes para las matemáticas discretas y muchos buenos libros.

existe Graph Theory de Diestel, que tiene una versión gratuita en pdf disponible en

diestel-graph-theory.com

hay una función de generación por wilf, versión gratuita en pdf en

math.upenn.edu/~wilf/DownldGF.html

Otros libros que son buenos incluyen Combinatoria enumerativa 1 y 2 de Richard P Stanley (un libro que es lo suficientemente denso como para tener al menos 1 curso de análisis y álgebra cada uno).

Dicho esto, para más exposiciones introductorias en términos de madurez matemática esperada, sugeriría buscar en Google y mirar varias notas de conferencias del tipo "introducción a la combinatoria" o "matemáticas para científicos informáticos". Descubrí que las notas de "matemáticas para informáticos" del MIT OCW eran bastante agradables cuando las miré hace varios años.

ocw.mit.edu/courses/electrical-engineering-and-computer-science...

tiene un enlace a las notas de clase. Hay algunos apartes realmente divertidos en él. Uno de mis favoritos "... cualquiera que diga eso está mal, y deberías burlarte de él hasta que llore".

Además, si desea profundizar aún más en las matemáticas discretas/combinatoria, el valor de desarrollar un poco de conceptos básicos matemáticos en otras áreas de las matemáticas. Análisis complejo, análisis real (al nivel de al menos baby rudin, y tal vez incluso hasta el análisis funcional), tal vez alguna probabilidad hasta el nivel de formulación de la teoría de la medida, y al menos una pizca de álgebra abstracta. Luego, puede hacer cosas como mirar la combinatoria de procesos aleatorios (excelente para analizar algoritmos aleatorios) y mirar problemas geniales como la filtración.

Probablemente hay otras cosas que debería sugerir, pero el punto es que las matemáticas discretas son accesibles sin tanta experiencia, pero también te recompensan por enriquecer esa formación matemática con algunas cosas increíblemente hermosas que son 1) increíbles y divertidas 2) útiles.

Me gusta mucho Matemáticas discretas de Norman Biggs . No recomendaría la segunda edición. Más bien, obtenga la primera edición (la primera edición "revisada" si puede). El texto pretende ser autónomo (me lo parece).

Dado que no hay mucha información sobre esta edición del texto en línea (la vista previa en Amazon es la segunda edición), aquí hay un resumen:

Parte 1: Números y contar

1. Números enteros (ordenación, recursividad, inducción, divisibilidad, gcd, factorización)
2. Función y conteo (sobreyecciones, inyecciones, biyecciones, principio del casillero, finito vs infinito)
3. Principios de conteo (función de Euler, principio de adición, palabras, permutaciones)
4. Subconjuntos y diseños (teorema del binomio, principio del tamiz, diseños,$t$-diseños)
5. Partición (relaciones de equivalencia, distribuciones, números multinomiales, clasificación de permutaciones)
6. Aritmética modular (congruencias,$\mathbb{Z}_m$, construcciones cíclicas, cuadrados latinos)

Parte 2: Gráficos y Algoritmos:

1. Algoritmos y eficiencia (probar corrección,$O$notación, comparación, clasificación)
2. Gráficos (isomorfismo de gráficos, valencia, caminos, ciclos, árboles, coloración, algoritmo codicioso)
3. Árboles, clasificación, búsqueda (conteo de hojas, algoritmos de clasificación, árboles de expansión, problema MST, primero en profundidad, primero en ancho, problema de la ruta más corta)
4. Gráficos bipartitos (relaciones, coloraciones de bordes, coincidencias, coincidencias máximas, transversales)
5. Dígrafos, redes, flujos (caminos críticos, flujos y cortes, teorema de corte mínimo de flujo máximo, algoritmo de etiquetado)
6. Técnicas recursivas (recursión lineal, bisección recursiva, optimización recursiva, programación dinámica)

Parte 3: Métodos algebraicos:

1. Grupos (axiomas, isomorfismos, grupos cíclicos, subgrupos, clases laterales)
2. Grupos de permutaciones (definiciones, órbitas, estabilizadores, tamaño/número de órbitas, representación de grupos por permutaciones)
3. Anillos, campos, polinomios (algoritmo de división, algoritmo euclidiano, factorización)
4. Campos finitos (orden, construcción, teorema del elemento primitivo, geometría finita, planos proyectivos, existencia)
5. Corrección de errores (palabras, códigos, errores, códigos lineales, códigos cíclicos)
6. Funciones generadoras (series de potencias, fracciones parciales, teorema del binomio, recursividad lineal)
7. Particiones de un entero positivo (particiones conjugadas, funciones generadoras, identidad misteriosa)
8. Simetría y conteo (simetría cíclica y diédrica, simetría 3D, coloraciones no equivalentes, coloraciones y funciones generadoras, teorema de Polya)

Me gusta mucho Matemática discreta de Ross y Wright:

Pensamiento matemático: resolución de problemas y pruebas.

John P. D'Angelo, Douglas B. West.

Disponible en Amazon .

Se supone que esto es una introducción a las demostraciones matemáticas. Como tal, no se limita a las matemáticas discretas. Pero hace un muy buen trabajo para las matemáticas discretas. También vería alguna prueba en un análisis real; pero puede concentrarse solo en la parte discreta ignorando esto.

Encontré el libro Elements of Discrete Mathematics de CL Liu extremadamente útil.

Está en un nivel muy básico y es excelente si está buscando una introducción a las matemáticas discretas.

Los mejores libros que yo sepa son estos dos:

Matemáticas discretas por Norman L.Biggs

o

Matemáticas discretas y sus aplicaciones por Kenneth H. Rosen

El mejor libro para estudiar matemáticas discretas es " Matemáticas discretas y estructuras " de Satinder Bal Gupta ". Está publicado por University Science Press . El lenguaje del libro es muy simple. Contenía cientos de problemas resueltos y no resueltos con sugerencias.

Fundamentos de estructuras matemáticas discretas, 3ª edición. Está escrito según ACM-Curriculum, comprende muchas preguntas de nivel GATE y escrito por un profesor de informática.