Module 2: Algorithmique et Programmation : Notions debase pour les biologistesObjectif:Initiation à la programmation et à l'algorithmique. Faisabilité d'un algorithme : les problèmessimples et les problèmes complexes. Présentation des algorithmes classiques pour l'optimisationet le traitement des données.Contenu :Qu'est ce qu'un algorithme  ? Analyse d'un problème.Représentation et structures de données.Liaisons entre les structures de données et les algorithmes.Complexité d'un algorithme. Résolutions exactes et heuristiques.La mise en oeuvre sera faite dans un langage de programmation interprété et souple (Python).

Jour 1:cours:notions générales d'algorithmique et de programmation (variables, structure de contrôle,fonctions).Voyageur de commerce – NP complet (factorielle)Heuristique (planche à clous, savon – MonteCarlo)Programmation dynamique – Camions (tranches)

Présentation du langage Python (Interprété/Interactif)Variables: type impliciteliste, tuple et string sont des séquences.Indentation délimite les blocs d'instructions – instruction vide "pass"Listes:a = [] # déclaration d'une listeT-uples:a = (4, ‘titi’,3.14159) # déclaration d'un t-uple (un t-uple est nonmodifiable)

Les listes et t-uples commencent à 0, coordonnées négatives == permutations circulaires –1 ==dernière case (maximum négatif = -longueur, dernière case +1 : erreur,, types différentsautorisés. Donc les coordonnées vont de –longueur à +(longueur –1)a.append("toto")a[3:10] # extrait éléments 3 à 9

for i in liste: # i prend successivement les valeurs de la liste

for i in range(debut, fin, step):# i prend les valeurs de "debut à ("fin"-1) par pas de "step".

while <test> :

def foo(arguments):# indentation nécessaire

Fonctions : attention, passage par valeur, sauf les listes, strings et tuples.Cela veut dire une variable est copiée dans la fonction : la fonction ne peut donc modifier lavariable de l’appelant.Mais dans le cas des listes, strings et tuples, le nom de la variable est une référence, donc laréférence n’est pas modifiable, mais l’objet référencé peut l’être (puisqu’on a la référence !).Références :Voir l’exemple suivant :>>> x=[1,2,3]>>> x[1, 2, 3]>>> y=x>>> y[1, 2, 3]>>> x[2]=-1>>> x[1, 2, -1]>>> y[1, 2, -1]

y est donc bien une référence à x, y et x désignent un même objet (une liste)Pour copier une liste, il faut l’expliciter, avec par exemple les index de début et de fin, commeici :>>> z=x[:]>>> z[1, 2, -1]>>> x[2]=-2>>> x[1, 2, -2]>>> z[1, 2, -1]

Là, x a été copiée dans z, et si on touche à x, on ne touche pas à z.Si on ne veut pas qu’une liste soit touchée dans une fonction, il faudrait alors faire :>>> def foo(l):... l[2]=-5... print l

>>> foo(x)[1, 2, -5]>>> x[1, 2, -5] # là, x est touchée>>> foo(z[:])[1, 2, -5]>>> z[1, 2, -1] # là, y n’est pas touchée

# lister les méthodes liées a un objetrange(4)liste[0, 1, 2, 3]liste=dir(liste)['__add__', '__class__', '__contains__', '__delattr__', '__delitem__','__eq__', '__ge__', '__getattribute__', '__getitem__', '__getslice__',

'__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__le__', '__len__','__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__repr__','__rmul__', '__setattr__', '__setitem__', '__setslice__', '__str__', 'append','count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']map, reduce, filterreduce(plus,liste) # f(f(f(liste[0],liste[1]),liste[2]), liste[3])..etc6map(carre,liste)[0, 1, 4, 9]map(plus, liste,liste)[0, 2, 4, 6]map(None, liste1,liste2): applique None aux doublets d'une liste constituéede chacune des paires des éléments de liste1 et liste2filter(f,liste): retourne la sous liste de liste constituée de chacun deséléments pour lesquels f est vraie.

TP:Utilisation des structures de données et des structures de contrôles de Python, fonctions.

Boucle TestsCalcul moyennemoyenne cumulative selon formule: mi = mi-1 + vi*i/(i-1)

mi: moyenne au "temps" i, vi ième valeur

calcul varianceFaire avec programmation impérative (boucle) et fonctionnelle (reduce).fichier python "fonctions"def somme(a, b):

return a+b

def carre(n):return n*n

def sommeseq(seq): # somme d'une séquences=0for x in seq:

s=s+xreturn s

# somme par reduce (programmation fonctionnelle)def sum(liste): # somme d'une liste

return reduce(somme,liste)

def moyenne(liste):return float(sommeseq(liste))/len(liste)

# variancedef var(liste):

return (moyenne(map(carre,liste))-carre(moyenne(liste))*(float(len(liste))/(len(liste)-1)))

def admis(s): return (s[-1]>=10)

# retourne une liste de n-uplets qui sont les mots des lignes# du fichier fdef readfile(f): t= [] fil = open(f,'r') tmp= fil.readlines() for x in tmp: t.append(x.split()) # fil.close() return t

# retourne 0 si a==b, -1 si a<b, + 1 si a>bdef compare(a,b): if a>b: return 1 elif a<b: return -1 else : return 0

=================

fichier "notes":Terrieur Alain 12 4 16Potanpoche Jessica 0 12 4Chemonfis Thierry 8.5 14 17Bonnot Jean 18 12Kiroul Pierre 10 4.5 15...

#!/usr/local/bin/python2.1

import fonctions

f=open('notes','r')ll=f.readlines()

t=[]

for x in ll:t.append(x.split())

et=[]etud=[]for x in t:

et=x[0:2]et.append(fonctions.moyenne(map(float,x[2:])))etud.append(et)

w=open('moys','w')for x in etud:

w.write(x[0]+" "+x[1]+" "+"%2.2f" % x[2]+"\n")

# afficher à l'écra les admis:print "etudiants admis :listeadmis = filter(fonctions.admis,etud)

for x in listeadmis : print x[0], x[1], '%2.2f' % x[2]

w.close()

Jour 2 :

Cours:Récursivité (Cf document recursif.pdf)Algorithmes de tri. TP: tri (insertion, sélection, bulle, merge)Sur le net : applications graphiques en java :http://java.sun.com/applets/jdk/1.4/demo/applets/SortDemo/example1.htmlhttp://www.cs.ubc.ca/spider/harrison/Java/http://lwh.free.fr/pages/algo/tri/tri.htm

TP:Recherche séquentielle dans une liste triée.C’est l’algorithme de recherche le plus élémentaire qui parcourt la listejusqu’à ce qu’un objet soittrouvé ou bien que la fin du tableau soit atteinte. Nous allons appliquer cela à la liste obtenueaprès lecture du fichier notes en cherchant la ligne correspondant à un étudiant sur la base de sonnom de famille.

def rec_seq(tab, name): cpt = 0 for i in tab: test = compare(i[0], name) cpt = cpt+1 if test ==0 : return i, cpt print "pas trouve"

Le nombre maximum de comparaisons d’objets effectuées par cette algorithme est N le nombred’éléments de la liste, ce maximum étant atteint lorsque l’élément n’est pas trouvé. En moyenneil procède à N/2 comparaisons. Cela est très mauvais et on sait faire beaucoup mieux.

Recherche dichotomique dans une liste triée.Un supplément d’information, permet souvent de réduire la complexité d’un problème.L’algorithme de recherche séquentielle n’utilisait que le test d’égalité avec deux réponsespossibles (oui/non). Comme les éléments (les noms) sont triés par ordre croissant. On peutréaliser un test avec trois résultats : égalité, inférieur, supérieur.

#!/prog/seq_analysis/pythonimport fonctions

# t est une liste de triplets (nom, prenom, notes) triée sur les noms# v est le nom recherchédef dicho(t,v): g=0 d=len(t)-1

while g<=d: m=(g+d)/2 test = fonctions.compare(v,t[m][0]) if test == 1: g=m+1 elif test == -1: d=m-1 else: print 'trouve en position',m return print 'pas trouve'# 'notes' est le fichier du jour 1note = fonctions.readfile('notes')dicho (note,'Grange')

- Ouvrir un texte (nedit) pour le programme "tri.py"# "driver" pour les tris en interactifimport tri # la première foisreload(tri) # les autres fois

# création du fichier de nombres aléatoiresimport randomf=open("random","w")i = 0while i < 100: f.write("%f " % random.random()) i=i+1f.close()

f=open("random","r") # lecture du fichier de nombres aléatoiresll=f.readline() # ll est une string avec toutes les valeurs

t=[] # création du tableau de valeursfor x in string.split(ll):

t.append(float(x))(ensuite trier...)

====== tri.py#!/usr/bin/python

import sysfrom copy import deepcopyimport randomimport pdb#----------------def Compare(x,y):

p=0if y < x :

p = -1elif x < y :

p = 1return p

#----------------def Echange(Tr,x,y):

#Copie en dur, par valeur pas par adresseT=deepcopy(Tr)temp=T[x]T[x]=T[y]T[y]=tempreturn T

#----------------def RechSeq(T,x):

if T[0] == x :return 0

else:L=len(T)i=0while i < L and T[i] != x :

i=i+1if i < L :

return ielse:

return -1

#----------------def RechDich(T,x):

trouve = -1i = 0j=len(T)while i <= j and trouve == -1 :

mid=int((i+j)/2)if x == T[mid] :

trouve = midelse :

if x > T[mid] :i = mid + 1

else:j = mid - 1

return trouve

#----------------def PosMin(T,x,y):

mini=xfor i in xrange(x+1,y):

if Compare(T[i],T[min]) == 1 :mini=i

return mini

#----------------def TriSeq(T):

i=0L = len(T)Trie=deepcopy(T)while i < L-1 :

min = PosMin(i,L)if i != min :

Trie=Echange(Trie,i,min)i=i+1

return Trie

#----------------def TriBulle(Tr):

permut=1L = len(Tr)T=deepcopy(Tr)i=ntot=0comp=ech=0while permut > 0 : if i == L-1 :

print "Bulle ",ntotif ntot == 0 :

permut = 0else:

i = 0ntot = 0

#pdb.set_trace() else:

p=Compare(T[i],T[i+1])comp+=1if p == -1 : ntot+=1 Trie=Echange(T,i,i+1) ech+=1i=i+1

return T,comp,ech

#----------------def TriIns(Tr):

i=1L = len(Tr)T=deepcopy(Tr)while i < L :

p=Compare(T[i-1],T[i])if p == -1 :

pos=0j=0while j < i and T[i] > T[j] :

j=j+1pos = jif pos == 0 :

temp=T[0:i]temf=T[i+1:L]T=[T[i]]+temp+temf

elif pos < i :temp=T[0:pos]temf=T[pos:i]tem2=T[i+1:L]T=temp+[T[i]]+temf+tem2

i=i+1print "TriIns ",T

return T

#----------------def TriShell(Tr) :

T=deepcopy(Tr)#Calcul du pas

h=0while h < L :

h = 3*h + 1print hwhile h > 0 :

i=hwhile i < L : valeur=T[i] j=i-h while j >= 0 and T[j] > valeur :

T=Echange(T,j,j+h)j=j-h

i+=1print h," ** ",Th = h/3

return T

#----------------def Fusion(T1,T2) :

L1=len(T1)L2=len(T2)Fus=[]i=j=0while i < L1 and j < L2 :

if T1[i] < T2[j] :Fus.append(T1[i])i+=1

else :Fus.append(T2[j])j+=1

if i == L1 :Fus.extend(T2[j:])

else :Fus.extend(T1[i:])

return Fus

#----------------def TriFusion(T) :

if len(T) == 1 :return T

else:mid=int(len(T)/2)Tfus=Fusion( TriFusion(T[:mid]) , TriFusion(T[mid:]) )return Tfus

#----------------def TriRapide(Tr,deb,fin) :

T=deepcopy(Tr)if deb < fin :

#Definition du pivot au milieupivot = (deb+fin)/2#On place le pivot au debut du tableau pour faire une

comparaison continueT=Echange(T,deb,pivot)#Comparaison des valeurs % pivot et range val inf au

debutposinf=debfor k in xrange(deb+1,fin) :

if Compare(T[k],T[deb]) == 1:posinf+=1T=Echange(T,k,posinf)

#Mettre le pivot à sa position, donc à la suite deselements qui lui sont inferieurs

T=Echange(T,deb,posinf)#Tri sous tableau gaucheT=TriRapide(T,deb,posinf)#Tri sous tableau droitT=TriRapide(T,posinf+1,fin)

return T

#----------------def main():

x=10T=[]for i in range(x) :

T.append(int(10*random.random()))#T=[2, 3, 4, 3, 5, 9, 3, 4, 1, 6]print TT=TriRapide(T,0,x)print T

main()

Jour 3 :

CoursCours optimisation (simplexe, monte carlo et méthodes dérivées (recuit simulé), gradients)

Optimisation numérique:(Cf document Minimisation numérique.doc)

- monte carlo: exemple du calcul de π

Optimisation combinatoire (Pierre)(Cf document Optimisation_combinatoire.doc)

TP: dénombrement des mono et dinucléotides (comparaison)–les dictionnaires- comptage dans les séquences des mots de longueur 1 et 2- calcul du CG skew le long d’un génome

séquence au format fasta:>NC_002162 Ureaplasma urealyticum, complete genome.atggctaataattatcaaactttatatgattcagcaataaaaaggattccatacgatcttatttctgatcaagcttatgcaattctacaaaatgctaaaactcataaagtttgcgatggtgttttatatataattgtagccaatgcctttgaaaaaagtattattaacggtaattttatt...Programme pour compter les mononucléotides, les dinucléotides, et calculer le GC Skew sur unefenêtre de longueur w avec sortie dans un fichier (lignes : <position> <GCskew>) à plotter dansgnuplot (avec plot "plotgc.txt" )

#!/usr/bin/python

# ---------------------------------------------------------def readfasta(nf):

f=open("seq.fst","r")nf="seq.fst"seq=""line=f.readline()while (line!=""):

line=f.readline()seq=seq+line[:-1]

return seq

# ---------------------------------------------------------def dico(nf):

dico={}for x in nf:

if dico.has_key(x):dico[x]=dico[x]+1

else:dico[x]=1

return dico

# ---------------------------------------------------------def dicodi(nf):

dicodi={}for i in range(len(seq[:-2])):

dicodi[seq[i:i+2]]=dicodi.get(seq[i:i+2],0)+1

for j in dicodi.keys():dicodi[j]=float(dicodi[j])/float(len(seq))

return dicodi

# ---------------------------------------------------------def compare(dico_mono,dico_dinuc):

for i in dico_dinuc.keys():fmono=float(dico_mono[i[0]]*dico_mono[i[1]])fdinuc=dico_dinuc[i]print "%s %f %f" %(i,fmono,fdinuc)

# ---------------------------------------------------------def calcgc(dicogc):

return float((dicogc["G"]-dicogc["C"]))/(dicogc["G"]+dicogc["C"])

# ---------------------------------------------------------def gc(seq,w):

gc={}gc=dico(seq[0:w])

filout=open("plotgc.txt","w")filout.write("%d %.3f\n" %(0, calcgc(gc)))

for i in range(1,len(seq)-w+1):gc[seq[i-1]]=gc[seq[i-1]]-1gc[seq[i+w-1]]=gc[seq[i+w-1]]+1

filout.write("%d %.3f\n" %(i, calcgc(gc)))

filout.close()return

# --------- MAIN ------------------------------------------seq=readfasta("seq.fst")m=dico(seq)d=dicodi(seq)

compare(m,d)

print "nombre de bases total",len(seq)

countbases=dico(seq)print countbases

dinucleotides=dicodi(seq)print dinucleotides

gc(seq,1000)

TP: camion, programmation dynamiquecamions (programmation dynamique). liens avec les séquencesprendre le fichier de villes sur le site de Joel

#---------------------------------------------------------------

#!/usr/local/bin/python

#!/usr/bin/pythonimport sys

def lit_fichier(fname):

""" A partir du nom de fichier contenant les distances entre les

paires de villes sous le format: ville1 ville2 distance, cette fonction rend la ville de depart (premier champs de la premiere ligne ainsi qu'un dictionnaire de distance ou les cles sont les paires (ville1, ville2) et les valeurs sont les distances en reels. """

f=open(fname,'r') l=f.readlines() dico={} for x in l: t=x.split() dico[t[0],t[1]]=float(t[2]) deb=l[0].split()[0] return deb,dico

#---------------------------------------------------------------

def tranche(debut,dict): """ Cette fonction a partir de la ville de depart et des cles du dictionnaire dict rend une liste de listes ou le ieme element correspond aux villes de la ieme trance a traverser """ tv=[] dd=dict.keys() temp=[debut] while len(temp)!=0: tv.append(temp) temp=[] debut=tv[-1][0] for i in dict.keys(): if i[0]==debut: temp.append(i[1]) return tv

#---------------------------------------------------------------

def chemin(liste,dict, dep): """ Cette fonction determine le chemin minimum en passant par une ville et une seule de chaque tranche de villes contenues dans liste en partant de la ville dep et en fonction des distances contenues dans dict cour correspond au meilleur chemin courrant (donc il est remis a rien a chaque nouvelle tranche l etudiee). A chaque fois qu'une tranche est terminee,je mets dans chem1 le resultat de cour. Chem1 est donc le meilleur chemin pour les villes de la lieme tranche -1."""

depart = [(dep), 0] cour=[depart] # Remplissage de cour pour la tranche 0

for l in liste[1:]: # Pour chaque tranche de villes chem1 = cour cour=[] for i in l: # Pour chaque ville de la tranche l # on fixe arbitrairement le minimum # a la premiere distance mini=chem1[0][-1]+dict[(chem1[0][-2],i)] for j in chem1: # Pour chaque ville de la tranche l-1

v=j[-2],i distemp=j[-1]+dict[v]

if distemp<=mini: mini = distemp cmini = j[:-1] cmini.append(i) cmini.append(mini) cour.append(cmini) return cour

#---------------------------------------------------------------

def main(): if len(sys.argv)!=2: print "entrez la commande sous la forme: camion.py fichier" else: fichier=sys.argv[1] dep,donnees=lit_fichier(fichier) tran=tranche(dep,donnees) #print tran print chemin(tran, donnees, dep)main()

#---------------------------------------------------------------

Jour 4 :TP: optimisation suite (recuit simulé à partir du montecarlo, gradient).Taboo search: grille à 2 dimensions

#!/usr/bin/python

import randomimport math

#fonction de rosenbroockdef rosen((x,y)):

return 100.0*(y-(x*x))*(y-(x*x))+(1-x)*(1-x)

# calcul du paysage de la fonction# sauvergarde dans fichier "paysage"# pour affichage dans gnuplot (sans "line")# Dans gnuplot, il suffira d'entrer# splot "paysage","recuit.xyz","taboo.xyz"# pour voir en 3D les chemins differe# (note: on peut aussi le faire directement# dans gnuplot, donc facultatif)def paysage(fun,xmin,xmax,ymin,ymax,pas):

f=open("paysage","w")x=xminwhile x<=xmax:

y=yminwhile y>=ymax:

f.write("%f %f%f\n" %(y,y,fun((x,y))))y=y+pas

#print x,y,fun((x,y))x=x+pas

f.close()return

## recuit simule (fichier "recuit.py")# impression des points dans fichier "recuit.xyz" a# a tracer dans gnuplot avec l'option "with line"# arguments:# f: fonction# pstart: point 2D de depart (x,y)# tempinit: Temperature de depart# Tf: Temperature finale# npas: nombre de pas a chaque temperature# pas: longueur du pas#def recuit(f,(x,y),ti,tf,pas,npas):

t = tir= open("recuit.xyz",'w')# xmin,ymin vont etre les minima courantxmin,ymin=(x,y)# X,Y va etre le minimum minimorumX,Y = (xmin ,ymin)

while t>tf:for i in range(0,npas):

x = xmin + (random.random()*2 - 1)*pasy = ymin + (random.random()*2 - 1)*pasd = f((x,y)) - f((xmin,ymin))if (d < 0):

xmin ,ymin = x,yr.write("%f %f %f\n" % (xmin,ymin,f((xmin,ymin))))if f((xmin,ymin)) < f((X,Y)):

X,Y = (xmin ,ymin)elif math.exp((-d)/t) > random.random():

xmin ,ymin = x,yr.write("%f %f %f\n" %(xmin,ymin,f((xmin,ymin))))if f((xmin,ymin)) < f((X,Y)):

X,Y = (xmin ,ymin)t=t*0.7

return (X,Y)

## taboo search## NotInList:# fonction verifiant que l'element el# n'est pas dans la liste (retourne 1# si c'est vrai)#

def NotInList(el, liste): # liste est une liste de 2-uples d'entiers

# qui sont les arrondis de 10 fois les coordonnees # de maniere a ne pas repasser par un point proche # puisque les reels ne retomberaient jamais juste # el est le tuple des coordonnees reelles du point # dont on veut savoir si il est dans la liste taboo

eli = (int(10*el[0]+5),int(10*el[1]+5)) for i in liste:

if eli == i: return 0

return 1

## taboo search: routine principale# impression des points dans fichier "taboo.xyz" a# tracer dans gnuplot avec l'option "with line"# arguments:# f: fonction# pstart: point 2D de depart (x,y)# npas: nombre de pas total a ne pas depasser# pas: longueur du pas# lentaboo: longueur de la liste tabou#def taboo(f,(x,y),npas,pas,lentaboo):

r= open("taboo.xyz",'w')n = 0listetaboo = [None]*lentaboolistetaboo[0] = (int(10*x+5),int(10*y+5))xmin,ymin = (x,y)solutions = 1while n < npas:

x = (random.random()*2 - 1)*pas + xy = (random.random()*2 - 1)*pas + yif NotInList((x,y),listetaboo) == 1 and f((x,y)) <f((xmin,ymin)) :

xmin,ymin = (x,y)solutions = solutions + 1r.write("%f %f %f\n" %(x,y,f((x,y))))listetaboo[solutions % lentaboo] = (int(10*x+5),int(10*y+5))n+=1

return (xmin,ymin)

s = recuit(rosen,(-2,2),1000,1,1.0,100)print "recuit: meilleure solution: ",s, rosen(s)

s = taboo(rosen,(-2,2),10000,1,30)print"taboo: meilleure solution: ", s, rosen(s)

Si on met les données du paysage dans « paysage », celle du trajet (x,y,f(x,y)) dans « recuit.xyz »(ou dans « taboo.xyz »), il suffit pour tracer le chemin de minimisation dans le paysage de donnerles ordres suivant dans gnuplot :splot "paysage","taboo.xyz" with line,"recuit.xyz" with line# ou mieux, on peut créer le « paysage » directement avec :set hidden3dset isosamples 30set view 60,30,1splot [-2.0:2] [-2:2] 100 * (y - (x*x))*(y - (x*x))+(1-x)*(1-x), "recuit.xyz"with line, "taboo.xyz" with line(* ceci figure la fontion de Rosenbrook en 3D avec les trajets par dessus *)

ANNEXE

Affectation: Auction algorithm:

Personnes Voitures i -> A[i] u[i,j] pour chaque j appartenant a A[i]

Si C = MAX{u[i,j]: (i,j) appartenant a A}

A chaque pas, il existe un prix price [j] pour les voitures.Marginal utility de la personne i pour acheter j -> u[i,j] - price[j]A chaque itération, une personne "non assignée" choisit un j tel que u[i,j]-price[j] est maximumOn associe a chaque personne i une value[i], plafond sur la plus haute "marginal utility",cad value[i] >= MAX{u[i,j]: (i,j) appartenant a A}On dit que: Bid[i,j] est admissible si value[i] = u[i,j] - price[j] Bid[i,j] est inadmissible si value[i] sinon

Il faut pour l'algorithme que chaque Bid soit "admissible".Si la personne i est la prochaine à être traitée et qu'elle n'a pas de Bid "admissible",alors value[i] est trop haute, et on décroît cette valeur a: MAX{u[i,j]-price[j]: (i,j) appartenant a A}Donc, l'algorithme procède en personnes "préemptant" des voitures.Si une personne i préempte une voiture j, alors le prix de j augmente de 1F; ainsi lespréemptions suivantes seront plus élevées, et i est assigné à j.La personne k qui avait une préemption sur j (si elle existe) devient "inassignée",elle devra préempter une autre voiture par la suite.Tant que le marché continue, le prix des voitures augmente et les valeurs marginales despersonnes décroissent.L'algorithme s'arrête dès que chaque personne a une voiture.On atteint un assignement optimum.

Depart: price[j] = 0 pour chaque voiturevalue[i] = MAX{u[i,j]: (i,j) appartenant a A} (c'est suffisantpour une version pseudo-polynomiale)

exemple d'affectation:Min SOMME(i,j) (xiyj) y 6 12 15 15 x 4 8 9 11 10 5 7 8 12 10 6 9Resultat: (x1y1),(x2y4),(x3y2),(x4y3), SOMME=28