Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Correction td algo in3 2020

CORRECTION FICHE TD ALGORITHMIQUE IN Exercice Expliquez la di ?érence entre les notations O et sans donner leur dé ?nition formelle O exprime une borne supérieure sur la consommation de ressources exprime une borne inférieure sur la consommation de ressources Les algorithmes diviser-pour-régner et de programmation dynamique sont tous deux basés sur une relation de récurrence Expliquez cependant la di ?érence fondamentale entre les deux techniques de conception Diviser-pour-régner procède de haut en bas alors que la programmation dynamique procède de bas en haut Qu ? est-ce qu ? un algorithme vorace Un algorithme vorace est un algorithme qui fait toujours le choix qui lui semble le meilleur sur le moment Autrement dit il fait le choix localement optimal dans l ? espoir que ce choix conduira à une solution globalement optimale Exercice Complexité Le if ? s ? exécute en O et le return ? e ?ectue T n- appels récursifs la complexité du code précédent sera donc sous la forme T n T n- avec T on aura donc T n T n- T n- T n- T n- ? ? n T n- n- ? or T n n- n- ? n ?? n ? T n O n Algorithme int T int n int T new int if n ? return else return T n- juste T n- appels récursifs return T n Complexité O n CExercice T n T n n il faut utiliser la substitution pour prouver que T n O n log n car T n a la même complexité qu ? un T ? n T ? n n dont la complexité O n log n est facile à obtenir car classique Supposons donc que T n O n log n et montrons que T n O n log n il existe alors c R tq T n ? c n log n ? T n ? c n log n c n log n ?? log ? T n n ? c n log n ?? log n pour c log on aura ? T n c n log n d ? o? T n O n log n On a T n T n n n n n n ? ? ? k ? n k n n ? T n T n n T n T n ? n T n ? T n ? n ? T n k T k on a n k ? k log n c ? n c n n c ? n ? ? n ? ck k n k k n T n c c ? ck n ? ? k n k ?? ?? n log n ?? or log n elog n ln e ln n ln ln ?? ln e ln n log ?? e ln n n T n n n ? T n O n ? T n T n log n on doit e ?ectuer un changement de variable ici Pour se faciliter la t?