TP : révisions d’informatique commune 1ère année
Contents
TP : révisions d’informatique commune 1ère année#
Si vous avez besoin de rappels, regarder mon cours de première année.
Représentation des nombres#
Exercice
Ecrire une fonction to_base10(L, b) qui renvoie l’entier (en base 10) qui s’écrit en base \(b\) avec les chiffres de la liste L.
Par exemple, to_base10([0, 0, 1, 1], 2) doit renvoyer \(2^2 + 2^3 = 12\).
Solution
def to_base10(L, b):
s = 0
for i in range(len(L)):
s += L[i] * b**i
return s
to_base10([0, 0, 1, 1], 2)
12
Exercice
Ecrire une fonction from_base10(n, b) qui renvoie la liste des chiffres de l’entier n en base b.
Solution
def from_base10(n, b):
L = []
while n > 0:
L.append(n % b)
n //= b
return L
from_base10(12, 2)
[0, 0, 1, 1]
Exercice
Quelle valeur donne 0.1 + 0.1 + 0.1 ? Expliquer pourquoi.
Solution
0.1 + 0.1 + 0.1
0.30000000000000004
Solution
0.1 est converti en base \(2\) (en notation scientifique) ce qui donne un développement binaire infini. Un float étant stocké avec \(52\) chiffres significatifs (il est impossible de stocker une infinité de chiffres après la virgule), on ne peut pas stocker exactement \(0.1\) en binaire. Il y a donc une troncature qui induit une erreur d’arrondi.
Exercice
Quelle valeur donne 2.0**53 + 1.0 - 2.0**53 ? 2.0**52 + 1.0 - 2.0**52 ? Expliquer.
Solution
2.0**53 + 1.0 - 2.0**53
0.0
Solution
2.0**53 + 1.0 demanderait de stocker le \(1\) en tant que \(53\)ème chiffre après la virgule et est donc tronqué.
Dichotomie#
Exercice
Ecrire une fonction dichotomie(L, e) qui renvoie True si e est dans la liste triée L et False sinon, en complexité \(O(\log n)\). Justifier la complexité.
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é
Solution
def dichotomie(L, e):
a, b = 0, len(L) - 1
while a <= b:
m = (a + b) // 2
if L[m] == e:
return m
elif L[m] < e:
a = m + 1
else:
b = m - 1
return None
Solution
À chaque passage du while, on divise la taille de la liste par \(2\). Si \(L\) est de taille \(n\), le while s’arrête, dans le pire cas, quand \(\frac{n}{2^k}\leq 1\), c’est-à-dire à partir de \(k = \lceil \log_2 n \rceil\).
dichotomie([1, 2, 3, 4, 5, 6, 7, 8, 9], 5) and not dichotomie([1, 2, 3, 4, 5, 6, 7, 8, 9], 10)
True
Exercice
Donner un invariant de boucle permettant de prouver la correction de la fonction dichotomie.
Solution
Invariant de boucle : si e appartient à L, e appartient à L[a:b].
Graphes#
Exercice
Ecrire une fonction mat_to_adj(M) qui convertit une matrice d’adjacence M en liste d’adjacence.
Solution
def mat_to_adj(M):
L = []
for i in range(len(M)):
L.append([])
for j in range(len(M)):
if M[i][j] == 1:
L[i].append(j)
return L
Exercice
Ecrire une fonction dfs(G, s) qui renvoie la liste des sommets visités par un parcours en profondeur du graphe G depuis le sommet s. G est représenté par une liste d’adjacence.
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)
Cell In [9], line 9
aux(s)
^
IndentationError: expected an indented block
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([[1, 4], [0, 2], [], [0, 1], [], []], 0)
0
1
2
4
Exercice
Expliquer l’intérêt et le fonctionnement d’un parcours en largeur.
Solution
Il permet de trouver les distances depuis un sommet \(s\) vers les autres sommets, dans un graphe non pondéré. On visite \(s\) puis tous les voisins de \(s\), puis tous les voisins des voisins de \(s\), etc.
Dijkstra#
On rappelle qu’une file de priorité (min) est une structure de donnée permettant de récupérer efficacement l’élément de plus petite priorité. On définit le type suivant de file de priorité :
class PriorityQueue:
def __init__(self) -> None:
self.d = dict()
def update(self, element, priority):
self.d[element] = priority
def add(self, element, priority):
self.d[element] = priority
def take_min(self):
k_min = None
for k in self.d:
if k_min is None or self.d[k] < self.d[k_min]:
k_min = k
self.d.pop(k_min)
return k_min
def is_empty(self):
return len(self.d) == 0
def __contains__(self, element):
return element in self.d
Il n’est pas nécessaire de comprendre ce code, juste de savoir l’utiliser :
q = PriorityQueue() # file de priorité vide
q.add(0, 6) # ajoute l'élément 0 avec une priorité de 6
q.add(1, 3)
q.add(2, 5)
q.take_min() # renvoie l'élément de priorité min, ici 1
q.update(0, 2) # met à jour la priorité de l'élément 0 à 2
q.take_min()
q.add(3, 7)
q.take_min()
2
Exercice
Rappeler à quoi sert l’algorithme de Dijkstra et quelle condition le graphe doit vérifier pour que l’algorithme fonctionne.
Solution
Il permet de trouver les plus courts chemins depuis un sommet \(s\) vers les autres sommets, dans un graphe pondéré. Les poids des arêtes doivent être positifs.
Solution
L’algorithme de Dijkstra permet de trouver le plus court chemin entre un sommet de départ et tous les autres sommets d’un graphe pondéré. Il faut que les poids des arêtes soient positifs.
Exercice
Compléter la fonction suivante pour implémenter l’algorithme de Dijkstra permettant de trouver les distances de \(s\) aux autres sommets de \(G\). \(G\) est représenté par une matrice d’adjacence pondérée (G[i][j] est le poids de l’arête entre \(i\) et \(j\), float('inf') s’il n’y a pas d’arête).
Tester sur un graphe de votre choix.
def dijkstra(G, s):
n = ... # nombre de sommets de G
dist = ... # créer une liste de taille n remplie de float("inf")
dist[s] = 0
q = PriorityQueue()
# ajouter chaque sommet v de G à q, avec comme priorité dist[v]
while ...: # tant que q n'est pas vide
u = ... # extraire de q le sommet de priorité minimum
for v in range(n): # pour chaque voisin de u
d = dist[u] + G[u][v]
if v in q and ...: # si d < dist[v]
... # mettre à jour dist[v] et la priorité de v
return dist
Solution
def dijkstra(G, s):
n = len(G)
dist = [float("inf")]*n
dist[s] = 0
q = PriorityQueue()
for v in range(n):
q.add(v, dist[v])
while not q.is_empty():
u = q.take_min()
for v in range(n):
d = dist[u] + G[u][v]
if v in q and d < dist[v]:
q.update(v, d)
dist[v] = d
return dist
Exercice
Résoudre cet exercice.
A*#
l’algorithme A* permet de trouver un plus court chemin d’un sommet \(s\) à un sommet \(t\) fixé dans un graphe \(G\) (contrairement à Dijkstra, qui trouve le plus court chemin de \(s\) à tous les sommets). Il est plus rapide que Dijkstra si une bonne heuristique est utilisée.
Principe de l’algorithme A* :
Définir une fonction \(h\) telle que \(h(v)\) soit une estimation de la distance de \(v\) à \(t\).
Modifier l’algorithme de Dijkstra en utilisant
dist[u] + G[u][v] + h(v)comme priorité, au lieu dedist[u] + G[u][v].
Exercice
Modifier la fonction dijkstra pour implémenter l’algorithme A*.
Solution
def astar(G, s, t, h):
n = len(G)
dist = n*[float("inf")]
dist[s] = 0
q = PriorityQueue()
for v in range(n):
q.add(v, dist[v])
while not q.is_empty():
u = q.take_min()
if u == t:
return dist[t]
for v in range(n):
d = dist[u] + G[u][v]
if v in q and d < dist[v]:
q.update(v, d + h(v))
dist[v] = d
Exercice
Si les sommets du graphes sont des points du plan \(\mathbb{R}^2\), quelle heuristique \(h\) serait-il raisonnable d’utiliser pour trouver le plus court chemin entre deux points ? Plusieurs réponses sont possibles.
Solution
On peut utiliser la distance euclidienne, la distance de Manhattan (norme infinie)…