Graphes, recherche arborescente et complexité

Thèmes abordés

Algèbre, algorithme, fonctions mathématiques, instance positive, instance négative, arborescence

Résumé du document

Le document est un devoir corrigé de niveau Master, composé de deux problèmes incluant différentes questions : instances, fonctions, algorithmes, variables et boucles

Extraits

[...] et sont images par r de trois entiers b et chacun de ceux-ci pouvant appartenir à Y ou Z. On va tester les différents cas possibles (le nom des variables n'ayant pas d'importance, on peut les réordonner si nécessaire). Sia,b,c∈X:a'+b'+c'=10a+1+10b+1+10c+1=10(a+b+c)+3qui ne peut pas être nul. Sia,b,c∈Y:a'+b'+c'=10a+2+10b+2+10c+2=10(a+b+c)+60 qui ne peut pas être nul. Sia,b,c∈Z:a'+b'+c'=10a-3+10b-3+10c-3=10(a+b+c)-9 qui ne peut pas être nul. Sia,b∈X,c∈Y:a'+b'+c'=10a+1+10b+1+10c+2=10(a+b+c)+4 qui est non nul. Sia,b∈X,c∈Z:a'+b'+c'=10a+1+10b+1+10c-3=10(a+b+c)-1 qui est non nul. (Pareil avec a,b∈Y,c∈X, a,b∈Y,c∈Z, a,b∈Z,c∈X, a,b∈Z,c∈Y). Il reste le cas a∈X,b∈Y,c∈Z: a'+b'+c'=10a+1+10b+2+10c-3=10(a+b+c), qui est nul si et seulement si a+b+c = 0. [...]

[...] Graphes, recherche arborescente et complexité Exercice 1 - Un problème dans la classe P Question 1 1.a. La liste [6,−7,− 10,− est une instance positive de ZERO car 6 + 12 + = 0 1.b. La liste [−10, 13,−7,−2,−4] n'est pas une instance positive de ZERO. En effet, supposons qu'il existe trois nombres dont la somme est nulle. Le seul nombre positif de cette liste est 13, donc il doit forcément être un des trois nombres, sinon la somme des trois nombres serait strictement négative. [...]

[...] On part de et on calcule E=r(X,Y,Z). On utilise la fonction testZERO pour savoir si E est une instance de ZERO ou non. Cela nous dira si est une instance de TRILISTE ou non. 8.b. def testTRILISTE(X: list[int], list[int], list[int]) bool: red = reduction(X, return testZERO(red) Question 9. reduction estO(n)et testZERO estO(n2), donc testTRILISTE estO(n2)(carn [...]

[...] On sait qu'un algorithme de tri a une complexité au mieux deO(nlogn). La boucle for parcourra au maximum n-2 éléments (du 1[er] à l'avant-avant-dernier). La boucle while, elle, pourra être parcourue au maximumn-2fois, dans le cas où les valeurs dep et fin sont consécutives (par exemple si dep=1 et fin=2, alors la variable dep n'aura pas changé de valeur et fin aura décrémenté den-1à ce qui fait bienn-2étapes). Au final, on aura parcouru les boucles un nombre inférieur ou égal à(n-2)2et donc la complexité des deux boucles de l'algorithme est deO(n2). [...]

[...] La taille de la sortie est égale à X + Y + Z car chaque élément des ensembles Y et Z a son image dans la liste finale. La taille de la sortie est donc identique à la taille de départ. Question 7 7.a. { = { -3}∈ZEROcar 11+32-43 = 0. { = { 37}∉ZEROcar tous les termes sont positifs. 7.b. Soit tels que x+y+z=0. Alors si on note les images de y et z par la transformation on a x'+y'+z'=10x+1+10y+2+10z-3=10(x+y+z)=0. [...]