L2 - I31 - Examen de travaux pratiques d'algorithmique


Mardi 06 décembre 2016        G1 : 13:15 → 15:30     G2 : 16:15 →18:30  

TOUS DOCUMENTS INTERDITS. Vous avez 1/4 d'heure au début de l'examen pour vous installer et lire en détail le contenu de ce paragraphe avant de commencer les exercices, et un deuxième 1/4 d'heure en fin d'examen pour le finaliser

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 : l'expérience prouve que nombre d'étudiants ne savent pas recopier une simple commande. Vous pouvez donc les copier avec 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 (15% des étudiants de la promotion 2015-2016), je retirerai 4 points à votre note.



Important : Expliquez en français sous forme de commentaire les algorithmes ques vous utilisez pour écrire vos fonctions ! Vous pourrez utiliser la fonction suivante pour saisir facilement une liste d'entiers :

def LireListe(L):
    L = input("Valeurs de votre liste (séparées par un espace): ")
    L = [int(x) for x in L.split()]
    return L

Écrivez une fonction TriSelection(L) qui effectue le tri de la liste L in situ (sur place, on ne crée par d'autre liste) à l'aide de l'algorithme du tri par sélection étudié en cours. Vous écrirez à part la fonction IdxMin(L) qui renvoie le plus petit indice des éléments les plus petits dans la liste.
Deux ensembles sont représentés par deux listes A et B (elles ne contiennent donc jamais plus d'une occurrence d'un objet). Écrivez une fonction Intersection(A,B) qui renvoie la liste correspondant à l'intersection des deux ensembles. Quelle est la complexité de votre algorithme ?
Écrivez une fonction Python Fusion(A,B) qui renvoie la fusion de deux listes A et B d'entiers triées, c'est-à-dire la liste triée contenant toutes les valeurs des deux listes. Par exemple si A = [1,2,5,6,9] et B = [2,4,5,5,7,8], la liste fusionnée est la liste [1,2,2,4,5,5,5,6,7,8,9]. Attention : vous ne devez pas trier la liste A+B ! Quelle est la complexité de votre algorithme ?
Écrivez une fonction Python PGCD(a,b) qui calcule le plus grand commun diviseur des entiers a et b noté (a,b). Indications : on rappelle que le théorème de la division euclidienne affirme qu'il existe un unique entier q (le quotient) et un unique entier r (le reste) tels que
a = bq + r    où  0 ≤ r < b
On a alors (a,b) = (b,r) si r > 0 et (a,b) = b sinon.