Mathématiques appliquées à l'informatique

Thèmes abordés

Induction, récursivité, algorithme d'Euclide, questions, réponses, mathématiques

Résumé du document

Le document est composé de 5 questions/réponses, niveau licence : sur les algorithmes, sur les nombres entiers et les méthodes de preuve, sur l'induction, sur les nombres définis récursivement, et sur les relations.

Extraits

[...] Mathématiques appliquées à l'informatique I. Les algorithmes En appliquant l'algorithme au tableau donné, on obtient : ii) On effectue d'abord la comparaison fois puis fois, ainsi de suite jusqu'à Au total le nombre de comparaison qui est faite est alors : C'est la somme des termes d'une suite arithmétique de raison . On obtient ainsi : iii) D'après la question qui précède, la complexité temporelle de l'algorithme est d'ordre En appliquant ce nouvel algorithme, on obtient le tableau suivant : ii) La comparaison peut se faire au maximum fois pour la première valeur de puis fois pour la deuxième valeur de et ainsi de suite jusqu'à ce qu'on ait . [...]

[...] On en déduit que est de la forme : où est un nombre entier. Ainsi . On sait également que le PPCM entre et est de . Et . Le PPCM entre et est donc : . Ainsi on peut prendre et . - Obtention de m : De la même manière que pour , on peut affirmer que est un multiple de puisque et . Ainsi .De plus, le PPCM de et de est . Or et . De plus : . [...]

[...] De plus chaque préfixe de cette nouvelle chaîne est soit la chaîne vide (donc vérifie les contraintes nécessaires), soit (là encore le nombre de est alors supérieur ou égal au nombre de , soit suivi d'un préfixe de (et le nombre de sera là strictement supérieur au nombre de puisque est une chaîne déco), soit suivi de suivi de (là encore le nombre de est alors supérieur ou égal au nombre de car le signe final est compensé par le signe du début, et est une chaîne déco), soit finalement constitué de puis de puis de puis d'un préfixe de et le même raisonnement nous montre que le nombre de sera là aussi supérieur ou égal au nombre de . iii) Montrons par récurrence forte sur que tous les membres de l'ensemble sont des chaînes déco. On appellera la longueur des chaînes de . (les membres de l'ensemble sont créés de manière récursive en rajoutant deux symboles à deux chaînes appartenant à , donc la longueur de n'importe quel élément de ne peut être que pair. [...]

[...] Conclusion : La propriété est vraie au rang et héréditaire : elle est donc vraie pour tout Montrons par récurrence pour tout l la propriété : ? Initialisation : Pour on a : et est donc vérifiée. ? Hérédité : Supposons vraie et montrons qu'on a alors en appliquant l'hypothèse de récurrence. Or : On obtient : on en déduit que est vraie. ? Conclusion : La propriété est vraie au rang et héréditaire : elle est donc vraie pour tout IV. [...]

[...] Il ne répond donc pas aux contraintes des préfixes des chaînes déco. La dernière lettre de est donc forcément un Remarque pour le client : il y a très certainement à ce niveau une erreur d'énoncé. Il faut certainement lire « soit ce plus court préfixe? » et non pas « soit ce plus court préfixe? ». V. [...]