TP : Révisions de 1ère année
Contents
TP : Révisions de 1ère année#
Pour programmer, vous pouvez soit utiliser Pyzo, soit Basthon en cliquant sur la “fusée” en haut à droite de chaque TP.
Commandes Basthon :
Ctrl + Entrée : exécuter la cellule
Shift + Entrée : exécuter la cellule puis passer à la suivante
Entrée : passer en mode édition
Échap : sortir du mode édition
Les commandes suivantes sont valables uniquement hors du mode édition :
A : créer une nouvelle cellule (en haut)
B : créer une nouvelle cellule (en bas)
D D : supprimer la cellule
Bases de Python#
Exercice
Calculer \(u_{10}\), où \(u_n\) est définie par \(u_0 = 42\) et \(u_{n+1} = \sqrt{u_n} + 3u_n\).
Il faut trouver 2787204.895558157.
Solution
u = 42
for i in range(10):
u = u**0.5 + 3*u
u
2787204.895558157
Exercice
Écrire une fonction appartient telle que appartient(x, L) renvoie True si x appartient à la liste L, False sinon.
Solution
def appartient(x, L):
for e in L:
if e == x:
return True
return False
print(appartient(3, [1, 5, 3, 4, 1]))
print(appartient(3, [1, 5, 4, 2]))
True
False
Exercice
Écrire une fonction pour déterminer si une liste est triée par ordre croissant.
Solution
def croissant(L):
for i in range(len(L)-1):
if L[i] > L[i+1]:
return False
return True
print(croissant([1, 2, 3, 4, 5]))
print(croissant([1, 2, 3, 5, 4]))
True
False
Dichotomie#
La méthode par dichotomie consiste à divise à chaque étape la taille du problème par 2.
L’exemple le plus classique est la recherche par dichotomie dans une liste triée : on souhaite savoir si un élément \(e\) appartient à une liste triée L.
Considérons par exemple L = \([-2, 1, 2, 4, 6, 7, 8, 9, 11, 12, 14, 15, 18, 22, 54]\) et \(e\) = \(14\).
Au lieu de commencer par regarder le 1er élément de L, on va regarder l’élément du milieu (ici \(9\)):
Comme \(9 < 14\) et que la liste est triée par ordre croissant, on en déduit que \(e\), s’il est dans L, est forcément dans la partie droite :
On se restreint donc par la suite à la partie de L qui est encadrée. On compare \(e\) au milieu de cette partie, c’est-à-dire \(15\) :
Comme \(e < 15\), on peut cette fois se restreinte à la partie gauche. On cherche donc maintenant \(e\) dans la zone suivante :
On compare encore une fois \(e\) au milieu :
Comme \(e > 12\), on regarde à droite :
On a trouvé \(e\) !
Exercice
Compléter le code suivant permettant de rechercher un élément dans une liste triée, par dichotomie.
def dichotomie(e, L):
i, j = 0, len(L) - 1 # i et j sont les indices de L entre lesquels on cherche e
while ...: # tant qu'il reste au moins 1 élément entre les indices i et j
m = ... # milieu de i et j
if e < L[m]:
... # regarder dans la partie gauche
elif e > L[m]:
... # regarder dans la partie droite
else:
... # on a trouvé e
... # e n'a pas été trouvé
Puis tester votre fonction avec le jeu de tests suivant (assert déclenche une erreur si son argument est False) :
L1, L2, L3 = [0, 2], [0, 2, 5], [-2, 1, 2, 4, 6, 7, 8, 9, 11, 12, 14, 15, 18, 22, 54]
assert (dichotomie(0, L1) and not dichotomie(1, L1))
assert (dichotomie(5, L2) and not dichotomie(7, L2))
assert (dichotomie(14, L3) and not dichotomie(-4, L3))
Solution
def dichotomie(e, L):
i, j = 0, len(L) - 1
while i <= j:
m = (i+j)//2
if L[m] == e:
return True
elif L[m] < e:
i = m + 1
else:
j = m - 1
return False
L1, L2, L3 = [0, 2], [0, 2, 5], [-2, 1, 2, 4, 6, 7, 8, 9, 11, 12, 14, 15, 18, 22, 54]
assert (dichotomie(0, L1) and not dichotomie(1, L1))
assert (dichotomie(5, L2) and not dichotomie(7, L2))
assert (dichotomie(14, L3) and not dichotomie(-4, L3))
Matrices#
Exercice
Définir une fonction make_matrix telle que make_matrix(n, p) renvoie une matrice \(n\times p\) remplie de \(0\), sous forme de liste de listes.
Solution
# on propose plusieurs possibilités
def make_matrix(n, p):
return [[0]*p for _ in range(n)]
def make_matrix2(n, p):
M = []
for i in range(n):
M.append([0]*p)
return M
def make_matrix3(n, p):
M = []
for i in range(n):
L = []
for j in range(p):
L.append(0)
M.append(L)
return M
make_matrix(3, 4)
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Question
Écrire une fonction transposee(M) qui renvoie la transposée de la matrice M.
Solution
def transposee(M):
n = len(M)
p = len(M[0])
Mt = make_matrix(p, n)
for i in range(n):
for j in range(p):
Mt[j][i] = M[i][j]
return Mt
transposee([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
[[1, 4, 7], [2, 5, 8], [3, 6, 9]]
Question
Écrire une fonction symetrique(M) qui renvoie True si la matrice M est symétrique, False sinon.
Solution
def symetrique(M):
for i in range(len(M)):
for j in range(i):
if M[i][j] != M[j][i]:
return False
return True
print(symetrique([[1, 2, 3], [2, 4, 5], [3, 5, 6]])) # True
print(symetrique([[1, 2, 3], [2, 4, 7], [3, 5, 6]])) # False
True
False
Graphes#
Si besoin, vous pouvez revoir ce cours (Graphes : Représentations).
Représentation par matrice d’adjacence#
Exercice
Définir dans une variable G la matrice d’adjacence du graphe suivant (on pourra éventuellement utiliser les fonctions précédentes) :
Solution
G = make_matrix(7, 7)
# façon rapide de remplir la matrice
for i, j in [(0, 6), (1, 2), (1, 3), (1, 4), (2, 4), (2, 5), (3, 4), (4, 5)]:
G[i][j] = G[j][i] = 1
G
[[0, 0, 0, 0, 0, 0, 1],
[0, 0, 1, 1, 1, 0, 0],
[0, 1, 0, 0, 1, 1, 0],
[0, 1, 0, 0, 1, 0, 0],
[0, 1, 1, 1, 0, 1, 0],
[0, 0, 1, 0, 1, 0, 0],
[1, 0, 0, 0, 0, 0, 0]]
Exercice
Définir une fonction voisins telle que voisins(G, v) renvoie la liste des voisins du sommet v.
Vérifier que les voisins du sommet \(2\) dans le graphe ci-dessus sont les sommets \(1\), \(4\), \(5\).
Solution
def voisins(G, v):
L = []
for i in range(len(G)):
if G[v][i] == 1:
L.append(i)
return L
voisins(G, 2)
[1, 4, 5]
Exercice
En déduire une fonction deg telle que deg(G, v) renvoie le degré du sommet v.
Solution
def deg(G, v):
return len(voisins(G, v))
deg(G, 2)
3
Exercice
Écrire une fonction n_aretes pour calculer le nombre d’arêtes d’un graphe donné par matrice d’adjacence. Tester avec le graphe G précédent. On pourra soit réutiliser deg, soit deux boucles for pour parcourir les éléments de la matrice.
Solution
def n_aretes(G):
s = 0
for i in range(len(G)):
s += deg(G, i)
return s//2
n_aretes(G)
8
Représentation par liste d’adjacence#
Exercice
Écrire une fonction mat_to_list telle que mat_to_list(G) renvoie la liste d’adjacence du graphe G donné par matrice d’adjacence. Calculer la représentation par liste d’adjacence G_list du graphe G précédent.
Solution
def mat_to_list(G):
L = []
for i in range(len(G)):
L.append(voisins(G, i))
return L
G_list = mat_to_list(G)
G_list
[[6], [2, 3, 4], [1, 4, 5], [1, 4], [1, 2, 3, 5], [2, 4], [0]]
Parcours en profondeur#
Exercice
Écrire une fonction dfs(G, s) renvoyant la liste des sommets de G (défini par liste d’adjacence) suivant un parcours en profondeur depuis le sommet s. Vérifier sur le graphe G_list précédent.
On pourra compléter le code ci-dessous. Ne regarder le cours que si cela est vraiment nécessaire.
def dfs(G, s):
# définir une liste de booléens pour savoir si un sommet a été visité
def aux(u): # fonction récursive
# si u n'a pas été visité :
# afficher u
# marquer u comme visité
# pour chaque voisin v de u
# appeler aux(v)
aux(s)
Solution
def dfs(G, s):
visited = [False]*len(G)
def aux(u):
if not visited[u]:
print(u)
visited[u] = True
for v in G[u]:
aux(v)
aux(s)
dfs(G_list, 0)
0
6
dfs(G_list, 2)
2
1
3
4
5
Exercice
En utilisant un parcours en profondeur, écrire une fonction connexe(G) qui renvoie True si le graphe G est connexe, False sinon.
Vérifier sur G_list (non connexe) et sur un graphe connexe de votre choix.
Solution
# deux solutions
def connexe(G):
visited = [False]*len(G)
def aux(u):
if not visited[u]:
visited[u] = True
for v in G[u]:
aux(v)
aux(0)
return all(visited) # vérifie que tous les éléments de visited sont True
def connexe(G):
visited = [False]*len(G)
def aux(u):
if not visited[u]:
visited[u] = True
for v in G[u]:
aux(v)
aux(0)
for v in range(len(G)):
if not visited[v]:
return False
return True
connexe(G_list)
False
Parcours en largeur#
On rappelle l’utilisation d’une file en Python, avec la classe deque :
from collections import deque
q = deque() # file vide
q.appendleft(4) # ajoute 4 au début
q.appendleft(7)
q.pop() # supprime et renvoie le dernier élément (4)
q.appendleft(-5)
q.pop() # supprime et renvoie le dernier élément (7)
7
Exercice
Écrire une fonction bfs(G, s) affichant les sommets du graphe G lors d’un parcours en largeur depuis le sommet s. Vérifier sur le graphe G_list précédent.
from collections import deque
def bfs(G, s):
# définir une file q contenant s
# définir une liste visited contenant n False, où n est le nombre de sommets
# tant que q est non vide
# extraire le dernier élément de q dans une variable u
# si u n'a pas été visité:
# afficher u
# mettre True dans visited[u]
# pour chaque voisin v de u
# ajouter v au début de q
Solution
from collections import deque
def bfs(G, s):
q = deque()
q.appendleft(s)
visited = [False]*len(G)
while q:
u = q.pop()
if not visited[u]:
print(u)
visited[u] = True
for v in G[u]:
q.appendleft(v)
bfs(G_list, 2)
2
1
4
5
3
Exercice
Écrire une fonction distances(G, s) qui renvoie une liste dist telle que dist[v] soit la distance (en nombre d’arêtes) du sommet s au sommet v. Vérifier sur le graphe G_list précédent.
Solution
def distances(G, s):
q = deque()
q.appendleft(s)
visited = [False]*len(G)
dist = [float("inf")]*len(G)
dist[s] = 0
while q:
u = q.pop()
visited[u] = True
for v in G[u]:
if not visited[v]:
q.appendleft(v)
dist[v] = dist[u] + 1
return dist
distances(G_list, 2)
[inf, 1, 0, 3, 2, 3, inf]