Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 18-11-2016 23:45:03

capesman
Modérateur
Inscription : 15-08-2016
Messages : 129

[Info 8] - Exemples d'algorithmes de tri. Comparaison.

Bonjour,

  Cette discussion est ouverte pour parler de la leçon du capes de mathématiques : Exemples d'algorithmes de tri. Comparaison.

Capesman.

Dernière modification par capesman (27-11-2018 17:51:12)

Hors ligne

#2 22-09-2017 20:09:19

capesman
Modérateur
Inscription : 15-08-2016
Messages : 129

Re : [Info 8] - Exemples d'algorithmes de tri. Comparaison.

Bonjour,

  Voici ce que dit le rapport de jury 2017 de cette leçon :

"Cette leçon amène à exposer au moins un algorithme de tri élémentaire comme le tri par sélection, ou par insertion, ou à bulle;  développer longuement chacun de ces trois tris n’est en revanche pas attendu. Suite à une étude de la complexité de l’algorithme élémentaire choisi, on peut évoquer au moins  un algorithme de tri plus performant, comme le tri fusion ou le tri rapide. D’autres algorithmes spécifiques, adaptés quand les données ont une taille particulière, peuvent être aussi évoqués avec intérêt (voir par exemple le tri par base, ou radix sort).

Le  terme  «comparaison»  utilisé  dans  l’intitulé  peut  renvoyer  à  la  comparaison  d’un  tri  de complexité quadratique à un tri de complexité $O(n\ln n)$, mais peut également conduire le candidat à évoquer la question d’un tri «en place» ou non."

Capesman

Hors ligne

#3 27-11-2018 20:30:05

capesman
Modérateur
Inscription : 15-08-2016
Messages : 129

Re : [Info 8] - Exemples d'algorithmes de tri. Comparaison.

Bonjour,

  Voici ce que dit le rapport 2018 sur cette leçon, fautes d'orthographe d'origine conservées!

"Cette  leçon  est  sans  doute  l'une  des  plus  attractive,  mais  c'est  aussi  l'une  des  plus  exigeante  à cause de la richesse du matériel disponible.

Une première difficulté est de définir rigoureusement la spécification du tri d'un tableau. En effet, il ne suffit pas que le tableau obtenu soit trié, il faut aussi que ses éléments soient les mêmes que ceux  du  tableau  de  départ.  C'est  un  peu  délicat à  spécifier  à  cause  de  la  présence  éventuelle d'éléments répétés. Une première contribution intéressante est de proposer une fonction qui prend en paramètre deux tableaux de même taille et qui teste si le second est une version triée du premier.

Cette leçon amène à exposer au moins un algorithme de tri élémentaire comme le tri par sélection, ou par insertion, ou à bulle ; développer longuement chacun de ces trois tris n’est en revanche pas attendu.

Ces implémentations sont délicates car la gestion des indices est une source majeure d'erreur. Le candidat devra justifier très soigneusement chacune des bornes par un invariant. Ces algorithmes sont  beaucoup  plus  simples  à  implémenter  en  distinguant  soigneusement  ce  qui  concerne  le parcours  du  tableau  («le  moteur»)  et  la  détection  de  la  terminaison  («l'échappement»).  Le
parcours gagnera à être implémenté par des boucles, alors que la terminaison gagnera à être gérée par des instructions d'échappement (
break ou return).

Suite à une étude de la complexité de l'algorithme élémentaire choisi, on peut évoquer au moins un algorithme de tri plus performant, comme le tri fusion ou le tri rapide. D’autres algorithmes spécifiques, adaptés quand les données ont une taille particulière, peuvent être aussi évoqués avec intérêt (voir par exemple le tri par base, ou radix sort). Un cas souvent négligé est celui où le tableau initial  ne  contient  qu'un  petit  nombre  donné  de  valeurs  qu'il  est  alors  possible  de  trier  en  temps  linéaire  en comptant le  nombre d'occurrences de chaque  valeur puis en reconstituant  le tableau final  à  partir  de  ce  décompte.  On  pourra  remarquer  que  l'utilisation  d'un  dictionnaire  Python  est particulièrement pratique pour programmer ce type d'algorithme.

Le terme « comparaison » utilisé dans l’intitulé peut renvoyer à la comparaison d’un tri de complexité quadratique à un tri de complexité $O(n\ln n)$),  mais peut également conduire le candidat à évoquer la question d’un tri « en place » ou non.


Capesman

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
quatre-vingt dix-neuf plus treize
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums