J. 0734 SESSION 2000 Option MP EPREUVE D'INFORMATIQUE Durée : 4 heures L 'usage des calculutrices est uutorisé. Les algorithmes demandés peuvent êire codis en CAML ou en PASCAL. Quand aucune directive n *est donnie le candidat peut établir une version rccursive ou non. @el que soit le choix du langage, les algorithmes rioiveni Ptre écrits de la maniire la plus courte possible, pavaitement lisible, avec une indentation convenable. sans uucune rature et en respectant scrupuleusemint les notations introduites. Ils doivent Ptre documentés par des e.rplications concises et précises sur les points qui le tricessitent. La lecture de l'annexe correspondant au langage choisi est vivemen! conseillée avant d'aborder les questions de programmation. qui ne respecteraient pas les consi,qnes preckrlentes ne seront pas prises en corsidiration. Les réponses Les questioris sont assez souvent indépendantes les unes ries uutres. il est cependant conseil12 rie respecter la chronologie proposée. Les parties 1. II et III sont izdipendantes. 1- Parcours en escalier dans un tableau. Soit M une matrice de n+l lignes et de n+l colonnes (@O). telle que m,,, = 2'3' pour 05 isn et 05jln. 1) Décrire un algorithme de remplissage du tableau h deux dimensions représentant la matrice M 2) Quel est le nombre total de multiplications de votre algorithme '? 3) Ecrlre la foncaon pgcd qui a prend pour arguments une matnce M (telle que m,, , = 2'3 ' pour O1 i$n et OIj