Buen libro matemático sobre algoritmos [cerrado]

11

Soy un fanático de la elegancia y el rigor matemático, y ahora estoy buscando literatura sobre algoritmos y análisis de algoritmos. Ahora, no me importa mucho qué algoritmos están cubiertos, sino cómo se presentan y tratan. Valoro mucho un lenguaje muy claro y preciso que defina todas las nociones utilizadas de una manera estricta y abstracta.

Descubrí que el clásico Introducción a los algoritmos , de Cormen, Leiserson, Rivest y Stein es bastante bueno, pero no maneja bien las matemáticas y es bastante informal con sus pruebas y definiciones. La Introducción de Sipser a la Teoría de la Computación parece mejor en ese sentido, pero aún no ofrece una transición perfecta de las matemáticas a los algoritmos.

¿Alguien puede recomendar algo?


¹: Los algoritmos deberían al menos invocar la gestión de sus datos necesarios utilizando estructuras clásicas de datos abstractos no triviales como gráficos, matrices, conjuntos, listas, árboles, etc., preferiblemente también operando en tales estructuras de datos. No me interesaría demasiado si se ignorara por completo el problema del uso y la gestión de las estructuras de datos. Sin embargo, no me importan mucho los problemas resueltos con ellos.

k.stm
fuente
2
Esto es subjetivo; definir "bueno". Además, si bien no tenemos una política estricta para las preguntas de la lista, existe una aversión general . Tenga en cuenta también esto y esta discusión; es posible que desee mejorar su pregunta para evitar los problemas explicados allí. Si no está seguro de cómo mejorar su pregunta, ¿podemos ayudarlo en Computer Science Chat ?
Raphael
@ Raphael Gracias. Solo usé la palabra "bueno" en el título, en mi pregunta especifiqué lo que quiero. Si bien intencionalmente no me volví demasiado específico, al menos debería quedar claro que mi enfoque es (como se insinuó) en la elegancia y el rigor matemático . No creo que esta respuesta pida una lista de libros, porque no debería haber demasiados libros dentro de esa categoría, y aun así, no creo en eso "preservar la pureza de una pregunta estricta" "estructura de respuesta" que sucede en varios sitios de intercambio de pila aquí, pero supongo que no es mi llamada. No estoy seguro si puedo mejorar la pregunta.
k.stm
Además, no creo que la "solicitud de referencia" sea apropiada para la pregunta. Al menos no según su descripción: ni estoy buscando documentos ni estoy interesado en un tema específico y limitado. De hecho, estoy bastante abierto en cuanto a qué contenidos están cubiertos, vea mi segunda oración. ¿Está bien si elimino la etiqueta nuevamente? ¿Quizás podría y debería limitarme con qué tipo de algoritmos estaría contento?
k.stm
2
Tal vez debería considerar la semántica denotacional y la verificación del programa.
Yuval Filmus

Respuestas:

7

Hendrik Lenstra escribió en 1992 :

Aunque es, desde un punto de vista matemático riguroso, deseable que defina lo que quiero decir con un algoritmo y su tiempo de ejecución, no lo haré. Mi principal excusa es que yo mismo no conozco estas definiciones. Peor aún, nunca vi un tratamiento de la teoría apropiada que sea preciso, elegante y conveniente para trabajar. Sería una empresa loable llenar este vacío aparente en la literatura.

No sé si se han realizado progresos desde entonces, o si el consenso incluso considera que esto es una "brecha". Pero el punto sigue siendo que al menos algunos matemáticos eminentes no están satisfechos con el rigor matemático de la derivación de algoritmos. Por lo tanto, es posible que no exista ningún libro con el nivel deseado de formalismo del OP.

La gran variedad de perspectivas prácticas que tenemos debido a Knuth, Gries , Stepanov y otros está destinada a ayudar a los programadores más que a las matemáticas y, por lo tanto, inevitablemente no alcanzan el rigor y la subjetividad.

No obstante, el trabajo de Stepanov es ampliamente aclamado en Silicon Valley como uno de los mejores intentos de síntesis científica.

En Elementos de programación , Alexander Stepanov y Paul McJones intentan sentar las bases algebraicas abstractas de los algoritmos. El libro comienza con definiciones axiomáticas un tanto informales de entidades, valores y sus atributos, pero en 288 páginas avanza deductivamente a través de una serie de lemas a los fundamentos de la Biblioteca de plantillas estándar.

El TOC, el prefacio y un capítulo de muestra sobre Transformaciones y sus órbitas se pueden encontrar aquí , y una conferencia introductoria aquí .

El libro más reciente y relajado de Stepanov, From Mathematics to Generic Programming , está estructurado más por una hoja de ruta de la historia de las matemáticas, construyendo desde la multiplicación egipcia a monoides, semigrupos y el teorema de Lagrange, eventualmente desarrollando estructuras de datos modernas con sus iteradores y algoritmos utilizados en el STL.


fuente
?!? "actualmente no existe una derivación matemática precisa, elegante y conveniente del concepto de algoritmo ..." ¿qué tal una máquina de Turing?
vzn
1
Lenstra aborda las máquinas de Turing en el documento vinculado, pero creo que la idea es que no proporcionan un análisis algebraico completo. La cita es casi literal, incluida la parte "gap", si desea leerla usted mismo. Editaré la publicación para eliminar el "consenso" sugerido, en caso de que se considere discutible.
ofc am / sabía que estaba citando a Lenstra pero podía agregar citas o una cita en bloque más larga de su afirmación notable / discutible / cuestionable
vzn
piensan que las máquinas de Turing no pueden derivarse , por el contrario, forman el axioma de un sistema computacional (ala tesis de la Iglesia-Turing ). Es todo el análisis de Lenstras y CS en general que se deriva del axioma de la existencia TM.
vzn
1
@Raphael, si mamá dice que sería una "empresa loable" limpiar mi habitación adecuadamente, la esencia de su discurso es "no te molestes en limpiar tu habitación". ¿Te estoy malentendiendo o me estás malentendiendo?
7

Creo que el libro que describe tiene un nombre. Está en siete volúmenes, de los cuales solo tres y la mitad han sido publicados. Se llama The Art of Computer Programming (TAOCP) y está escrito por Donald Knuth.

Sin embargo, puede ser que a veces describa aplicaciones. Pero siempre puedes saltarte eso, y dudo que haga gran parte del contenido. No deberías estar demasiado decepcionado con las matemáticas.

babou
fuente
Temía que esta respuesta pudiera surgir. Lo miré y no me convenía. "No deberías estar demasiado decepcionado con las matemáticas". - tal vez, pero Knuth tampoco parece definir cosas, sino que más bien las presenta informalmente, explicándolas. Sin embargo, es genial transmitir la idea, no es lo que espero de las matemáticas.
k.stm
Tal vez podría contribuir al campo publicando la versión matemáticamente ofuscada de su trabajo. Pero si lo que le interesa es la "transición fluida de las matemáticas a los algoritmos", un tema mejor para usted podría ser la teoría de tipos. La relación entre las matemáticas y los algoritmos sigue siendo un tema de investigación.
babou
1
PD Si "temía que esta respuesta pudiera surgir", debería haberlo dicho en su pregunta, ya que es uno de los principales libros de referencia. Las preguntas completas y documentadas obtienen mejores respuestas.
babou
Solo se me ocurrió después de haber hecho la pregunta, cuando estaba lejos de mi computadora. Mi comentario sobre el libro de Knuth no debe tomarse de manera peyorativa (que es así como creo que lo ha tomado para el comentario de "publicar la versión matemáticamente ofuscada"), probablemente sería similar a la blasfemia. Su camino tampoco es lo que estoy buscando. Tal vez simplemente no hay nada como lo que imagino por ahí ...
k.stm
2
@ k.stm Bueno, olvídate de la ofuscación, que es un tema en sí mismo. El punto es que creo que la algorítmica no es (¿todavía?) Matemática. Puede ser que pueda obtener formalizaciones, pero es probable que sean simples codificaciones que pierden la sustancia, con poco beneficio. Eso depende del tema. Probablemente sea mucho menos cierto para la teoría de autómatas, que tiene algoritmos significativos. El punto es que identificar adecuadamente la naturaleza matemática abstracta de las estructuras no es obvio. Es una cuestión de comprensión, no de formalización, y lleva años. Piense en ello como física
babou