Quels livres chacun devrait-il lire?

229

[ 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:

MS Dousti
la source
Puisque je ne peux pas répondre à la question, je le ferai ici. Mathématiques discrètes - TTC: Mathématiques discrètes par Arthur T. Benjamin. Il s'agit d'un ensemble de conférences sur divers sujets allant de la théorie des ensembles à la graphique et à la probabilité.
Pithikos
Peut-être est-il intéressant de comparer cette liste d'ouvrages remarquables à celle d'introduction du livre? Existe - t-il une liste des manuels d'introduction canoniques couvrant les principales branches de l'informatique? question sur reddit / compsci. Il y a un certain chevauchement, mais heureusement les différences sont suffisamment significatives.
Thomas Klimpel

Réponses:

91

Complexité informatique:

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

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:

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:

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 .

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.

Mohammad Al-Turkistany
la source
2
Pour ceux qui s'intéressent à la comparaison de ces livres, je peux également vous proposer cette revue de livre sur Arora / Barak et Goldreich que j'ai récemment écrite pour la chronique de critique de livre SIGACT.
Daniel Apon
1
Voir aussi la liste de Lance Fortnow de ses livres préférés sur la complexité informatique sur Amazon: amzn.com/l/22R1UX0Y9YRT2
Alessandro Cosentino
5
Le seul commentaire sur le livre de Sipser est qu'il utilise parfois des noms non standard pour couvrir la théorie de la calculabilité. Par exemple, il utilise "reconnaissable" au lieu de "semi-décidable". Mais je suppose que puisque le manuel est si largement utilisé, il pourrait bien devenir la norme maintenant.
Dai Le
4
En fait, c’est un excellent commentaire en général, @Dai Le. Je peux penser à des différences similaires entre Goldreich et Arora / Barak. Par exemple, Goldreich utilise le nom et Arora / Barak utilise le nom , bien qu'ils parlent tous deux du même concept. F N PPCFNP
Daniel Apon
1
J'ai trouvé Sipser bien plus utile que Papadimitriou pour enseigner la théorie de la complexité, ymmv.
Jeff Burdges
49

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.

Sadeq Dousti
la source
6
Toujours la meilleure introduction à la théorie de la complexité après 30 ans.
Emil
1
Après des décennies, ce livre est toujours la liste la plus complète des problèmes complets de NP dans un endroit, apparemment, presque une encyclopédie, et de nombreux chercheurs de cs semblent partager ce point de vue
vzn
1
recommander que ceci soit ajouté à la FAQ pour une question générale, "mon problème X NP est-il complet?" avec réponse, "1ère vérification de ce livre 1 er puis retournez-nous"
2012 à 04:29
47

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)

Nikita Zhiltsov
la source
7
"Une introduction à l'analyse des algorithmes" de Sedgewick et Flajolet est formidable.
Jay
Daniel Spielman utilise le livre de Kleinberg et Tardos dans son cours "Conception et analyse d'algorithmes". Je l'ai pris et j'ai vraiment aimé le livre. Je l'ai trouvé beaucoup plus abordable que le CLRS.
Alex Reinking
41

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.

Dave Clarke
la source
7
Pour une perspective plus mathématique de la théorie des types, "Conférences sur l'isomorphisme de Curry-Howard" de Sorensen et Urzyczyn est un bon début, offrant une bonne vue d'ensemble des lambda-calculs dactylographiés jusqu'au calcul des constructions, et au-delà.
Dominic Mulligan
4
Je suggérerais les Fondements pour les langages de programmation de John Mitchell sur ce sujet. Comme dans le commentaire précédent, il est plus mûr mathématiquement.
Artem Pelenitsyn
2
Vote positif pour TAPL. FYI Benjamin Pierce est l'un des auteurs d'un nouveau livre "Software Foundation" qui utilise le Coq.
Kunjan Kshetri
40

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:

Sadeq Dousti
la source
1
Si je peux ajouter un lien vers quelque chose que j'ai moi-même recueilli (à partir de nombreuses sources différentes, y compris certaines des réponses
László Kozma
1
Hardy, Littlewood, Polya, "Inégalités", un joyau des années 1930 (?)
kodlu
38

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.

temps
la source
4
Le TAOCP est toujours d'actualité et Vol. 4A vient de sortir.
dbasnett
33

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:

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:

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?"

CVCVCC

PVPV

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

PV0

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.

Dai Le
la source
32

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 .

Hsien-Chih Chang 之
la source
3
Ce livre a été suggéré dans un autre sujet (je pense par Suresh). Je l'ai trouvé excellent. Merci à Aaron de le mentionner ici.
MS Dousti
29

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:


Sujets spécifiques:

Sadeq Dousti
la source
2
Depuis leur introduction en 1993, les oracles aléatoires ont été largement utilisés dans la littérature; spécialement dans les schémas de signature. Je ne connais pas de livre couvrant ce domaine de manière appropriée. Les suggestions sont les bienvenues.
MS Dousti
1
Un livre sur des oracles aléatoires serait d' une grande aide. Je ne travaille pas en crypto, mais j'ai lu Katz / Lindell avant-arrière. La transition de la littérature de manuel à la littérature cryptographique a été rude à cause de cette raison spécifique. Aussi, @Sadeq, par curiosité: l'un des livres que vous avez lu couvre-t-il bien le rembobinage?
Daniel Apon
1
@Daniel: La thèse de Martin Gagné "Une étude du modèle d'oracle aléatoire" (UC Davis, 2008) est une référence relativement bonne sur les oracles aléatoires (bien que loin d'être complète). En ce qui concerne la question du "rembobinage": je ne connais pas de livre à ce sujet, mais je pense l'avoir complètement compris. Pourriez-vous préciser quelle partie vous semble problématique? Vous pouvez même le demander sur un sujet séparé.
MS Dousti,
@Sadeq, je suis enclin à ne pas poser de question indépendante à ce sujet, car cela ne représenterait guère plus que "Aide, qu'est-ce que le rembobinage?" :) La partie problématique est que le rembobinage ne figurait pas dans le manuel utilisé dans le cours de cryptographie que j'ai suivi (par exemple Katz / Lindell), je n'ai donc jamais vu d'introduction au concept. Je suis conscient que cela apparaît régulièrement dans la littérature cryptographique, mais en tant que personne qui ne participe pas activement à la recherche cryptographique, je doute que je lise assez de papier pour acquérir une solide compréhension du rembobinage simplement en le rencontrant suffisamment. Je pourrais peut-être poser une question sur les origines du rembobinage ...
Daniel Apon
3
@ Daniel: L'introduction de mon livre sur la connaissance zéro concurrente explique le rebobinage et les difficultés induites par celui-ci dans le contexte de la composition du protocole. Les autres sources sont les suivantes: (1) Oded Goldreich, Hugo Krawczyk: sur la composition des systèmes de preuve du zéro. SIAM J. Comput. 25 (1): 169-192 (1996) et (2) Cynthia Dwork, Moni Naor et Amit Sahai: Connaissance zéro simultanée. J. ACM 51 (6): 851-898 (2004).
Alon Rosen
25

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.
Sadeq Dousti
la source
21

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.

Sadeq Dousti
la source
21

Combinatoire

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

Textes plus avancés.

Sadeq Dousti
la source
21

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.

Lamine
la source
20

Vérification du programme

Chan Li
la source
1
Certains livres (Manna et Apt et al.) Sont assez datés (Manna date de 1977 et Apt et al 1991), le domaine de la vérification de programme basée sur la logique a connu des progrès majeurs au cours de la dernière décennie. Hélas, il n'y a pas de texte à jour disponible.
Martin Berger
@MartinBerger Avez-vous une idée de l'endroit où cette avancée majeure pourrait être apprise, si ce n'est dans aucun manuel récent?
Mitch
@Mitch Je crains que cela n'ait pas encore été écrit dans les manuels. Peut-être regardons-nous une partie de la littérature sur les outils interactifs comme Isabelle / HOL et Coq. Examinez également les outils de vérification automatique récents tels que "déduire" de Facebook et la théorie qui le sous-tend.
Martin Berger
Huth & Ryan est très convivial pour les débutants. Pour quelqu'un qui n'est pas très familier avec toutes les mathématiques rigoureuses de CS, c'est un bon début. C'est le premier livre que j'ai lu sur le côté formel de CS et je suis devenu accro depuis! C'est aussi le premier manuel que j'ai effectivement terminé toutes les lectures.
RexYuan
19

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 .

Sadeq Dousti
la source
Le titre est "Quels livres faut-il lire?", La recommandation doit donc être sélective. Tout le monde peut trouver une grande liste de livres sur la "théorie de l'information" sur Amazon / library, mais si vous n'avez que 2 ou 3 choix, quels seront-ils? Vous ne devriez recommander que des livres ou des articles que vous avez lus avec beaucoup d'attention et précisez dans vos favoris!
Dai Le
1
@ Dai Le: Vous avez raison. Je pense que la liste devrait être réduite. (Je suis personnellement responsable du ballonnement de la liste!) Cependant, ceci est un post wiki de la communauté . J'ai ajouté une longue liste proposant ce que sont les candidats. Veuillez couper la liste pour inclure uniquement les livres les plus appropriés.
MS Dousti
1
@Sadeq: J'ai bien peur qu'il soit rare qu'une personne réduise la liste d'une autre personne. Tant que le message est toujours dans sa forme actuelle, cela n'a aucune valeur en ce qui concerne le but du message.
Dai Le
@ DAI: Vous avez raison. Mais comme je ne suis pas un expert en "théorie de l'information", je ne peux pas couper la liste moi-même. Je peux: 1) supprimer complètement la liste que j'ai ajoutée (en laissant la liste d'origine) ou 2) ajouter une notification dans le texte pour attirer l'attention d'un expert. Que suggérez-vous?
MS Dousti
@Sadeq: Je ne travaille pas non plus sur la théorie de l'information, sinon j'aiderais à réduire la liste. Je sais que le livre "Thomas M. Cover, Joy A. Thomas. Eléments de la théorie de l'information" est recommandé par beaucoup, y compris Lance Fortnow. Mais je ne suis pas sûr que tout le monde devrait le lire ou non. Je pense que nous devrions respecter l'affiche originale car le livre pourrait être son préféré. Donc, supprimer toute la liste est une bonne option. Je m'excuse vraiment d'être trop simple. Aussi, pourriez-vous demander aux gens d'expliquer pourquoi ils suggèrent leurs livres?
Dai Le
19

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

Massimo Cafaro
la source
19

L'informatique quantique

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

Sadeq Dousti
la source
17

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.

eiπ=1

Mugizi Rwebangira
la source
17

Complexité de la communication:


La complexité de la communication par Eyal Kushilevitz et Noam Nisan.

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.

Marcos Villagra
la source
16
Hsien-Chih Chang 之
la source
Analyse des fonctions booléennes , par Ryan O'Donnell (2014) , est un autre outil idéal pour l'analyse de Fourier booléenne (comme le titre l'indique) et couvrant à la fois les bases, des sujets plus avancés et (beaucoup) d'applications . Il est disponible en ligne librement ici aussi.
Clement C.
16

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 ,

Analyse computationnelle

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

Hsien-Chih Chang 之
la source
16

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.

Jay
la source
14

Écriture logique / preuve:

  1. Comment le prouver: une approche structurée de Daniel J. Velleman
Sazzad Bin Kamal
la source
3
Comment cela se compare-t-il à "Comment le résoudre" de G. Polya? Je crois avoir lu les conseils que Polya est l'original et beaucoup mieux, mais je ne suis pas sûr et ne peut pas refind sur les interwebs;)
DaveBall alias user750378
2
"Comment le résoudre" de Polya (HTSI) aborde un sujet différent de celui de Velleman. Polya est une sorte de rumination sur la façon de trouver des solutions à des problèmes difficiles, tandis que Velleman est un manuel sur la façon de formaliser des solutions en utilisant les conventions et le langage des mathématiques. HTSI possède des informations sur les preuves, mais elles sont présentées sous la forme d'un "glossaire" sans structure, alors que Velleman vous présente un programme systématique avec des exercices. Les deux méritent d'être lus, mais l'un ne remplace pas l'autre.
Nate CK
13

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:

Sadeq Dousti
la source
Que pensez-vous du livre de Rosen ou des réimpressions de Dover?
Marc C
@ Mark: Ils sont bons aussi. Pourquoi ne pas éditer le message et ajouter ces livres également?
MS Dousti
11

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

heure
la source
1
Il y a aussi The Theory of Graphs de Claude Berge, l'un des fondateurs de la théorie des graphes. Et Graphes et algorithmes de Michel Minoux et Michel Gondran.
Lamine
9

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:

M.S. Dousti
la source
Dans ce domaine, je recommanderais ce livre extrêmement lisible: Synthèse et optimisation de circuits numériques de Giovanni De Micheli
Chan Li