L2 - I31. Examen de travaux pratiques d'algorithmique.


Vendredi 20 novembre 2015 - 10:00 → 12:15 (durée 2H15)  DOCUMENTS INTERDITS

Vous avez 1/4 d'heure pour vous installer et lire en détail le contenu de ce paragraphe avant de commencer les exercices ! Lisez attentivement les énoncés et suivez scrupuleusement les instructions en respectant à la lettre les commandes, les noms des fichiers proposés, majuscules/minuscules comprises. Suggestion : copiez les à la souris afin d'éviter, entre autres, de confondre la quote ' et l'antiquote `... Les réponses aux questions posées doivent être incorporées aux fichiers sources Python sous forme de commentaires en début de programme.

Le barème est approximativement de 5 points par exercice.

NB. Pour les étudiants de la filière SI : si vous n'avez pas réussi à suivre les instructions ci-dessus et que je dois intervenir pour faire ce travail à votre place (20% des étudiants de la promotion 2014-2015), je retirerai 4 points à votre note.
Écrivez une fonction TriSelection(L) qui effectue le tri in situ (sur place, on ne crée par d'autre liste) de la liste L à l'aide de l'algorithme du tri par sélection étudié en cours.
Écrivez une fonction Python Delta(A,B) qui renvoie la différence symétrique de deux ensembles A et B : A Δ B := AB \ AB. Un ensemble est représenté sous forme de liste et on supposera que chaque valeur contenue dans une liste n'apparaît qu'une fois. Par exemple si A=[2,1,5,6,9] et B=[7,4,5,2,8], la liste renvoyée est la liste [1,6,9,7,4,8]. Quelle est la complexité de votre algorithme ?
On rappelle qu'un dictionnaire en python est une structure énumérée (comme les listes, tuples, chaînes) dont les clés sont quelconques (dans les autres cas les clefs sont entières). Comme pour une liste, on accède à la valeur associée à une clef c par H[c]. On crée un dictionnaire vide dico avec dico = {}. On crée une nouvelle entrée en écrivant par exemple dico["pseudo"] = "Keyser Söze". On obtient la liste des clés avec list(dico.keys()) et la liste des valeurs avec list(dico.values()). Pour récupérer une valeur à partir de sa clef, il suffit d'écrire dico[clef].

Écrivez une fonction Python Distribution(chaine) qui renvoie un dictionnaire dont les clefs sont les caractères de la chaîne passée en paramètre et la valeur associée à une clef c est le nombre d'occurences de ce caractère dans la chaîne. Par exemple, si chaine="abaccab", alors le dictionnaire renvoyé est {"a":3,"b":2,"c":2}. Écrivez une fonction LettreLaPlusFrequente(chaine) qui renvoie la lettre la plus fréquente dans la chaine.

Écrivez une fonction Zero(f,a,b,ε) qui cherche une valeur x qui annule la fonction f, plus précisément telle que |f(x)| < ε. On supposera que les paramètres sont tels que f(a)f(b) < 0 pour chercher la valeur x par dichotomie : on calcule le milieu x de l'intervalle [a,b] et on vérifie si |f(x)| < ε. Dans le cas contraire, on change l'intervalle en remplaçant a ou b par x afin que l'on conserve l'inégalité f(a)f(b) < 0. NB. En python, on peut parfaitement définir une fonction f et la passer en paramètre d'une autre:
def f(x):
    return x * 2

def g(x):
    return x + 1

def h(fonction, x):
    return fonction(x)
L'appel h(f, 3) renverra 6, h(g, 2) renverra 3 et h(lambda x: x*x, 3) renverra 9.