Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Répondre
Résumé de la discussion (messages les plus récents en premier)
- capesman
- 27-11-2018 21:30:05
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
- capesman
- 22-09-2017 21:09:19
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
- capesman
- 19-11-2016 00:45:03
Bonjour,
Cette discussion est ouverte pour parler de la leçon du capes de mathématiques : Exemples d'algorithmes de tri. Comparaison.
Capesman.