AgregmathKL - Contributions de l’utilisateur [fr]

Fichier:Dvt terminaison.pdf

2015-03-31T13:21:50Z

Frédéric Valet :

Indécidabilité de la terminaison d'un système de réécriture

2015-03-31T13:21:29Z

Frédéric Valet : Page créée avec « On montre que le problème de la terminaison d'un système de réécriture est indécidable. ==Développement== *24px Média:dvt_termi... »

On montre que le problème de la terminaison d'un système de réécriture est indécidable.

==Développement==
*[[Fichier:Pdf.png|alt=Tex|link=|24px]] [[Média:dvt_terminaison.pdf | Indécidabilité de la terminaison d'un système de réécriture.]]

==Référence==

Baader Nipkow, Term rewriting and all that.

== Recasements ==
* [[913 -- Machines de Turing. Applications.]]
* [[914 -- Décidabilité et indécidabilité. Exemples.]]
* [[920 -- Réécriture et formes normales. Exemples.]]
* [[922 -- Ensembles récursifs, récursivement énumérables. Exemples.]]

[[Category: Développement de la leçon 913]]
[[Category: Développement de la leçon 914]]
[[Category: Développement de la leçon 920]]
[[Category: Développement de la leçon 922]]

Développements par thèmes

2015-03-31T13:15:31Z

Frédéric Valet : /* Décidabilité & Calculabilité */

Cette page liste tous les développements présents sur le site, triés par thèmes. Les doublons sont autorisés et même conseillés dans la mesure où la plupart des théorèmes sont à cheval entre plusieurs domaines.

Il est donc explicitement demandé à ceux qui ajoutent un développement de le faire apparaitre dans '''toutes''' les parties qui le concernent.

(le choix des découpages est arbitraire, toute modification éclairée est la bienvenue).

Si vous préférez vous pouvez toujours vous dépêtrer avec le fouillis de la permière version de cette page : [[Développements]].

= Algèbre =

=== Algèbre linéaire, bilinéaire, réduction d'endomorphismes ===
* [[Action du groupe modulaire sur le demi-plan de Poincaré]]
* [[Algorithme des facteurs invariants]]
* [[Commutant d'un endomorphisme]]
* [[Lemme de Morse ]]
* [[Convergence d'une suite de polygônes vers l'isobarycentre]]
* [[Décomposition de Bruhat]]
* [[Décomposition de Dunford]]
* [[Diagrammes de Young et réduction de Jordan]]
* [[Ellipsoïde de John-Lœwner]]
* [[Endomorphismes cycliques, invariants de similitude et réduction de Frobenius]]
* [[Formes de Hankel]]
* [[Isomorphisme entre M_n(K) et son dual]]
* [[Lemme de Morse]]
* [[Nombre de matrices diagonalisables sur Fq]]
* [[Orthodiagonalisation des endomorphismes auto-adjoints]]
* [[Points extrémaux de la boule unité de L(E) ]]
* [[Réduction des matrices normales]]
* [[Sous-espaces de C(R,C) de dimension finie stables par translations]]
* [[Sous-groupes compacts de GL_n | Sous-groupes compacts de <math>GL_n</math>]]
* [[Surjectivité de l'exponentielle matricielle]]
* [[Théorème de Burnside]]
* [[Théorème de Cartan-Dieudonné]]
* [[Théorème de Frobenius-Zolotarev]]
* [[Théorème de Molien]]
* [[Un homéomorphisme réalisé par l'exponentielle matricielle]]
* [[Une méthode itérative de résolution de systèmes linéaires]]

=== Anneaux, arithmétique, dénombrement ===
* [[Algorithme des facteurs invariants]]
* [[Automorphismes de ZnZ | Automorphismes de <math>\mathbb{Z}/n\mathbb{Z}</math>]]
* [[Borne de Bézout]]
* [[Décomposition de Dunford]]
* [[Équation de Fermat pour n=3]]
* [[Groupes d'ordre pq]]
* [[Nombres de Bell]]
* [[Nombre de matrices diagonalisables sur Fq | Nombre de matrices diagonalisables sur <math>\mathbb{F}_q</math>]]
* [[Partitions d'un entier en parts fixées]]
* [[Primalité des nombres de Mersenne]]
* [[Probabilité que deux entiers soient premiers entre eux]]
* [[Sous-groupes finis de SO(3)]]
* [[Théorème de Gauß pour les polygones réguliers constructibles]]
* [[Théorème de Kronecker]]
* [[Théorème de Rothstein-Trager]]
* [[Théorème des deux carrés]]
* [[Une version faible du théorème de Dirichlet]]

=== Géométrie ===
* [[Action du groupe modulaire sur le demi-plan de Poincaré]]
* [[Classification des groupes de pavage du plan]]
* [[Convergence d'une suite de polygônes vers l'isobarycentre]]
* [[Ellipse de Steiner]]
* [[Groupe circulaire]]
* [[Inégalité isopérimétrique]]
* [[Isométries du cube]]
* [[Le folium de Descartes]]
* [[Le paradoxe de Banach-Tarski]]
* [[Points extrémaux de la boule unité de L(E)]]
* [[Simplicité de SO(3)]]
* [[Sous-groupes finis de SO(3)]]
* [[Théorème de Caratheodory]]
* [[Théorème de Cartan-Dieudonné]])
* [[Théorème de Gauß pour les polygones réguliers constructibles]]
* [[Théorème de Hahn-Banach]]
* [[Théorème de Jordan]]
* [[Théorème de Krein-Milman]]
* [[Théorème des quatre sommets]]

=== Théorie des corps, irréductibilité, primalité ===
* [[Irréductibilité des polynômes cyclotomiques]]
* [[Loi de réciprocité quadratique]]
* [[Polynômes irréductibles sur Fq]]
* [[Primalité des nombres de Mersenne]]
* [[Théorème de Chevalley-Warning]]
* [[Théorème de d'Alembert-Gauss]]
* [[Théorème de Gauß pour les polygones réguliers constructibles]]
* [[Théorème de Kronecker]]
* [[Théorème de l'élément primitif]]
* [[Théorème de Wedderburn]]

=== Théorie des groupes ===
* [[Action du groupe modulaire sur le demi-plan de Poincaré]]
* [[Automorphismes de ZnZ]]
* [[Décomposition de Bruhat]]
* [[Groupes d'ordre 12]]
* [[Isométries du cube]]
* [[Le paradoxe de Banach-Tarski]]
* [[Loi de réciprocité quadratique]]
* [[Nombre de matrices diagonalisables sur Fq | Nombre de matrices diagonalisables sur <math>\mathbb{F}_q</math>]]
* [[Simplicité de An | Simplicité de <math>\mathfrak{A}_n</math> ]]
* [[Simplicité de SO(3) | Simplicité de <math>\mathcal{SO}(3)</math>]]
* [[Sous-groupes compacts de GL_n | Sous-groupes compacts de <math>GL_n</math>]]
* [[Sous-groupes finis de SO(3)]]
* [[Tables de caractères]]
* [[Théorème de Burnside]]
* [[Théorème de Cartan-Von Neumann]]
* [[Théorème de Frobenius sur les représentations]]
* [[Théorème de Frobenius-Zolotarev]]
* [[Théorème de Gauß pour les polygones réguliers constructibles]]
* [[Théorème de Lie-Kolchin]]
* [[Théorème de Molien]]
* [[Théorème de Sylow]]

= Analyse =

=== Analyse fonctionelle et distributions ===
* [[Densité des fonctions continues nulle part dérivables]]
* [[Densité des polynômes orthogonaux]]
* [[Dérivée des fonctions lipschitziennes]]
* [[Formule d'inversion de Fourier]]
* [[Projection dans un espace de Hilbert]]
* [[Réduction des opérateurs compacts symétriques dans un Hilbert]]
* [[Solution elementaire de l'equation de Schrodinger | Solution élémentaire de l'équation de Schrodinger]]
* [[Sous-espaces de C(R,C) de dimension finie stables par translations]]
* [[Théorème d'Ascoli]]
* [[Théorème d'échantillonnage de Shannon]]
* [[Théorème de Benedicks]]
* [[Théorème de Cartan-Von Neumann]]
* [[Théorème de Fejér]]
* [[Théorème de Riesz - Fischer]]
* [[Théorème de Hahn-Banach]]
* [[Théorème de Helly]]
* [[Théorème de Riesz-Fréchet-Kolmogorov]]
* [[Un espace de Sobolev]]

=== Analyse numérique, méthodes d'approximation ===
* Convergence de la méthode de gradient à pas optimal (+Kantorovitch) ([[Fichier:Tex.png|alt=Tex|link={{filepath:Gradient_optimal.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Gradient_optimal.pdf}} |24px]])
* Méthode de Gauss d'approximation d'intégrale ([[Fichier:Tex.png|alt=Tex|link={{filepath:Methode_gauss.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Methode_gauss.pdf}} |24px]])
* [[Méthode de Newton]]
* Série harmonique ([[Fichier:Tex.png|alt=Tex|link={{filepath:Série_harmonique.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Série_harmonique.pdf}} |24px]])
* Une méthode itérative de résolution de systèmes linéaires ([[Fichier:Tex.png|alt=Tex|link={{filepath:Inverse_methode_iterative.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Inverse_methode_iterative.pdf}} |24px]])

=== Calcul différentiel et fonctions holomorphes ===
* Courbe brachistochrone ([[Fichier:Tex.png|alt=Tex|link={{filepath:Courbe brachistochrone.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Courbe brachistochrone.pdf}} |24px]])
* Couronnes biholomorphes ([[Fichier:Tex.png|alt=Tex|link={{filepath:Couronnes biholomorphes.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Couronnes biholomorphes.pdf}} |24px]])
* Densité des polynômes orthogonaux ([[Fichier:Tex.png|alt=Tex|link={{filepath: densite_polynomes_orthogonaux.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: densite_polynomes_orthogonaux.pdf}} |24px]])
* Équation de Bessel ([[Fichier:Tex.png|alt=Tex|link={{filepath:Equation_de_Bessel.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Equation_de_Bessel.pdf}} |24px]])
* Formule des compléments ([[Fichier:Tex.png|alt=Tex|link={{filepath:Formule_complements.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Formule_complements.pdf}} |24px]])
* [[Inégalités de Kolmogorov]]
* Lemme de Borel ([[Fichier:Tex.png|alt=Tex|link={{filepath:Borel.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Borel.pdf}} |24px]])
* [[Lemme de Morse]]
* Méthode de Laplace ([[Fichier:Tex.png|alt=Tex|link={{filepath:MethodedeLaplace.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:MethodedeLaplace.pdf}} |24px]])
* [[Méthode de Newton]]
* Séries entières avec coupure p.s. ([[Fichier:Tex.png|alt=Tex|link={{filepath:Séries_entières_avec_coupure_ps.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Séries_entières_avec_coupure_ps.pdf}} |24px]])
* [[Surjectivité de l'exponentielle matricielle]]
* [[Théorème d'inversion locale]]
* Théorème de D'Alembert-Gauss ([[Fichier:Tex.png|alt=Tex|link={{filepath:DAlembert-Gauss.tex}} |24px]] ; [[Fichier:Pdf.png|alt=Tex|link={{filepath: DAlembert-Gauss.pdf}} |24px]])
* Théorème de Cartan-Von Neumann ([[Fichier:Tex.png|alt=Tex|link={{filepath:Cartan_von_neumann.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Cartan_von_neumann.pdf}} |24px]])
* [[Théorème de Hadamard-Lévy]]
* [[Théorème de Jordan]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Montel.pdf | Théorème de Montel]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:TEL.pdf | Théorème des extrema liés]]
* Théorème des extrema liée (avec utilisation du théorème des sous-variétés) ([[Fichier:Tex.png|alt=Tex|link={{filepath:Extrema_liés_ssvar.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Extrema_liés_ssvar.pdf}} |24px]])
* [[Théorème des fonctions implicites]]

=== Équations différentielles ===
* Courbe brachistochrone ([[Fichier:Tex.png|alt=Tex|link={{filepath:Courbe brachistochrone.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Courbe brachistochrone.pdf}} |24px]])
* Équation de Bessel ([[Fichier:Tex.png|alt=Tex|link={{filepath:Equation_de_Bessel.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Equation_de_Bessel.pdf}} |24px]])
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:H-M.pdf | Équation de Hill-Mathieu]]
* Étude asymptotique d'une suite de polynômes ([[Fichier:Tex.png|alt=Tex|link={{filepath:Étude_asymptotique_suite_polynômes.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Étude_asymptotique_suite_polynômes.pdf}} |24px]])
* [[Solution elementaire de l'equation de Schrodinger | Solution élémentaire de l'équation de Schrodinger]]
* [[Sous-espaces de C(R,C) de dimension finie stables par translations]]
* Théorème de Cauchy-Arzela-Peano ([[Fichier:Tex.png|alt=Tex|link={{filepath:Cauchy_arzela_peano.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Cauchy_arzela_peano.pdf}} |24px]])
* [[Théorème de Cauchy-Lipschitz]]
* [[Théorème de Hadamard-Lévy]]
* [[Théorème de stabilité de Lyapounov]]

=== Intégration ===
* Critère de Weyl ([[Fichier:Tex.png|alt=Tex|link={{filepath: Critere_Weyl.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: Critere_Weyl.pdf}} |24px]])
* [[Formule d'inversion de Fourier]]
* Formule des compléments ([[Fichier:Tex.png|alt=Tex|link={{filepath:Formule_complements.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Formule_complements.pdf}} |24px]])
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:E-Mcb.pdf | Formule sommatoire d'Euler Maclaurin]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Poisson.pdf | Formule Sommatoire de Poisson]]
* [[Intégrale de Fresnel]]
* Méthode de Gauss d'approximation d'intégrale ([[Fichier:Tex.png|alt=Tex|link={{filepath:Methode_gauss.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Methode_gauss.pdf}} |24px]])
* Méthode de Laplace ([[Fichier:Tex.png|alt=Tex|link={{filepath:MethodedeLaplace.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:MethodedeLaplace.pdf}} |24px]])
* Prolongement de la fonction <math>\Gamma</math> ([[Fichier:Tex.png|alt=Tex|link={{filepath:ProlongementGamma.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:ProlongementGamma.pdf}} |24px]])
* Théorème d'Abel angulaire ([[Fichier:Tex.png|alt=Tex|link={{filepath:Abel_angulaire.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Abel_angulaire.pdf}} |24px]])
* [[Théorème d'échantillonnage de Shannon]]
* Théorème de Benedicks ([[Fichier:Tex.png|alt=Tex|link={{filepath: Benedicks.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: Benedicks.pdf}} |24px]])
* [[Théorème de Fejér]]
* Théorème de Riesz-Fréchet-Kolmogorov ([[Fichier:Tex.png|alt=Tex|link={{filepath: RFK.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: RFK.pdf}} |24px]])
* Théorème taubérien fort ([[Fichier:Tex.png|alt=Tex|link={{filepath: Tauberien_fort.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: Tauberien_fort.pdf}} |24px]])
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Abel.pdf | Théorèmes d'Abel angulaire et taubérien faible]]
* Un exemple de calcul d'intégrale ([[Fichier:Tex.png|alt=Tex|link={{filepath:Calcul_integrale.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Calcul_integrale.pdf}} |24px]])

=== Probabilités ===
* Autour des variables aléatoires gaussiennes ([[Fichier:Tex.png|alt=Tex|link={{filepath: va_gaussiennes.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: va_gaussiennes.pdf}} |24px]])
* Bernoulli et développement dyadique ([[Fichier:Tex.png|alt=Tex|link={{filepath:Devdyadique.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Devdyadique.pdf}} |24px]])
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:EMV.pdf | EMV de la loi uniforme]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Ecarts.pdf | Estimation des grands écarts]]
* [[Etude de la loi Gamma]]
* [[Marche aléatoire sur Z]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Normaux.pdf | Nombres normaux]]
* Processur de Galton-Watson ([[Fichier:Tex.png|alt=Tex|link={{filepath: Galton-Watson.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: Galton-Watson.pdf}} |24px]])
* Ruine du joueur ([[Fichier:Tex.png|alt=Tex|link={{filepath: Ruinedujoueur.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: Ruine.pdf}} |24px]])
* Séries entières avec coupure p.s. ([[Fichier:Tex.png|alt=Tex|link={{filepath:Séries_entières_avec_coupure_ps.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Séries_entières_avec_coupure_ps.pdf}} |24px]])
* Théorème central limite ([[Fichier:Tex.png|alt=Tex|link={{filepath: TCL.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: TCL.pdf}} |24px]])
* [[Théorème de Weierstrass via les probabilités]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Rademacher.pdf | Variables de Rademacher]]

=== Topologie ===
* [[Lemme_de_Morse | Composantes connexes de l'ensemble des formes quadratiques non dégénérées.]]
* Couronnes biholomorphes ([[Fichier:Tex.png|alt=Tex|link={{filepath:Couronnes biholomorphes.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Couronnes biholomorphes.pdf}} |24px]])
* [[Ellipsoïde de John-Lœwner]]
* [[Lemme de Morse]]
* [[Sous-groupes compacts de GL_n | Sous-groupes compacts de <math>GL_n</math>]]
* [[Théorème d'Ascoli]]
* [[Théorème de Banach-Steinhaus et application aux séries de Fourier]]
* Théorème de Brouwer en dimension 2 ([[Fichier:Tex.png|alt=Tex|link={{filepath: Brouwer.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: Brouwer.pdf}} |24px]])
* Théorème de Cartan-Von Neumann ([[Fichier:Tex.png|alt=Tex|link={{filepath:Cartan_von_neumann.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Cartan_von_neumann.pdf}} |24px]])
* [[Théorème de Fejér]]
* [[Théorème de Jordan]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Montel.pdf | Théorème de Montel]]
* [[Théorème de Müntz]]
* Théorème de Riesz-Fréchet-Kolmogorov ([[Fichier:Tex.png|alt=Tex|link={{filepath: RFK.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: RFK.pdf}} |24px]])
* Théorème de Weierstrass (via les polynômes de Bernstein) ([[Fichier:Tex.png|alt=Tex|link={{filepath:Weierstrass.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Weierstrass.pdf}} |24px]])

= Non classés =
* Théorème de Glaeser ([[Fichier:Tex.png|alt=Tex|link={{filepath:Glaeser.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Glaeser.pdf}} |24px]])

= Informatique =
=== Algorithmique et structures de données ===
* [[2SAT est décidable en temps linéaire]]
* [[Arbres binaires de recherche optimaux]]
* [[Automate des occurrences]]
* [[Hachage parfait]]
* [[Plus longue sous-séquence commune]]
* [[Algorithme d'unification]]
* [[Tri polyphasé]]
* [[Transformée de Fourier rapide]]
* [[Algorithme de Hopcroft]]

=== Complexité ===
* [[2SAT est décidable en temps linéaire]]
* [[Problème de séparation par automates]]
* [[Universalité d'un langage rationnel]]
* [[Théorème de Cook]]

=== Décidabilité & Calculabilité ===
* [[Théorème de Rice]]
* [[Décidabilité de l'arithmétique de Presburger]]
* [[Une fonction calculable est récursive]]
* [[Indécidabilité de la terminaison d'un système de réécriture]]

=== Langages formels ===
* [[Automate des occurrences]]
* [[Arithmétique de Presburger]]
* [[Langage de pile d'un automate à pile]]
* [[Problème de séparation par automates]]
* [[Universalité d'un langage rationnel]]
* [[Analyse LR(0)]]
* [[Algorithme CYK]]
* [[Algorithme de Hopcroft]]
* [[Théorème de Parikh]]

=== Logique ===
* [[Compacité du calcul propositionnel]]
* [[Arithmétique de Presburger]]
* [[Fonction d'Ackermann]]
* [[Algorithme d'unification]]
* [[Complétude de la méthode de résolution]]
* [[Exemple d'un programme PROLOG]]
* [[Théorème de Lowenheim-Skolem]]

=== Réécriture ===
* [[Théorème de Higman]]
* [[Algorithme d'unification]]
* [[Ordre de simplification / Lemme de Highman / Théorème de Kruskal]]

Fichier:Dvt ordre de simplifaction.pdf

2015-03-31T13:13:17Z

Frédéric Valet :

Ordre de simplification / Lemme de Highman / Théorème de Kruskal

2015-03-31T13:12:45Z

Frédéric Valet : /* Développement */

On montre avec beaucoup d'efforts pour un développement, qu'un ordre de simplification et une signature finie entraînent la bien-fondaison.

==Recasement==

* [[919 ? -- Uniﬁcation : algorithmes et applications.]]

* [[920 -- Réécriture et formes normales. Exemples]]

==Développement==

*[[Fichier:Pdf.png|alt=Tex|link=|24px]] [[Média:dvt_ordre_de_simplifaction.pdf | Ordre de simplifcation]]

[[Category: Développement de la leçon 920]]

Ordre de simplification / Lemme de Highman / Théorème de Kruskal

2015-03-31T13:04:09Z

Frédéric Valet : Page créée avec « On montre avec beaucoup d'efforts pour un développement, qu'un ordre de simplification et une signature finie entraînent la bien-fondaison. ==Recasement== * 919 ? --... »

Développements par thèmes

2015-03-31T12:57:14Z

Frédéric Valet : /* Réécriture */

Cette page liste tous les développements présents sur le site, triés par thèmes. Les doublons sont autorisés et même conseillés dans la mesure où la plupart des théorèmes sont à cheval entre plusieurs domaines.

Il est donc explicitement demandé à ceux qui ajoutent un développement de le faire apparaitre dans '''toutes''' les parties qui le concernent.

(le choix des découpages est arbitraire, toute modification éclairée est la bienvenue).

Si vous préférez vous pouvez toujours vous dépêtrer avec le fouillis de la permière version de cette page : [[Développements]].

= Algèbre =

=== Algèbre linéaire, bilinéaire, réduction d'endomorphismes ===
* [[Action du groupe modulaire sur le demi-plan de Poincaré]]
* [[Algorithme des facteurs invariants]]
* [[Commutant d'un endomorphisme]]
* [[Lemme de Morse ]]
* [[Convergence d'une suite de polygônes vers l'isobarycentre]]
* [[Décomposition de Bruhat]]
* [[Décomposition de Dunford]]
* [[Diagrammes de Young et réduction de Jordan]]
* [[Ellipsoïde de John-Lœwner]]
* [[Endomorphismes cycliques, invariants de similitude et réduction de Frobenius]]
* [[Formes de Hankel]]
* [[Isomorphisme entre M_n(K) et son dual]]
* [[Lemme de Morse]]
* [[Nombre de matrices diagonalisables sur Fq]]
* [[Orthodiagonalisation des endomorphismes auto-adjoints]]
* [[Points extrémaux de la boule unité de L(E) ]]
* [[Réduction des matrices normales]]
* [[Sous-espaces de C(R,C) de dimension finie stables par translations]]
* [[Sous-groupes compacts de GL_n | Sous-groupes compacts de <math>GL_n</math>]]
* [[Surjectivité de l'exponentielle matricielle]]
* [[Théorème de Burnside]]
* [[Théorème de Cartan-Dieudonné]]
* [[Théorème de Frobenius-Zolotarev]]
* [[Théorème de Molien]]
* [[Un homéomorphisme réalisé par l'exponentielle matricielle]]
* [[Une méthode itérative de résolution de systèmes linéaires]]

=== Anneaux, arithmétique, dénombrement ===
* [[Algorithme des facteurs invariants]]
* [[Automorphismes de ZnZ | Automorphismes de <math>\mathbb{Z}/n\mathbb{Z}</math>]]
* [[Borne de Bézout]]
* [[Décomposition de Dunford]]
* [[Équation de Fermat pour n=3]]
* [[Groupes d'ordre pq]]
* [[Nombres de Bell]]
* [[Nombre de matrices diagonalisables sur Fq | Nombre de matrices diagonalisables sur <math>\mathbb{F}_q</math>]]
* [[Partitions d'un entier en parts fixées]]
* [[Primalité des nombres de Mersenne]]
* [[Probabilité que deux entiers soient premiers entre eux]]
* [[Sous-groupes finis de SO(3)]]
* [[Théorème de Gauß pour les polygones réguliers constructibles]]
* [[Théorème de Kronecker]]
* [[Théorème de Rothstein-Trager]]
* [[Théorème des deux carrés]]
* [[Une version faible du théorème de Dirichlet]]

=== Géométrie ===
* [[Action du groupe modulaire sur le demi-plan de Poincaré]]
* [[Classification des groupes de pavage du plan]]
* [[Convergence d'une suite de polygônes vers l'isobarycentre]]
* [[Ellipse de Steiner]]
* [[Groupe circulaire]]
* [[Inégalité isopérimétrique]]
* [[Isométries du cube]]
* [[Le folium de Descartes]]
* [[Le paradoxe de Banach-Tarski]]
* [[Points extrémaux de la boule unité de L(E)]]
* [[Simplicité de SO(3)]]
* [[Sous-groupes finis de SO(3)]]
* [[Théorème de Caratheodory]]
* [[Théorème de Cartan-Dieudonné]])
* [[Théorème de Gauß pour les polygones réguliers constructibles]]
* [[Théorème de Hahn-Banach]]
* [[Théorème de Jordan]]
* [[Théorème de Krein-Milman]]
* [[Théorème des quatre sommets]]

=== Théorie des corps, irréductibilité, primalité ===
* [[Irréductibilité des polynômes cyclotomiques]]
* [[Loi de réciprocité quadratique]]
* [[Polynômes irréductibles sur Fq]]
* [[Primalité des nombres de Mersenne]]
* [[Théorème de Chevalley-Warning]]
* [[Théorème de d'Alembert-Gauss]]
* [[Théorème de Gauß pour les polygones réguliers constructibles]]
* [[Théorème de Kronecker]]
* [[Théorème de l'élément primitif]]
* [[Théorème de Wedderburn]]

=== Théorie des groupes ===
* [[Action du groupe modulaire sur le demi-plan de Poincaré]]
* [[Automorphismes de ZnZ]]
* [[Décomposition de Bruhat]]
* [[Groupes d'ordre 12]]
* [[Isométries du cube]]
* [[Le paradoxe de Banach-Tarski]]
* [[Loi de réciprocité quadratique]]
* [[Nombre de matrices diagonalisables sur Fq | Nombre de matrices diagonalisables sur <math>\mathbb{F}_q</math>]]
* [[Simplicité de An | Simplicité de <math>\mathfrak{A}_n</math> ]]
* [[Simplicité de SO(3) | Simplicité de <math>\mathcal{SO}(3)</math>]]
* [[Sous-groupes compacts de GL_n | Sous-groupes compacts de <math>GL_n</math>]]
* [[Sous-groupes finis de SO(3)]]
* [[Tables de caractères]]
* [[Théorème de Burnside]]
* [[Théorème de Cartan-Von Neumann]]
* [[Théorème de Frobenius sur les représentations]]
* [[Théorème de Frobenius-Zolotarev]]
* [[Théorème de Gauß pour les polygones réguliers constructibles]]
* [[Théorème de Lie-Kolchin]]
* [[Théorème de Molien]]
* [[Théorème de Sylow]]

= Analyse =

=== Analyse fonctionelle et distributions ===
* [[Densité des fonctions continues nulle part dérivables]]
* [[Densité des polynômes orthogonaux]]
* [[Dérivée des fonctions lipschitziennes]]
* [[Formule d'inversion de Fourier]]
* [[Projection dans un espace de Hilbert]]
* [[Réduction des opérateurs compacts symétriques dans un Hilbert]]
* [[Solution elementaire de l'equation de Schrodinger | Solution élémentaire de l'équation de Schrodinger]]
* [[Sous-espaces de C(R,C) de dimension finie stables par translations]]
* [[Théorème d'Ascoli]]
* [[Théorème d'échantillonnage de Shannon]]
* [[Théorème de Benedicks]]
* [[Théorème de Cartan-Von Neumann]]
* [[Théorème de Fejér]]
* [[Théorème de Riesz - Fischer]]
* [[Théorème de Hahn-Banach]]
* [[Théorème de Helly]]
* [[Théorème de Riesz-Fréchet-Kolmogorov]]
* [[Un espace de Sobolev]]

=== Analyse numérique, méthodes d'approximation ===
* Convergence de la méthode de gradient à pas optimal (+Kantorovitch) ([[Fichier:Tex.png|alt=Tex|link={{filepath:Gradient_optimal.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Gradient_optimal.pdf}} |24px]])
* Méthode de Gauss d'approximation d'intégrale ([[Fichier:Tex.png|alt=Tex|link={{filepath:Methode_gauss.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Methode_gauss.pdf}} |24px]])
* [[Méthode de Newton]]
* Série harmonique ([[Fichier:Tex.png|alt=Tex|link={{filepath:Série_harmonique.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Série_harmonique.pdf}} |24px]])
* Une méthode itérative de résolution de systèmes linéaires ([[Fichier:Tex.png|alt=Tex|link={{filepath:Inverse_methode_iterative.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Inverse_methode_iterative.pdf}} |24px]])

=== Calcul différentiel et fonctions holomorphes ===
* Courbe brachistochrone ([[Fichier:Tex.png|alt=Tex|link={{filepath:Courbe brachistochrone.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Courbe brachistochrone.pdf}} |24px]])
* Couronnes biholomorphes ([[Fichier:Tex.png|alt=Tex|link={{filepath:Couronnes biholomorphes.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Couronnes biholomorphes.pdf}} |24px]])
* Densité des polynômes orthogonaux ([[Fichier:Tex.png|alt=Tex|link={{filepath: densite_polynomes_orthogonaux.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: densite_polynomes_orthogonaux.pdf}} |24px]])
* Équation de Bessel ([[Fichier:Tex.png|alt=Tex|link={{filepath:Equation_de_Bessel.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Equation_de_Bessel.pdf}} |24px]])
* Formule des compléments ([[Fichier:Tex.png|alt=Tex|link={{filepath:Formule_complements.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Formule_complements.pdf}} |24px]])
* [[Inégalités de Kolmogorov]]
* Lemme de Borel ([[Fichier:Tex.png|alt=Tex|link={{filepath:Borel.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Borel.pdf}} |24px]])
* [[Lemme de Morse]]
* Méthode de Laplace ([[Fichier:Tex.png|alt=Tex|link={{filepath:MethodedeLaplace.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:MethodedeLaplace.pdf}} |24px]])
* [[Méthode de Newton]]
* Séries entières avec coupure p.s. ([[Fichier:Tex.png|alt=Tex|link={{filepath:Séries_entières_avec_coupure_ps.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Séries_entières_avec_coupure_ps.pdf}} |24px]])
* [[Surjectivité de l'exponentielle matricielle]]
* [[Théorème d'inversion locale]]
* Théorème de D'Alembert-Gauss ([[Fichier:Tex.png|alt=Tex|link={{filepath:DAlembert-Gauss.tex}} |24px]] ; [[Fichier:Pdf.png|alt=Tex|link={{filepath: DAlembert-Gauss.pdf}} |24px]])
* Théorème de Cartan-Von Neumann ([[Fichier:Tex.png|alt=Tex|link={{filepath:Cartan_von_neumann.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Cartan_von_neumann.pdf}} |24px]])
* [[Théorème de Hadamard-Lévy]]
* [[Théorème de Jordan]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Montel.pdf | Théorème de Montel]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:TEL.pdf | Théorème des extrema liés]]
* Théorème des extrema liée (avec utilisation du théorème des sous-variétés) ([[Fichier:Tex.png|alt=Tex|link={{filepath:Extrema_liés_ssvar.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Extrema_liés_ssvar.pdf}} |24px]])
* [[Théorème des fonctions implicites]]

=== Équations différentielles ===
* Courbe brachistochrone ([[Fichier:Tex.png|alt=Tex|link={{filepath:Courbe brachistochrone.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Courbe brachistochrone.pdf}} |24px]])
* Équation de Bessel ([[Fichier:Tex.png|alt=Tex|link={{filepath:Equation_de_Bessel.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Equation_de_Bessel.pdf}} |24px]])
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:H-M.pdf | Équation de Hill-Mathieu]]
* Étude asymptotique d'une suite de polynômes ([[Fichier:Tex.png|alt=Tex|link={{filepath:Étude_asymptotique_suite_polynômes.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Étude_asymptotique_suite_polynômes.pdf}} |24px]])
* [[Solution elementaire de l'equation de Schrodinger | Solution élémentaire de l'équation de Schrodinger]]
* [[Sous-espaces de C(R,C) de dimension finie stables par translations]]
* Théorème de Cauchy-Arzela-Peano ([[Fichier:Tex.png|alt=Tex|link={{filepath:Cauchy_arzela_peano.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Cauchy_arzela_peano.pdf}} |24px]])
* [[Théorème de Cauchy-Lipschitz]]
* [[Théorème de Hadamard-Lévy]]
* [[Théorème de stabilité de Lyapounov]]

=== Intégration ===
* Critère de Weyl ([[Fichier:Tex.png|alt=Tex|link={{filepath: Critere_Weyl.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: Critere_Weyl.pdf}} |24px]])
* [[Formule d'inversion de Fourier]]
* Formule des compléments ([[Fichier:Tex.png|alt=Tex|link={{filepath:Formule_complements.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Formule_complements.pdf}} |24px]])
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:E-Mcb.pdf | Formule sommatoire d'Euler Maclaurin]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Poisson.pdf | Formule Sommatoire de Poisson]]
* [[Intégrale de Fresnel]]
* Méthode de Gauss d'approximation d'intégrale ([[Fichier:Tex.png|alt=Tex|link={{filepath:Methode_gauss.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Methode_gauss.pdf}} |24px]])
* Méthode de Laplace ([[Fichier:Tex.png|alt=Tex|link={{filepath:MethodedeLaplace.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:MethodedeLaplace.pdf}} |24px]])
* Prolongement de la fonction <math>\Gamma</math> ([[Fichier:Tex.png|alt=Tex|link={{filepath:ProlongementGamma.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:ProlongementGamma.pdf}} |24px]])
* Théorème d'Abel angulaire ([[Fichier:Tex.png|alt=Tex|link={{filepath:Abel_angulaire.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Abel_angulaire.pdf}} |24px]])
* [[Théorème d'échantillonnage de Shannon]]
* Théorème de Benedicks ([[Fichier:Tex.png|alt=Tex|link={{filepath: Benedicks.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: Benedicks.pdf}} |24px]])
* [[Théorème de Fejér]]
* Théorème de Riesz-Fréchet-Kolmogorov ([[Fichier:Tex.png|alt=Tex|link={{filepath: RFK.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: RFK.pdf}} |24px]])
* Théorème taubérien fort ([[Fichier:Tex.png|alt=Tex|link={{filepath: Tauberien_fort.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: Tauberien_fort.pdf}} |24px]])
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Abel.pdf | Théorèmes d'Abel angulaire et taubérien faible]]
* Un exemple de calcul d'intégrale ([[Fichier:Tex.png|alt=Tex|link={{filepath:Calcul_integrale.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Calcul_integrale.pdf}} |24px]])

=== Probabilités ===
* Autour des variables aléatoires gaussiennes ([[Fichier:Tex.png|alt=Tex|link={{filepath: va_gaussiennes.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: va_gaussiennes.pdf}} |24px]])
* Bernoulli et développement dyadique ([[Fichier:Tex.png|alt=Tex|link={{filepath:Devdyadique.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Devdyadique.pdf}} |24px]])
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:EMV.pdf | EMV de la loi uniforme]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Ecarts.pdf | Estimation des grands écarts]]
* [[Etude de la loi Gamma]]
* [[Marche aléatoire sur Z]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Normaux.pdf | Nombres normaux]]
* Processur de Galton-Watson ([[Fichier:Tex.png|alt=Tex|link={{filepath: Galton-Watson.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: Galton-Watson.pdf}} |24px]])
* Ruine du joueur ([[Fichier:Tex.png|alt=Tex|link={{filepath: Ruinedujoueur.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: Ruine.pdf}} |24px]])
* Séries entières avec coupure p.s. ([[Fichier:Tex.png|alt=Tex|link={{filepath:Séries_entières_avec_coupure_ps.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath:Séries_entières_avec_coupure_ps.pdf}} |24px]])
* Théorème central limite ([[Fichier:Tex.png|alt=Tex|link={{filepath: TCL.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: TCL.pdf}} |24px]])
* [[Théorème de Weierstrass via les probabilités]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Rademacher.pdf | Variables de Rademacher]]

=== Topologie ===
* [[Lemme_de_Morse | Composantes connexes de l'ensemble des formes quadratiques non dégénérées.]]
* Couronnes biholomorphes ([[Fichier:Tex.png|alt=Tex|link={{filepath:Couronnes biholomorphes.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Couronnes biholomorphes.pdf}} |24px]])
* [[Ellipsoïde de John-Lœwner]]
* [[Lemme de Morse]]
* [[Sous-groupes compacts de GL_n | Sous-groupes compacts de <math>GL_n</math>]]
* [[Théorème d'Ascoli]]
* [[Théorème de Banach-Steinhaus et application aux séries de Fourier]]
* Théorème de Brouwer en dimension 2 ([[Fichier:Tex.png|alt=Tex|link={{filepath: Brouwer.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: Brouwer.pdf}} |24px]])
* Théorème de Cartan-Von Neumann ([[Fichier:Tex.png|alt=Tex|link={{filepath:Cartan_von_neumann.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Cartan_von_neumann.pdf}} |24px]])
* [[Théorème de Fejér]]
* [[Théorème de Jordan]]
* [[Fichier:Pdf.png|alt=Pdf|link=|24px]] [[Média:Montel.pdf | Théorème de Montel]]
* [[Théorème de Müntz]]
* Théorème de Riesz-Fréchet-Kolmogorov ([[Fichier:Tex.png|alt=Tex|link={{filepath: RFK.tex}} |24px]], [[Fichier:Pdf.png|alt=Pdf|link={{filepath: RFK.pdf}} |24px]])
* Théorème de Weierstrass (via les polynômes de Bernstein) ([[Fichier:Tex.png|alt=Tex|link={{filepath:Weierstrass.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Weierstrass.pdf}} |24px]])

= Non classés =
* Théorème de Glaeser ([[Fichier:Tex.png|alt=Tex|link={{filepath:Glaeser.tex}} |24px]], [[Fichier:Pdf.png|alt=Tex|link={{filepath:Glaeser.pdf}} |24px]])

= Informatique =
=== Algorithmique et structures de données ===
* [[2SAT est décidable en temps linéaire]]
* [[Arbres binaires de recherche optimaux]]
* [[Automate des occurrences]]
* [[Hachage parfait]]
* [[Plus longue sous-séquence commune]]
* [[Algorithme d'unification]]
* [[Tri polyphasé]]
* [[Transformée de Fourier rapide]]
* [[Algorithme de Hopcroft]]

=== Complexité ===
* [[2SAT est décidable en temps linéaire]]
* [[Problème de séparation par automates]]
* [[Universalité d'un langage rationnel]]
* [[Théorème de Cook]]

=== Décidabilité & Calculabilité ===
* [[Théorème de Rice]]
* [[Décidabilité de l'arithmétique de Presburger]]
* [[Une fonction calculable est récursive]]

=== Langages formels ===
* [[Automate des occurrences]]
* [[Arithmétique de Presburger]]
* [[Langage de pile d'un automate à pile]]
* [[Problème de séparation par automates]]
* [[Universalité d'un langage rationnel]]
* [[Analyse LR(0)]]
* [[Algorithme CYK]]
* [[Algorithme de Hopcroft]]
* [[Théorème de Parikh]]

=== Logique ===
* [[Compacité du calcul propositionnel]]
* [[Arithmétique de Presburger]]
* [[Fonction d'Ackermann]]
* [[Algorithme d'unification]]
* [[Complétude de la méthode de résolution]]
* [[Exemple d'un programme PROLOG]]
* [[Théorème de Lowenheim-Skolem]]

=== Réécriture ===
* [[Théorème de Higman]]
* [[Algorithme d'unification]]
* [[Ordre de simplification / Lemme de Highman / Théorème de Kruskal]]

Théorème de Higman

2015-03-31T12:54:26Z

Frédéric Valet : /* Développement */

Les antichaînes sont finies.

== Développement ==
*[[Fichier:Tex.png|alt=Tex|link=|24px]] [[Média:dvt_higman.tex | Théorème de Higman]]
*[[Fichier:Pdf.png|alt=Tex|link=|24px]] [[Média:dvt_higman.pdf | Théorème de Higman]]

== Recasements ==
* [[909 -- Langages rationnels. Exemples et applications.]]

== Références ==
* Bruno Petazzoni, 16 problèmes d'informatique

[[Category: Développement de la leçon 909]]

Théorème de Higman

2015-03-31T11:00:06Z

Frédéric Valet : /* Développement */