DM Informatique

[angelV]

Bonjour,

J'ai reçu un DM d'informatique composé de 5 exercices.

Cependant, 2 exos me posent de gros problèmes car je ne l'ai comprends totalement pas...

J'ai n'ai aucune idée, aucune piste sur les réponses attendues ...

Merci d'avance pour votre aide ! ?

 

[julesx]

Bonjour,

Pour le 2), je ne peux pas t'aider, je suppose que tu peux retrouver certaines réponses dans le cours ou sur la toile. La seule chose, à mon avis, est qu'aucune des réponses à la question 3), n'est correcte. Pour moi le rang de la médiane est donné par n//2+1.

Pour le 3)

Pour la partie A :

Je suppose que tu as trouvé l'aide sur append et les réponses aux questions 1.1 et 1.2.

Pour la suite, il faut écrire le code donné dans l'énoncé et y rajouter la transcription de l'algorithme, simplement  il faut penser à transformer "pour k allant de 1 à n-1" en "k allant de 1à n" à cause de la syntaxe propre à Python pour l'instruction "for". Pour moi, cela donne

def tri_insertion_croissant(tableau):
  for j in range(1,len(tableau)):
    cle=tableau[j]
    i=j-1
    while i>=0 and tableau>cle:
      tableau[i+1]=tableau
      i=i-1
    tableau[i+1]=cle
  return tableau
 
def tri_insertion_decroissant_1(tableau):
  n=len(tableau)
  tableau_croissant=tri_insertion_croissant(tableau)
  tableau_decroissant=[]
  for k in range(0,n):
    tableau_decroissant.append(tableau_croissant[(n-1)-k])
  return tableau_decroissant

tab=[5,4,0,7,2]
print(tri_insertion_decroissant_1(tab))

Je te laisse juge pour la question 2.3.

Pour la partie B :

3.1 A vérifier, mais, pour moi, il suffit de remplacer > par < dans le test avec la cle.

Ensuite, là encore, regarde ce qu'il en est de la  "docstring" et du "docstest" et adapte le à ton code.

 

Voilà, c'est tout ce que je peux faire pour toi.

 

[Étienne9]

Hello,

Exercice 2 :

1)

a) => Faux ! Par exemple, si tu as une boucle n fois avec une instruction en téta 0, la fonction aura la même complexité d'une boucle n avec 2 instructions en téta 0. Le nombre d'instructions n'est pas le même....

b) => Personnellement je dirais FAUX mais vu les autres propositions, il faut je pense dire oui quand même à ce point là. Pourquoi je dis non ? Car n² je ne peux pas te dire, ça va prendre 20 minutes et 32 secondes et 6 nanosecondes !!! ça va dépendre du paramètre que tu auras passé, et comme vu au point 1, tu peux avoir un nombre d'instructions différent pour 2 algo de même complexité. Et même, la puissance de la machine va jouer aussi... Donc c'est un ordre de grandeur du temps OUI mais dans la précision NON

c) => Faux ! La complexité n'a aucun lien avec la qualité du résultat, du moins pas toujours, sinon on met 24 000 boucles imbriquées qui ne servent à rien, la complexité est plus élevée voire catastrophique, si c'est pour calculer a*b on n'aura pas un meilleur résultat pour autant....

d) => Faux ! S'il y a un tableau de 100 éléments, au premier tour de boucle la recherche linéaire a éliminé 1 élément, tandis que la dichotomie en a éradiqué dans les 50 éléments ! Elle coûte beaucoup moins cher que 2 fois moins... Elle ne fonctionne que sur un tableau trié par contre....D'un côté téta n de l'autre téta de log n

 

2)

a) Faux ! Certains algorithmes sont plus rapides quand c'est déjà trié. Si déjà trié ou presque trié: il vaut mieux utiliser le tri par insertion cf Wikipédia

b) Faux ! J'ai regardé vite fait pour voir comment il fonctionne, on aura du téta n ! La deuxième boucle ne sera jamais effectuée car l'élément sur lequel on est sera toujours plus petit que son voisin de droite donc aucune valeur à bouger

c) Vrai ! Cf point ci-dessus

d) Faux ! Temps quadratique ! Il ne réalisera même pas que c'est déjà trié et pour chaque élément, il va tout parcourir ce qu'il reste pour rechercher à chaque fois le plus petit et le mettre devant alors que tout est déjà trié....

 

Et moi je te laisse là, je vois qu'on t'a aidé pour le 3, je fais confiance ^^