PARTIE I: REVISIONS

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:

  • en initialisant une liste avec des $0$ qu'on remplace ensuite par les bonnes valeurs;
  • en initialisant une liste vide qu'on agrandit dynamiquement ( = en utilisant append) avec les bonnes valeurs;
  • en utilisant la syntaxe des listes par compréhension (donc en une seule ligne).
In [1]:
# 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$.

In [ ]:
# Cellule à compléter

def probabilite(n):
    prod = 1
    for k in range(1, n):
        prod = prod * (1 - k/365)
    p = 1- prod
    return p
In [3]:
# Test unitaires

print( abs( probabilite(24) - 0.53 ) < 0.01 )
print( abs( probabilite(31) - 0.73 ) < 0.01 )
True
True
In [4]:
# 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.

In [5]:
# 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.

In [6]:
# Cellule à compléter

def moyenne(L):
    m = 0
    for x in L:
        m = m+x
    m = m / len(L)
    return m        
In [7]:
# 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
In [8]:
# 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.

In [9]:
# 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        
In [10]:
# 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
In [11]:
# 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).

In [12]:
# 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
In [13]:
# Tests unitaires

print( indices_pics([10, 51, 32, 14, 78, 40, 82]) == [1, 4, 6] )
True
In [14]:
# 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.

In [15]:
# 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)
In [16]:
# Tests unitaires

print( occurences('toto joue au loto','o') == 5 )
True
In [17]:
# Tests libres

PARTIE II: GRAPHE DU WEB

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.

A) Une petite mise en jambe

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].

In [18]:
# 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
In [19]:
# Tests unitaires

L = [ ('a', [1, 2, 3]), ('b', ['answer', 42]), (813, []) ]
print( aplatir(L) == ['a', 1, 2, 3, 'b', 'answer', 42, 813] )
True
In [20]:
# 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.

In [21]:
# 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

In [22]:
# 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

In [23]:
# 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].

In [24]:
# CELLULE A EXECUTER

for cle in personnage:
    print(cle)  # on affiche les clés
Nom
Age
Taille
In [25]:
# CELLULE A EXECUTER

for cle in personnage:
    print(personnage[cle])  # on affiche les valeurs
Yoda
901
0.66
In [26]:
# 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).

In [27]:
# CELLULE A EXECUTER

print(len(personnage))
3

On peut supprimer une clé et sa valeur avec l'instruction del dictionnaire[cle].

In [28]:
# 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).

In [29]:
# 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:

In [30]:
print( {'Nom': 'Yoda', 'Age': 901, 'Taille': 0.66} == {'Age': 901, 'Taille': 0.66, 'Nom': 'Yoda'} )
True

alors qu'il l'est pour une liste:

In [31]:
print( ['Nom', 'Age', 'Taille'] == ['Age', 'Taille', 'Nom'] )
False

En résumé on a donc les propriétés suivantes :

  • création d'un dictionnaire vide à l’aide d’accolades : dico = {} ;
  • ajout d’une valeur v pour une clé k: dico[k] = v;
  • vérification si une clé appartient au dictionnaire avec la syntaxe if (k in dico);
  • accès à la valeur de la clé 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ération if (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}.

In [32]:
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
            
In [33]:
# Tests unitaires

L = ['zz', 'xy', 'zz', 't', 't', 'xy']
print( unique(L) == {'xy': 1, 't': 3, 'zz': 0} )
True
In [34]:
# Tests libres

Q3. Quelle la complexité de unique(L) en fonction de n = len(L) ?

In [35]:
# 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)

B) Crawler simple

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.

In [36]:
# 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:

In [37]:
# 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.

In [38]:
# 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).

In [39]:
# 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
In [40]:
# Tests unitaires

print( crawler_bfs(4, "p1") == [('p1', ['p2', 'p5']), ('p2', ['p1', 'p4']), ('p5', ['p5']), ('p4', ['p3', 'p5'])] )
True
In [41]:
# 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).

In [42]:
# 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
In [43]:
# Tests unitaires

print( crawler_dfs(4, "p1") == [('p1', ['p2', 'p5']), ('p5', ['p5']), ('p2', ['p1', 'p4']), ('p4', ['p3', 'p5'])] )
True
In [44]:
# Test libres