Server : Apache System : Linux webd348.cluster026.gra.hosting.ovh.net 5.15.148-ovh-vps-grsec-zfs-classid #1 SMP Thu Feb 8 09:41:04 UTC 2024 x86_64 User : hednacluml ( 122243) PHP Version : 8.3.9 Disable Function : _dyuweyrj4,_dyuweyrj4r,dl Directory : /home/hednacluml/encyclo/articles/t/h/é/ |
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="fr" lang="fr" dir="ltr">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<!-- headlinks removed -->
<link rel="shortcut icon" href="../../../../misc/favicon.ico"/>
<title>Théorie des domaines - Wikipédia</title>
<style type="text/css">/*<![CDATA[*/ @import "../../../../skins/offline/main.css"; /*]]>*/</style>
<link rel="stylesheet" type="text/css" media="print" href="../../../../skins/common/commonPrint.css" />
<!--[if lt IE 5.5000]><style type="text/css">@import "../../../../skins/monobook/IE50Fixes.css";</style><![endif]-->
<!--[if IE 5.5000]><style type="text/css">@import "../../../../skins/monobook/IE55Fixes.css";</style><![endif]-->
<!--[if IE 6]><style type="text/css">@import "../../../../skins/monobook/IE60Fixes.css";</style><![endif]-->
<!--[if IE]><script type="text/javascript" src="../../../../skins/common/IEFixes.js"></script>
<meta http-equiv="imagetoolbar" content="no" /><![endif]-->
<script type="text/javascript" src="../../../../skins/common/wikibits.js"></script>
<script type="text/javascript" src="../../../../skins/offline/md5.js"></script>
<script type="text/javascript" src="../../../../skins/offline/utf8.js"></script>
<script type="text/javascript" src="../../../../skins/offline/lookup.js"></script>
<script type="text/javascript" src="../../../../raw/gen.js"></script> <style type="text/css">/*<![CDATA[*/
@import "../../../../raw/MediaWiki%7ECommon.css";
@import "../../../../raw/MediaWiki%7EMonobook.css";
@import "../../../../raw/gen.css";
/*]]>*/</style> </head>
<body
class="ns-0">
<div id="globalWrapper">
<div id="column-content">
<div id="content">
<a name="top" id="contentTop"></a>
<h1 class="firstHeading">Théorie des domaines</h1>
<div id="bodyContent">
<h3 id="siteSub">Un article de Wikipédia, l'encyclopédie libre.</h3>
<div id="contentSub"></div>
<!-- start content -->
<div class="plainlinks bandeau-niveau-ebauche bandeau">
<table style="background-color:transparent">
<tr>
<td class="bandeau-icone">
<div style="text-align:center;white-space:nowrap"><a href="../../../../articles/c/r/y/Image%7ECrystal_mycomputer.png_ff1d.html" class="image" title="Crystal mycomputer.png"><img alt="" src="../../../../images/shared/thumb/e/e3/Crystal_mycomputer.png/35px-Crystal_mycomputer.png" width="35" height="35" border="0" /></a></div>
</td>
<td>
<div class="bandeau-titre"><strong>Cet article est une <a href="../../../../articles/%C3%A9/b/a/Aide%7E%C3%89bauche_a94d.html" title="Aide:Ébauche">ébauche</a> concernant l’<a href="../../../../articles/i/n/f/Portail%7EInformatique_2d39.html" title="Portail:Informatique">informatique</a>.</strong></div>
<div class="bandeau-texte">Vous pouvez partager vos connaissances en l’améliorant. <b>(<a href="../../../../articles/c/o/m/Aide%7EComment_modifier_une_page_32be.html" title="Aide:Comment modifier une page">Comment ?</a>)</b>.</div>
</td>
</tr>
</table>
</div>
<p>La <b>théorie des domaines</b> est une branche des mathématiques dont le principal champ d'application se trouve en informatique théorique. Cette partie de la théorie des ensembles ordonnés a été introduite par <a href="../../../../articles/d/a/n/Dana_S._Scott_ccf3.html" title="Dana S. Scott">Dana Scott</a> pendant les années 60, afin de fournir le cadre théorique nécessaire à la définition d'une <a href="../../../../articles/s/%C3%A9/m/S%C3%A9mantique_d%C3%A9notationnelle.html" title="Sémantique dénotationnelle">sémantique dénotationnelle</a> du <a href="../../../../articles/l/a/m/Lambda-calcul.html" title="Lambda-calcul">lambda-calcul</a>.</p>
<p>Les domaines sont des ensembles <a href="../../../../articles/r/e/l/Relation_d%27ordre.html" title="Relation d'ordre">partiellement ordonnés</a>. Dans la sémantique dénotationnelle du lambda-calcul, les éléments des domaines représentent les lambda-termes, et le plus petit élément (quand on en munit le domaine) représente le résultat d'un calcul ne finissant pas, c'est l'élément dit « indéfini », noté <img class="tex" alt="\perp" src="../../../../math/d/2/1/d21e3d53f78769beee8ff7b6c4a9a92c.png" /> (prononcer « bottom »). L'ordre du domaine définit, dans l'idée, une notion de quantité d'information : un élément du domaine contient au moins toute l'information contenue dans les éléments qui lui sont inférieurs.</p>
<p>L'idée est ensuite de se ramener à des domaines particuliers où toute fonction monotone (croissante) a un plus petit point fixe. En général, on utilise des <i><a href="../../../../articles/o/r/d/Ordre_partiel_complet.html" title="Ordre partiel complet">ordres partiels complets</a></i> (complete partial order, ou CPO), c'est-à-dire des domaines qui possèdent un plus petit élément et où toute <a href="../../../../articles/c/h/a/Cha%C3%AEne_%28ordres%29.html" title="Chaîne (ordres)">chaîne</a> (partie strictement ordonnée) a une borne supérieure.</p>
<p>Ainsi, il devient aisé d'associer une sémantique au combinateur de point fixe <i>Y</i>, en le représentant par une fonction totale qui à une fonction associe un de ses points fixes s'il existe, et <img class="tex" alt="\perp" src="../../../../math/d/2/1/d21e3d53f78769beee8ff7b6c4a9a92c.png" /> sinon. Par là-même, donner un sens à une fonction définie « récursivement » (c'est-à-dire en fait, en tant que point fixe d'une fonctionnelle <i>G</i>) devient possible :<br /></p>
<ul>
<li>si <i>f</i> est la fonction qui à <i>0</i> associe <i>1</i> et à <i>n > 0</i> associe <i>n * f(n - 1)</i>,</li>
<li>on peut aussi définir f comme ceci : <i>f = Y(G)</i> (point fixe de <i>G</i>) où <i>G</i> est la fonction qui prend une fonction φ en entrée et rend la fonction qui à <i>0</i> associe 1 et à <i>n > 0</i> associe <i>n *</i> φ<i>(n - 1)</i> (et à <img class="tex" alt="\perp" src="../../../../math/d/2/1/d21e3d53f78769beee8ff7b6c4a9a92c.png" /> associe <img class="tex" alt="\perp" src="../../../../math/d/2/1/d21e3d53f78769beee8ff7b6c4a9a92c.png" />, par définition de <img class="tex" alt="\perp" src="../../../../math/d/2/1/d21e3d53f78769beee8ff7b6c4a9a92c.png" />). On note que G est monotone sur le domaine des fonctions de ℕ<sub><img class="tex" alt="\perp" src="../../../../math/d/2/1/d21e3d53f78769beee8ff7b6c4a9a92c.png" /></sub> dans ℕ<sub><img class="tex" alt="\perp" src="../../../../math/d/2/1/d21e3d53f78769beee8ff7b6c4a9a92c.png" /></sub>, et, à ce titre, admet un point fixe (la fonction factorielle !)</li>
<li>alors, on a un moyen de calculer <i>f</i> : en itérant <i>G</i> sur la fonction <i>f<sub>0</sub> = <img class="tex" alt="\perp" src="../../../../math/d/2/1/d21e3d53f78769beee8ff7b6c4a9a92c.png" /></i>, c'est-à-dire la fonction qui a tout entier naturel et à <img class="tex" alt="\perp" src="../../../../math/d/2/1/d21e3d53f78769beee8ff7b6c4a9a92c.png" /> associe <img class="tex" alt="\perp" src="../../../../math/d/2/1/d21e3d53f78769beee8ff7b6c4a9a92c.png" />. <i>f</i> est la limite de la suite ainsi obtenue (et le plus petit point fixe de <i>G</i>).</li>
</ul>
<p>La théorie des domaines permet aussi de donner un sens aux équations de domaine de type <img class="tex" alt="A = A \rightarrow A" src="../../../../math/1/7/4/174185239a5df7d57f66a9bf5c0e9096.png" /> (<i>A</i> est l'ensemble des fonctions de <i>A</i> dans <i>A</i> !). Dans les mathématiques habituelles, ceci est absurde, à moins de donner un sens particulier à cette flèche. Par exemple <img class="tex" alt="\reals = \reals \rightarrow \reals" src="../../../../math/e/5/9/e59f5e4625dc8d6e7dc0d7a57b049ccd.png" /> paraît impossible, ne serait-ce que pour des raisons de cardinalité (Dans la théorie des cardinaux <img class="tex" alt="\reals" src="../../../../math/2/3/6/2369a2488f59aa39a3fca53e0eff9f88.png" /> est un <a href="../../../../articles/i/n/f/Infini.html" title="Infini">infini</a> strictement plus petit que <img class="tex" alt="\reals \rightarrow \reals" src="../../../../math/9/b/1/9b1e7d4980d2123f75c3385cbe6b3048.png" />); pourtant, si cette flèche ne représente que les applications continues de <img class="tex" alt="\reals" src="../../../../math/2/3/6/2369a2488f59aa39a3fca53e0eff9f88.png" /> dans <img class="tex" alt="\reals" src="../../../../math/2/3/6/2369a2488f59aa39a3fca53e0eff9f88.png" />, on garde bien le même cardinal que <img class="tex" alt="\reals" src="../../../../math/2/3/6/2369a2488f59aa39a3fca53e0eff9f88.png" /> (en effet, une application continue de <img class="tex" alt="\reals" src="../../../../math/2/3/6/2369a2488f59aa39a3fca53e0eff9f88.png" /> dans <img class="tex" alt="\reals" src="../../../../math/2/3/6/2369a2488f59aa39a3fca53e0eff9f88.png" /> peut être définie par sa restriction à l'ensemble dénombrable <i>Q</i>, donc cet ensemble a le cardinal de <img class="tex" alt="\reals ^ \omega" src="../../../../math/c/7/a/c7a861e8f5b23c1734bb0d35753ba57c.png" />, donc de <img class="tex" alt="\reals" src="../../../../math/2/3/6/2369a2488f59aa39a3fca53e0eff9f88.png" />).</p>
<p>En théorie des domaines, la notion de continuïté sur un ensemble <i>A</i> aura son équivalent : la continuïté selon Scott sur un domaine <i>A</i>. Une fonction est Scott-continue ssi elle est monotone sur <i>A</i> et que pour toute <a href="../../../../articles/e/n/s/Ensemble_filtrant.html" title="Ensemble filtrant">partie filtrante</a> (partie où toute paire d'éléments a un majorant) <i>B</i> de <i>A</i> admettant une borne supérieure, on a <span class="texhtml"><i>s</i><i>u</i><i>p</i>(<i>f</i>(<i>B</i>)) = <i>f</i>(<i>s</i><i>u</i><i>p</i>(<i>B</i>))</span>. Cette définition sera souvent simplifiée pour le cas où A est un CPO : la fonction est continue ssi elle est monotone, et si pour toute chaîne B, on a <span class="texhtml"><i>s</i><i>u</i><i>p</i>(<i>f</i>(<i>B</i>)) = <i>f</i>(<i>s</i><i>u</i><i>p</i>(<i>B</i>))</span>.</p>
<!--
NewPP limit report
Preprocessor node count: 334/1000000
Post-expand include size: 2372/2048000 bytes
Template argument size: 687/2048000 bytes
Expensive parser function count: 2/500
-->
<div class="printfooter">
</div>
<div id="catlinks"><div id='catlinks' class='catlinks'><div id="mw-normal-catlinks"><a href="../../../../articles/a/c/c/Cat%C3%A9gorie%7EAccueil_1aae.html" title="Catégorie:Accueil">Catégories</a> : <span dir='ltr'><a href="../../../../articles/t/h/%C3%A9/Cat%C3%A9gorie%7ETh%C3%A9orie_2450.html" title="Catégorie:Théorie">Théorie</a></span> | <span dir='ltr'><a href="../../../../articles/i/n/f/Cat%C3%A9gorie%7EInformatique_th%C3%A9orique_644b.html" title="Catégorie:Informatique théorique">Informatique théorique</a></span></div><div id="mw-hidden-catlinks" class="mw-hidden-cats-hidden">Catégorie cachée : <span dir='ltr'><a href="../../../../articles/w/i/k/Cat%C3%A9gorie%7EWikip%C3%A9dia%7E%C3%A9bauche_informatique_1039.html" title="Catégorie:Wikipédia:ébauche informatique">Wikipédia:ébauche informatique</a></span></div></div></div> <!-- end content -->
<div class="visualClear"></div>
</div>
</div>
</div>
<div id="column-one">
<div id="p-cactions" class="portlet">
<h5>Views</h5>
<ul>
<li id="ca-nstab-main"
class="selected" ><a href="../../../../articles/t/h/%C3%A9/Th%C3%A9orie_des_domaines.html">Article</a></li><li id="ca-talk"
><a href="../../../../articles/t/h/%C3%A9/Discuter%7ETh%C3%A9orie_des_domaines_e6e7.html">Discussion</a></li><li id="ca-current"
><a href="http://fr.wikipedia.org/wiki/Th%C3%A9orie_des_domaines">Version actuelle</a></li> </ul>
</div>
<div class="portlet" id="p-logo">
<a style="background-image: url(../../../../misc/Wiki.png);"
href="../../../../index.html"
title="Accueil"></a>
</div>
<script type="text/javascript"> if (window.isMSIE55) fixalpha(); </script>
<div class='portlet' id='p-navigation'>
<h5>Navigation</h5>
<div class='pBody'>
<ul>
<li id="n-mainpage"><a href="../../../../index.html">Accueil</a></li>
<li id="n-thema"><a href="../../../../articles/a/c/c/Portail%7EAccueil_bcc9.html">Portails thématiques</a></li>
<li id="n-alphindex"><a href="../../../../articles/t/o/u/Special%7EToutes_les_pages_fabc.html">Index alphabétique</a></li>
<li id="n-randompage"><a href="../../../../articles/p/a/g/Special%7EPage_au_hasard_9c81.html">Un article au hasard</a></li>
<li id="n-contact"><a href="../../../../articles/c/o/n/Wikip%C3%A9dia%7EContact_929e.html">Contacter Wikipédia</a></li>
</ul>
</div>
</div>
<div class='portlet' id='p-Contribuer'>
<h5>Contribuer</h5>
<div class='pBody'>
<ul>
<li id="n-help"><a href="../../../../articles/s/o/m/Aide%7ESommaire_c9f0.html">Aide</a></li>
<li id="n-portal"><a href="../../../../articles/a/c/c/Wikip%C3%A9dia%7EAccueil_5272.html">Communauté</a></li>
<li id="n-recentchanges"><a href="../../../../articles/m/o/d/Special%7EModifications_r%C3%A9centes_b222.html">Modifications récentes</a></li>
<li id="n-aboutwp"><a href="../../../../articles/a/c/c/Wikip%C3%A9dia%7EAccueil_des_nouveaux_arrivants_0784.html">Accueil des nouveaux arrivants</a></li>
<li id="n-sitesupport"><a href="http://meta.wikimedia.org/wiki/Faire_un_don:_explication">Faire un don</a></li>
</ul>
</div>
</div>
<div id="p-search" class="portlet">
<h5><label for="searchInput">Rechercher</label></h5>
<div id="searchBody" class="pBody">
<form action="javascript:goToStatic(3)" id="searchform"><div>
<input id="searchInput" name="search" type="text"
accesskey="C" value="" />
<input type='submit' name="go" class="searchButton" id="searchGoButton"
value="Aller" />
</div></form>
</div>
</div>
<div id="p-lang" class="portlet">
<h5>Autres langues</h5>
<div class="pBody">
<ul>
<li>
<a href="../../../../../en/articles/d/o/m/Domain_theory.html">English</a>
</li>
<li>
<a href="../../../../../ja/articles/%E9%A0%98/%E5%9F%9F/%E7%90%86/%E9%A0%98%E5%9F%9F%E7%90%86%E8%AB%96.html">日本語</a>
</li>
<li>
<a href="../../../../../zh/articles/%E5%9F%9F/%E7%90%86/%E8%AE%BA/%E5%9F%9F%E7%90%86%E8%AE%BA.html">中文</a>
</li>
</ul>
</div>
</div>
</div><!-- end of the left (by default at least) column -->
<div class="visualClear"></div>
<div id="footer">
<div id="f-poweredbyico"><a href="http://www.mediawiki.org/"><img src="../../../../skins/common/images/poweredby_mediawiki_88x31.png" alt="Powered by MediaWiki" /></a></div> <div id="f-copyrightico"><a href="http://wikimediafoundation.org/"><img src="../../../../misc/wikimedia-button.png" border="0" alt="Wikimedia Foundation"/></a></div> <ul id="f-list">
<li id="f-credits">Cette page a été modifiée pour la dernière fois le 8 février 2008 à 12:41 par Utilisateur <a href="../../../../articles/d/u/m/Utilisateur%7EDumZiBoT_1015.html" title="Utilisateur:DumZiBoT">DumZiBoT</a>. Basé sur le travail de Utilisateur(s) <a href="../../../../articles/p/a/l/Utilisateur%7EPalpalpalpal_2811.html" title="Utilisateur:Palpalpalpal">Palpalpalpal</a>, <a href="../../../../articles/r/o/b/Utilisateur%7ERobotQuistnix_d78e.html" title="Utilisateur:RobotQuistnix">RobotQuistnix</a>, <a href="../../../../articles/b/a/d/Utilisateur%7EBadmood_4dbf.html" title="Utilisateur:Badmood">Badmood</a>, <a href="../../../../articles/y/u/r/Utilisateur%7EYurikBot_0f63.html" title="Utilisateur:YurikBot">YurikBot</a>, <a href="../../../../articles/p/i/e/Utilisateur%7EPIerre.Lescanne_15f9.html" title="Utilisateur:PIerre.Lescanne">PIerre.Lescanne</a>, <a href="../../../../articles/m/i/s/Utilisateur%7EMisterMatt_Bot_f0f9.html" title="Utilisateur:MisterMatt Bot">MisterMatt Bot</a>, <a href="../../../../articles/m/e/d/Utilisateur%7EMedBot_8f10.html" title="Utilisateur:MedBot">MedBot</a>, <a href="../../../../articles/s/a/m/Utilisateur%7ESam_Hocevar_d973.html" title="Utilisateur:Sam Hocevar">Sam Hocevar</a>, <a href="../../../../articles/m/e/d/Utilisateur%7EMed_63f8.html" title="Utilisateur:Med">Med</a>, <a href="../../../../articles/x/m/l/Utilisateur%7EXmlizer_b1f6.html" title="Utilisateur:Xmlizer">Xmlizer</a>, <a href="../../../../articles/a/l/d/Utilisateur%7EAldoo_3b0c.html" title="Utilisateur:Aldoo">Aldoo</a> et <a href="../../../../articles/f/v/d/Utilisateur%7EFvdP_f002.html" title="Utilisateur:FvdP">FvdP</a>.</li> <li id="f-copyright"><span style="white-space:normal"><a class="internal" href="http://fr.wikipedia.org/wiki/Wikip%C3%A9dia:Droit_d'auteur" title="Droit d'auteur">Droit d'auteur</a> : Tous les textes sont disponibles sous les termes de la <a class="internal" href="http://fr.wikipedia.org/wiki/Wikip%C3%A9dia:Licence_de_documentation_libre_GNU" title="GFDL">licence de documentation libre GNU</a> (GFDL).<br/>
Wikipedia® est une marque déposée de la <a href="http://wikimediafoundation.org/wiki/Accueil" title="Wikimedia Foundation">Wikimedia Foundation, Inc.</a>, organisation de bienfaisance régie par le paragraphe <a class="internal" href="http://en.wikipedia.org/wiki/501(c)" title="501(c)">501(c)(3)</a> du code fiscal des États-Unis.</span><br/></li> <li id="f-about"><a href="../../../../articles/%C3%A0/_/p/Wikip%C3%A9dia%7E%C3%80_propos_5de1.html" title="Wikipédia:À propos">À propos de Wikipédia</a></li> <li id="f-disclaimer"><a href="../../../../articles/a/v/e/Wikip%C3%A9dia%7EAvertissements_g%C3%A9n%C3%A9raux_fef1.html" title="Wikipédia:Avertissements généraux">Avertissements</a></li> </ul>
</div>
</div>
</body>
</html>