Implémentation en Python

Nous allons implémenter chacun des trois algorithmes vus précédémments en Python, sous forme d'un TP noté. A chaque activité que vous complétez ou pensez avoir complété, appelez le professeur pour validation. Pour avoir la note maximale, vous devez compléter toutes les activités sans aide. Demander de l'aide sur une activité vous retirera entre 1 et 2 points sur cette activité. Une participation assidue au TP, même sans résultats, vous garantis d'avoir la moyenne. Il vous est conseillé d'appeler le professeur pour vérifier vos tests avant d'implémenter. Les questions sur la spécification ou les tests ne vous donneront pas de pénalité.

Pour tester avec doctest, vous pouvez utiliser le code suivant, à ajouter en fin de votre fichier Python:

if __name__ == "__main__":
    import doctest
    doctest.testmod()

Tri par selection

Activité : position du minimum

EnoncéAide 1Aide 2

Implementez une fonction position_minimum qui a la spécification suivante, en ajoutant des tests à cette spécification.

def position_minimum(l, d):
    """l une liste non vide
    d un entier >= 0 et < len(l)
    retourne l'indice du minimum des éléments de l, ne tient pas compte des éléments qui ont un indice inférieur strictement à d.
    """

Pensez bien à écrire des tests avant d'implémenter la fonction !

Pour parcourir les valeurs entières de 0 inclus à n exclut, vous pouvez utilisez la structure suivante :

for i in range(0, n):
    #ici des instructions

Activité : tri par sélection

EnoncéAide 1Aide 2

Implémentez l'algorithme du tri par sélection en Python, en utilisant la fonction position_minimum, sous forme d'une fonction qui retourne la liste en paramètres après l'avoir triée. N'oubliez pas de spécifier la fonction, et d'écrire quelques tests !!!

Pour échanger les valeurs des variables a et b, on passe par en général par une troisième variable temporaire :

a = 2
b = 4
#ici, on inverse
tmp = a
a = b
b = tmp

Pour parcourir les valeurs entières de 0 inclus à n exclut, vous pouvez utilisez la structure suivante :

for i in range(0, n):
    #ici des instructions

Tri par insertion

Activité : insertion triée

EnoncéAide

Implémentez la fonction insertion_triee, qui a la spécification suivante :

def insertion_triee(l, i):
    """l une liste non vide, la sous-liste de 0 à i-1 est triée.
    i un entier < len(l)
    insère l'élément en position i dans la sous-liste allant de 0 à i - 1, de façon à ce que la sous-liste allant de 0 à i soit triée.
    """

Pour échanger les valeurs des variables a et b, on passe par en général par une troisième variable temporaire :

a = 2
b = 4
#ici, on inverse
tmp = a
a = b
b = tmp

Activité : tri par insertion

EnoncéAide

Implémentez l'algorithme du tri par insertion en Python, en utilisant la fonction insertion_triee, sous forme d'une fonction qui retourne la liste en paramètres après l'avoir triée. N'oubliez pas de spécifier la fonction, et d'écrire quelques tests !!!

Pour parcourir les valeurs entières de 0 inclus à n exclut, vous pouvez utilisez la structure suivante :

for i in range(0, n):
    #ici des instructions

Recherche dichotomique

Activité : recherche dichotomique

Enoncé" === "Aide 2Aide

Pour parcourir les valeurs entières de 0 inclus à n exclut, vous pouvez utilisez la structure suivante :

for i in range(0, n):
    #ici des instructions

Implémentez la fonction recherche_dichotomique :

def recherche_dichotomique(l, v):
    """l une liste triée
    v une valeur
    retourne la position de v si v est dans l, len(l) sinon.
    """

Réflechissez bien aux variables que vous allez utiliser, et comment l'utiliser !

Comparateur

Si vous arrivez jusqu'ici, appelez le professeur pour la suite !

TODO (prof) ecrire sujet ici