rendu.docx (3).zip

<?xml version="1.0" encoding="UTF-8" standalone="yes"?> <w:document xmlns:ve="http://schemas.openxmlformats.org/markup-compatibility/2006" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:r="http://schemas.openxmlformats.org/officeDocument/2006/relationships" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math" xmlns:v="urn:schemas-microsoft-com:vml" xmlns:wp="http://schemas.openxmlformats.org/drawingml/2006/wordprocessingDrawing" xmlns:w10="urn:schemas-microsoft-com:office:word" xmlns:w="http://schemas.openxmlformats.org/wordprocessingml/2006/main" xmlns:wne="http://schemas.microsoft.com/office/word/2006/wordml"><w:body><w:p w:rsidR="00C07735" w:rsidRPr="00C07735" w:rsidRDefault="00C07735" w:rsidP="00C07735"><w:pPr><w:jc w:val="center"/><w:rPr><w:b/><w:sz w:val="36"/></w:rPr></w:pPr><w:r><w:rPr><w:b/><w:sz w:val="36"/></w:rPr><w:t>Génération des permutations</w:t></w:r></w:p><w:p w:rsidR="00C07735" w:rsidRDefault="00C07735"/><w:p w:rsidR="00C07735" w:rsidRDefault="00C07735"/><w:p w:rsidR="00C07735" w:rsidRDefault="00C07735"/><w:p w:rsidR="00BC6628" w:rsidRDefault="00BC6628"/><w:p w:rsidR="00BC6628" w:rsidRDefault="00BC6628"/><w:p w:rsidR="000A5AF2" w:rsidRDefault="0042315D"><w:r><w:t xml:space="preserve">Les permutations sont des objets mathématiques assez simples dont l’étude remonte à l’Antiquité, où des mathématiciens comme Euclide s’y sont </w:t></w:r><w:r w:rsidR="009B092A"><w:t>intéressés</w:t></w:r><w:r><w:t xml:space="preserve">. Malgré cela, le problème auquel nous nous </w:t></w:r><w:r w:rsidR="000355EB"><w:t>intéresserons</w:t></w:r><w:r><w:t xml:space="preserve"> ici n’a été réellement résolu efficacement qu’après les années 1950, date à partir de laquelle un </w:t></w:r><w:r w:rsidR="000355EB"><w:t>engouement</w:t></w:r><w:r><w:t xml:space="preserve"> est né dans la communauté scientifique pour trouver des algorithmes optimaux.</w:t></w:r><w:r w:rsidR="00C1796C"><w:t xml:space="preserve"> Pour comprendre l’importance d’avoir des programmes efficaces capables d’énumérer toutes les permutations d’une liste d’éléments, il faut d’abord comprendre pourquoi la complexité de ceux-ci peut exploser s’ils ne sont pas optimisés – et donc comprendre ce qu’est une permutation – et aussi comprendre pourquoi nous avons besoin d’avoir une solution à ce problème.</w:t></w:r></w:p><w:p w:rsidR="00C1796C" w:rsidRDefault="007B6224"><w:r><w:t>La d</w:t></w:r><w:r w:rsidR="00C1796C"><w:t xml:space="preserve">éfinition d’une permutation est simple : </w:t></w:r><w:r w:rsidR="006952E7"><w:t>s</w:t></w:r><w:r w:rsidR="00C1796C"><w:t>i on a une liste d’éléments, une permutation de cette liste est tout simplement une liste contenant ces même</w:t></w:r><w:r w:rsidR="00CA3792"><w:t>s</w:t></w:r><w:r w:rsidR="00C1796C"><w:t xml:space="preserve"> éléments</w:t></w:r><w:r w:rsidR="004B1F00"><w:t>,</w:t></w:r><w:r w:rsidR="00C1796C"><w:t xml:space="preserve"> mais dans un ordre différent. Si on prend par exemple la liste [1, 2, 3] alors [2, 3, 1] en serait une permutation. Comme on s’</w:t></w:r><w:r w:rsidR="007A5E20"><w:t>intéresse</w:t></w:r><w:r w:rsidR="00C1796C"><w:t xml:space="preserve"> ici à l’énumération de toutes les permutations possible pour une liste donnée, il est important d’en conna</w:t></w:r><w:r w:rsidR="00237C1F"><w:t>î</w:t></w:r><w:r w:rsidR="00C1796C"><w:t>tre le nombre. Celui-ci est facile à calculer : pour notre liste précédente :</w:t></w:r></w:p><w:p w:rsidR="00C1796C" w:rsidRDefault="00C1796C"><w:proofErr w:type="gramStart"/><w:r><w:t>[ 3</w:t></w:r><w:proofErr w:type="gramEnd"/><w:r><w:t xml:space="preserve"> choix possibles, 2 choix possibles, 1 choix possible ] on voit facilement qu’il y a 3 x 2 x 1 = 6 choix possible</w:t></w:r><w:r w:rsidR="00B65969"><w:t>s</w:t></w:r><w:r><w:t xml:space="preserve">. De manière générale, pour une liste de N éléments on aura N ! = N x N-1 x N-2 x …. x 2 x </w:t></w:r><w:proofErr w:type="gramStart"/><w:r><w:t>1 permutations</w:t></w:r><w:proofErr w:type="gramEnd"/><w:r><w:t xml:space="preserve"> possibles</w:t></w:r><w:r w:rsidR="000D2288"><w:t>, ce qui croit très vite avec la taille de la liste, d’où la nécessité d’optimiser les algorithmes.</w:t></w:r></w:p><w:p w:rsidR="000D2288" w:rsidRDefault="000D2288"><w:r><w:t>La nécessité des algorithme</w:t></w:r><w:r w:rsidR="00B65969"><w:t>s</w:t></w:r><w:r><w:t xml:space="preserve"> en elle-même vient de l’utilité que l’on fait d’une liste de toutes les permutations dans différents domaines des mathématiques et de l’informatique. On peut </w:t></w:r><w:r w:rsidR="007C76A7"><w:t>notamment</w:t></w:r><w:r><w:t xml:space="preserve"> citer son</w:t></w:r><w:r w:rsidR="007C76A7"><w:t xml:space="preserve"> </w:t></w:r><w:r><w:t>importance dans la résolution de problèmes, comme le problème du voyageur de commerce, ou dans la sécurité informatique, les permutations étant utilisées dans des algorithmes de chiffrement.</w:t></w:r></w:p><w:p w:rsidR="000A5AF2" w:rsidRDefault="000D2288"><w:r><w:t xml:space="preserve">Nous verrons donc dans un premier temps des algorithmes se basant sur la méthode par échange, qui sont </w:t></w:r><w:r w:rsidR="000355EB"><w:t>parmi</w:t></w:r><w:r><w:t xml:space="preserve"> les plus optimisés et qui ont été publiés pendant la période d’</w:t></w:r><w:r w:rsidR="00BD34A8"><w:t>engouement</w:t></w:r><w:r><w:t xml:space="preserve"> des années 50-70, puis nous nous </w:t></w:r><w:r w:rsidR="000355EB"><w:t>intéresserons</w:t></w:r><w:r><w:t xml:space="preserve"> à une application plus spécifique du problème, dont la solution présentée remonte au 19è siècle.</w:t></w:r></w:p><w:p w:rsidR="002D1800" w:rsidRDefault="002D1800"/><w:p w:rsidR="002D1800" w:rsidRDefault="002D1800"/><w:p w:rsidR="002D1800" w:rsidRDefault="002D1800"/><w:p w:rsidR="002D1800" w:rsidRPr="002D1800" w:rsidRDefault="002D1800" w:rsidP="002D1800"><w:pPr><w:jc w:val="center"/><w:rPr><w:b/><w:sz w:val="32"/></w:rPr></w:pPr><w:r w:rsidRPr="002D1800"><w:rPr><w:b/><w:sz w:val="32"/></w:rPr><w:lastRenderedPageBreak/><w:t>I – Différentes solutions au problème</w:t></w:r></w:p><w:p w:rsidR="002D1800" w:rsidRDefault="002D1800"/><w:p w:rsidR="000D2288" w:rsidRDefault="000D2288"/><w:p w:rsidR="000A5AF2" w:rsidRDefault="002D1800" w:rsidP="002D1800"><w:pPr><w:rPr><w:sz w:val="28"/><w:u w:val="single"/></w:rPr></w:pPr><w:r w:rsidRPr="002D1800"><w:rPr><w:sz w:val="28"/><w:u w:val="single"/></w:rPr><w:t>A</w:t></w:r><w:r w:rsidR="004A1A13"><w:rPr><w:sz w:val="28"/><w:u w:val="single"/></w:rPr><w:t xml:space="preserve"> </w:t></w:r><w:r w:rsidR="000D2288" w:rsidRPr="002D1800"><w:rPr><w:sz w:val="28"/><w:u w:val="single"/></w:rPr><w:t>-</w:t></w:r><w:r w:rsidR="004A1A13"><w:rPr><w:sz w:val="28"/><w:u w:val="single"/></w:rPr><w:t xml:space="preserve"> </w:t></w:r><w:r w:rsidR="000D2288" w:rsidRPr="002D1800"><w:rPr><w:sz w:val="28"/><w:u w:val="single"/></w:rPr><w:t>Méthodes par échange</w:t></w:r><w:r w:rsidR="00BF1031" w:rsidRPr="002D1800"><w:rPr><w:sz w:val="28"/><w:u w:val="single"/></w:rPr><w:t>s</w:t></w:r><w:r><w:rPr><w:sz w:val="28"/><w:u w:val="single"/></w:rPr><w:t> :</w:t></w:r></w:p><w:p w:rsidR="004A1A13" w:rsidRPr="002D1800" w:rsidRDefault="004A1A13" w:rsidP="002D1800"><w:pPr><w:rPr><w:sz w:val="28"/><w:u w:val="single"/></w:rPr></w:pPr></w:p><w:p w:rsidR="000A5AF2" w:rsidRDefault="000D2288"><w:r><w:t>Nous allons voir ici deux algorithmes qui suivent cette méthode par échange dont l’idée est simple et plutôt instinctive :</w:t></w:r></w:p><w:p w:rsidR="000D2288" w:rsidRPr="00BF1031" w:rsidRDefault="00BF1031"><w:r><w:t xml:space="preserve">Si on a une permutation P, alors échanger le contenu de deux cases de cette liste nous donne une permutation différente (ex : [A, B, C, D, E] -&gt; [A, </w:t></w:r><w:r w:rsidRPr="00BF1031"><w:rPr><w:b/><w:color w:val="FF0000"/></w:rPr><w:t>D</w:t></w:r