Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 19-11-2016 06:57:01

capesman
Modérateur
Inscription : 15-08-2016
Messages : 152

[Info 11] - Exemples de détermination de la complexité....

Bonjour,

  Cette discussion est ouverte pour parler de la leçon du capes de mathématiques : Exemples de détermination de la complexité (en temps et dans le pire des cas) d'un algorithme.

Capesman.

Dernière modification par capesman (27-11-2018 18:51:44)

Hors ligne

#2 22-09-2017 21:07:38

capesman
Modérateur
Inscription : 15-08-2016
Messages : 152

Re : [Info 11] - Exemples de détermination de la complexité....

Bonjour,

  Voici ce qu'en dit le rapport du jury (2017 et 2018):

"Cette leçon est orientée vers l'utilisation pratique de méthodes d'évaluation de la complexité, avec comme objectif le choix entre plusieurs algorithmes pour résoudre un problème donné. Le candidat précise clairement ce qu’il choisit comme mesure de la complexité : le nombre de comparaisons, le nombre d’appels, etc. Le candidat doit savoir équiper le programme qu’il présente d’un compteur qui permette la mesure expérimentale de sa complexité.

Si le candidat utilise la notion d’ordre de grandeur et la notation de Landau $O(f)$, il doit savoir la définir et justifier l'ordre de grandeur des fonctions classiquement rencontrées dans ce domaine, par exemple que $\frac{n(n+1)}2$ est un $O(n^2)$.

On pourra mettre en évidence que le comportement d'un algorithme dans un cas donné  peut  être très variable,  et éventuellement très différent de son comportement dans le pire cas. Le choix d'un algorithme ne doit pas être seulement dicté par sa complexité en pire cas,
mais  aussi  par  une  définition  soigneuse  de  l'espace  des  cas  considérés.  Par  exemple,  certains algorithmes de tri sont très efficaces si le tableau est déjà «presque trié», alors que c'est indifférent pour d'autres. Un problème  classique  est  bien  sûr  le  tri  d'un  tableau  de  taille  $N$,  mais  on  peut  aussi  penser  à  la recherche  d'un  motif  dans  une  chaîne  de  caractère,  le  calcul  de  suites  numériques  récurrentes (Fibonnaci, etc.), les opérations sur les listes (reverse, etc.), etc."

Capesman

Dernière modification par capesman (27-11-2018 21:33:17)

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
vingt cinq plus quarantesept
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums