Différences

Ci-dessous, les différences entre deux révisions de la page.

--- teaching:progappchim:algos_entiers [2015/04/13 15:02] – [Problème des apéritifs] villersd
+++ teaching:progappchim:algos_entiers [2023/01/10 09:04] (Version actuelle) – villersd
@@ Ligne 5: / Ligne 5: @@
 ===== Recherche du PGCD (plus grand commun diviseur) =====
-  * [[http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide]] (lire les explications géométriques
+Explication géométrique : en comprenant un nombre entier comme une longueur et un couple d'entiers (a,b) comme un rectangle, leur PGCD est la longueur du côté du plus grand carré permettant de carreler entièrement ce rectangle. L'algorithme d'Euclide décompose ce rectangle en carrés, de plus en plus petits, par divisions euclidiennes successives, de la longueur par la largeur, puis de la largeur par le reste, jusqu'à un reste nul (**observez bien [[http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide#Explications_g.C3.A9om.C3.A9triques|ici]] !**).
-  * [[http://en.literateprograms.org/Euclidean_algorithm_%28Python%29]]
+Cela donne ceci en Python :
-  * [[http://stackoverflow.com/questions/11175131/code-for-greatest-common-divisor-in-python]]
+<code python pgcd.py>
-  * [[https://docs.python.org/dev/library/fractions.html#fractions.gcd]]
+#!/usr/bin/env python
+# -*- coding: UTF-8 -*-
+def gcd(a, b):
+    """Calculate the Greatest Common Divisor of a and b.
-===== Recherche du PPCM =====
+    Unless b==0, the result will have the same sign as b (so that when
+    b is divided by it, the result comes out positive).
+    """
+    while b:
+        a, b = b, a%b
+    return a
+n1=210
+n2=126
+print(gcd(n1, n2))
+</code>
+Si on dispose des décompositions en facteurs premiers d'un nombre entier, on peut aussi établir la valeur du PGCD en effectuant le produit de tous les facteurs communs.
+==== Références ====
+  * [[http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide|Algorithme d'Euclide]]
+  * [[http://stackoverflow.com/questions/11175131/code-for-greatest-common-divisor-in-python]]
+  * [[https://docs.python.org/dev/library/fractions.html#fractions.gcd]] (version incluse dans le langage)
+  * [[http://en.literateprograms.org/Euclidean_algorithm_%28Python%29]] (améliorable !)
 ===== Nombres premiers =====
+Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs (qui sont alors 1 et lui-même) : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ...
+Pour lister les nombres premiers strictement inférieur à un nombre N donné, un algorithme naïf (appelés tests de primalité) consiste à considérer les naturels un par un, en essayant de le diviser par tous les nombres inférieurs à sa racine carrée : s'il est divisible par l'un d'entre eux, il est composé, et sinon, il est premier. Voici une implémentation en Python de cette idée.
+<code python nombres_premiers-01.py>
+#!/usr/bin/env python
+# -*- coding: UTF-8 -*-
+"""
+Liste de nombres premiers strictement inférieurs à un entier donné
+"""
+def isprime(n):
+    for x in range(2,int(n**0.5)+1):
+        if n % x == 0:
+            return False
+    return True
+def primelist(n):
+    return [a for a in range(2,n) if isprime(a)]
+p=primelist(1000)
+print(p)
+</code>
+L'algorithme peut être rendu plus efficace : il suggère beaucoup de divisions inutiles, par exemple, si un nombre n'est pas divisible par 2, il est inutile de tester s'il est divisible par 4. En fait, il suffit de tester sa divisibilité par tous les nombres premiers inférieurs à sa racine carrée. Le crible d'Ératosthène est une méthode, reposant sur cette idée, qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. En supprimant tous les multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier, et qui sont donc les nombres premiers. Voici une implémentation en Python du crible d'Ératosthène :
+<code python nombres_premiers-03.py>
+#!/usr/bin/env python
+# -*- coding: UTF-8 -*-
+"""
+Liste de nombres premiers strictement inférieurs à un entier donné
+"""
+def primelist(n):
+    """
+    Version avec crible d'Eratosthenes
+    """
+    li = range(n+1)  # création d'une liste d'entiers jusque n
+    li[1] = 0        #  0 (déjà à 0) et 1 ne sont pas premiers
+    ncur = 2            # prochain nombre à tester
+    while ncur ** 2 <= n:  # tant que ncur est inférieur à sqrt(n)
+        li[ncur*2::ncur] = [0] * (n // ncur - 1) # éliminer (mettre à 0)
+                                          # les multiples de ncur
+        # ncur suivant (il ne doit pas être déjà mis à zéro)
+        ncur += 1
+        while not li[ncur]:
+            ncur += 1
+    return [a for a in li if a != 0]  # renvoie une liste avec les élements non nuls
+p=primelist(1000)
+print(p)
+</code>
+==== Références ====
+  * [[http://fr.wikipedia.org/wiki/Nombre_premier|Nombre premier]] (wikipedia)
+  * [[http://fr.wikipedia.org/wiki/Crible_d%27%C3%89ratosth%C3%A8ne|Crible d'Ératosthène]] (wikipedia)
+  * [[https://www.daniweb.com/software-development/python/code/216880/check-if-a-number-is-a-prime-number-python]]
+  * [[http://python.jpvweb.com/mesrecettespython/doku.php?id=liste_des_nombres_premiers]]
+  * [[http://fr.wikibooks.org/wiki/Exemples_de_scripts_Python#Impl.C3.A9mentation_du_crible_d.27.C3.89ratosth.C3.A8ne]]
+  * [[http://stackoverflow.com/questions/3939660/sieve-of-eratosthenes-finding-primes-python]]
+  * [[http://openclassrooms.com/forum/sujet/crible-d-eratosthene-87347]]
+  * [[http://gumuz.nl/weblog/python-extended-slice-assignment/|Explication de l'affectation multiple via des slices]]
+  * [[wp>fr:Nombre_premier_tronquable|Nombre premier tronquable]]
+    * [[https://www.geeksforgeeks.org/left-truncatable-prime/]]
+    * [[https://rosettacode.org/wiki/Find_largest_left_truncatable_prime_in_a_given_base#Python]]
+    * [[https://tutorialspoint.dev/algorithm/mathematical-algorithms/left-truncatable-prime]]
 ===== Factorisation en nombres premiers =====
+Version élémentaires, par essais systématiques de diviseurs :
+<code python; title : factorisation_nombres_premiers-01.py>
+#!/usr/bin/env python
+# -*- coding: UTF-8 -*-
+"""
+Factorisation en nombres premiers ; méthode par essais successifs
+"""
+def prime_factors(n):
+    li = []
+    f = 2  # premier facteur à tester
+    while f*f <= n:
+        while (n % f) == 0:
+            li.append(f)  # on ajoute f à la liste
+            n = n/f           # on divise par f
+        f = f+1 if f == 2 else f+2  # pour ne pas essayer les nombres pairs
+    if n > 1:  # si on n'a pas obtenu n=1, alors le facteur restant est premier
+       li.append(n)
+    return li
+p=prime_factors(1234567890)
+print(p)
+</code>
+Exercices :
+  * amélioration la recherche en combinant l'utilisation du crible d'Eratosthenes
+  * utiliser la décomposition en facteurs premiers de deux nombres (ou plus) pour trouver leur PGCD : pour l'ensemble des facteurs communs aux nombres, il s'agit du produit de ces facteurs élevés à la puissance la plus basse dans les décompositions
+Techniques avancées :
+  * [[wp>Integer_factorization|Integer factorization]]
+  * [[https://stackoverflow.com/questions/4643647/fast-prime-factorization-module|Fast prime factorization module]] (stackoverflow)
+  * librairie sympy → pip install sympy (ou conda install sympy)
+    * Use the function sympy.ntheory.factorint : "Given a positive integer n, factorint(n) returns a dict containing the prime factors of n as keys and their respective multiplicities as values." For example:
+<code python>
+from sympy.ntheory import factorint
+factorint(10**20+1) → {73: 1, 5964848081: 1, 1676321: 1, 137: 1}
+</code>
+===== Références =====
+  * [[http://stackoverflow.com/questions/16996217/prime-factorization-list]]
+  * [[http://en.wikipedia.org/wiki/Talk%3APrime_factorization_algorithm]] (récursif)
+  * [[http://rosettacode.org/wiki/Prime_decomposition#Python]] (avancé)
+  * [[http://codereview.stackexchange.com/questions/11317/prime-factorization-of-a-number]] (améliorable)
+  * [[http://stackoverflow.com/questions/4643647/fast-prime-factorization-module]] (intéressant)
+  * [[http://gilles.dubois10.free.fr/Nombres/Naturels/decomposition.html]]
+  * [[http://python.jpvweb.com/mesrecettespython/doku.php?id=decomposition_en_facteurs_premiers]] (améliorable)
+  * [[http://anh.cs.luc.edu/331/code/factoring.py]] (intéressant)
+  * [[http://en.wikipedia.org/wiki/Wheel_factorization]]
+  * [[https://github.com/grinsted/teachprimes|Some code to for teaching primes]] (génération de figures pour enseigner les nombres premiers)
+===== Recherche du PPCM =====
+Explication de la relation entre PGCD et PPCM via les facteurs premiers des nombres  (//cf.// [[http://fr.wikipedia.org/wiki/Plus_petit_commun_multiple|wikipedia]]) : le PPCM de deux nombres est obtenu par le produit de chacun des facteurs premiers dans la décomposition des deux nombres, élevés à la puissance la plus haute dans ces décompositions. On a alors que le produit des deux nombres équivaut au produit du PGCD par le PPCM et dès lors : PPCM(a,b) = a * b / PGCD(a,b) !
+Voici un exemple utilisant les décompositions en facteur premier de 1470 et 252 :
+^ Facteurs premiers de 1470 ^ Facteurs premiers de 252^
+| __2__ | **2<sup>2</sup>** |
+| __3__ | **3<sup>2</sup>**|
+| **5** | |
+| **7<sup>2</sup>** | __7__ |
+Le PGCD est 42, obtenu par le produit des facteurs communs (soulignés), tandis que le PPCM est obtenu par le produit de tous les facteurs, en utilisant la puissance la plus grande (en gras). Tous les facteurs du tableau de décomposition, soit de la première colonne, soit de la seconde, sont tous utilisés. Par conséquent on a bien pour deux nombres a et b que PPCM(a,b) = a * b / PGCD(a,b) !
 ===== Problème des apéritifs =====
+Énoncé en version "appliquée" :
+<blockquote>La carte des apéritifs propose un certain nombre d’éléments, à des prix différents. Quel assortiment puis-je acheter, coûtant exactement une certaine somme d’argent N ?</blockquote>
+Illustration :
+{{ http://imgs.xkcd.com/comics/np_complete.png }}
+En chimie, un problème tout à fait équivalent consiste, en masses entières (donc en nombre de nucléons), à trouver une formule chimique incluant différents atomes d'éléments différents qui donnera une masse entière
+donnée. En voici une solution :
+<code python; title : aperitif_initial-02.py>
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+"""
+http://paternault.fr/informatique/jouets/aperitif.html
+https://git.framasoft.org/spalax/jouets/blob/master/README.rst
+https://wiki.python.org/moin/Generators
+"""
+def aperitif(total, prix):
+    """Solutions du problème des apéritifs.
+    version sans itérateur
+    :arg total int: Prix total à atteindre.
+    :arg prix list: Liste des prix disponibles.
+    :return: liste des solutions, ces solutions étant des
+             listes correspondant à ``prix``.
+    """
+    if len(prix) == 0:
+        return []
+    if len(prix) == 1:
+        if total % prix[0] == 0:
+            return [[int(total // prix[0])]]
+    liste=[]
+    for nombre in range(int((total // prix[0])+1)):
+        for solution in aperitif(total - prix[0]*nombre, prix[1:]):
+            liste.append([nombre] + solution)
+    return liste
+atomes=[1,12,14,16,32]
+# atomes=atomes[::-1]
+masse=59
+print(atomes,type(atomes))
+print(masse, type(masse))
+print(aperitif(masse, atomes))
+</code>
+==== Références ====
   * [[http://xkcd.com/287/]]
   * [[http://paternault.fr/informatique/jouets/aperitif.html]] et [[https://git.framasoft.org/spalax/jouets/blob/master/README.rst|ici]]
+===== Applications chimiques =====
+  * formules CHON(S)
+  * protéines
+  * spectrométrie de masse (en masses entières)
 ===== Problème du sac à dos =====
+L’énoncé  de  ce  problème extrêmement difficile ([[http://fr.wikipedia.org/wiki/21_probl%C3%A8mes_NP-complets_de_Karp|un des problèmes de Karp]]) est par contre simple, faisant référence à un problème courant :
+<blockquote>Étant  donné  plusieurs  objets  possédant chacun  un  poids  et  une  valeur  et  étant  donné  un  poids  maximum  pour  le  sac,  quels  objets faut-il  mettre  dans  le  sac  de  manière  à  maximiser  la  valeur  totale  sans  dépasser  le  poids maximal autorisé pour le sac ?</blockquote>
+En voici une illustration (source wikimedia) :
+{{ http://upload.wikimedia.org/wikipedia/commons/thumb/c/c6/Knapsack_greedy.svg/500px-Knapsack_greedy.svg.png }}
+Ce problème revêt une importance économique dans de nombreux secteurs tels que la découpe de matériaux (afin de minimiser les pertes) ou le chargement de cargaisons (avions, camions, bateaux,...). Un examen systématique des possibilités conduit à une explosion combinatoire du nombre de configurations à examiner !
+Solutions en Python :
+  * [[http://rosettacode.org/wiki/Knapsack_problem/0-1|Rosetta code]], en force brute et programmation dynamique
+  * [[http://codereview.stackexchange.com/questions/20569/dynamic-programming-solution-to-knapsack-problem|codereview.stackexchange.com]], programmation dynamique
+  * [[http://www.markhneedham.com/blog/2013/01/07/knapsack-problem-python-vs-ruby/]]
+  * [[https://medium.freecodecamp.org/if-you-have-slow-loops-in-python-you-can-fix-it-until-you-cant-3a39e03b6f35|If you have slow loops in Python, you can fix it…until you can’t]] (knapsack problem)
   * [[http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos]]
+  * [[https://interstices.info/jcms/c_19213/le-probleme-du-sac-a-dos]]
-==== Applications chimiques ====
-  * formules CHON
-  * protéines
-  * spectro de masse ?
 ===== Références diverses =====