Chapitre 21 : Diviser pour régner

Question 1

$	ext{Algorithmique}$

Accepted Answer

$	ext{Branche de l'informatique dédié à l'étude des techniques de conception algorithmique}$

Question 2

$	ext{Paradigmes algorithimiques}$

Accepted Answer

$	ext{Techniques de conception algorithmique}$

Question 3

$	ext{Schéma d'un algorithme diviser pour régner}$

Accepted Answer

$\begin{cases}	ext{Diviser} \ 	ext{Régner} \ 	ext{Rassembler / Fusion}\end{cases}$

Question 4

$	ext{Étape "Diviser" d'un algorithme DPR}$

Accepted Answer

$	ext{On décompose le problème en plusieurs sous-problèmes de même nature et indépendants}$

Question 5

$	ext{Étape "Régner" d'un algorithme DPR}$

Accepted Answer

$	ext{On résout les sous-problèmes récursivement jusqu'à atteindre un cas de base}$

Question 6

$	ext{Étape "Rassembler / Fusion" d'un algorithme DPR}$

Accepted Answer

$	ext{On construit la solution du problème en combinant celles des sous-problèmes}$

Question 7

$	ext{Relation de récurrence vérifier par la complexité d'un algorithme DPR}$

Accepted Answer

$T(n) = aT(\frac{n}{b}) + O(f(n))$

Question 8

$	ext{Compléxité d'un algorithme vérifiant : } T(n) = T(\frac{n}{2}) + O(1)$

Accepted Answer

$T(n) = O(ln(n))$

Question 9

$	ext{Compléxité d'un algorithme vérifiant : } T(n) = 2T(\frac{n}{2}) + O(1)$

Accepted Answer

$T(n) = O(n)$

Question 10

$	ext{Compléxité d'un algorithme vérifiant : } T(n) = 2T(\frac{n}{2}) + O(n)$

Accepted Answer

$T(n) = O(n 	imes ln(n))$

Question 11

$	ext{Algorithme naïf}$

Accepted Answer

$	ext{Algorithme le plus évident pour résoudre un problème donné}$

Alle Karten