Différences

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

--- teaching:progappchim:algos_entiers [2015/04/14 16:04] – villersd
+++ teaching:progappchim:algos_entiers [2015/04/20 10:04] – villersd
@@ Ligne 124: / Ligne 124: @@
 </sxh>
-FIXME : amélioration utilisant un crible
+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
 ===== Références =====
@@ Ligne 137: / Ligne 140: @@
   * [[http://en.wikipedia.org/wiki/Wheel_factorization]]
 ===== Recherche du PPCM =====
-Explication de la relation entre pgcd et ppcm via les facteurs premiers des nombres !
+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) !
-  * [http://fr.wikipedia.org/wiki/Plus_petit_commun_multiple]]
+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__ |
-===== Problème du sac à dos =====
+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) !
-  * [[http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos]]
 ===== 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 :
+<sxh 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)
+</sxh>
+==== 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]]
@@ Ligne 155: / Ligne 215: @@
   * formules CHON(S)
   * protéines
-  * spectro de masse ?
+  * 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/]]
+  * [[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]]
 ===== Références diverses =====