{"id":1264,"date":"2020-06-16T09:22:16","date_gmt":"2020-06-16T07:22:16","guid":{"rendered":"http:\/\/labodemaths.fr\/WordPress3\/?p=1264"},"modified":"2020-09-09T19:16:40","modified_gmt":"2020-09-09T17:16:40","slug":"algorithme-et-optimisation","status":"publish","type":"post","link":"https:\/\/labodemaths.fr\/WordPress3\/algorithme-et-optimisation\/","title":{"rendered":"Algorithme et optimisation"},"content":{"rendered":"\n

On consid\u00e8re le probl\u00e8me suivant :
on a diff\u00e9rents objets de poids divers que l’on veut ranger dans un certain nombre de contenants ayant une capacit\u00e9 limit\u00e9e.
Par exemple, on a 8 objets de poids respectifs 7,6,3,4,8,5,9,2 que l’on veut ranger dans des cartons dont la capacit\u00e9 est de 11 kg maximum.
On veut \u00e9videmment, si possible :
– ranger tous les objets,
– minimiser le nombre de cartons n\u00e9cessaires.<\/p>\n\n\n\n

\"\"
Exemple 1<\/figcaption><\/figure>\n\n\n\n

Exercice 1<\/h3>\n\n\n\n

Proposer diff\u00e9rents algorithmes en langage \u00ab\u00a0naturel\u00a0\u00bb.
Pour chaque algorithme, d\u00e9terminer l’invariant, le variant et pr\u00e9ciser si la condition d’arr\u00eat est v\u00e9rifi\u00e9e.
Tester vos algorithmes avec les 3 exemples.
Vos algorithmes permettent-ils d’obtenir une solution optimale ?<\/p>\n\n\n\n

\"\"
Exemple 2<\/figcaption><\/figure>\n\n\n\n
\"\"
Exemple 3<\/figcaption><\/figure>\n\n\n\n

Exercice 2<\/h3>\n\n\n\n

Impl\u00e9menter en Python vos diff\u00e9rents algorithmes.
On utilisera des listes pour simuler les poids des objets et le rangement obtenu par l’algorithme.
Par exemple :<\/p>\n\n\n\n

>>> poids=[6,5,5,3,3,2]\n>>> rangement1_poids(12,3) # fonction avec un param\u00e8tre poids maximal et le nombre de carton\n[[6,5],[5,3,2],[3]]<\/code><\/pre>\n\n\n\n
correspondra \u00e0 la solution :<\/p>\n\n\n\n
\"\"
solution non optimale<\/figcaption><\/figure>\n\n\n\n
Trouver la solution optimale \u00e0 l’exemple 3.<\/p>\n\n\n\n
Proposition de correction<\/p>\n\n\n\n
Une proposition de correction avec 3 algorithmes :
– une algorithme de rangement totalement al\u00e9atoire : on tire un poids au hasard que l’on range dans une bo\u00eete disponible au hasard,
– un algorithme de rangement ordonn\u00e9 : on prend les poids au fur et \u00e0 mesure et on les range dans la 1ere bo\u00eete disponible,
– un algorithme glouton sur le principe de \u00ab\u00a0on range d’abord les poids les plus lourds dans la premi\u00e8re bo\u00eete disponible\u00a0\u00bb.<\/p>\n\n\n\n
from random import randint\n\ndef creation_boites(nombre,poids_max):\n    '''\n    creation d'une liste de longueur n+1,\n    les n premiers \u00e9l\u00e9ments repr\u00e9sentent une boite\n    le dernier \u00e9l\u00e9ment repr\u00e9sente la val max par boite\n    retour : une liste\n    >>> boites=creation_boites(6,12)\n    >>> boites==[[], [], [], [], [], [], 12]\n    True\n    '''\n    boites=[[] for i in range(nombre)]\n    boites.append(poids_max)\n    return boites\n\ndef boite_dispo(indice,val):\n    '''\n    indique si la boite correspondante \u00e0 l'indice peut accueillir la val \n    sans d\u00e9passer le poids max\n    >>> boites=[[5,2], [9], [], [], [], [], 12]\n    >>>  boite_dispo(0,5)\n    True\n    >>> boite_dispo(1,5)\n    False\n    >>> boite_dispo(10,5)\n    False\n    '''\n    global boites\n    if indice>=len(boites):\n        return False\n    if sum(boites[indice])+val>boites[-1]:\n        return False\n    return True\n\n    \ndef indice_boite_aleatoire(val):\n    '''\n    d\u00e9termine l'indice d'une bo\u00eete al\u00e9atoire pouvant\n    accueiller la valeur val, revoie False si aucune bo\u00eetes\n    n'est dispo\n    return : int ou False\n    '''\n    global boites\n    boites_dispo=[]\n    poids_max=boites[-1]\n    for i in range(len(boites)-1):\n        if boite_dispo(i,val)!=False:\n            boites_dispo.append(i) \n    if len(boites_dispo)==0:\n        return False\n    else :\n        indice_alea=randint(0,len(boites_dispo)-1)\n        return int(boites_dispo[indice_alea])\n\ndef algo_on_range_au_hasard(a_ranger):\n    '''\n    principe : on prend une valeur \u00e0 ranger au hasard,\n    on la range au hasard dans un boite disponible si\n    il y en a une\n    return : False si on ne peut pas ranger une valeur,\n    sinon la liste boites avec les valeurs rang\u00e9es al\u00e9atoriement\n    effet de bord : modifie la liste boites\n    '''\n    global boites\n    val_a_ranger=a_ranger.copy()\n    while len(val_a_ranger)>0 :\n        # on tire une valeur \u00e0 ranger au hasard\n        val=val_a_ranger[randint(0,len(val_a_ranger)-1)]\n        # on cherche \u00e0 la ranger al\u00e9atoirement\n        ind_alea=indice_boite_aleatoire(val)\n        # on teste si l'indice est un entier\n        # ind_alea!=False ne fonctionne pas pour\n        # ind_alea=0 ( False = 0 )\n        if type(ind_alea)==int:\n            boites[ind_alea].append(val)\n        else:\n            print(\"Je n'ai pas pu ranger tous vos \u00e9l\u00e9ments.\")\n            return False\n        # on supprime la valeur rang\u00e9e de la liste\n        # des valeurs \u00e0 ranger\n        val_a_ranger.remove(val)\n    return boites\n        \ndef algo_on_range_les_poids_successivement(a_ranger):\n    '''\n    principe : on prend les valeurs \u00e0 ranger dans l'ordre au fur\n    et \u00e0 mesure, on les range dans la 1ere boite disponible\n    return : False si on ne peut pas ranger une valeur,\n    sinon la liste boites avec les valeurs rang\u00e9es\n    effet de bord : modifie la liste boites\n    >>> a_ranger=[11,12,8,1,5,4,3,7]\n    >>> boites=[[], [], [], [], [], 13]\n    >>> algo_on_range_les_poids_successivement(a_ranger)\n    >>> boites==[[11, 1], [12], [8, 5], [4, 3], [7], 13]\n    True\n    '''\n    \n    global boites\n    for i in range(len(a_ranger)):\n        indice=0\n        while boite_dispo(indice,a_ranger[i])==False:\n            indice+=1\n            if indice==len(boites)-1:\n                print(\"Je n'ai pas pu ranger vos valeurs\")\n                return False\n        boites[indice].append(a_ranger[i])\n    return boites\n\ndef rangement_par_poids_max(a_ranger):\n    '''\n    principe : on prend les valeurs \u00e0 ranger par ordre d\u00e9croissant au fur\n    et \u00e0 mesure, on les range dans la 1ere boite disponible\n    return : False si on ne peut pas ranger une valeur,\n    sinon la liste boites avec les valeurs rang\u00e9es\n    effet de bord : modifie la liste boites\n    >>> a_ranger=[11,12,8,1,5,4,3,7]\n    >>> boites=[[], [], [], [], [], 13]\n    >>> algo_on_range_les_poids_successivement(a_ranger)\n    >>> boites==[[12,1], [11], [8,5], [7,4], [3], 13]\n    True\n    '''\n    global boites\n    a_ranger.sort()\n    a_ranger.reverse()\n    for i in range(len(a_ranger)):\n        indice=0\n        while boite_dispo(indice,a_ranger[i])==False:\n            indice+=1\n            if indice==len(boites)-1:\n                print(\"Je n'ai pas pu ranger vos valeurs\")\n                return False\n        boites[indice].append(a_ranger[i])\n    return boites\n    \n    \n    \na_ranger=[11,12,8,1,5,4,3,7]\nboites=creation_boites(5,13)\nprint(\"Algo al\u00e9atoire\")\nprint(\"A ranger\",a_ranger)\nprint(\"dans\",boites)\nalgo_on_range_au_hasard(a_ranger)\nprint(boites)\n\nprint(\"Algo par parcours des listes\")\nboites=creation_boites(5,13)\nprint(\"A ranger\",a_ranger)\nprint(\"dans\",boites)\nalgo_on_range_les_poids_successivement(a_ranger)\nprint(boites)\n\nprint(\"Algo par parcours des listes\")\nboites=creation_boites(5,13)\nprint(\"A ranger\",a_ranger)\nprint(\"dans\",boites)\nrangement_par_poids_max(a_ranger)\nprint(boites)\n\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
On consid\u00e8re le probl\u00e8me suivant :on a diff\u00e9rents objets de poids divers que l’on veut…<\/p>\n
Read the postAlgorithme et optimisation<\/span><\/a><\/div>\n","protected":false},"author":2,"featured_media":1270,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1264"}],"collection":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/comments?post=1264"}],"version-history":[{"count":4,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1264\/revisions"}],"predecessor-version":[{"id":1280,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1264\/revisions\/1280"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media\/1270"}],"wp:attachment":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media?parent=1264"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/categories?post=1264"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/tags?post=1264"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}