1. Programmation et algorithmiques

1.1. Python

Question 1

Soit le morceau de code suivant :

def ma_procedure(x,y):
    y = 0
    z = 1.1
    print "La valeur de x est %i, celle de y est %i et celle de z est %f" % (x, y, z)

Qu'affiche Python si vous appelez la procédure ma_procedure(0, 1) ?

Question 2

def fonction_X(a, b=True, c=1):
    if b:
        return(a+c)
    else:
        return(a-c)

Après les lignes suivantes, que valent les variables a, b et c ?

>>> a = 42
>>> b = 12
>>> a = fonction_X(a, False)
>>> c = fonction_X(a, c=-2)

1.2. Petits exercices

Question 1

Écrivez une fonction compte(t, a) qui compte combien de fois la valeur a apparaît dans le tableau t,

Question 2

Écrivez une fonction addition(t) qui fait la somme de tous les éléments du tableau t,

Question 3

Écrivez une fonction multiplication(t,m) qui fait la multiplication modulo m de tous les éléments du tableau t. Si m est un nombre négatif, on fait la multiplication normale. Essayez de ne pas faire de calculs inutiles

Rappel : le modulo un Python s'écrit avec %. Par exemple :

>>> 24 % 7
3

Question 4

Une matrice m peut-être vue comme un tableau à deux dimensions : on accède à la case (i,j) avec m[i][j]. Écrivez la fonction de multiplication de deux matrices.

Quelle est la complexité de cette fonction ?

1.3. Petit problème

Complétez la définition suivante :

def format(s, taille=78, couper=False):
    """Cette fonction prend en argument un tableau de mots "s" et produit
une liste de lignes contenant au plus "taille" caractères. À l'intérieur
de chaque ligne, les mots sont séparés par un espace, mais on ne met
d'espace ni au début ni à la fin des lignes

Si "couper" est faux, les mots ne sont pas découpés.
Si "couper" est vrai, les mots sont découpés pour que les lignes aient la
bonne taille
    ...
    ...

Par exemple :

>>> format(["un", "deux", "trois", "quatre", "cinq"], 11)
["un deux", "trois", "quatre cinq"]

>>> format(["un", "deux", "trois", "quatre", "cinq"], 11, True)
["un deux tr", "ois quatre", "cinq"]

1.4. Moyen problème

Un satellite vous envoie des morceaux d'image de la lune. Chaque morceau est une matrice 64x64 de niveaux de gris (entiers entre 0 et 255). Comme la transmission n'est pas très bonne, chaque morceau est envoyé deux fois.

L'image finale est composée de 64x64 tels morceaux. Si tout se passe bien, vous recevez donc 2 * 64 * 64 = 8192 morceaux.

Pour récupérer un morceau, vous devez utiliser la fonction morceau_suivant() qui ne prend pas d'argument et vous donne comme résultat un tuple ((i,j),m) où :

  1. (i,j) sont les coordonnées du morceau dans l'image finale,
  2. m est le tableau bidimensionnel correspondant au morceau.

Pour des raisons techniques, les morceau arrivent dans un ordre quelconque.

-

Vous devez écrire un programme pour faire les choses suivantes :

  1. créer l'image finale,
  2. compter, pour chaque morceau, le nombre minimal d'erreurs de transmission.

Décrivez l'architecture de votre programme (noms et descriptions de vos fonctions) et donnez rapidement le squelette des fonctions intéressantes.

Il ne faut pas écrire tout le programme ! Il suffit de décrire son architecture globale...