#

Suites_u_v Last saved: Oct 29 10:47 AM

- File
- Edit
- View
- Insert
- Cell
- Kernel
- Help

In [1]:

    %pylab inline

    Welcome to pylab, a matplotlib-based Python environment [backend: module://IPython.zmq.pylab.backend_inline].
    For more information, type 'help(pylab)'.

. . .

    x

# Calcul des premiers termes des suites u et v

In [2]:

    def u(n):

        if n==0 : return 1

        return u(n-1)+u(n-1)

    def v(n):

        if n==0 : return 1

        return 2*v(n-1)

    for i in range(8) :

        print '%3d %3d' %(u(i), v(i))

      1   1
      2   2
      4   4
      8   8
     16  16
     32  32
     64  64
    128 128

. . .

    x

# Calcul de u(26) et v(26) : affichage du temps

In [3]:

    import time

    start = time.time()

    v(26)

    print time.time() - start

    0.000134944915771

. . .
In [4]:

    start = time.time()

    u(26)

    print time.time() - start

    21.0937569141

. . .

    x

# Courbes des temps de calculs

In [5]:

    def temps(f,L):

        tps=[]# contiendra une liste de temps de calcul

        for j in L:

            start = time.time()

            f(j)

            dureeCalcul=time.time() - start # dureeCalcul=temps de calcul de f(j)

            tps.append(dureeCalcul)

        return tps

    X=range(10,23)

    Yu=temps(u,X)# liste des temps de calcul de u(10), u(11), u(12), ..., u(22)

    Yv=temps(v,X)# liste des temps de calcul de v(10), v(11), v(12), ..., v(22)

    axis([min(X),max(X),-0.05*(max(Yu)-min(Yu)),max(Yu)])# paramètres d'ouverture pour fenêtre graphique

    plot(X,Yu,'r--') #   rouge tireté

    plot(X,Yv,'b*')#   bleu étoilé

    show()

. . .

    x

# Pour comprendre ce qui distingue les deux fonctions

In [6]:

    c=[]

    c.append("\033[01;31m{0}\033[00m")

    c.append('\033[1;36m{0}\033[00m')

    c.append('\033[1;32m{0}\033[00m')

    c.append('\033[1;34m{0}\033[00m')

    c.append('\033[1;46m{0}\033[00m')

    c.append('\033[1;32m{0}\033[00m')

    c.append('\033[1;33m{0}\033[00m')

    c.append('\033[1;34m{0}\033[00m')

    c.append('\033[1;35m{0}\033[00m')

    c.append('\033[1;38m{0}\033[00m')

    c.append('\033[1;41m{0}\033[00m')

    c.append('\033[1;43m{0}\033[00m')

    nb=len(c)

    def uu(n,color=-1):

        if n==0 : return 1

        else:

            print c[color].format('++'*(n**2)+"appel de u({}) (premier terme)".format(n-1))

            y=uu(n-1,(color+1)%nb)

            print c[color].format('--'*(n**2)+"sortie de u({}) (premier terme)".format(n-1))

            print c[color].format('++'*(n**2)+"appel de u({}) (second terme)".format(n-1))

            y+=uu(n-1,(color+1)%nb)

            print c[color].format('--'*(n**2)+"sortie de u({}) (second terme)".format(n-1))

            return y

    def vv(n,color=-1):

        if n==0 : return 1

        else:

            color=(color+1)%nb

            print c[color].format('++'*(n**2)+"appel de v({})".format(n-1))

            y=2*vv(n-1,color)

            print c[color].format('--'*(n**2)+"sortie de v({})".format(n-1))

            return y

    vv(4)

    print "\n\n\n\n\n"

    uu(4)

    ++++++++++++++++++++++++++++++++appel de v(3)
    ++++++++++++++++++appel de v(2)
    ++++++++appel de v(1)
    ++appel de v(0)
    --sortie de v(0)
    --------sortie de v(1)
    ------------------sortie de v(2)
    --------------------------------sortie de v(3)

    ++++++++++++++++++++++++++++++++appel de u(3) (premier terme)
    ++++++++++++++++++appel de u(2) (premier terme)
    ++++++++appel de u(1) (premier terme)
    ++appel de u(0) (premier terme)
    --sortie de u(0) (premier terme)
    ++appel de u(0) (second terme)
    --sortie de u(0) (second terme)
    --------sortie de u(1) (premier terme)
    ++++++++appel de u(1) (second terme)
    ++appel de u(0) (premier terme)
    --sortie de u(0) (premier terme)
    ++appel de u(0) (second terme)
    --sortie de u(0) (second terme)
    --------sortie de u(1) (second terme)
    ------------------sortie de u(2) (premier terme)
    ++++++++++++++++++appel de u(2) (second terme)
    ++++++++appel de u(1) (premier terme)
    ++appel de u(0) (premier terme)
    --sortie de u(0) (premier terme)
    ++appel de u(0) (second terme)
    --sortie de u(0) (second terme)
    --------sortie de u(1) (premier terme)
    ++++++++appel de u(1) (second terme)
    ++appel de u(0) (premier terme)
    --sortie de u(0) (premier terme)
    ++appel de u(0) (second terme)
    --sortie de u(0) (second terme)
    --------sortie de u(1) (second terme)
    ------------------sortie de u(2) (second terme)
    --------------------------------sortie de u(3) (premier terme)
    ++++++++++++++++++++++++++++++++appel de u(3) (second terme)
    ++++++++++++++++++appel de u(2) (premier terme)
    ++++++++appel de u(1) (premier terme)
    ++appel de u(0) (premier terme)
    --sortie de u(0) (premier terme)
    ++appel de u(0) (second terme)
    --sortie de u(0) (second terme)
    --------sortie de u(1) (premier terme)
    ++++++++appel de u(1) (second terme)
    ++appel de u(0) (premier terme)
    --sortie de u(0) (premier terme)
    ++appel de u(0) (second terme)
    --sortie de u(0) (second terme)
    --------sortie de u(1) (second terme)
    ------------------sortie de u(2) (premier terme)
    ++++++++++++++++++appel de u(2) (second terme)
    ++++++++appel de u(1) (premier terme)
    ++appel de u(0) (premier terme)
    --sortie de u(0) (premier terme)
    ++appel de u(0) (second terme)
    --sortie de u(0) (second terme)
    --------sortie de u(1) (premier terme)
    ++++++++appel de u(1) (second terme)
    ++appel de u(0) (premier terme)
    --sortie de u(0) (premier terme)
    ++appel de u(0) (second terme)
    --sortie de u(0) (second terme)
    --------sortie de u(1) (second terme)
    ------------------sortie de u(2) (second terme)
    --------------------------------sortie de u(3) (second terme)

Out[6]:

    16

. . .

    x

# Courbes des nombres d'opérations

In [7]:

    def opu(n):

        if n==0 : return 0

        return 1+2*opu(n-1)

    def opv(n):

        if n==0 : return 0

        return 1+opv(n-1)

    for i in range(10) :

        print '%3d %3d' %(opu(i), opv(i))

      0   0
      1   1
      3   2
      7   3
     15   4
     31   5
     63   6
    127   7
    255   8
    511   9

. . .
In [8]:

    X=range(10,23)

    Yopu=[opu(x) for x in X]

    Yopv=[opv(x) for x in X]

    axis([min(X),max(X),-0.05*(max(Yopu)-min(Yopu)),max(Yopu)])# paramètres d'ouverture pour fenêtre graphique

    plot(X,Yopu,'r--',X,Yopv,'b*')

    show()

. . .

    x

### Décompte des opérations par la machine

In [16]:

    def NbOpU(n):

        l=[0]

        def u(n):

            if n==0 :

                return 1

            else :

                y=u(n-1)+u(n-1)

                l[0]+=1

                return y

        u(n)

        return l[0]

    def NbOpV(n):

        l=[0]

        def v(n):

            if n==0 :

                return 1

            else :

                y=2*v(n-1)

                l[0]+=1

                return y

        v(n)

        return l[0]

. . .
In [17]:

    print NbOpU(4)

    print NbOpV(4)

    15
    4

. . .

    x

# Estimation du temps de calcul de u(27) à partir de celui de u(22).

    x

### Temps de calcul de u(22)

In [9]:

    start = time.time()

    u(22)

    tempsu22=time.time() - start

    print tempsu22

    1.23486089706

. . .

    x

### Estimation d'un temps pour u(27)

In [10]:

    tempsu22*2**5

Out[10]:

    39.51554870605469

. . .

    x

### Mesure expérimentale du temps pour le calcul de u(27)

In [11]:

    start = time.time()

    u(27)

    tempsu27=time.time() - start

    print tempsu27

    42.5974290371

. . .

    x

# Temps linéaire pour la suite v

    x

### vraiment linéaire ?

In [12]:

    X=range(10,22)

    Y=temps(v,X)

    plot(X,Y,'b*')

    show()

. . .

    x

### plus convaincant

In [13]:

    import timeit

    def tempsAvecCalculsRepetes(L):

        tps=[]# contiendra une liste de temps de calcul

        for j in L:

            timeit.timeit(number=100000000)

            t = timeit.Timer(stmt="v(%d)"%j, setup="from __main__ import v")

            tps.append(t.timeit() )

        return tps

    X=range(10,22)

    Y=tempsAvecCalculsRepetes(X)

    plot(X,Y,'b*')

    show()

. . .
In [13]:

. . .
Close Expand Open in Pager Close