Auteur : romainbondil

Un exemple de fonction dont la complexité est logarithmique en fonction des données (pour les plus avancés en info)

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.

 

Ex. 5 pl. 11 avec la dérivée de la fonction différence, qui dit mieux?

Une bonne rédaction de la solution de l’ex 5. pl. 11 avec la dérivée de la fonction différence, en fixant une variable.

A la fin, on a bien la conclusion pour tous les a et b, car b est fixé quelconque 🙂

Cependant, il y a une solution plus illuminante, à la fois plus courte à rédiger et surtout qui permet de deviner l’inégalité.

Laquelle ?

Ex. 4 pl. 11

Bonjour,

pour lancer le débat sur les inégalités, voici une rédaction sur l’Inégalité Arithmético Géométrique, qui sert d’exercice de référence sur ce thème.

Ex4pl11

Noter l’importance du cas t=1/2 dans les inégalités de convexité :  f((1-t)a+tb) inférieur ou égal à  (1-t) f(a)+t f(b).

Avec un sens géométrique évident :  l’image par f du  milieu de [a,b] est en dessous du milieu  [f(a), f(b)].

L’idéal serait d’embrayer ainsi tout de suite sur l’ex. 5. et que quelqu’un propose une rédaction de cet exercice 5 pour ce soir.

r.b.

Ex. 3 pl. 11

Pour l’exercice du jour : une application presque sans histoire de la formule de Leibniz, encore faut-il ne pas se tromper sur les exposants de dérivations..

Dans la rédaction soignée  ci-dessous un élève qu’on appellera Théo (ce qui équivaut à l’anonymat dans notre classe), rédige même la preuve par récurrence pour la formule sur les dérivées n-ièmes du ln. C’est bien, mais ne serait pas forcément demandé dans cet exercice, qui est centré plutôt sur l’application de Leibniz.

En revanche cette preuve par récurrence permet de voir une erreur de rédaction à éviter absolument.

JAMAIS « Quelque soit n dans l’écriture de H(n) » , car H(n) est un prédicat où n est une variable « parlante »… Faute à éviter absolument.

 

 

 

 

 

 

 

 

 

 

Ex. 1 pl. 11 bis avec une rédaction à éviter !

Dérivable car « définie et continue et ayant une dérivée » je ne sais si on enseigne vraiment  des trucs aussi affreux au lycée,

mais pitié ne le faites pas !

‘Définie et continue’ déjà ca me hérisse : ce n’est certainement pas cela qui va donner la dérivabilité…

et ensuite la fin de la phrase dirait qu’elle est dérivable car elle a une dérivée… on peut méditer cette phrase profonde.

Rédaction pl. 10 et interro de vendredi

Bonjour à tous,

après j’espère un bon premier w.e. de vacances, voici le temps de faire un peu de maths chaque jour !

Pour commencer du bon pied, je vous livre une rédaction des deux exercices que nous n’avions pas complètement rédigés au tableau en classe pl. 10, et des solutions pour les exercices inconnus de l’I.E. de vendredi. (qui était très proches du dernier exo de la pl. 10).

Les voici ici : Sol-ex-pl-10

IE-S-4

 

Ce que j’attends de vous (comme dit en classe vendredi) : une rédaction par jour d’un exo (ou deux suivant la taille des exos) de la pl. 11 pour cette semaine, en même temps que vous dégrossirez le D.M. 5.

Pour ce soir : ex.1 ET  ex.2 pl. 11.  (l’ex. 1 est très court surtout quand on a fait les exos que j’ai rédigé ci-dessus !)

Avec tout cela, vos révisions du B2 sur la dérivation devraient commencer à être bonnes !

Attention, j’attends une personne différente chaque jour !

bonne journée, bonne planche.

r.b.