Pour illustrer le comportement de cette fonction, nous considérons un exemple de mini-graphe du Web à six pages et neuf hyperliens comme suit:
Q1. On souhaite construire la liste des $\cos(2k\pi/N)$ pour $N=100$ et $k\in[\![0,N-1]\!]$.
Donner trois façons de le faire:
append) avec les bonnes valeurs;# Cellule à compléter
from math import cos, pi
N = 100
L1 = [ 0 for k in range(N) ]
for k in range(N):
L1[k] = cos(2*k*pi/N)
L2 = []
for k in range(N):
L2.append( cos(2*k*pi/N) )
L3 = [ cos(2*k*pi/N) for k in range(N) ]
Q2. La probabilité ́$p_n$ qu’au moins deux ́etudiants d’une classe de $n\geq2$ ́etudiants aient leur anniversaire le même jour de l’année est donnée par la formule (que l’on ne demande pas de démontrer):
$$p_n= 1-\prod_{k=1}^{n-1}\left(1-\dfrac{k}{365}\right)= 1-\left(1-\dfrac{1}{365}\right)\left(1-\dfrac{2}{365}\right)\times\cdots\times \left(1-\dfrac{n-1}{365}\right)$$
Ecrire une fonction probabilite(n) qui prend en argument un entier naturel n et renvoie $p_n$.
# Cellule à compléter
def probabilite(n):
prod = 1
for k in range(1, n):
prod = prod * (1 - k/365)
p = 1- prod
return p
# Test unitaires
print( abs( probabilite(24) - 0.53 ) < 0.01 )
print( abs( probabilite(31) - 0.73 ) < 0.01 )
True True
# Tests libres
Q3. On cherche à partir de quelle valeur de n cette probabilité devient supérieure ou égale à $0.5$. Ecrire un script (pas une fonction) permettant d’afficher cette valeur de n cherchée.
# Cellule à compléter
n = 2
p = probabilite(n)
while p < 0.5:
n = n+1
p = probabilite(n)
print(n)
23
Q4. Ecrire une fonction moyenne(L) qui renvoie la moyenne des éléments de la liste de flottants L.
# Cellule à compléter
def moyenne(L):
m = 0
for x in L:
m = m+x
m = m / len(L)
return m
# Tests unitaires
eps = 0.00001
print( abs( moyenne([1,1,1,1]) - 1 ) < eps )
print( abs( moyenne([5,1,3,9,-12,35]) - 6.8333333333 ) < eps )
True True
# Tests libres
Q5. En déduire une fonction variance(L) qui renvoie la variance V de la liste de flottants L.
Pour rappel, la formule mathématiques de la variance d’une liste de nombres $(\ell_1, \dots,\ell_n)$ vaut
$$V = \dfrac{1}{n}\sum_{k=1}^n(\ell_k-m)^2$$
où $m$ est la moyenne des élément de la liste.
# Cellule à compléter
def variance(L):
m = moyenne(L)
v = 0
for x in L:
v = v+(x-m)**2
v = v / len(L)
return v
# Tests unitaires
eps = 0.00001
print( abs( variance([1,1,1,1]) - 0 ) < eps )
print( abs( variance([5,1,3,9,-12,35]) - 200.8055555 ) < eps )
True True
# Tests libres
Q6. On dit qu’un ́elément d’une liste est un pic s’il est supérieur à ses deux voisins (ou son unique voisin s’il est
sur le bord). Par exemple, dans la liste L=[10, 51, 32, 14, 78, 40, 82], les pics sont $51$, $78$ et $82$. Le but
est de trouver les indices des pics dans une liste : les indices des pics précédents sont $1$, $4$ et $6$.
Ecrire une fonction indices_pics(L) prenant en entrée une liste (qu’on supposera de longueur au moins
$2$) et renvoyant la liste des indices de ses pics (dans l’ordre croissant).
# Cellule à compléter
def indices_pics(L):
pics = []
n = len(L)
for k in range(0,n):
if k == 0 and L[k] > L[k+1]:
pics.append(k)
elif k == n-1 and L[k] > L[k-1]:
pics.append(k)
elif L[k] > L[k-1] and L[k] > L[k+1]:
pics.append(k)
return pics
# Tests unitaires
print( indices_pics([10, 51, 32, 14, 78, 40, 82]) == [1, 4, 6] )
True
# Tests libres
Q7. Ecrire une fonction récursive occurrences(mot, x) qui prend une chaine de caractères mot et un caractère x et renvoie le nombre d’occurrences de x.
# Cellule à compléter
def occurences(mot, x):
if len(mot) == 0:
return 0
else:
if mot[0] == x:
return 1 + occurences(mot[1:], x)
else:
return occurences(mot[1:], x)
# Tests unitaires
print( occurences('toto joue au loto','o') == 5 )
True
# Tests libres
Le World Wide Web (ou plus simplement « Web ») est un ensemble de pages internet, identifiées de manière unique par leurs adresses web ou URL pour Uniform Ressource Locator, et reliées entre elles par des hyperliens.
Le Web est souvent modélisé par un graphe orienté dont les sommets sont les pages web et les arcs sont les hyperliens entre page.
Le Web étant grand et sauvage , on s’intéresse souvent à des sous-graphes du Web obtenus en naviguant sur le Web, c’est-à-dire en le parcourant page par page en suivant les hyperliens d’une manière bien déterminée. Ce parcours du Web pour en collecter des sous-graphes est réalisé de manière automatique par des logiciels autonomes appelés Web crawlers ou crawlers en anglais, ou « collecteurs » en français.
Q1. Implémenter en python une fonction aplatir(L) qui prend en argument une liste L de couples où
le premier élément du couple est un objet quelconque et le second une liste (potentiellement vide)
d’objets potentiellement quelconques. La fonction doit renvoyer une liste où tous les objets sont mis
à la suite.
Par exemple si L = [ ('a', [1, 2, 3]), ('b', ['answer', 42]), (813, []) ] alors aplatir(L)
renvoie ['a', 1, 2, 3, 'b', 'answer', 42, 813].
# Cellule à compléter
def aplatir(L):
liste = []
for couple in L:
liste.append(couple[0])
for x in couple[1]:
liste.append(x)
return liste
# Tests unitaires
L = [ ('a', [1, 2, 3]), ('b', ['answer', 42]), (813, []) ]
print( aplatir(L) == ['a', 1, 2, 3, 'b', 'answer', 42, 813] )
True
# Test libres
Les dictionnaires sont des structures bien utiles assez similaires aux structures de listes.
Les dictionnaires permettent d’associer des valeurs à des clés. A partir d’une clé, on peut alors accéder directement à la valeur qui lui est associée. On créé un dictionnaire en indiquant les couples clé / valeur entre accolade et séparés par des virgules:
mon_dictionnaire = {clé_1 : valeur_1, clé_2 : valeur_2, clé_3 : valeur_3, ...}
Les clés peuvent être des nombres ou des chaînes de caractères.
Les valeurs peuvent être des nombres, des chaînes de caractères, des tuples ou des listes.
# CELLULE A EXECUTER
# Initialisation d'un dictionnaire non vide nommé personnage
personnage = {"Nom" : "Yoda", "Age" : 900}
# Affichage de la valeur associée à chaque clé
print(personnage["Nom"])
print(personnage["Age"])
print(personnage["Taille"]) # la clé "Taille" n'existe donc on va obtenir une erreur KeyError
Yoda 900
--------------------------------------------------------------------------- KeyError Traceback (most recent call last) Cell In[21], line 9 7 print(personnage["Nom"]) 8 print(personnage["Age"]) ----> 9 print(personnage["Taille"]) # la clé "Taille" n'existe donc on va obtenir une erreur KeyError KeyError: 'Taille'
On ajoute un couple clé / valeur de la manière suivante: dictionnaire[cle] = valeur
# CELLULE A EXECUTER
personnage["Taille"] = 0.66
print(personnage)
{'Nom': 'Yoda', 'Age': 900, 'Taille': 0.66}
On modifie de la même façon la valeur associée à une clé déjà présente: dictionnaire[cle] = valeur
# CELLULE A EXECUTER
personnage["Age"] = 901
print(personnage)
{'Nom': 'Yoda', 'Age': 901, 'Taille': 0.66}
De la même manière que les listes et les tuples, les dictionnaires sont itérables. On itère sur les clés avec l'instruction: for cle in dictionnaire. Noter qu'on obtient la valeur correspondante avec dictionnaire[cle].
# CELLULE A EXECUTER
for cle in personnage:
print(cle) # on affiche les clés
Nom Age Taille
# CELLULE A EXECUTER
for cle in personnage:
print(personnage[cle]) # on affiche les valeurs
Yoda 901 0.66
# CELLULE A EXECUTER
for cle in personnage:
print(cle, " : ", personnage[cle]) # on affiche les clés et les valeurs
Nom : Yoda Age : 901 Taille : 0.66
Pour connaître le nombre de clés on utilise l'instruction len(dictionnaire).
# CELLULE A EXECUTER
print(len(personnage))
3
On peut supprimer une clé et sa valeur avec l'instruction del dictionnaire[cle].
# CELLULE A EXECUTER
del personnage["Age"]
print(personnage)
{'Nom': 'Yoda', 'Taille': 0.66}
On peut tester la présence d'une clé avec l'instruction if (cle in dictionnaire).
# CELLULE A EXECUTER
if ( "Age" in personnage ):
print(True)
else:
print(False)
False
Enfin l'ordre des couples clés : valeurs n'est pas important dans un dictionnaire:
print( {'Nom': 'Yoda', 'Age': 901, 'Taille': 0.66} == {'Age': 901, 'Taille': 0.66, 'Nom': 'Yoda'} )
True
alors qu'il l'est pour une liste:
print( ['Nom', 'Age', 'Taille'] == ['Age', 'Taille', 'Nom'] )
False
En résumé on a donc les propriétés suivantes :
v pour une clé k: dico[k] = v;if (k in dico);k à l’aide de dico[k].On admettra que toutes ces opérations se font à coût constant c'est-à-dire en $O(1)$.
Pour une liste l'opérationif (k in liste)est beaucoup plus coûteuse: elle est en $O\big(len(liste)\big)$ car il faut parcourir toute la liste jusqu'à trouver l'élément cherché.
C'est donc tout l'intérêt des structures de dictionnaires par rapport aux structures de listes : la recherche d'une élément est beaucoup plus rapide, elle se fait à coût constant, quelle que soit la taille du dictionnaire. Cette propriété sera justifiée dans le cours de seconde année.
Q2. Implémenter une fonction unique(L) qui prend en argument une liste L d’objets pouvant servir
comme clé d’un dictionnaire et renvoie un dictionnaire dont les clefs sont les éléments de L et la
valeur correspond à l’ordre de première apparition dans la liste (à commencer par $0$).
Par exemple si L = ['zz', 'xy', 'zz', 't', 't', 'xy'] alors unique(L)renvoie {'xy': 1, 't': 3, 'zz': 0}.
def unique(L):
k = 0 # position dans la liste L
dico = {}
for cle in L:
if not(cle in dico):
dico[cle] = k
k = k+1
return dico
# Tests unitaires
L = ['zz', 'xy', 'zz', 't', 't', 'xy']
print( unique(L) == {'xy': 1, 't': 3, 'zz': 0} )
True
# Tests libres
Q3. Quelle la complexité de unique(L) en fonction de n = len(L) ?
# Répondre en français:
dans la boucle for les instructions sont en O(1) (même cle in dico car dico est un dictionnaire).
donc au total la complexité est en O(n)
Nous allons à présent implémenter un crawler simple en Python. On donne une
fonction recupere_liens(p) qui prend en argument l’URL d’une page Web p et renvoie la liste des URL
des pages q pour lesquelles il existe un hyperlien de p à q, dans l’ordre lexicographique.
# CELLULE A EXECUTER
def recupere_liens(p):
return Web[p]
Pour illustrer le comportement de cette fonction, nous considérons un exemple de mini-graphe du Web à six pages et neuf hyperliens comme suit:
# CELLULE A EXECUTER
Web = { "p1": ["p2", "p5"], "p2": ["p1", "p4"], "p3": ["p5", "p6"], "p4": ["p3", "p5"], "p5": ["p5"], "p6": []}
Dans cette représentation, p1, p2, etc., sont les URL de pages Web (simplifiées pour l’exemple), et les
arcs représentent les hyperliens entre pages Web.
Dans ce mini-graphe, un appel à recupere_liens("p1") renvoie la liste ["p2", "p5"].
Un crawler est un programme qui, à partir d’une URL, parcourt le graphe du Web en visitant progressivement les pages dont les liens sont présents dans chaque page rencontrée, en suivant une stratégie
de parcours de graphe (par exemple, largeur d’abord, ou profondeur d’abord). À chaque nouvelle page,
si celle-ci n’a pas déjà été visitée, tous ses hyperliens sont récupérés et ajoutés à une liste de liens à traiter.
Le processus s’arrête quand une condition est atteinte (par exemple, un nombre fixé de pages ont été
visitées). Le résultat renvoyé par le crawler, que l’on définira plus précisément plus loin, est appelé un
crawl.
Q4. En $2008$, un utilisateur de Wikipédia (l’encyclopédie libre en ligne) a remarqué qu’en démarrant d’une page quelconque du Wikipédia en anglais et en cliquant systématiquement sur le premier lien du texte de la page, on finissait presque toujours (dans 97% des cas en 2016 ) sur l’article «Philosophy». S’agit-il d’un parcours en largeur ou en profondeur du graphe associé au site Wikipédia ? Justifier succinctement.
# Répondre en français:
# il s'agit d'un parcours en profondeur car on clique à chaque fois sur le premier lien
# donc on sur le premier sommet découvert parmi les fils du sommet courant
# un parcours en largeur consisterait à explorer d'abord tous les liens de chaque page
Q5. Implémenter la fonction crawler_bfs(n, u) qui prend en entrée un nombre n de pages et une
URL u et renvoie en sortie une liste de longueur au plus n de couples (v, l) où v est l’URL d’une page
visitée (les pages apparaissant dans l’ordre où elles ont été visitées) et l la liste des liens récupérés
sur la page v. On demande que crawler_bfs parcourt le graphe du Web en suivant une stratégie en
largeur d’abord (breadth-first search), c’est-à-dire en visitant en priorité les pages rencontrées le plus
tôt dans l’exploration. Le crawler doit visiter n pages distinctes, et donc appeler au plus n fois la
fonction recupere_liens. On utilisera une variable de type dictionnaire pour se souvenir des pages
déjà visitées.
Par exemple, sur le mini-graphe, crawler_bfs(4, "p1") pourra renvoyer le résultat
[("p1", ["p2", "p5"]),
("p2", ["p1", "p4"]),
("p5", ["p5"]),
("p4", ["p3", "p5"])]
Pour vous aider on donne l'algorithme de parcours en largeur d'un graphe représenté par une liste d'adjacence L en partant d'un sommet s:
import collections
def parcours_largeur(L, s):
marques = {} # dictionnaire des sommets visités
# on aura marques[sommet]=True si sommet été visité
# et sommet ne sera pas une clé de marques lorsqu'il n'a pas encore été visité
file = collections.deque([s]) # initialisation de la file
parcours = [] # liste qui va stocker les sommets dans l'ordre de leur visite
while len(file) != 0:
sommet = file.popleft()
if not(sommet in marques):
marques[sommet] = True
parcours.append(sommet)
for voisin in L[sommet]:
if not(voisin in marques):
file.append(voisin)
return parcours
Modifier cette fonction pour implémenter la fonction crawler_bfs(n, u).
# Cellule à modifier
import collections
def crawler_bfs(n , u):
marques = {}
file = collections.deque([u])
parcours = []
while len(file) != 0 and len(parcours) < n:
sommet = file.popleft()
if not(sommet in marques):
marques[sommet] = True
voisins = recupere_liens(sommet)
parcours.append( (sommet, voisins) )
for voisin in voisins:
if not(voisin in marques):
file.append(voisin)
return parcours
# Tests unitaires
print( crawler_bfs(4, "p1") == [('p1', ['p2', 'p5']), ('p2', ['p1', 'p4']), ('p5', ['p5']), ('p4', ['p3', 'p5'])] )
True
# Test libres
Q6. Implémenter la fonction crawler_dfs(n, u) qui prend en entrée un nombre n de pages et une
URL u et renvoie en sortie une liste de longueur au plus n de couples (v, l) où v est l’URL d’une page
visitée (les pages apparaissant dans l’ordre où elles ont été visitées) et l la liste des liens récupérés
sur la page v. On demande que crawler_dfs parcourt le graphe du Web en suivant une stratégie en
profondeur d’abord (depth-first search), c’est-à-dire en visitant en priorité les pages rencontrées le plus
tard dans l’exploration. Le crawler doit visiter n pages distinctes, et donc appeler au plus n fois la
fonction recupere_liens. On utilisera une variable de type dictionnaire pour se souvenir des pages
déjà visitées.
Par exemple, sur le mini-graphe, crawler_dfs(4, "p1") pourra renvoyer le résultat
[('p1', ['p2', 'p5']),
('p5', ['p5']),
('p2', ['p1', 'p4']),
('p4', ['p3', 'p5'])]
Pour vous aider on donne l'algorithme de parcours en profondeur d'un graphe représenté par une liste d'adjacence L en partant d'un sommet s:
import collections
def parcours_profondeur(L, s):
marques = {} # dictionnaire des sommets visités
# on aura marques[sommet]=True si sommet été visité
# et sommet ne sera pas une clé de marques lorsqu'il n'a pas encore été visité
pile = [s] # initialisation de la pile
parcours = [] # liste qui va stocker les sommets dans l'ordre de leur visite
while len(pile) != 0:
sommet = pile.pop()
if not(sommet in marques):
marques[sommet] = True
parcours.append(sommet)
for voisin in L[sommet]:
if not(voisin in marques):
pile.append(voisin)
return parcours
Modifier cette fonction pour implémenter la fonction crawler_bfs(n, u).
# Cellule à modifier
import collections
def crawler_dfs(n , u):
marques = {}
pile = [u]
parcours = []
while len(pile) != 0 and len(parcours) < n:
sommet = pile.pop()
if not(sommet in marques):
marques[sommet] = True
voisins = recupere_liens(sommet)
parcours.append( (sommet, voisins) )
for voisin in voisins:
if not(voisin in marques):
pile.append(voisin)
return parcours
# Tests unitaires
print( crawler_dfs(4, "p1") == [('p1', ['p2', 'p5']), ('p5', ['p5']), ('p2', ['p1', 'p4']), ('p4', ['p3', 'p5'])] )
True
# Test libres