Sujet pdf

Les implantations demandées dans cette épreuve sont à réaliser en langage algorithmique à l'exception des questions 3a et 3c pour lesquelles les codages en langage Java et en langage algorithmique sont demandés.
Le seul document autorisé est la fiche PDL-Java.

Exercice n°1

a) Dans quelle mesure est-il possible de développer un type agrégé dont un ou plusieurs champs sont eux-mêmes de type agrégé?

L'utilisation d'un type agrégé en tant que type de définition pour un champ créé au sein d'un type agrégé est possible. La seule restriction est que la création d'un cycle est interdite. C'est à dire qu'un type agrégé A ne peut pas contenir parmi ses champs un champ lui-même défini de type agrégé A. La notion de cycle est à étendre aux cycles plus longs. Par exemple, en longueur 2, le type agrégé A ne peut pas utiliser le type agrégé B si celui-ci utilise le type A pour l'un de ses champs.

b) Quel est le rôle des paramètres d'entête d'un sous-algorithme?

Les paramètres d'entête permettent l'échange d'informations entre un sous-algorithme et l'algorithme qui va l'utiliser (l'appeler). Chacun des paramètres est défini dans la liste des paramètres par son nom, par son type et par un modificateur qui indique dans quel sens est réalisée la communication:
 - en "Données" pour le sens entrant dans le sous-algorithme,
 - en "Résultats" pour le sens sortant du sous-algorithme,
 - en "Données/Résultat" pour une communication dans les sens entrant et sortant.
Une matérialisation concrète du caractère de ses modificateurs est la suivante: Les paramètres définis en "Données" seront lus dans le sous-algorithme et ne subiront pas d'affectation. Les paramètres définis en "Résultats" seront affectés mais pas lus. Les paramètres définis en "Données/Résultats" seront lus et affectés.

c) De quels types peuvent être définis les composantes élémentaires d'un tableau?

Les composantes élémentaires d'un tableau peuvent être définies de n'importe quel type prédéfini (booléen, réel, entier, caractère, chaîne de caractères) ou n'importe quel type défini/créé par le développeur (type agrégé voire type tableau).

d) Un tableau étant défini de taille N entière, quel est l'intervalle de validité des indices de ses composantes?

[0, N-1]

Exercice n°2

Lorsque l'on génère une série de 20 valeurs booléennes calculées individuellement avec la probabilité p d'obtenir un "vrai", le nombre nbv de vrais comptabilisés sur cette série peut être 0, 1, 2, 3, 4, ..., 20. On souhaite analyser la distribution des valeurs nbv sur un échantillon de 1000000 de séries de 20 booléens. On souhaite donc calculer combien de fois 0 vrai, combien de fois 1 vrai, combien de fois 2 vrais, ..., combien de fois 20 vrais ont été obtenus.
Développer sous la forme d'un algorithme principal faisant appel à des sous-algorithmes de résolution de problème élémentaire le programme informatique de réalisation des traitements suivants:
  • Déclaration d'un tableau tnbv de 21 entiers.
  • Initialisation de ce tableau avec des 0.
  • Génération de 1000000 de séries de 20 booléens tirés au sort avec la probabilité p d'obtenir la valeur "vrai" (p acquise au clavier dans l'algorithme principal). Pour générer des nombres aléatoires, on pourra utiliser la fonction réel random() qui retourne un réel tiré au sort avec équiprobabilité entre 0.0 et 1.0.
  • Concurremment à la génération de chacune des 1000000 séries, calcul, pour chacune d'elles, du nombre nbv de "vrai" qu'elle contient et comptabilisation (addition de 1) de cette valeur dans tnbv.
  • Affichage du tableau tnbv.

Un certain nombre de problèmes élémentaires peuvent être extraits du problème complexe à programmer:
 (1) Initialiser à 0 les valeurs d'un tableau de N entiers (N = 21).
 (2) Générer un booléen tel que la probabilité d'obtention d'un vrai soit égale à une valeur p donnée.
 (3) Générer une série de M booléens selon la probabilité p donnée que chacun d'eux soit un vrai (M = 20).
 (4) Calculer le nombre de vrais contenus dans une série de M booléens (M = 20).
 (5) Afficher un tableau de N entiers (N = 21).
Le problème élémentaire (3) fait appel au problème élémentaire (2).
Le problème complexe fait appel aux problèmes (1), (3), (4) et (5).

(1) Une action est développée. Elle prend en paramètre en "Résultats" le tableau de N = 21 entiers à initialiser à 0.
(2) Une fonction est développée. Elle retourne un booléen et prend en paramètre en "Données" la probabilité p définie de type réel.
(3) Une série de M booléens est modélisée par un tableau de M booléens. Une fonction est développée. Elle retourne un tableau de M = 20 booléens et prend en paramétre en "Données" la probabilité p définie de type réel.
(4) Une fonction est développée. Elle retourne un entier et prend en paramètre en "Données" un tableau de M = 20 booléens.
(5) Une action est développée. Elle prend en paramètre en "Données" le tableau de N = 21 entiers à afficher.

constante N : entier <- 21
constante M : entier <- 20

{                             (1)                           }
{ Fonction de generation d'un booleen selon une probabilite }

booleen fonction booleenSelonProbabilite(p)
  Données
    p : réel
  Locales
    res : booléen
  si random() < p alors
    res <- vrai
    sinon
    res <- faux
  fsi
  retourner res
fin fonction

{                             (2)                           }
{ Action d'initialisation a zero des valeurs                }
{ d'un tableau de N entier                                  }

action initialisation(t)
  Résultats
    t : Tableau[N] de entier
  Locales
    i : entier
  pour i de 0 à N-1 faire
    t[i] <- 0
  fait
fin action

{                             (3)                           }
{ Fonction de generation d'un tableau de M booleens         }
{ selon une probabilite                                     }

Tableau[M] de booleen fonction generationSerie(p)
  Données
    p : réel
  Locales
    i : entier
    res : Tableau[M] de booleen
  pour i de 0 à M-1 faire
    res[i] <- booleenSelonProbabilite(p)
  fait
  retourner res
fin fonction

{                             (4)                           }
{ Fonction de comptage du nombre de vrais contenus          }
{ dans un tableau de M booleens                             }

entier fonction nombreVrais(t)
  Données
    t : Tableau[M] de booleen
  Locales
    i : entier
    res : entier <- 0
  pour i de 0 à M-1 faire
    si t[i] = vrai alors
      res <- res+1
    fsi
  fait
  retourner res
fin fonction

{                             (5)                           }
{ Action d'affichage des valeurs d'un tableau de N entier   }

action affichage(t)
  Données
    t : Tableau[N] de entier
  Locales
    i : entier
  pour i de 0 à N-1 faire
    Ecran.afficherln(t[i])
  fait
fin action

{ Action principale                                         }

action principale()
  Locales
    i : entier
    serie : Tableau[M] de booleen
    tnbv : Tableau[N] de entier
    p : reel
    nbv : entier
  Ecran.afficher("Probabilite ? ")
  p <- Clavier.saisirReel()
  initialisation(tnbv)
  pour i de 1 à 1000000 faire
    serie <- generationSerie(p)
    nbv <- nombreVrais(serie)
    tnbv[nbv] <- tnbv[nbv]+1
  fait
  affichage(tnbv)
fin action

Exercice n°3

Un porte-monnaie peut contenir des pièces de 1, 2, 5, 10, 20, 50 centimes et des pièces de 1 et 2 euros. On souhaite modéliser et manipuler des porte-monnaie dans une application informatique.

a) Définir un type agrégé porteMonnaie. Donner les codages en langage algorithmique et en langage Java.

On stocke les nombres de pièces de 1, 2, 5, 10, 20, 50 centimes et les nombres de pièces de 1 et 2 euros.

structure porteMonnaie
  nb1c  : entier <- 0
  nb2c  : entier <- 0
  nb5c  : entier <- 0
  nb10c : entier <- 0
  nb20c : entier <- 0
  nb50c : entier <- 0
  nb1e  : entier <- 0
  nb2e  : entier <- 0
fin structure

En langage Java

static class PorteMonnaie {
  int nb1c  = 0;
  int nb2c  = 0;
  int nb5c  = 0;
  int nb10c = 0;
  int nb20c = 0;
  int nb50c = 0;
  int nb1e  = 0;
  int nb2e  = 0; };

On s'intéresse au problème consistant à déterminer si, pour une somme donnée sm comptée en euros et centimes d'euros, il existe une combinaison de tout ou partie des pièces contenues dans un porteMonnaie donné pm telle que le total des pièces de cette combinaison est égal à sm. Il est possible que 0, 1 ou plusieurs combinaisons existent suivant les valeurs respectives de sm et pm. Dit autrement, le problème consiste à déterminer si le contenu d'un porte-monnaie permet de rendre exactement une certaine somme.

b) Décrire sans l'implanter informatiquement une technique utilisable pour tester si, une somme sm comptée en euros étant donnée, il existe une combinaison de tout ou partie des pièces contenues dans un porteMonnaie lui aussi donné telle que le total des pièces de cette combinaison est égal à sm.

Une technique simple à base de divisions entières et de modulo permettant une décomposition en partant de la pièce de 2 euros et en traitant les pièces par ordre décroissant de valeur ne peut être utilisée ici car elle ne permet pas de résoudre toutes les situations rencontrées. Le problème vient du fait qu'il existe des couples de valeurs de pièces tels que la valeur de la pièce de plus grande valeur ne peut pas être divisée par la valeur de l'autre pièce: 50 et 20 centimes, 5 et 2 centimes. Par exemple ce type de décomposition pourrait conduire à conclure qu'il n'existe pas de combinaison lorsque l'on souhaite rendre 110 centimes à partir d'un porte-monnaie contenant 2 pièces de 50 centimes et 3 pièces de 20 centimes.
Une méthode de test qui fonctionne consiste à tester toutes les combinaisons de manière à déterminer s'il en existe au moins une qui permet d'obtenir la somme souhaitée. Cette méthode marche mais elle est très "brutale" et peut conduire à des temps de calcul très longs s'il y a beaucoup de pièces.

c) Définir l'entête (pas d'implantation du corps) du sous-algorithme que vous créeriez pour calculer, si elle existe, l'une des combinaisons de pièces dont l'existence est testée à la question (b). Donner les codages en langage algorithmique et en langage Java.

Le but est ici de calculer l'une des combinaisons de pièces correspondant à une somme donnée en euros et centimes d'euro pouvant être extraite d'un porte-monnaie si les pièces qu'il contient le permettent. On dispose donc en données d'un porte-monnaie (un paramètre de type porteMonnaie) et d'une somme (un paramètre de type réel). Deux résultats sont à obtenir: un booléen pour indiquer s'il a été possible de trouver une combinaison et la combinaison.
Deux problèmes se posent:
  - On ne dispose pas d'un type de donnée permettant de stocker une combinaison. Un type est développé à cette fin. Celui-ci est très semblable au type porteMonnaie car le contenu d'un porte-monnaie n'est pas autre chose qu'une combinaison de pièces.
  - Il y a deux résultats. On peut développer une action avec deux paramètres en "Données" et deux paramètres en "Résultats". Une première variante consiste à développer une fonction qui retourne un booléen et qui possède trois paramètres: le porte-monnaie et la somme en "Données" et la combinaison calculée en "Résultats". Une deuxième variante pourrait consister à développer une fonction qui retourne une combinaison de pièces en considérant que si celle-ci n'existe pas, tous ses champs restent à la valeur zéro. Cette variante a pour inconvénient d'être moins expressive quant au fait qu'une combinaison peut ne pas être trouvée.

structure combinaisonPieces
  nb1c  : entier <- 0
  nb2c  : entier <- 0
  nb5c  : entier <- 0
  nb10c : entier <- 0
  nb20c : entier <- 0
  nb50c : entier <- 0
  nb1e  : entier <- 0
  nb2e  : entier <- 0
fin structure

{ Une action de calcul d'une combinaison de pieces }

action combinaisonDePieces(pm,sm,existe,cmb)
  Données
    pm : porteMonnaie
    sm : reel
  Résultats
    existe : booleen
    cmb : combinaisonPieces

{ Premiere variante                                }

booleen fonction combinaisonDePieces(pm,sm,cmb)
  Données
    pm : porteMonnaie
    sm : reel
  Résultats
    cmb : combinaisonPieces

{ Deuxieme variante                                }

combinaisonPieces fonction combinaisonDePieces(pm,sm)
  Données
    pm : porteMonnaie
    sm : reel

En langage Java, le passage de paramètre en "Résultats" n'existant pas pour le type booléen, le développement d'une fonction à résultat booléen est la meilleure solution.

static class CombinaisonPieces {
  int nb1c  = 0;
  int nb2c  = 0;
  int nb5c  = 0;
  int nb10c = 0;
  int nb20c = 0;
  int nb50c = 0;
  int nb1e  = 0;
  int nb2e  = 0; };
  
public static boolean combinaisonDePieces(PorteMonnaie pm,double sm,CombinaisonPieces cmb)

d) Développer entièrement un sous-algorithme permettant, si c'est possible en fonction des pièces qui y sont présentes, de retirer une somme exacte donnée d'un porteMonnaie donné.

La question (c) nous donne le sous-algorithme à utiliser pour calculer la combinaison de pièces qui va être retranchée au porte-monnaie. Il ne reste à implanter que l'opération de retrait qui consiste à retrancher pièce pour pièce la combinaison trouvée. On développe une action. Celle-ci possède deux paramètres:
  - le porte-monnaie auquel on souhaite retirer une somme (passage en "Données/Résultats"),
  - la somme à retirer (passage en "Données").

action retraitSomme(pm,sm)
  Données / Résultats
    pm : porteMonnaie
  Données
    sm : réel
  Locales
    cmb : combinaisonPieces
  si combinaisonDePieces(pm,sm,cmb) = vrai alors
    pm.nb1c <- pm.nb1c - cmb.nb1c
    pm.nb2c <- pm.nb2c - cmb.nb2c
    pm.nb5c <- pm.nb5c - cmb.nb5c
    pm.nb10c <- pm.nb10c - cmb.nb10c
    pm.nb20c <- pm.nb20c - cmb.nb20c
    pm.nb50c <- pm.nb50c - cmb.nb50c
    pm.nb1e <- pm.nb1e - cmb.nb1e
    pm.nb2e <- pm.nb2e - cmb.nb2e
  fsi
fin action

Commentaires sur la notation

Outre la validation des techniques élémentaires de programmation abordées depuis le début du semestre, l'évaluation a porté sur la décomposition en sous-problèmes, l'implantation de sous-algorithmes de résolution de ces sous-problèmes et leur utilisation.

Exercice n°1
  - Question (a): 2 pts
  - Question (b): 2 pts
  - Question (c): 2 pts
  - Question (d): 2 pts
Exercice n°2
  - Déclaration du ou des tableaux utilisés: 1 pt
  - Initialisation à 0 du tableau tnbv: 1 pt
  - Génération du million de séries de 20 booléens: 2 pts
  - Comptage des nombres de vrais de chacune des séries de 20 booléens: 2 pts
  - Comptabilisation dans tnbv des effectifs de nombres de vrais: 1 pt
  - Affichage du tableau tnbv: 1 pt
  - Décomposition en problèmes élémentaires, implantation et utilisation des sous-algorithmes correspondant: 5 pts
Exercice n°3
  - Type agrégé en langage algorithmique: 1 pt
  - Type agrégé en langage Java: 1pt
  - Technique de détermination de l'existence d'une combinaison de pièces: 3 pts
  - Entête en langage algorithmique: 1,5 pt
  - Entête en langage Java: 1,5 pt
  - Sous-algorithme de retrait d'une somme à un porte-monnaie: 1,5 pt
  - Utilisation du sous-algorithme de la question (c): 1,5 pt

La somme des notes élémentaires est de 32.0. Cette note a été rapportée sur 22.0 par régle de 3.