0. Modalités

1.Vous disposez de une heure et quarante cinq minutes,

2.vos documents personnels sont autorisés,

3.vos algorithmes seront commentés,

4.le barème est donné à titre indicatif et est susceptible d'être modifié,

Algorithmique

1. Tri sélection

Le tri (en copie) d’une liste par la méthode de sélection consiste à rechercher systématiquement l’élément le plus petit de la liste à trier, le mettre en fin de la liste triée, le supprimer de la liste à trier et recommencer l’opération autant de fois que nécessaire. C’est ce tri que nous souhaitons programmer.

2.1. Ecrire, sous forme de pseudo-code, un algorithme de recherche de l’indice de l’entier minimum dans une liste quelconque d’entiers (env. 2 pts)

2.2. Ecrire, sous forme de pseudo-code, un algorithme de suppression d’un élément d’indice donné dans une liste d’entiers (env. 2 pts)

2.3. Ecrire, sous forme de pseudo-code et en utilisant les deux algorithmes précédents, un algorithme de tri par la méthode de sélection (env. 2 pts)

Remarque : Il est inutile de réécrire les deux premiers algorithmes, il suffit de dire à quel moment vous utilisez l’un ou l’autre.

2.5. Quelle est la complexité de l’algorithme de tri par sélection ? (env. 1 pts)

2. Indexation et recherche dans une liste indexée

L’une des méthodes les plus utilisée pour effectuer des recherches rapides dans des listes triées, de tailles importantes mais ne subissant que peu de modifications est l’indexation. Cette technique consiste à fabriquer une liste de repères sur la liste afin, lors d’une recherche, de pouvoir sauter très rapidement au début de la zone de recherche et restreindre ainsi la recherche effective à une petite partie de la liste.

Exemple 1 : un dictionnaire de mots triés dans l’ordre alphabétique serait muni d’une liste d’index donnant la position du premier mot commençant par A, la position du premier mot commençant par B, … La recherche d’un mot (par exemple Informatique) ne se ferait alors plus par une recherche sur l’ensemble du dictionnaire mais simplement entre la position de début des mots en I et la position de début des mots en J.

Exemple 2 : La liste triée d’entiers

4 ; 12 ; 34 ; 44 ; 46 ; 52 ; 55 ; 59 ; 74 ; 88 ; 125 ; 148

se verrait dotée, pour une fréquence de 10, d’une liste d’index

0 ; 1 ; -1 ; 2 ; 3 ; 5 ; -1 ; 8 ; 9 ; -1 ;-1 ;-1 ; 10 ;-1 ; 11

signifiant que les unités commencent à l’indice 0, les dizaines à l’indice 1, qu’il n’y a pas de vingtaines, les trentaines commencent à l’indice 2, …, les cinquantaines commencent à l’indice 5, …

se verrait dotée, pour une fréquence de 5, d’une liste d’index

0 ; -1 ; 1 ; -1 ; -1 ; -1 ; 2 ; -1 ; 3 ; 4 ; 5 ; 6 ; -1 ; -1 ; 8 ; -1 ; -1 ; 9 ; -1 ; -1 ; -1 ; -1 ; -1 ; -1 ; -1 ; 10 ; -1 ; -1 ; -1 ; 11

signifiant que les unités commencent à l’indice 0, il n’y a pas de nombres entre 5 et 10, les nombres entre 10 et 15 commencent à l’indice 1, …, les nombres entre cinquante et cinquante-cinq commencent à l’indice 6, …

2.1. Ecrire, sous forme de pseudo-code, un algorithme d’indexation, selon une fréquence donnée, d’une liste triée d’entiers positifs (env. 4 pts)

Cet algorithme sera simple et pourra faire appel au divisions entières ou être plus rusé …

2.2. Combien d’opérations élémentaires (quelles opérations élémentaires ?) sont effectuées par votre algorithme d’indexation pour une liste de taille N et une fréquence d’indexation de freq ? (env. 2 pts)

2.3. Ecrire, sous forme de pseudo-code un algorithme de recherche de la place d’insertion d’un élément dans une liste d’entiers positifs triée et indexée (env. 5 pts)

L’algorithme rendra la place de l’élément si celui-ci appartient à la liste ou sa place d’insertion dans la liste triée si il n’appartient pas.