Les List Comprehensions sont très utiles pour creer des listes qui obeissent à des rêgles simples rapidement
In [1]:
cubes = [i**3 for i in range(5)]
print(cubes)
1) Ecrivez une variable "Ma_liste" qui prends des nombres produits par 10, en partant d'un index allant de de 5 a 10
In [2]:
Ma_liste= [x*10 for x in range(5,11)]
In [3]:
Ma_liste
Out[3]:
2) Creer une liste de multiples de 3 de 0 à 20:
In [4]:
res=[]
for it in range(20):
if (it % 3 == 0): res += [it]
print(res)
In [5]:
a=[i for i in range(20) if i%3 == 0]
print(a)
3) Creer une liste de nombre entiers impairs j'usqu'a 20:
In [6]:
res=[]
for it in range(20):
if (it % 2 != 0): res += [it]
print(res)
In [7]:
b=[i for i in range(20) if i % 2 != 0]
print(b)
In [8]:
def isprime(startnumber):
startnumber*=1.0
prime = True
for divisor in range(2,startnumber**0.5+1):
if startnumber/divisor==int(startnumber/divisor):
prime=False
return prime
On peux simplifier en enlevant la variable locale prime, et en se rappellant que Ptyhon est dynamique
In [9]:
def isprime(test_number):
for divisor in range(2,int(test_number**0.5)+1):
if test_number/divisor==int(test_number/divisor):
return False
return True
In [10]:
isprime(7)
Out[10]:
On remarque que cet algorithme est itératif, il implique un test systematique sur TOUS les entiers compris entre 2 et l'entier arrondi supérieur de la racine carrée de test_number, on dit par exemple que cet algoritme utilise un espace asymptotique en : $$\mathcal{O}\Big(\sqrt{n}\Big)$$ C'est la notation de LANDAU
In [11]:
for a in range(2,100):
if isprime(a):
print(a,end=" ")
Nous avons déja vu un algorithme qui permettait de trouver le plus gran facteur pemier dans un nombre quelconque :
In [12]:
def largest_prime_factor(n):
i = 2
while i * i <= n:
if n % i:
i += 1
else:
n //= i
return n
In [13]:
largest_prime_factor(97)
Out[13]:
Nous allons proposer un algorithme qui décompose les entiers en une liste de nombre premiers... $$100=2*2*5*5$$
In [14]:
Ma_decomposition=[]
it_1 = largest_prime_factor(100)
Ma_decomposition.append(int(it_1))
it_2 = largest_prime_factor(100/it_1)
Ma_decomposition.append(int(it_2))
it_3 = largest_prime_factor(100/(it_1*it_2))
Ma_decomposition.append(int(it_3))
it_4 = largest_prime_factor(100/(it_1*it_2*it_3))
Ma_decomposition.append(int(it_4))
Ma_decomposition.reverse()
print(Ma_decomposition)
In [15]:
Ma_decomposition=[]
nombre_a_factoriser=9
it=largest_prime_factor(nombre_a_factoriser)
Ma_decomposition.append(int(it))
while it < nombre_a_factoriser:
it1 = largest_prime_factor(nombre_a_factoriser/it)
Ma_decomposition.append(int(it1))
it *= it1
Ma_decomposition.reverse()
print(Ma_decomposition)
In [16]:
resultat = 1
for it in Ma_decomposition: resultat *= it
print(resultat)
In [17]:
def liste_decomposition(nombre_a_factoriser):
Ma_decomposition=[]
it=0
if nombre_a_factoriser != 2:
it=largest_prime_factor(nombre_a_factoriser)
Ma_decomposition.append(int(it))
while it < nombre_a_factoriser:
it1 = largest_prime_factor(nombre_a_factoriser/it)
Ma_decomposition.append(int(it1))
it *= it1
Ma_decomposition.reverse()
return Ma_decomposition
else:
Ma_decomposition=[2]
return Ma_decomposition
In [18]:
liste_decomposition(100)
Out[18]:
La complexité d'un algorithme est déterminée par le nombre d'opérations nécessaires pour arriver au résultat. Elle permet de déterminer le temps que mettra un algorithme à s'exécuter, et plus précisément sa dépendance par rapport à la taille des données.
Elle est indépendante de l'ordinateur utilisée.
En algorithmique comme en programation, on aborde les questions suivantes afin d'acprecier la validité et la qualité d'un argorithme ou d'un programme:
- Preuve de terminaison : l'execution s'achève et l'algorithme se termine en un nombre fini d'étapes)
- Efficience : l'algorithme réalise bien ce pourquoi il est conçu
- Spécification complète : de même que les hypothèses d'un énoncé ou le domaine de définition d'une fonction sont clairement définis, les étapes et instructions qui composent l'algorithme sont toutes parfaitement déterminées, par leur nature et par les données sur lesquelles elles s'appliquent.
Mesurer la complexité et l'efficacité d'un programme exige de se doter de protocoles et outils permettant d'établir des comparaisons, entre algorithmes d'une part, et entre différentes programmation d'autre part.
In [19]:
from time import clock
def duree(fonction, n=100):
debut = clock()
fonction(n)
fin = clock()
return fin - debut
def temps_moyen(f, n):
total_time=0
for it in range(10):
total_time += duree(f, n)
return total_time/10
#On se rappelle du cours 10 où l'on a fait quelque chose de semblable
In [20]:
def somme_1(n):
"""
Methode brutale en O(n)
pour calculer la somme des n premiers entiers
"""
for it in range(n+1):
n += it
return n
In [21]:
def somme_a(n):
"""
Methode élégante et analytique en O(1)
pour calculer la somme des n premiers entiers
"""
return n*(n+1)//2
In [22]:
nombre_sup = 1000
print("La durée en µs du calcul des {1} premier entiers est {0: 1.0f}µs par methode balaise ".format(10e6*temps_moyen(somme_1, nombre_sup),nombre_sup))
print("La durée en µs du calcul des {1} premier entiers est {0: 1.0f}µs par methode analytique ".format(10e6*temps_moyen(somme_a, nombre_sup),nombre_sup))
Les deux fonctions ci-dessus possèdent des complexités en :
Ici la complexité se calcule par rapport au terme maximum de la suite que l'on veut caculer. Elle peut se calculer par rapport à différentes valeurs, suivant ce que l'on veut calculer, mais toujours par rapport à une grandeur qui caractérise la complexité du calcul / sa difficulté, par exemple :
- la taille d'une liste (très fréquent)
- une précision (ou son inverse)
- la valeur d'un nombre
- la dimension d'une matrice (son nombre d'élément où le plus grand nombre entre son nombre de ligne et son nombre de colonnes ??)
- le nombre de décimale de $\pi$ que l'on souhaite calculer.
- etc ...
La complexité ne donne pas le temps de calcul ! Celui-ci dépend du type d'opérations que vous souhaitez effectuer, de la puissance de votre machine, du langage, etc ...
A noter que la puissance actuelle des ordinateurs fait que vous n'êtes pas forcément sensibilisé à cette notion, car on peut avoir l'impression que tout est "instantané" Par exemple en python, pour des listes de 10000, voire 100000 éléments toute opération, pas trop compliquée, sera faite instantanément.
Pour pouvoir réfléchir de façon plus poussée qu'un simple chronométrage de temps d'exécution, on a besoin de s'abstraire des éléments matériels.
La complexité est propre à l'algorithme, et non pas au programme (il faut toutefois faire attention que l'implémentation de l'algorithme est correcte).
In [23]:
import random
def get_r_liste(n):
liste = list(range(n))
random.shuffle(liste)
return liste
def minimum(l):
mini = l[0]
for it in range(len(l)):
if l[it] < mini:
mini = l[it]
return mini
print("Test de la fonction 'min' dans des listes contenant entre 100 et 10000 élements")
for it in range(2,5):
l = get_r_liste(10**it)
print( '{0: <10}'.format(10**it), "=> temps moyen : ", '{0: 1.1f} µs'.format(1e6*temps_moyen(min, l)))
print("Test de la fonction 'minimum' dans des listes contenant entre 100 et 10000 élements")
for it in range(2,5):
l = get_r_liste(10**it)
print( '{0: <10}'.format(10**it), "=> temps moyen : ", '{0: 1.1f} µs'.format(1e6*temps_moyen(minimum, l)))
In [24]:
def est_premier_1(n):
if n < 2:
return False
for it in range(2,n):
if n % it == 0:
return False
return True
def est_premier_2(n):
if n < 2:
return False
for it in range(2,int(n**0.5)+2):
if n % it == 0:
return False
return True
def isprime(test_number):
for divisor in range(2,int(test_number**0.5)+1):
if test_number/divisor==int(test_number/divisor):
return False
return True
def trouve_premier_1(n):
while not est_premier_1(n):
n += 1
return n
def trouve_premier_2(n):
while not est_premier_2(n):
n += 1
return n
def trouve_premier_3(n):
while not isprime(n):
n += 1
return n
print("comparaison de la recherche sequentielle de tous les premiers entre 2**15 et 2**20")
print("Methode brutale en O(n)")
for it in range(15,20):
print( '{0: <13}'.format(2**it), "=> temps moyen : ", \
'{0: 1.1f} µs'.format(1e6*temps_moyen(trouve_premier_1, 2**it)))
print("Methode fine en O(sqrt(n))")
for it in range(15,20):
print( '{0: <13}'.format(2**it), "=> temps moyen : ", \
'{0: 1.1f} µs'.format(1e6*temps_moyen(trouve_premier_2, 2**it)))
print("Methode implicant l'appel à une fonction int")
for it in range(15,20):
print( '{0: <13}'.format(2**it), "=> temps moyen : ", \
'{0: 1.1f} µs'.format(1e6*temps_moyen(trouve_premier_3, 2**it)))
Les grandes familles de complexités sont les suivantes :
Une grande partie de l'informatique théorique cherche à caractériser les problèmes, et c'est aussi un problème cruciale en informatique industrielle. En automatique, la question de l'accès aux données des capteurs, où la prises en compte des signaux des consignes peu rendre un automate complettement instable si ce problème n'a pas été correctement résolu.