Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Répondre
Résumé de la discussion (messages les plus récents en premier)
- capesman
- 22-09-2017 21:07:38
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
- capesman
- 19-11-2016 06:57:01
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.