Ads Area

Exercice avec solution sur la complexité algorithmique as3

Exercice avec solution sur la complexité algorithmique as3

Bienvenue, le sujet d'aujourd'hui portera sur l'étude de la complexité des algorithmes, ce sujet s'adresse particulièrement aux étudiants de deuxième année Informatique (branche MI - AS3), bon lecture.

Contenu du sujet

Qu'entendons-nous par algorithme

Un algorithme est un proc´ed´e automatique pour r´esoudre un probl`eme en un nombre fini d’´etapes.

Pour accéder aux leçons des algorithmes d'ici

Qu'entendons-nous par complexité des algorithmes

Le calcul de la complexité d’un algorithme permet de mesurer sa performance. Il existe deux types de complexité :

  • complexité spatiale : permet de quantifier l’utilisation de la mémoire
  • complexité temporelle : permet de quantifier la vitesse d’exécution

Bientôt, un sujet détaillé sera développé sur la leçon de la complexité des algorithmes

Exercices sur la complexité des algorithmes

Maintenant devant vous quelques exercices sur l'étude de la complexité des algorithmes, des exercices merveilleux et très utiles pour comprendre les techniques de détermination du degré de complexité des algorithmes, et bien sûr ces exercices sont joints à la correction typique, afin que vous puissiez identifier vos erreurs et les étudier

  • Exercice 1

    • On considère, pour effectuer la recherche d’un élément dans un tableau, la recherche séquentielle et la recherche dichotomique. On s’intéresse à leur complexité temporelle. Pour cela, considérer un tableau ayant mille éléments (version trié, et version non trié). Pour chaque algorithme, et pour chaque version du tableau, combien de comparaisons sont à effectuer pour :
    - trouver un élément qui y figure ?
    - trouver un élément qui n'y figure pas ? Quels sont les cas où le tableau est parcouru complètement et les cas où un parcours partiel est suffisant ? Conclure en donnant la complexité temporelle pour chaque algorithme

  • Exercice 2

    • On considère un tableau à une dimension contenant des lettres majuscules. On désire compter la fréquence de chacune des 26 lettres de l’alphabet. Ecrire deux procédures qui donnent en sortie un tableau de fréquence: l’une où le tableau est parcouru 26 fois, et l’autre (plus performante !) où le calcul est fait en un seul parcours. On pourra supposer que l’on dispose d’une fonction auxiliaire position(lettre) qui pour chaque lettre donne sa position dans l’alphabet : position(‘A’) = 1, …, position(‘Z) = 26.

    La méthode qui parcourt le tableau 26 fois consiste à parcourir le texte pour compter d’abord tous les A, recommencer pour compter tous les B, etc. On utilise un tableau d’entiers de 26 cases, qui sert à mémoriser les occurrences. La deuxième méthode demande de disposer de la conversion d’une lettre en un entier, qui correspond à sa place dans l’alphabet. (En c++, on ferait tout simplement appel à i = car – ‘A’).

                                       
                                        char texte[TMAX]
                                        int cpt, pos, occ[26]
                                        pour cpt := 1 à 26 faire occ[cpt]:= 0 {initialisation à zéro}
                                        cpt := 1
                                        tant que (texte[cpt] ≠ CARFIN) faire
                                             pos := conversion(texte[cpt])
                                              occ[pos] := occ[pos] + 1
                                              cpt := cpt + 1
                                        ftq
Tags

Plus d'éléments