Scribd Logo
Importer

Bienvenue sur Scribd !

  • 5 vues

    1-TD Complexité

    Transféré par

    Yassine El Hadiri

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    1-TD Complexité

    Transféré par

    Yassine El Hadiri
    5 vues2 pages

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    5 vues2 pages

    1-TD Complexité

    Transféré par

    Yassine El Hadiri

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 2

    Najlaa ESSALHI MP-2020/2021 CPGE Mohamad V

    TD Complexité
    Exercice1
    Soit une liste T de longueur n dont les termes valent 0 ou 1. Le but de cet exercice
    est de trouver le nombre maximal de 0 contigus dans T (c’est-à-dire figurant dans
    des cases consécutives). Par exemple : le nombre maximal de zéros contigus de la
    liste [0,1,1,1,0,0,1,0,0,0,0] vaut 4:

    1) Écrire une fonction nombreZeros(T,i), prenant en paramètres une liste T, et un


    indice i et renvoyant :
    - 0 si T[i]=1
    - le nombre de zéros consécutifs dans T à partir de T[i] inclus, si T[i]=0
    2) Rédiger la fonction nombreZerosMax(T), renvoyant le nombre maximal de 0
    contigus d’une liste T non vide. On utilisera la fonction nombreZeros. Quelle
    est sa complexité ?
    3) Essayer d’écrire un autre algorithme plus performant.

    Exercice 2
    On dispose d’un tableau non trié A de longueur n qui contient tous les entiers de 0 à
    n, sauf un.

    1. Donnez un algorithme qui trouve l’entier manquant en temps O(n2)

    2. On suppose qu’on peut trier le tableau A avec une fonction tri(A) dont la
    complexité est en O(nlog(n)). Donnez un algorithme qui trouve l’entier manquant en
    temps en O(nlog(n))

    3. Donnez un algorithme qui trouve l’entier manquant en temps O(n) en utilisant un


    tableau auxiliaire

    4. Donnez un algorithme qui trouve l’entier manquant en temps O(n), sans utiliser
    un tableau auxiliaire
    Najlaa ESSALHI MP-2020/2021 CPGE Mohamad V

    Exercice 3
    1. Ecrire une fonction itérative qui calcul : an=a×a×...×a
    2. Ecrire une fonction récursive qui calcul an en utilisant la remarque :
    an=a×an-1
    3. Ecrire une fonction récursive qui calcul an en utilisant la remarque :
    + +
    a* = a , ×a ,
    4. Ecrire une fonction récursive qui calcul a* en utilisant la remarque
    𝑛
    𝑎𝑛 = (𝑎2 )2 𝑠𝑖 𝑛 𝑒𝑠𝑡 𝑝𝑎𝑖𝑟𝑒
    suivante: 𝑛−1
    𝑎𝑛 = 𝑎×(𝑎2 ) 2
    𝑠𝑖 𝑛 𝑒𝑠𝑡 𝑖𝑚𝑝𝑎𝑖𝑟
    5. Comparer la complexité temporelle de ces fonctions

    Exercice 4

    Soit P un polynôme de degré n : P(x) = a0 + a1 x + a2 x2 + ... + an xn

    Les coefficients du polynôme sont stockés dans une liste a = [a0, a1 , ... . , an]

    1. Ecrire une fonction qui permet d’évaluer le polynôme P en un point X.


    Calculer sa complexité
    2. Ecrire une nouvelle fonction pour évaluer le polynôme P en un point X en
    utilisant le fait que : Xi = Xi-1 X . Calculer sa complexité

    On peut écrire (schéma de Horner) :

    P(x) = a0 + x(a1 + x(a2 +x( ... +x (an-1+ x an))…)

    3. Ecrire une nouvelle fonction pour évaluer le polynôme P en un point X en


    utilisant le schéma de Horner. Calculer sa complexité

    Vous aimerez peut-être aussi