Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
tc_info:tpa2 [2018/12/04 09:28] – edauce | tc_info:tpa2 [2019/10/22 12:53] (Version actuelle) – edauce | ||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | ==== TP en autonomie ==== | ||
+ | |||
+ | [[http:// | ||
+ | |||
+ | |||
+ | ===== But du TP ===== | ||
+ | |||
+ | On vous demande ici de programmer avec plein de **petites fonctions** qui effectuent une tâche unique dont le nom permet de comprendre la fonction. On essayera ainsi de décomposer les algorithmes en tâches que l'on pense insécables. | ||
+ | |||
+ | Par exemple pour le [[https:// | ||
+ | |||
+ | |||
+ | <code python> | ||
+ | def insertion(tableau): | ||
+ | """ | ||
+ | """ | ||
+ | |||
+ | for etape in range(len(tableau)): | ||
+ | valeur_a_placer = tableau[etape] | ||
+ | indice_insertion = cree_place_pour_inserer(valeur_a_placer, | ||
+ | |||
+ | tableau[indice_insertion] = valeur_a_placer | ||
+ | |||
+ | def cree_place_pour_inserer(valeur_a_inserer, | ||
+ | position = indice_max_tableau | ||
+ | while position > 0 and ordre_non_respecte(tableau[position - 1], valeur_a_inserer): | ||
+ | decale_a_droite(tableau, | ||
+ | position = position - 1 | ||
+ | |||
+ | return position | ||
+ | |||
+ | def ordre_non_respecte(valeur_petite, | ||
+ | return valeur_grande < valeur_petite | ||
+ | |||
+ | def decale_a_droite(tableau, | ||
+ | tableau[indice] = tableau[indice - 1] | ||
+ | |||
+ | </ | ||
+ | |||
+ | L' | ||
+ | |||
+ | ===== Tests ===== | ||
+ | |||
+ | On vous demande de coder des tests (voir [[restricted: | ||
+ | On vous demande donc de : | ||
+ | * copier-coller le code du tri par insertion dans un fichier que vous nommerez '' | ||
+ | * de créer un fichier '' | ||
+ | * un tableau déjà trié, | ||
+ | * un tableau trié à l' | ||
+ | * un tableau de nombres placés aléatoirement. | ||
+ | |||
+ | Vous utiliserez ces tests pour valider les implémentations des différents tris que vous coderez dans ce tp. | ||
+ | |||
+ | Le code ci-dessous vous donne la matrice du fichier '' | ||
+ | |||
+ | |||
+ | <code python> | ||
+ | from tri_insertion import insertion | ||
+ | |||
+ | def test_deja_trie: | ||
+ | tableau_a_trier = [1, 3, 5, 6] | ||
+ | insertion(tableau_a_trier) | ||
+ | | ||
+ | assert tableau_a_trier == [1, 3, 5, 6] | ||
+ | | ||
+ | def test_a_l_envers: | ||
+ | # faire le test | ||
+ | |||
+ | assert True == False | ||
+ | |||
+ | def test_aleatoire: | ||
+ | # faire le test | ||
+ | | ||
+ | assert True == False | ||
+ | |||
+ | </ | ||
+ | |||
+ | ===== Tri Rapide (Quicksort) ===== | ||
+ | |||
+ | Le [[https:// | ||
+ | |||
+ | Ainsi : | ||
+ | * codez l' | ||
+ | * vérifiez expérimentalement que le temps mis pour trier un tableau trié est de l' | ||
+ | |||
+ | |||
+ | ===== Affichage ===== | ||
+ | |||
+ | Adaptez le code de la partie [[restricted: | ||
+ | |||
+ | ===== Complexité moyenne ===== | ||
+ | |||
+ | Utilisez le module [[https:// | ||
+ | |||
+ | Afficher la courbe de temps. | ||
+ | |||
+ | |||
+ | ===== Tri Fusion (Mergesort) ===== | ||
+ | |||
+ | Le [[https:// | ||
+ | |||
+ | Vérifiez expérimentalement que le rapport entre temps pris pour trier des tableaux déjà tris avec MergeSort et Quicksort tend vers 0 lorsque la taille augmente. | ||
+ | |||