Conseil pour démonstration (concaténation de listes)

Bonsoir, on me demande de faire une démonstration de récurrence en programmation. Je pense qu'il est plus simple de réaliser une étape intermédiaire en la réalisant premièrement en maths.

Démontrer que la liste vide est neutre à droite pour l'opération de concaténation.
Démontrer que la concaténation est 1 opération associative liste vide neutre pour les listes l1,l2, l3.

Pour la première prenons la liste l1: [1,2,3,4] et la liste l2: []
la concaténation étant le fait de rapprocher les 2 listes :[1,2,3,4,[] ] on voit bien que la liste l2 est neutre

soit l1l2l3 = (l1l2)l3 =l1(l2l3)
visuellement je vois bien les choses

mais n'ayant jamais fait de démonstration en maths je ne sais pas trop comment m'y prendre

Merci et bonne soirée

Bonjour Dut,
Je ne suis pas sûre que ma réponse t’aide vraiment car pour faire une récurrence en programmation, il faudrait savoir les fonctions que tu utilises dans ce domaine, ce qui n’est pas le cas.

Je t’indique quelques idées éventuelles…

Tout d’abord , en mathématiques, pour une récurrence simple.
Soit P une propriété dépendant d’un naturel n.
On veut prouver par récurrence que P est vraie pour tout n de N

a) On commence par prouver que P est vraie pour n=0, c’est à dire que P(0) est vraie : c’est l’initialisation
b) On suppose que P est vraie pour une valeur n de N, c’est à dire que P(n) est vraie.
Avec cette hypothèse, on démontre que P est vraie pour la valeur n+1, c’est à dire que P(n+1) est vraie : c’est la transmission ( on dit aussi hérédité)

On peut ainsi conclure que P(n) est vraie pour tout n de N.

Pour répondre à ta première question.

Il faut prouver par récurrence , pour toute liste L , que L . [ ]=L (j'ai noté . la concaténation ; j'ignore comme elle est indiquée dans ton cours)

Initialisation pour L= $][\ ]$ (liste de longueur nulle)

$][\ ]$ $].[\ ]$ = $][\ ]$ est vraie. c’est trivial.

Transmission
Une explication possible mais j’ignore totalement si elle s’adapte à ton cours de programmation.
Pour passer d’une liste de longueur n à une liste de longueur n+1, j’ai vu , en consultant cette notion sur le web,qu' il y a une fonction cons (abrévation de « consécutif » je suppose ) qui permet d’ajouter une élément à gauche d’une liste.
Exemple : cons(3,[7 8 9])=[3 7 8 9]
J’utilise cette fonction cons pour la transmission.

On suppose que pour une liste de longueur n : L . [ ]=L
Soit L’ la liste cons(a, L) obtenue en ajoutant l’élément a à gauche de la liste L (L’ est donc composé de n+1 éléments)
Il faut prouver que L '. [ ]=L’

Pour cela :
L’ . [ ]=cons(a , L) . [ ]
Vu que a est à gauche de L, lui même suivi de [ ], on peut écrire
L’ . [ ]=cons(a , L . [ ])
Vu que par hypothèse de la récurrence L . [ ]=L , on peut écrire
L’. [ ]=cons(a , L)
Vu que cons(a , L)=L’, on peut tirer la conclusion
L’. [ ]=L’
(ce qu’il fallait démontrer)

J’ignore si cette fonction cons fait partie de ton cours...je n’ai pas trouvé mieux.

Tu peux faire une raisonnement de même type pour ta seconde question.

Bonne lecture !

Bonjour Mtschoon,
cela m'a beaucoup aidé, merci. Je pense que comprendre la récurrence en mathématique ne pouvait que m'aider pour cet exercice.

Dut, bonjour,

Contente que mon explication te soit utile pour comprendre la notion de raisonnement par récurrence.
Evidemment, pour la programmation, je ne sais, ni la fonction à utiliser, ni la syntaxe...

Bon dimanche à toi.