Catégorie : Uncategorized

Bon, on va faire rapide…

Ainsi nous voyons que les trois méthodes vues pour l’IAG s’appliquent pour cet exemple aussi…

Une première bonne rédaction de cette question…  attention à bien penser à toujours dire pour quel b pour quel a vos formules sont valables….

Par exemple une phrase comme « montrons que f(b) est positif » ne veut pas dire grand chose si on ne sait pas de quel b on parle.

 

Remarque : On peut faire d’autres preuves pour cette question, qui permettent de « deviner » cette inégalité.

Notamment en utilisant le fait qu’on a montré  que x->sqrt(x) est sous-additive.
Or un autre nom de la sous-additivité dans le cas de f : x-> |x| c’est l’inégalité triangulaire.

Et on sait que l’I.T. entraine l’I.T. 2. Or l’inégalité à démontrer, n’est ce pas une sorte d’ IT 2 pour x-> sqrt(x)?

 

 

Bonjour à tous,

après ma suggestion dans le post précédent, Ph. N., très motivé donc, a remarquablement traité le  même exercice en enlevant l’hyp. de dérivabilité.

(On peut enlever les lignes 2 ,4, et dire directement que la déf. de « f  concave » est la propriété dans le premier encadré (quantifiée comme ci-dessous ligne 3)

Bonjour,

une très bonne rédaction de l’ex. 6. (initiales de l’auteur :  E.D.) par intégration.

Dans la solution en question il est entendu que la fonction t-> f'(t+y) admet pour primitive t-> f(t+y) bien sûr.

 

Je propose aussi une autre rédaction très analogue, mais du point de vue des dérivées plutôt que des intégrales (méthode standard, dérivée de la fonction différence, en fixant une variable).

N.B. 1 : on dira qu’une fonction f est additive si f(x+y)=f(x)+f(y) pour tout x,y, d’où la dénomination sous-additive ici.

N.B. 2 Pour les plus motivés : peut-on montrer le même résultat sans hypothèse de dérivabilité, seulement avec la déf. de f convexe ?

 

Suite à la question d’hier sur les problèmes de complexité. Je vous propose une mauvaise solution de la question 7 du DM d’IPT en expliquant pourquoi elle est mauvaise. Pour que ce soit plus clair, je dois spoiler un peu la Q6.. en partie du moins

 

 

J’ai reçu hier soir une bonne solution de l’ex. 5. avec la convexité, mais sans photo, juste tapée. Bravo W. !
En voici une version avec traitement de texte.

Bien se dire que cet énoncé crie :  « je suis une inégalité de convexité avec f((a+b)/2) plus petit que (f(a)+f(b))/2 « .

Ouverture culturelle : on peut montrer réciproquement qu’une fonction continue sur un intervalle I  et qui vérifie que pour tout a,b dans I, f((a+b)/2) plus petit que (f(a)+f(b))/2 est automatiquement convexe…. mais c’est un exercice autrement plus difficile, qui aura plus sa place au chapitre F. Cet remarque veut seulement souligner l’importance de cette inégalité a priori bien particulière pour les fonctions convexes.

 

 

 

Dans l’énoncé de l’exo 3 dudit DM 6, dans l’équation 1, j’avais mis (x,y) dans R^2 alors que l’énoncé au-dessus dit bien que x et y sont strictement positifs.

Voici donc la modif. corrigée aussi sur le fichier de la page DM.

Le DM d’info. évoque la notion de fonction dont le temps de calcul est logarithmique en fonction des données qu’es aco ?

Voici un explication qui consiste a comparer deux exemples :

• Supposons qu’on ait une liste L de longueur n et qu’on veut savoir si un objet x est dans la liste alors on doit parcourir  (au pire) toute la liste et tester si L[i]==x avec une boucle for de longueur n. Cet algorithme est de complexité au plus n si on compte seulement le nombres de tests d’égalité L[i]== x qu’on y fait.(Au plus n car on peut s’arrêter si le L[i]==x vaut True).

C’est un algorithme qu’on dit  de complexité linéaire (le nombre (max.) de tests est  une fonction linéaire de la longueur de la liste i.e. de la forme a.n ici a=1).

Voici maintenant un autre algorithme :

• Supposons qu’on ait des listes L disons dont les entrées sont des entiers qui sont triées dans l’ordre croissant. Par exemple L=[3,5,8,14,17,24,29,45,72]. Alors on peut imaginer un algorithme plus efficace pour tester si un entier x est dans L, qui marche pour toutes les listes triées. On compare x avec L[n//2]. S’il est égal c’est gagné. S’il est inférieur, on sait que x est dans la première partie de la liste et on remplace L par L[:n//2] i.e. la première partie de la liste. S’il est supérieur, on sait que x dans la deuxième partie de la liste et on remplace L par L[n//2+1 : ]. Et on recommence. Le nombre total de fois qu’il faudra essayer est inférieur ou égal à N où N est tel que 2^N < n ( à un près… en gros). Donc N< log_2(n). Ce programme est donc de complexité logarithmique : le nombre d’étapes est très inférieur à la longueur de la liste.
• Par exemple si on cherche si x=45 est dans la liste L précédente où n=9, au premier coup on compare 45 avec L[4]=17. On sait que 45 (s’il est là) est dans la seconde partie de la liste [24,29,45,72] qui est de longueur 4. On prend L=cette seconde partie. On compare alors 45 au nouveau L[2], or L[2]=45 et c’est fini en deux coups contre 8 avec la méthode du premier algorithme.

 

Nous programmerons un tel algorithme de recherche en faisant un jeu de devinettes en TP à la rentrée.