Note : aucun document autorisé.
On appelle séquence d'entiers une suite finie ordonnée d'entiers relatifs. Par exemple, la séquence suivante contient 6 éléments :
25 4 12 9 17 32
1. Spécifier un type abstrait séquence avec les constructeurs et opérations suivants :
2. Donner deux invariants du type séquence.
3. Spécifier et réaliser les deux fonctions ci-dessous en utilisant seulement les constructeurs et opérations du type abstrait :
3.a La fonction concaténation prend en argument deux séquences s1 et s2 et retourne la séquence constituée des éléments de s1 suivis des éléments de s2. Par exemple, la concaténation de la séquence 10 20 30 et de la séquence 5 50 500 donne la séquence 10 20 30 5 50 500.
3.b La fonction sous-séquence prend en argument une séquence s et deux rangs i et j et retourne la séquence constituée des éléments de s compris entre les rangs i et j. Par exemple, la sous-séquence de 25 4 12 9 17 32 comprise entre les rangs 2 et 4 est la séquence 4 12 9.
4. Spécifier et réaliser les fonctions suivantes (on pourra utiliser les deux fonctions de la question 3 si nécessaire) :
4.a Rang du plus petit élément d'une séquence. Par exemple, le plus petit élément de la séquence 25 4 12 9 17 32 est 4, qui est le deuxième de la séquence, donc la valeur à retourner est 2.
4.b Retrait de l'élément de rang i d'une séquence. Par exemple, lorsque l'on retire l'élément de rang 3 de la séquence 25 4 12 9 17 32, on obtient la séquence 25 4 9 17 32.
4.c Insertion d'un élément à un rang donné dans une séquence. Par exemple, l'insertion de l'élément 10 au rang 3 dans la séquence 25 4 12 9 17 32 donne la séquence 25 4 10 12 9 17 32.
5. On désire définir une fonction qui prend en argument une séquence s et retourne une séquence contenant les mêmes éléments que ceux de s triés par ordre croissant. Appliquée à la séquence 25 4 12 9 17 32, cette fonction retourne la séquence 4 9 12 17 25 32. Pour chacune des deux méthodes ci-dessous, spécifier et réaliser cette opération de tri :
5.a Prendre le plus petit élément de la séquence non triée, le retirer de la séquence non triée et l'ajouter à la fin de la séquence triée. Répéter jusqu'à ce que la séquence non triée soit vide.
5.b Prendre chaque élément de la séquence non triée, chercher son rang dans la séquence triée et l'insérer à ce rang.
6. On décide de réaliser le type abstrait séquence par un type produit formé d'un tableau contenant les éléments de la séquence et d'un entier contenant le nombre d'éléments de la séquence. Le tableau est supposé être assez grand pour pouvoir contenir toutes les séquences qui seront utilisées par le programme.
6.a Donner la déclaration de ce type concret dans le langage de réalisation.
6.b Réaliser les constructeurs et opérations de la question 1 avec ce type concret.
6.c Réaliser les fonctions de la question 3 (concaténation et sous-séquence) avec ce type concret en tirant parti du codage implicite.
On souhaite représenter (de façon simplifiée) les notes obtenues par les étudiants en fin de DEUG MIAS. Dans chaque module M0, M1, M2, M3, chaque étudiant obtient une note de partiel et une note d'examen dans les 3 matières suivantes : mathématiques, physique, informatique. De plus, en M2 et M3, les étudiants choisissent une spécialisation (physique ou informatique) et obtiennent une note dans la spécialisation choisie. La note finale de chaque module est la moyenne des notes obtenues dans ce module, et la note finale du DEUG est la moyenne des notes des modules. Un étudiant est reçu s'il a obtenu plus de 10 à chaque module.
1. Spécifier un type concret étudiant contenant l'ensemble des informations nécessaires pour représenter les notes d'un étudiant. On pourra spécifier un ou plusieurs types auxiliaires, par exemple pour représenter les notes d'un module.
2. Spécifier et réaliser une action qui :
3. On représente l'ensemble des étudiants du DEUG par un tableau dont les éléments sont du type étudiant. Spécifier et réaliser l'action qui prend en argument un module et affiche la proportion d'étudiants reçus à ce module.
Donner une condition nécessaire pour qu'une itération tantque ou répéter ne boucle pas indéfiniment. Donner un exemple qui montre que cette condition n'est pas suffisante.