Références

Thèmes

Commentaires

Franz Baader et Tobias Nipkow : Term Rewriting and All That
La référence sur la réécriture. En outre, il est tout simplement excellent et sa lecture est des plus agréables. À lire !
Développements : Newman, Paires critiques, unification
Leçons : 920, 919

Jean-Michel Autebert : Calculabilité et décidabilité

Aucun développement.
Leçon : 914

René Cori et Daniel Lascar : Logique mathématique

Développements : complétude, lecture unique, compacité par la topologie + complétude de la coupure
Leçons : 916, 917, 918

Martin Davis, Ron Sigal et Elaine J. Weyuker : Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science
Titre explicite sur son contenu. Contient SAT (voir le Wolper aussi), mais aussi et surtout, l'algorithme de Davis-Putnam.
Développement : davis-puttnam
Leçon : 915

Patrick Dehornoy : Mathématiques de l'informatique

Développements : ackermann, castor
Leçons : 912, 913

Alfred Aho, Ravi Sethi et Jeffrey Ullman : Compilateurs : principes, techniques et outils
Son nom est très explicite. Considéré comme étant la référence dans le domaine. Son surnom, le « dragon », provient de son dessin de couverture, où il y est figuré un chevalier, concepteur de compilateurs, face au dragon qu'est la conception de compilateurs. Nous conseillons la lecture du Wilhelm-Maurer auparavant.
Aucun développement.
Leçons : 923, 924, 925

René Lalement : Logique, réduction, résolution

Aucun développement.
Leçons : 916, 917

Michael R. Garey et David S. Johnson : Computers and Intractability: A Guide to the Theory of NP-Completeness
La référence historique en le domaine. Il contient une grande liste de problème NP-complets, mais sans leur démonstration.
Aucun développement.
Leçon : 915

Richard Lassaigne et Michel de Rougemont : Logique et fondements de l'informatique
Bon livre. Lecture fortement conseillée. Ce livre a une suite qui parle de complexité et qui s'intitule « Logique et complexité ».
Développements : complétude, compacité par la topologie + complétude de la coupure
Aucune leçon.

Jacques Stern : Fondements mathématiques de l'informatique

Développements : MT-cal => µ-rec, prolog famille
Leçons : 912, 913, 915, 916, 917

Richard Lassaigne et Michel de Rougemont : Logique et complexité
Bien que son titre comporte le mot « logique », il s'agit bien d'un livre sur la complexité. Ce livre est le second tome d'une suite de deux livres (en logique).
Aucun développement.
Leçons : 915, 916, 917

Reinhard Wilhelm et Dieter Maurer : Les compilateurs : théorie, construction et génération
Un autre livre sur la compilation. De bonne qualité. Nous le conseillons en tant que première lecture en compilation.
Développements : exemple d'analyse lexicale, langages LL, gen code pascal appel fonction, gen code Prolog
Leçons : 921, 923, 924, 925

Glynn Winskel : The Formal Semantics of Programming Languages
Aucune autre référence dans le domaine.
Développements : point fixe + exemple, hoare, exemple Hoare
Aucune leçon.

Pierre Wolper : Introduction à la calculabilité

Développements : SAT, RE ⇔ type 0
Leçons : 912, 913, 914

David Gries : The Science of Programming
Un livre sur une sémantique des langages de programmation. Ce livre fait suite à la «crise dedu génie logiciel». Un peu vieillot et désuet par certains côtés, néanmoins il est parfaitement d'actualité sur le fond. Il y est enseigné comment bien programmer, comme utiliser la logique pour prouver ses programmes (sémantique WLP [weakest liberal precondition] des programmes). Livre très intéressant. Ce qu'il faut en retenir essentiellement, c'est que plutôt que de prouver chaque programme, ce qui se révèlerait très lourd et on ne convaincrait certainement pas tous les « anti-maths », c'est de bien commenter son programme et ne pas hésiter à utiliser préconditions, post-conditions et conditions dans un programme ; en C, cela revient à décorer son code avec la macro «assert».
Aucun développement.
Aucune leçon.

Andrew W. Appel : Modern Compiler Implementation in (ML|C|Java)
Un autre livre sur la compilation. Il y a une version du livre selon le langage à partir duquel on veut écrire un compilateur. Il est conseillé de lire d'abord le Wilhelm-Maurer.
Aucun développement.
Aucune leçon.

Steven S. Muchnick : Compiler Design Implementation
Un pavé de plus d'un millier de pages sur la compilation. Décrit comment implémenter un véritable compilateur, par opposition aux « toy » compilateurs et autres qui sont à destination pédagogique. Lire le Wilhelm-Maurer auparavant.
Aucun développement.
Aucune leçon.

V.A. Ouspenski : Leçons sur les fonctions calculables
Livre non trivial sur les fonctions récursives. Difficilement lisible du fait de sa structure bourbakiste (« dém: corollaire de la prop 3.4.2.8 et du thm 2.4.9 »). Ce livre est plutôt rare et pas facile à trouver. Il date de 1966, ce qui pose le problème de l'ISBN : il n'en a pas. Le nom exact de l'auteur est Vladimir Andreevich Uspensky. Il fut un thésard de Kolmogorov et actuellement a repris la tête du «Department of Mathematical Logic and Theory of Algorithms» de l'université d'état de Moscou, position tenu jusqu'alors par Kolmogorov.
Aucun développement.
Aucune leçon.

Bruno Petazzoni : Seize problèmes d'informatique
Livre intéressant. Comme son titre l'indique, il s'agit de problèmes corrigés. Il parle, entre autres, de langage formel, d'automate fini, de distance de Hamming, théorème de Higmann, etc.
Développement : higman
Aucune leçon.

Michael L. Scott : Programming Language Pragmatics
Un autre livre traitant de la compilation.
Aucun développement.
Aucune leçon.

Matthias Felleisen, Robert Bruce Findler, Matthew Flatt et Shriram Krishnamurthi : How to Design Programs
Un excellent livre. Il enseigne comment «bien» programmer. Il n'est pas a priori indispensable, mais en fait il l'est. Car, comme cela est très bien dit dans ce livre, la programmation, ce n'est pas le bête alignement de lignes de code, mais la suite de plusieurs étapes successives et réfléchies, permettant une meilleure organisation du programme (donc un meilleur entretien et une capacité à passer à la grande échelle, etc.), une meilleur lisibilité (donc lisible plusieurs mois après, lisible par d'autres, possibilité de travailler à plusieurs, etc.), travailler par raffinement successif (définition avant des spécifications), etc. Il y est vraiment expliqué ce qui entendu par « programmation 'top-down' » (on doit d'abord spécifier ce que l'on veut faire [analyse du programme], le programme doit toujours fonctionner, faire des points de contrôles [« releases », livraisons] etc.), abstraire, factoriser, pas de redondance, ne pas copier/coller, ne jamais programmer par effet de bords (« side-effect »), etc.
Aucun développement.
Aucune leçon.

Benjamin C. Pierce : Basic Category Theory for Computer Scientists
Les catégories ne sont pas un passage obligé pour l'agrégation. Ce livre présente la théorie des catégories. Bien que mince, les sujets et exemples traités sont nombreux et intéressants.
Développement : sûreté bien typé
Aucune leçon.

Christian Queinnec : Principes d'implantation de Scheme et Lisp
La référence pour comprendre marche un compilateur Scheme/Lisp, ou pour créer le sien. À mettre entre (presque) toutes les mains. Titre de l'édition originale : Les langages Lisp Titre de l'édition américaine (en langue anglaise) : Lisp in Small Pieces
Aucun développement.
Aucune leçon.

Gerald M. Weinberg : The Psychology of Computer Programming
Une autre référence pour apprendre à bien programmer. Avant ce livre, il est conseillé de lire How to Design Programs.
Aucun développement.
Aucune leçon.

Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein : Introduction à l'algorithmique
Ouvrage complet.
Développements : dijkstra, CFC, tri rapide/fusion, hauteur moyenne ABR, PLSSC, PPLP, tri par tas, rouge-noir, tri bitonique, FW
Leçons : 901, 902, 903, 904, 905, 906

Luc Albert, Paul Gastin, Bruno Petazzoni : Cours et exercices d'informatique : classes préparatoires, 1er et 2nd cycles universitaires

Développements : tri rapide/fusion, hauteur moyenne ABR
Leçon : 902

D. Beauquier, J. Berstel, Ph. Chrétienne : Eléments d'algorithmique

Développements : Moris-Pratt, AVL
Leçons : 905, 906, 907

C. Froidevaux, M.-C. Gaudel et M. Soria : Types de données et algorithmes

Aucun développement.
Leçon : 906

Jean-Daniel Boissonnat et Mariette Yvinec : Géométrie algorithmique

Développement : convex hull
Aucune leçon.

Jacques Sakarovitch : Éléments de théorie des automates

Développements : langages minces, étoile par blocs
Leçons : 908, 909

Robert Floyd, Richard Beigel : Le langage des machines : introduction à la calculabilité et aux langages formels

Développements : langages ND, séparation automate, CYK
Aucune leçon.

Diestel Reinhard : Graph Theory

Aucun développement.
Aucune leçon.

Jean-François Rey : Calculabilité, complexité et approximation

Développement : complémentaire algébrique
Leçons : 912, 913

Foulard, Flaus, Jacomino : Automatique pour les classes préparatoires

Aucun développement.
Aucune leçon.

Michael Huth et Mark D. Ryan : Logic in Computer Science : Modelling and Reasoning about Systems

Aucun développement.
Aucune leçon.

Gabriel Peyré : L'algèbre discrète de la transformée de Fourier

Aucun développement.
Aucune leçon.

Références

Thèmes

Algorithmique

Langages formels

Calculabilité

Logique

Réécriture

Langages de programmation

Compilation

Autre

Commentaires