Utilisateur : sieghttct
Développements
Papadimitriou pour 2-SAT, Cormen pour CLIQUE.
Références :
Computational complexity - Papadimitriou
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Développement : Construction d'un AFD reconnaissant une expression rationnelle
Carton en donne une version naïve (AFN puis déterminisation), qui montre seulement le résultat théorique, mais le développement devient intéressant si l'on calcule directement un AFD pas trop énorme, ce que font Aho et al.
Références :
Pour Tykhonoff dénombrable, on pourra voir chez Queffélec.
Le PDF ci-joint, dû à Benjamin Dadoun (que je remercie !), donne la preuve du théorème de compacité et deux applications classiques.
Références :
Références :
Références :
Cours de calcul formel. Corps finis, systèmes polynomiaux, applications - Philippe Saux Picart, Eric Rannou
Références :
Oraux X-ENS Algèbre 2 - Francinou, Gianella, Nicolas
Références :
Références :
Calcul intégral - Candelpergher
Références :
Analyse - Gourdon
Références :
Logique et fondements de l'informatique - Rougemont, Lassaigne
The Lambda Calculus. Its Syntax and Semantics - Henk Barendregt
Classical Recursion Theory - Piergiorgio Odifreddi
Le programme ne parle que de $\lambda$-calcul pur, ça peut donc paraître étonnant de mettre du typage ici. Néanmoins, le typage d'un terme est une méthode efficace pour prouver qu'il est (fortement) normalisant ! C'est l'intérêt du théorème rappelé en début de développement.
Pour la leçon 923, le rapport 2017 rappelle aussi qu'on peut introduire des bouts d'analyse sémantique, cet algo y trouve donc aussi toute sa place.
Références :
Lectures on the Curry-Howard Isomorphism - M. H. Sørensen, P. Urzyczyn
Term rewriting and All That - Franz Baader
Références :
The formal semantics of programming langages - Winskel
On propose aussi une adaptation de l'algo pour rechercher (sans trop de finesse) les facteurs d'un mot $w$ à distance d'édition au plus $k$ de $w$.
Références :
Algorithms on string - Crochemore, Hancart et Lecroq
À présenter tranquillement, en agitant beaucoup les mains...
Références :
Semantics with Applications: An Appetizer - H. R. Nielson, F. Nielson
Références :
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Leçons
Références :
Types de données et algorithmes - Christine Froidevaux, Marie-Claude Gaudel, Michèle Soria
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Eléments d'algorithmique - Beauquier, Berstel et Chrétienne
Références :
A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis - Anne Benoît, Yves Robert, Frédéric Vivien
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Références :
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Références :
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
An Introduction to the Analysis of Algorithms - Robert Sedgewick, Phillipe Flajolet
Références :
Algorithms on string - Crochemore, Hancart et Lecroq
Eléments d'algorithmique - Beauquier, Berstel et Chrétienne
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Références :
Langages formels, Calculabilité et Complexité - Carton
Mathématiques de l'informatique - Dehornoy
Références :
Langages formels, Calculabilité et Complexité - Carton
Mathématiques de l'informatique - Dehornoy
Logique mathématique Tome 2 - René Cori, Daniel Lascar
Logique et fondements de l'informatique - Rougemont, Lassaigne
Références :
Introduction to the theory of computation - Sipser
Langages formels, Calculabilité et Complexité - Carton
Computational complexity - Papadimitriou
Références :
Introduction to the theory of computation - Sipser
Langages formels, Calculabilité et Complexité - Carton
Références :
Introduction to the theory of computation - Sipser
Computational Complexity: A Modern Approach - Sanjeev Arora, Boaz Barak
Computational complexity - Papadimitriou
Références :
Logique mathématique Tome 1 - René Cori, Daniel Lascar
Logique et fondements de l'informatique - Rougemont, Lassaigne
Computational Complexity: A Modern Approach - Sanjeev Arora, Boaz Barak
Computational complexity - Papadimitriou
Topologie - Queffelec
Références :
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Compilers - Aho, Ullman, Lam, Sethi
Algorithms on string - Crochemore, Hancart et Lecroq
Types de données et algorithmes - Christine Froidevaux, Marie-Claude Gaudel, Michèle Soria
Références :
Compilers - Aho, Ullman, Lam, Sethi
Langages formels, Calculabilité et Complexité - Carton
Références :
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
Eléments d'algorithmique - Beauquier, Berstel et Chrétienne
Types de données et algorithmes - Christine Froidevaux, Marie-Claude Gaudel, Michèle Soria
Références :
Types de données et algorithmes - Christine Froidevaux, Marie-Claude Gaudel, Michèle Soria
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis - Anne Benoît, Yves Robert, Frédéric Vivien
Eléments d'algorithmique - Beauquier, Berstel et Chrétienne
Références :
Cours et exercices d'informatique - Albert
A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis - Anne Benoît, Yves Robert, Frédéric Vivien
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
The formal semantics of programming langages - Winskel
Semantics with Applications: An Appetizer - H. R. Nielson, F. Nielson
Références :
Computers and intractability - Garey, Johnson
Introduction à l'algorithmique - Thomas H. Cormen, Charles E. Leiserson, Clifford Stein, Ronald Rivest
A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis - Anne Benoît, Yves Robert, Frédéric Vivien
Références :
Logique et fondements de l'informatique - Rougemont, Lassaigne
Lectures on the Curry-Howard Isomorphism - M. H. Sørensen, P. Urzyczyn
The Lambda Calculus. Its Syntax and Semantics - Henk Barendregt