Les tris - NSI

Activité d'apprentissage

TRIS

ObjectiFs

III. Retour sur les gammes

I. Construction de la gamme de Pythagore

II. Les tris

Plan de l'activité

Attendus du programme

Les notions que nous allons aborder

Objectifs

Comment nous allons aborder ces notions

Objectifs

Nous allons voir les algorithmes de tris à travers la gamme de Pythagore et trier les fréquences de cette gamme. Les plus rapides utiliseront les résultats de ces tris pour comparer 2 gammes entre elles. Pour la première partie, nous nous appuierons sur vos connaissances en enseignement scientifique dans le chapitre "La musique ou l'art de faire entendre les nombres". Nous verrons ensuite les fonctions de tri et des outils pour valider les algorithmes puis nous comparerons la gamme de Pythagore à celle de Bach pour trouver les notes communes.

I. Construction de la gamme de Pythagore

Question Votre fichier de travail contient une fonction gamme_Pythagore qui reçoit en entrée une fréquence (réel) f et retourne la liste des fréquences des 12 notes (fréquence de départ comprise) de la gamme de Pythagore. 1. Afficher la liste retournée par la fonction gamme_Pythagore pour la gamme de Do (f=261,6 Hz) à 12 notes. Quel est l'ordre des fréquences dans cette liste ?

I. Construction de la gamme de Pythagore

Rappel d'enseignement scientifiqueUne gamme est un ensemble de notes réparties sur une octave. Les pythagoriciens construisent une gamme dont les notes sont séparées d'une quinte. La quinte est définie par le rapport de fréquence 3/2 et l'octave par le rapport 1/2. La gamme de Pythagore se construit par quintes successives avec retour dans l'octave si la nouvelle fréquence est hors de l'octave d'étude.

Nous souhaitons que les fréquences de notre gamme de Pythagore soient rangées dans l'ordre croissant de leurs valeurs. Les fonctions de tri permettent de classer les donnée d'un tableau dans un ordre défini (par exemple ordre croissant, décroissant). Certains langages ont de fonctions prédéfinies qui effectuent ces opérations de tri mais il est nécessaire de connaître les principes des algorithmes de tris pour être paré en cas de besoin de tri inconnu de notre langage. Ces algorithmes de tri nous permettent d'introduire des concepts d'algorithmique que l'on retrouvera dans de nombreux autres algorithmes. Nous verrons tout d'abord les tris par insertion et par sélection puis les concepts liés à ces algorithmes.

ii. Les tris

1. Le tri par insertion

C'est le tri utilisé par les joueurs de cartes pour ranger leur jeu. Dans l'animation ci-dessous, choisir "tri par insertion" et commencer le tri

Animation

Soyez particulièrement attentifs à l'évolution du tableau à trier (en jaune) et à l'évolution des valeurs des itérateurs (i et j) et de la valeur stockée (élément) dans la partie bleue.

Si vous souhaitez voir l'évolution des indices des boucles de l'algorithme ci-dessus, le lien ci-dessous, vous amène sur une page où vous pouvez faire avancer l'algorithme pas à pas. (Attendez peut-être quelques secondes pour obtenir l'écran ci-contre).

• Dans la partie gauche, utilisez le bouton next pour faire avancer votre algorithme pas à pas.
• Dans la partie droite, suivez le résultat de l'algorithme.

On peut écrire l'algorithme de la manière suivante, on remarque qu'il y a 2 boucles (bleue et rouge) imbriquées.

Questions 2. Écrire manuellement l'état du tableau (8,6,1,9,7,2) à la fin de chaque boucle bleue du tri par insertion 3. Compléter la fonction de tri_insertion dans votre fichier de travail (penser à enlever le # devant def) et l'appliquer à l'exemple précédent.

Lien

Principe

II. Les tris

Animation

Dans l'animation ci-dessous, choisir "tri par sélection" et commencer le tri

Questions 4. Écrire manuellement l'état du tableau (8,6,1,9,7,2) à la fin de chaque boucle principale du tri par sélection 5. Compléter la fonction de tri_selection dans votre fichier de travail (penser à enlever le # devant def) et l'appliquer à l'exemple précédent.

Link

Soyez particulièrement attentifs à l'évolution du tableau à trier (en jaune) et à l'évolution des valeurs des itérateurs (i et j) et de la valeur stockée (maximum) dans la partie bleue.

Si vous souhaitez voir l'évolution des indices des boucles de l'algorithme ci-dessus, le lien ci-dessous, vous amène sur une page où vous pouvez faire avancer l'algorithme pas à pas. (Attendez peut-être quelques secondes pour obtenir l'écran ci-contre).

• Dans la partie gauche, utilisez le bouton next pour faire avancer votre algorithme pas à pas.
• Dans la partie droite, suivez le résultat de l'algorithme.

2. Le tri par sélection

Principe

II. Les tris

On peut écrire l'algorithme que vous venez de voir de la manière suivante on remarque à nouveau qu'il y a 2 boucles (bleue et rouge) imbriquées.

Avez vous bien compris les principes de ces 2 tris ?

Principe

II. Les tris

Correction Nous aborderons cette notion en ensemble en classe. Néamoins, pour les curieux, une explication brute.

Terminaison De nombreux algorithmes contiennent des boucles bornées (boucles pour) ou non bornées (boucles tant que). S'assurer qu'un algorithme va s'arrêter quelles que soient les données est primordial et s'appelle vérifier la terminaison d'un algorithme. Les boucles bornées s'arrêtent une fois la borne supérieure du compteur atteinte et ne posent donc pas de problème de terminaison. Les boucles non bornées peuvent provoquer des boucles infinies, il est donc important de vérifier leur terminaison. Pour prouver la terminaison d'une boucle, il faut choisir un variant de boucle, c'est à dire une variable ou une expression qui évolue à chaque tour de boucle, et montrer qu'il évolue vers une valeur finie.

3. Concepts en algorithmique

concepts algorithmiques

II. Les tris

Complexité La complexité d'un algorithme traduit le nombre d'opérations que fait un algorithme pour s’exécuter en fonction du nombre de données en entrée. Cette notion a été vue dans les chapitres précédents.

8. Prouver la terminaison de cet algorithme de tri. 9. Reprendre les 3 questions précédentes pour le tri par sélection

Terminaison

Rappel de l'algorithme du tri par insertion

Questions - Application au tri par insertion.

concepts algorithmiques - Questions

II. Les tris

Complexité 6. Quel est le pire cas pour cet algorithme de tri ? Le meilleur cas ? 7. Établir la complexité de cet algorithmes de tri.

iII. retour sur nos gammes

Pour les plus rapides La fonction gamme_Bach de votre programme prend une fréquence de départ en entrée et renvoie la liste des fréquences de la gamme tempérée. Lorsque l'on écoute les notes des deux gammes de Do (f=261,6 Hz) créées, on entend des différences entre les notes de même rang. On peut considérer 2 notes identiques si la différence entre leurs fréquence est inférieure à 0,5 Hz. 11. Compléter la fonction comparaison_gammes qui reçoit une fréquence f (réel) de départ de gamme et retourne les noms des notes communes entre les gammes de Pythagore et de Bach. 12. Quelles sont les notes communes des gammes de Do (261,6 Hz) de Pythagore et Bach ?

Nous allons maintenant pouvoir trier notre gamme. 10. Appliquer une fonction de tri de votre choix au résultat votre fonction gamme_Pythagore pour obtenir les fréquences des notes dans l'ordre croissant.

Questions

III. Retour sur les gammes

Fin !