Quels livres chacun devrait-il lire?

[ Chronologie ]

Cette question a le même esprit: quels journaux doivent être lus par tout le monde et quelles vidéos doivent être visionnées par tout le monde . Il demande des livres remarquables dans différents domaines de l'informatique théorique.

Les livres peuvent être orientés vers les mathématiques, mais vous pouvez trouver cela génial pour un informaticien. Exemples:

• Probabilité
• Les inégalités
• Logique
• La théorie des graphes
• Combinatoire
• Conception et analyse d'algorithme
• Théorie du calcul / Théorie de la complexité du calcul

Veuillez consacrer chaque réponse à des ouvrages du même sujet (par exemple, des livres sur la combinatoire).

Remarque: Le titre peut être trompeur. Voici une clarification: Soit X et Y deux domaines de l’informatique. Il y a des livres que tout le monde

• dans le champ X devrait lire.
• dans le champ Y devrait lire.
• dans les deux champs devrait lire.

Cette question concerne les 3 cas. En d'autres termes, il n'est PAS spécifique à ce dernier cas.

Edit: comme suggéré par Dai Le , veuillez surligner les raisons pour lesquelles vous aimez le livre.

Rubriques connexes:

• Références pour les techniques de preuve TCS
• Livres sur la théorie des automates pour l'auto-apprentissage
• Livres de probabilité
• Livre de mathématiques populaire préféré
• Guide du débutant sur la dérandomisation
• Références sur les bornes inférieures du circuit
• Article d'enquête sur la théorie des fonctions récursives
• Livres sur la sémantique des langages de programmation
• Quels sont les récents ouvrages du SDC dont les projets sont disponibles en ligne
• Livres sur les probabilités

Complexité informatique:

Si vous recherchez des manuels récents de complexité. Les deux suivants sont incontournables.

• Complexité informatique: une approche moderne de Sanjeev Arora et Boaz Barak ( page d'accueil du manuel )

• Complexité informatique: une perspective conceptuelle par Oded Goldreich ( page d'accueil du manuel )

La majorité du contenu entre ces deux livres est comparable. Cependant, il existe quelques différences essentielles: Goldreich consacre plus d’espace à l’exploration des fondements conceptuels et philosophiques de la théorie de la complexité, tandis qu’Arora / Barak couvre un plus vaste éventail de sujets, notamment les modèles concrets de complexité, le calcul quantique et les limites inférieures des circuits, quasiment absents. de l'ancien.

Une autre option, un manuel ancien mais intemporel dans sa complexité est:

• Complexité informatique de Christos Papadimitriou

Le livre de Papadimitriou est remarquable pour ses chapitres couvrant la logique du premier ordre ainsi que les classes SNP, MaxSNP et APX (les fondements théoriques de la dureté de l'approximation), absents des textes plus modernes.$_0$

Un autre classique (relativement) ancien mais assez remarquable est:

• Introduction à la théorie du calcul par Michael Sipser

C'est l'un des rares / premiers manuels qui inclut explicitement "Proof Idea:" entre "Theorem:" et "Proof:", et constitue l'un des manuels mathématiques les mieux écrits sur tous les sujets. D'autre part, il ne s'agit que d'une introduction à la complexité, ne consacrant qu'un chapitre de 50 pages à des "sujets avancés" (y compris l'approximation, les algorithmes probabilistes, IP = PSPACE et le cryptage). En tant que premier livre sur la complexité, ou en tant qu'exemple d'écriture vraiment excellente, ce livre est excellent .

• La nature du calcul par Cristopher Moore et Stephan Mertens

Scott Aaronson écrit que ce livre a "le plaisir d'un livre populaire avec le poids intellectuel d'un manuel." Il raconte des histoires et donne beaucoup d'exemples et de références amusants (Game of Life et de nombreux autres exemples pour les machines complètes de Turing). Cela ne va pas trop loin dans la théorie de la complexité mais a une grande ampleur. Il convient de noter en particulier ses liens avec la physique statistique.

NP-Completeness:

Eh bien, j'imagine que Informatique et Intractabilité: un guide de la théorie de la NP-Complétude de Garey et Johnson figureront parmi les meilleurs livres de cette liste.

Conception et analyse d'algorithmes:

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest et Clifford Stein. Introduction aux algorithmes.

R. Motwani, P. Raghavan. Algorithmes randomisés.

J'ai trouvé ce livre suggéré par Ryan Williams sur MathOverflow: Algorithm Design de Kleinberg & Tardos .

Un autre excellent livre est Introduction aux algorithmes: une approche créative de Udi Manber . Ce livre n'est pas un catalogue d'algorithmes; il essaie plutôt de donner au lecteur l’intuition de "reconnaître la structure mathématique dans les problèmes abstraits". (cité d'un avis)

Mathématiques générales pour l'informatique:

• Mathématiques concrètes: un fondement de l'informatique par Graham, Knuth et Patashnik.

• Le Princeton Companion to Mathematics de Gowers et al.

• Les preuves du livre par Aigner et Ziegler.

Systèmes de types et sémantique de langage de programmation:

Types et langages de programmation de Benjamin Pierce et le volume de suivi Sujets avancés dans Types et langages de programmation . Ils fournissent une vue d'ensemble solide mais compréhensible du rôle de la théorie des types dans la conception du langage de programmation, ainsi que de l'utilisation de la sémantique opérationnelle pour exprimer la sémantique du langage de programmation.

Inégalités:

Un autre livre précieux pour toute personne en informatique qui souhaite lier n'importe quelle quantité (donc tout le monde!) Est: La classe de maître de Cauchy-Schwarz: une introduction à l'art des inégalités mathématiques de Michael Steele.

Un livre encyclopédique sur le sujet est Un dictionnaire des inégalités . Bien qu'il ne s'agisse pas d'un livre à lire en intégralité, il est bon de l'avoir à votre disposition. Voir aussi le supplément du livre.

De plus, Wikipedia possède une excellente liste d'inégalités .

Pour des sujets spécifiques, vous pouvez consulter:

• Inégalités probabilistes
• Inégalités matricielles
• Inégalités Géométriques
• Le livre "A = B" de Petkovsek, Wilf et Zeilberger

Intéressant. Personne n'a mentionné les volumes de The Art of Computer Programming de Donald E. Knuth . Un traitement très détaillé des sujets avec de très bons exercices.

J'ai trouvé des pierres précieuses comme «échantillonnage de résorption» dans ce livre, pour ne citer qu'un exemple.

Comme Sylvain Peyronnet l'a déjà mentionné, la logique est une partie importante de l'informatique théorique. Cependant, il ne suffit pas d'apprendre la logique à partir de manuels conçus pour les mathématiciens purs. En d'autres termes, il est également important d'apprendre la logique dans une perspective plus "informatique".

Théorie des modèles finis

Nous voulons apprendre des techniques qui traitent des structures finies. Il est bien connu que de nombreux outils traditionnels de la théorie des modèles, tels que la compacité et le théorème de Löwenheim-Skolem, ne sont pas applicables aux modèles finis. Cela nous conduit à étudier la théorie des modèles finis . Pour ce domaine, je recommande les excellents livres suivants:

• Leonid Libkin, Éléments de la théorie des modèles finis . (cahier de texte)
• Grädel et al., Théorie des modèles finis et ses applications . (articles de sondage et applications)

Un sous-domaine de la théorie des modèles finis est la complexité descriptive , dans laquelle nous voulons caractériser les classes de complexité en fonction du type de logique nécessaire pour définir les langages. La référence définitive pour la complexité descriptive est:

• Neil Immerman, Complexité descriptive .

Preuve de complexité

Un autre domaine important de la logique en informatique est la complexité de la preuve , une étude des relations à trois voies entre les classes de complexité, les systèmes logiques faibles et le système de preuve propositionnelle. Les deux aspects connexes suivants sont pris en compte: (i) la complexité des preuves de formules propositionnelles, et (ii) l’étude des théories faibles de l’arithmétique, appelée arithmétique bornée .

L'aspect (i) concerne la question suivante: "Existe-t-il un système de preuve propositionnelle dans lequel chaque tautologie a une preuve de polynôme de taille dans la taille de la tautologie?"

$C$$VC$$VC$$C$

$\mathsf{PV}$$\mathsf{PV}$

Pour d'excellents sondages sur la complexité des preuves, je recommande les deux livres suivants:

• Stephen Cook et Phuong Nguyen, Fondements logiques de la complexité de la preuve . (brouillon disponible ici )
• Jan Krajíček, Arithmétique bornée, logique propositionnelle et théorie de la complexité .

$\mathsf{P}$$V_0$

Le livre de Krajíček est un peu plus exigeant puisqu'il suppose que les lecteurs sont déjà familiarisés avec la logique mathématique et la théorie des modèles (ou qu'ils sont assez disposés à apprendre le contexte nécessaire au cours du processus). Mais vous apprendrez beaucoup en lisant et en comprenant ce livre.

Algorithmes Randomisés:

Probability and Computing: Algorithmes randomisés et analyse probabiliste par Michael Mitzenmacher et Eli Upfal.

Excellent livre pour expliquer les bases des algorithmes aléatoires. Les exemples et les preuves sont expliqués très clairement et sont faciles à suivre. De plus, les exercices sont très amusants.

(répondu par Marcos Villagra)

Analyse d'algorithmes randomisés:

Toute personne travaillant dans des algorithmes devrait avoir une concentration de mesure pour l'analyse d'algorithmes randomisés , qui est également disponible au téléchargement au format PDF ici .

Cryptographie:

Le livre Foundations of Cryptography de Oded Goldreich ( Volume 1: Outils de base et Volume 2: Applications de base ) est un excellent livre sur le sujet. (Les premières versions sont disponibles sur la page d'accueil de l' auteur .) Une version abrégée de ce livre est également disponible.

Un autre excellent livre est Introduction à la cryptographie moderne: principes et protocoles de Katz & Lindell.

Pour ceux qui s'intéressent aux bases mathématiques de la cryptographie, Une introduction à la cryptographie mathématique de Hoffstein et al. est le choix naturel.

D'autres excellents livres sont:

• Manuel de cryptographie appliquée de Menezes et al. (Les chapitres sont disponibles en ligne ).
• Cryptographie: théorie et pratique par Stinson.

Sujets spécifiques:

• Livres relatifs à la composition avancée de protocoles de sécurité:
  • Composition de protocoles multipartites sécurisés: une étude approfondie réalisée par Lindell.
  • Connaissance zéro concurrente par Rosen.
• Preuves formelles dans les protocoles de sécurité
  • Correction formelle des protocoles de sécurité par Bella.
• [Mathématiques de la cryptographie à clé publique] ( http://www.amazon.com/Mathematics-Public-Cryptography-Steven-Galbraith/dp/1107013925 ) de Galbraith

Programmation fonctionnelle

• Structures de données purement fonctionnelles par Chris Okasaki . La plupart des livres sur les structures de données supposent un langage impératif tel que C ou C ++. Cependant, les structures de données de ces langages ne traduisent pas toujours bien en langages fonctionnels. Ce livre est l’une des meilleures expositions sur la mise en oeuvre de structures de données et d’algorithmes dans un langage fonctionnel.
• Programmation fonctionnelle: pratique et théorie par Bruce J. Maclennan . Malgré son nom, ce livre est davantage axé sur la théorie que sur la pratique. Ceux qui liront ce livre auront une bien meilleure vision du sujet que ceux qui l’apprendront grâce à une programmation ad hoc.
• Perles de l'algorithme fonctionnel Design by Richard Bird . Une toute nouvelle exposition sur le sujet, qui adopte l'approche problème-solution et montre la beauté du domaine en exposant des idées attrayantes dans la conception d'algorithmes fonctionnels.
• Programmation certifiée avec types dépendants par Adam Chlipala . C'est l'une des meilleures ressources pour l'apprentissage de Coq et elle s'intéresse plus particulièrement à l'automatisation de la certification de programmes et à la démonstration de théorèmes à l'aide de systèmes logiques / à base de règles. Les exemples sont nombreux et faciles à suivre.

Algorithmes d'approximation

Le livre Algorithmes d'approximation de Vazirani est le meilleur livre sur le sujet. Un autre livre est Algorithmes d'approximation pour NP-Hard Problems de Hochbaum.

Voici les comparaisons de deux critiques:

J'utilise le livre de Dorit Hochbaum sur les algorithmes d'approximation pour les problèmes NP-Hard comme guide pour mon travail. Le livre de Hochbaum est sans aucun doute formidable. Toutefois, le format de l’enquête a compromis le bon déroulement des opérations en vue de réunir les meilleurs spécialistes du domaine. Le livre de Vazirani corrige cela en étant si lisse et élégant du début à la fin. D'excellents ensembles de problèmes, d'excellents conseils pour la plupart des problèmes, et une section à la fin du livre est consacrée aux problèmes non résolus, ce qui est une fonctionnalité vraiment intéressante.

et

Je cherchais des livres sur la résolution approximative de problèmes NP-complets et NP-durs. Hochbaum a publié un autre livre que je possède également. Malheureusement, ce livre est davantage un livre de recherche, car il a été écrit par plusieurs chercheurs. C'est comme lire plusieurs rapports de recherche dans deux couvertures rigides. Cela signifie qu’il faut avoir une sorte de niveau d’expérience intermédiaire en algorithmes d’approximation.

Un livre récent est La conception d’algorithmes d’approximation par Williamson et Shmoys.

Combinatoire

Livres d'introduction. N'importe lequel des livres suivants peut constituer une excellente introduction au sujet:

• Manuel de mathématiques discrètes et combinatoires de Rosen.
• Mathématiques discrètes et combinatoires: Introduction appliquée de Grimaldi. Voir aussi le manuel de la solution .
• Parcours de la combinatoire et introduction à la combinatoire énumérative et introduction à la combinatoire énumérative de Bona. Le premier livre est plus complet que classique. Le deuxième livre se chevauche considérablement avec le premier, mais l'accent est mis davantage sur les méthodes de comptage modernes.
• Un cours de combinatoire par van Lint & Wilson.
• La combinatoire: thèmes, techniques, algorithmes de Cameron. (Ce livre a beaucoup de beaux exercices.)
• Problèmes combinatoires et exercices de László Lovász (réponse de @Sazzad)

Textes plus avancés.

• Combinatoire énumérative, volume 1 et volume 2 par Stanley. C'est simplement un chef-d'œuvre de la combinatoire énumérative; très difficile, très profond.
• Algorithmes combinatoires: génération, énumération et recherche par Kreher & Stinson. Plus adapté aux applications informatiques de la combinatoire.
• Combinatoire additive de Terence Tao et Van H. Vu. Une référence très utile face à un problème combinatoire lié à la théorie des nombres.

Combinatoire

Je veux citer Analytik Combinatorics , de Philippe Flajolet et Robert Sedgewick. Il fournit une base mathématique solide pour l'énumération et l'analyse d'algorithmes. Je tiens également à rendre hommage à Philippe Flajolet, grand mathématicien et informaticien décédé il y a deux jours.

Vérification du programme

• Théorie mathématique du calcul par Zohar Manna
• Principes de vérification des modèles par Christel Baier et Joost-Pieter Katoen
• Vérification des modèles par Edmund M. Clarke Jr., Orna Grumberg et Doron A. Peled
• Vérification des programmes séquentiels et concurrents de Krzysztof R. Apt, Frank S. de Boer et Ernst-Rüdiger Olderog
• Logique en informatique: modélisation et raisonnement sur les systèmes par M. Huth et M. Ryan

Théorie de l'information

Algorithmes de théorie de l'information, d'inférence et d'apprentissage par David MacKay

D'autres manuels célèbres sur la théorie de l'information sont disponibles sur Wikipedia .

Algorithmes distribués

Algorithmes distribués par Nancy Lynch Il s'agit d'un texte classique écrit par un pionnier de l'informatique distribuée;

Introduction aux algorithmes distribués par Gerard Tel Très bonne introduction, convient également aux cours de premier cycle; concentré sur le modèle de transmission de messages

Informatique répartie: principes fondamentaux, simulations et sujets avancés par Hagit Attiya et Jennifer Welch Ce manuel contient des matériaux avancés, adaptés aux cours de niveau doctoral; les modèles de transmission de messages et de mémoire partagée sont discutés

Conception et analyse d'algorithmes distribués De Nicola Santoro Un livre relativement récent, peut être utilisé aussi bien au premier cycle qu'au doctorat; les matériaux sont présentés avec une emphase sur la conception du protocole

L'informatique quantique

• Quantum Computation and Quantum Information de Nielsen et Chuang est un excellent ouvrage de référence , idéal pour ceux qui souhaitent faire de la recherche sur le terrain. Cependant, pour commencer, il est difficile d'apprendre, et ce n'est certainement pas pour les apprenants autonomes. Puisque le livre manque d’exemples travaillés, je suggère le livre suivant:

  • Problèmes et solutions en informatique quantique et informations quantiques par Steeb & Hardy . Ce livre contient de nombreux exemples, mais il n’est pas encore pour le débutant absolu. Pour commencer, le livre suivant est suggéré:

    • Approche de l'informatique quantique par Marinescu & Marinescu . Bien que élémentaire et facile à apprendre, certaines personnes le trouvent "rempli d'erreurs". À cet égard, l' errata du livre est pratique.

• L'informatique quantique depuis Democritus par Scott Aaronson . Un tour de force beaucoup plus que de l'informatique quantique, avec des relations avec la physique, la philosophie, etc.

Deux autres excellents livres d'introduction sur le sujet sont:

• L'informatique quantique pour les informaticiens par Yanofsky & Mannucci .
• Une introduction à l'informatique quantique par Kaye, Laflamme et Mosca .

Optimisation

J'ai aimé Paul Nahin Quand le moins est le meilleur.

Essentiellement une histoire mignonne d'optimisation à travers des problèmes et des personnalités. Il y a une belle critique aux pages 32 à 36 dans l'une des colonnes de Bill Gasarch.

$e^{i\pi} = -1$

Complexité de la communication:

C'est un livre classique et très bien écrit. Bien qu'un peu vieux maintenant, toujours le meilleur livre d'introduction sur le terrain. En outre, les exercices sont extrêmement amusants et vous sont donnés exactement après avoir expliqué les concepts afin que vous puissiez corriger ce que vous venez d'apprendre.

La partie de la complexité de la communication randomisée devrait être complétée par des parties du premier livre.

Complexité de la communication et calcul parallèle par Juraj Hromkovič.

Très complet, bien que parfois un peu difficile à lire. Les explications intuitives sont très claires et de très bons exercices. Dans la deuxième partie, il présente les connexions au calcul parallèle.

• Les livres de Matousek & Chazelle sur Discrepancy sont excellents.

  En fait, presque tous les livres de Matousek méritent d’être lus dans une certaine mesure.

• Les livres de Douglas West sur la théorie des graphes ( [1] et [2] ) sont bons.

• Alon & Spencer est également excellent.
• Pach & Agarwal est bon pour la géométrie discrète, tout comme Sharir & Agarwal si vous aimez les séquences DS.
• Le livre de Brass, Moser et Pach sur les problèmes ouverts en géométrie discrète est également très bon.
• Le livre de Vanderbei sur LP est très bon.
• Les livres de Schrijver ( [1] et [2] ) sont étonnants.

Algèbre Computationnelle

Comme Shiva l’a dit dans cette réponse , les littératures de ce domaine sont dispersées partout, sans terminologies communes. On peut trouver des références utiles en cherchant "calcul symbolique", "théorie de la complexité algébrique", "calcul formel" ou "calcul formel". Comme suggéré dans les réponses à cette question ,

• Algèbre informatique moderne de Joachim von zur Gathen et Jürgen Gerhard.
• Théorie de la complexité algébrique par Peter Bürgisser, Michael Clausen, Mohammad A. Shokrollahi et T. Lickteig.
• Algèbre algorithmique de Bhubaneswar Mishra.
• Une introduction informatique à la théorie des nombres et à l'algèbre de Victor Shoup.

Analyse computationnelle

Un domaine intéressant également, qui traite des calculs dans les fonctions réelles. Également appelé «analyse informatique» ou «calcul informatique».

• Analyse calculable par Oliver Aberth.
• Analyse calculable: une introduction de Klaus Weihrauch.

Combinatoire

Le Génération de fonctionnalité , par Herbert S. Wilf, est une excellente introduction à la théorie des fonctions de génération, écrite de manière fluide et riche en exercices. S'il écrit tous ses livres comme ça, j'ai hâte d'en commencer un autre.

La combinatoire énumérative de Richard Stanley est une excellente référence.

La combinatoire: sujets, techniques, algorithmes de Peter Cameron et Invitation à la mathématique discrète de Matousek et Nesetril sont de bonnes introductions à la combinatoire.

Applied Combinatorics de Roberts et Tesman est une référence de l’encyclopédie sur la combinatoire appliquée.

Logique:

Ceci est un compte rendu de ma réponse à cette question .

La connaissance de la logique mathématique de base est, à mon avis, un atout. Vous pouvez consulter les deux livres de Cori et Lascar.

Logique mathématique: un cours avec exercices, première partie

Logique mathématique: un cours avec des exercices, partie II

Écriture logique / preuve:

1. Comment le prouver: une approche structurée de Daniel J. Velleman

La théorie du nombre

J'ai trouvé plusieurs livres fréquemment cités dans de nombreux journaux. Ils sont excellents sur le sujet, mais certains sont assez vieux. Voici une liste de ce dont je me souviens:

• Une introduction à la théorie des nombres de Hardy et al. Hardy est un mathématicien britannique renommé. Il était le mentor du mathématicien indien Ramanujan . Sa contribution au domaine de la théorie des nombres est assez étonnante .
• Une introduction à la théorie des nombres par Niven, Zuckerman, Montgomery. Une autre introduction classique sur le terrain.
• Problèmes résolus et non résolus dans la théorie des nombres par Shanks. Ceci est le livre pour ceux qui cherchent encore à conjectures-être éprouvées dans le domaine.
• La fonction zêta de Riemann par Edwards. Une partie importante de la théorie des nombres moderne, ainsi que plusieurs algorithmes probabilistes pour les tâches de la théorie des nombres, sont fondés sur l'hypothèse (étendue) de Riemann décrite dans ce livre.

Hypergraphes

Il n'y a pas beaucoup de livres consacrés exclusivement aux hypergraphes. Un tel livre est

Berge C. Hypergraphs: combinatoire des ensembles finis .

Théorie de la preuve

Le livre Basic Proof Theory de Troelstra et Schwichtenberg est le texte de facto sur le sujet.

Le livre Proofs and Types de Girard, Taylor & LaFont est un livre plus court sur le sujet. Une version est disponible en téléchargement à l' adresse http://www.paultaylor.eu/stable/Proofs%2BTypes.html.

La théorie des graphes

Pour introduction à la théorie des graphes: Introduction à la théorie des graphes par West

En savoir plus sur la théorie des graphes: Théorie des graphes par Bondy et Murty

Le livre complet qui contient de nouveaux développements ainsi que d'anciens résultats classiques en théorie des graphes:

Théorie des graphes: Reinhard Diestel .

Pour les graphiques sur des surfaces avec une approche combinatoire:

Graphes Sur Surfaces

Et pour les digraphes:

Digraphes: théorie, algorithmes et applications

Conception VLSI

Je ne suis pas dans le matériel. Cependant, comme la FAQ inclut VLSI comme l’un des sous-domaines de TCS, j’ai interrogé un expert sur des livres célèbres dans la conception de VLSI. Les voici:

• Circuits intégrés numériques
• Conception CMOS VLSI: perspective des circuits et des systèmes
• Conception VLSI moderne: Conception IP