TD8. Pierre Larousse

Ce TD a pour objectif d'introduire le type abstrait dictionnaire, et de voir comment utiliser ce type en Python.

Préambule : éléments de langage

Question 1

Donner une définition du terme dictionnaire.

Question 2

Donner une définition du terme dict ainsi qu'une ligne de code python permettant de créer un dict.

Exercice 1 : conjecture de Syracuse

La conjecture de Syracuse est une conjecture mathématique célèbre qui considère la suite d'entiers définie par :

• u₀ quelconque
• si u_i est pair alors u_i+1 = u_i/2
• sinon u_i+1 = 3*u_i + 1

La conjecture postule que pour toute valeur entière strictement positive de u₀, la suite finit toujours par atteindre la valeur 1.

Question 1

Écrire une fonction calcule_prochain_syracuse prenant en entrée u_i et renvoyant u_i+1

Question 2

Écrire une fonction calcule_nb_etapes_avant_1 prenant en entrée u₀ et renvoyant le nombre d'étapes nécessaires avant d'atteindre 1. La fonction ne doit pas être récursive.

Question 3

À l'aide d'un dictionnaire, modifier la fonction calcule_nb_etapes_avant_1 pour tirer parti des résultats des appels précédents à la fonction. L'appel à la fonction calcule_nb_etapes_avant_1 prenant en entrée u₀ devra ajouter uniquement la clef u₀ dans le dictionnaire.

Exercice 2 : fonctions injectives

On considère une fonction mathématique dont les résultats sont stockés dans un dictionnaire. Chaque élément du dictionnaire contient une valeur d'entrée de la fonction et la valeur de sortie associée. On suppose que le dictionnaire associe une valeur de sortie à chaque entrée possible.

Question 1

Écrire une fonction est_injective(fonction_dict) qui vérifie si la fonction représentée par fonction_dict est injective ou non.

Exercice 3 : comment faire mieux ? (pour aller plus loin)

Question 1

Modifier la version avec mémoisation de Syracuse pour stocker également tous les résultats intermédiaires.

Question 2

Modifier la fonction est_injective pour utiliser un set python.

Exercice 4 : soyons fous (pour aller encore plus loin)

Question 1

Démontrer ou invalider la conjecture de Syracuse.