<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 1A.e - Correction de l'interrogation écrite du 10 octobre 2014
dictionnaire et coût algorithmique
Step1:  Enoncé 1
Q1
Ecrire une fonction qui prend une chaîne de caractères en argument et la retourne sans ses voyelles.
Step2:  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" ....
Q2
Transformer une matrice représentée sous forme de double liste (exemple 
Step3:  Pour cette question, le code écrit fonction doit fonctionner pour n'importe quelle matrice.
Q3
Calculer $\sum_{i=1}^{10} \frac{1}{i}$
Step4:  Q4
Quel le coût du programme suivant en $O(N)$ ?
Step5:  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.
Step6:  Enoncé 2
Q1
On considère un mot abcdef, puis on construit un autre mot selon le schéma 
Step7:  Q2
Retourner un dictionnaire 
Step8:  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.
Step9:  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 
Step10:  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.
Step11:  On ne peut accéder aux éléments d'un générateur car cela n'a pas de sens 
Step12:  Mais on peut parcourir les éléments générés 
Step13:  Q3
Calculer $\frac{1}{1000} \sum_{i=1}^{1000} e^{ \frac{i}{1000} }$.
Step14:  Q4
Quel le coût du programme suivant en $O(N)$ ?
Step15:  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).
<ASSISTANT_TASK:>
Python Code:
from jyquickhelper import add_notebook_menu
add_notebook_menu()
Explanation: 1A.e - Correction de l'interrogation écrite du 10 octobre 2014
dictionnaire et coût algorithmique
End of explanation
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")
Explanation: Enoncé 1
Q1
Ecrire une fonction qui prend une chaîne de caractères en argument et la retourne sans ses voyelles.
End of explanation
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
Explanation: 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" ....
Q2
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).
End of explanation
sum (  1/i for i in range(1,11) )
Explanation: Pour cette question, le code écrit fonction doit fonctionner pour n'importe quelle matrice.
Q3
Calculer $\sum_{i=1}^{10} \frac{1}{i}$
End of explanation
from math import log
s = 0
N = 100
while N > 1 :
    for i in range(1, N):
        s += log(i)
    N //= 2
print(s)
Explanation: Q4
Quel le coût du programme suivant en $O(N)$ ?
End of explanation
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  )
Explanation: 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.
End of explanation
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")
Explanation: 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
End of explanation
dictionnaire_depart = { "cle1":"valeur1", "cle2":"valeur2" }
dictionnaire_retourne =  { } 
for k,v in dictionnaire_depart.items():
    dictionnaire_retourne[v] = k
    
dictionnaire_retourne
Explanation: 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).
End of explanation
dictionnaire_depart = { "cle1":"valeur1", "cle2":"valeur2" }
print ( dictionnaire_depart.items() )
print ( list ( dictionnaire_depart.items() ) )
Explanation: 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.
End of explanation
dictionnaire_depart.items() [0]
Explanation: 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 :
End of explanation
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) )
Explanation: 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.
End of explanation
iterateur(0,10) [0]
Explanation: On ne peut accéder aux éléments d'un générateur car cela n'a pas de sens :
End of explanation
for x in iterateur(0,10):
    print(x)
Explanation: Mais on peut parcourir les éléments générés :
End of explanation
from math import exp
1/1000 * sum ( exp ( i / 1000 ) for i in range(1,1001) )
Explanation: Q3
Calculer $\frac{1}{1000} \sum_{i=1}^{1000} e^{ \frac{i}{1000} }$.
End of explanation
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)
Explanation: Q4
Quel le coût du programme suivant en $O(N)$ ?
End of explanation
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)
Explanation: 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).
End of explanation
<END_TASK>