1A.e - Correction de l’interrogation écrite du 10 octobre 2014¶

dictionnaire et coût algorithmique

Enoncé 1¶

Q1¶

Ecrire une fonction qui prend une chaîne de caractères en argument et la retourne sans ses voyelles.

[2]:

def pas_de_voyelle(mot):
    s = ""
    for c in mot:
        if c not in "aeiouy":
            s += c
    return s


pas_de_voyelle("bonjour"), pas_de_voyelle("au revoir")

[2]:

('bnjr', ' rvr')

Cette réponse n’est qu’une réponse parmi d’autres. Certains utilisaient la méthode replace, d’autres un test c == "a" or c == "e" ....

Transformer une matrice représentée sous forme de double liste (exemple : [[0,1,0],[0,0,1]]) en un dictionnaire dont les clés sont les coordonnées et les valeurs les coefficients (soit autant d’éléments que de valeurs non nulles).

[3]:

mat = [[0, 1, 0], [0, 0, 1]]

mat_dict = {}
for i, line in enumerate(mat):
    for j, c in enumerate(line):
        if c != 0:
            mat_dict[i, j] = c

mat_dict

[3]:

{(0, 1): 1, (1, 2): 1}

Pour cette question, le code écrit fonction doit fonctionner pour n’importe quelle matrice.

Q3¶

Calculer $\sum_{i=1}^{10} \frac{1}{i}$

[4]:

sum(1 / i for i in range(1, 11))

[4]:

2.9289682539682538

Q4¶

Quel le coût du programme suivant en $O(N)$ ?

[5]:

from math import log

s = 0
N = 100
while N > 1:
    for i in range(1, N):
        s += log(i)
    N //= 2
print(s)

581.4676254832484

La première boucle s’exécute pour les valeurs $N$ , $N/2$ , $N/4$ , … jusqu’à ce que $N \leqslant 1$ . La boucle imbriquée fait la somme des $log$ de 1 à $N$ . Le nombre des opérations est en $O(N + N/2 + N/4 + ...)$ , soit quelque chose comme $N \sum_{i=1}^{\ln_2 N} \frac{1}{2^i} \leqslant N \sum_{i=1}^{\infty} \frac{1}{2^i} \leqslant 2N$ (c’est une somme géométrique). On vérifie avec le code suivant qui compte le nombre de fois où on ajoute un logarithme.

[6]:

def calcul(N):
    s = 0
    c = 0
    while N > 1:
        for i in range(1, N):
            s += log(i)
            c += 1
        N //= 2
    return c


for i in range(10000, 100000, 10000):
    print(i, calcul(i), i * 2)

10000 19981 20000
20000 39980 40000
30000 59978 60000
40000 79979 80000
50000 99978 100000
60000 119977 120000
70000 139977 140000
80000 159978 160000
90000 179974 180000

Enoncé 2¶

Q1¶

On considère un mot abcdef, puis on construit un autre mot selon le schéma :

1ère lettre, dernière lettre, 2ème lettre, avant-dernière lettre, 3ème lettre, …
Exemple 1 : abcdef $\rightarrow$ afbecd
Exemple 2 : kayak $\rightarrow$ kkaay

[7]:

def strange(mot):
    s = ""
    for i in range(len(mot) // 2):
        s += mot[i] + mot[-i - 1]
    if len(mot) % 2 == 1:
        s += mot[len(mot) // 2]
    return s


strange("abcdef"), strange("kayak")

[7]:

('afbecd', 'kkaay')

Q2¶

Retourner un dictionnaire : les clés deviennent les valeurs et les valeurs deviennent les clés (on suppose que les clés et valeurs sont uniques).

[8]:

dictionnaire_depart = {"cle1": "valeur1", "cle2": "valeur2"}
dictionnaire_retourne = {}
for k, v in dictionnaire_depart.items():
    dictionnaire_retourne[v] = k

dictionnaire_retourne

[8]:

{'valeur2': 'cle2', 'valeur1': 'cle1'}

La méthode items retourne un itérateur et non une liste. Un itéreur n’est pas un ensemble mais une façon de parcourir tous les éléments d’un ensemble.

[9]:

dictionnaire_depart = {"cle1": "valeur1", "cle2": "valeur2"}

print(dictionnaire_depart.items())
print(list(dictionnaire_depart.items()))

dict_items([('cle1', 'valeur1'), ('cle2', 'valeur2')])
[('cle1', 'valeur1'), ('cle2', 'valeur2')]

Le python est un langage paresseux car très lent. Il faut lui demander de façon explicite de construire un ensemble ou de copier un ensemble. Par défaut, il ne copie jamais un dictionnaire ou une liste et il préfère retourner un itérateur plutôt qu’une copie d’un ensemble. La plupart du temps, on ne s’en aperçoit pas à moins de vouloir accéder à un élément précis de l’ensemble :

[10]:

try:
    dictionnaire_depart.items()[0]
except Exception as e:
    print(e)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-24-68beadeaff45> in <module>()
----> 1 dictionnaire_depart.items() [0]

TypeError: 'dict_items' object does not support indexing

La fonction ensemble suivante retourne une liste d’éléments, la fonction iterateur retourne une façon de parcourir un ensemble. On appelle ce type ce fonction un générateur.

[11]:

def ensemble(a, b):
    res = []
    while a < b:
        res.append(a)
        a += 1
    return res


def iterateur(a, b):
    while a < b:
        yield a
        a += 1


print(iterateur(0, 10))
print(ensemble(0, 10))

<generator object iterateur at 0x0000000006F305E8>
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

On ne peut accéder aux éléments d’un générateur car cela n’a pas de sens :

[12]:

try:
    iterateur(0, 10)[0]
except Exception as e:
    print(e)

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-26-86215c660090> in <module>()
----> 1 iterateur(0,10) [0]

TypeError: 'generator' object is not subscriptable

Mais on peut parcourir les éléments générés :

[13]:

for x in iterateur(0, 10):
    print(x)

Q3¶

Calculer $\frac{1}{1000} \sum_{i=1}^{1000} e^{ \frac{i}{1000} }$ .

[14]:

from math import exp

1 / 1000 * sum(exp(i / 1000) for i in range(1, 1001))

[14]:

1.7191411125634257

Q4¶

Quel le coût du programme suivant en $O(N)$ ?

[15]:

from math import log

s = 0
ii = 1
N = 7
for i in range(1, N):
    ii *= 2
    for k in range(1, ii):
        s += log(k)
print(s)

317.3177321667311

A chaque itération $i$ , on calcule $2^i$ logarithmes. On fait $N$ itérations soit $1 + 2 + 4 + ... + 2^N$ calculs, c’est-à-dire environ $O(1 + 2^1 + 2^2 + 2^3 + ... + 2^N) = O(2^{N+1}) = O(2^N)$ (c’est une somme géométrique).

[16]:

from math import log


def calcul(N):
    s = 0
    ii = 1
    c = 0
    for i in range(1, N):
        ii *= 2
        for k in range(1, ii):
            s += log(k)
            c += 1
    return c


for N in range(10, 20):
    print(calcul(N), 2**N)

1013 1024
2036 2048
4083 4096
8178 8192
16369 16384
32752 32768
65519 65536
131054 131072
262125 262144
524268 524288

[17]:

Notebook on github