Quiz — Algorithmique — Complexité et algorithmes fondamentaux

Question 1

L'équipe de la mission lunaire Artemis III doit interroger une base de données des astronautes ayant marché sur la Lune pour trouver ceux qui ont participé à des missions Apollo. Voici la table `astronautes` :

| id | nom           | mission | annee |
|----|---------------|---------|-------|
| 1  | Armstrong     | Apollo  | 1969  |
| 2  | Aldrin        | Apollo  | 1969  |
| 3  | Collins       | Apollo  | 1969  |
| 4  | Cernan        | Apollo  | 1972  |
| 5  | Schmitt       | Apollo  | 1972  |
| 6  | Young         | Apollo  | 1972  |

Quelle requête SQL permet de récupérer uniquement les astronautes ayant participé aux missions *Apollo* ?

Accepted Answer

SELECT * FROM astronautes WHERE mission = 'Apollo';

Answer

SELECT nom FROM astronautes WHERE annee > 1969;

Answer

SELECT * FROM astronautes WHERE mission LIKE '%Apollo%';

Answer

SELECT id, nom FROM astronautes WHERE mission = Apollo;

Question 2

Lors d'une mission lunaire, l'astronaute Léo doit retrouver l'identifiant d'un module spatial perdu parmi $128$ modules stockés dans une base de données. La base est triée par identifiant. Il utilise l'algorithme suivant pour la recherche :
```python
def recherche_dichotomique(liste, valeur):
    gauche, droite = 0, len(liste)-1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if liste[milieu] == valeur:
            return milieu
        elif liste[milieu] < valeur:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1
```
Quel est le nombre maximal de comparaisons nécessaires pour trouver le module dans le pire cas ?

Accepted Answer

$7$ : car $2^7 = 128$, donc $7$ comparaisons suffisent.

Answer

$6$ : car $2^6 = 64$ et $2^7 = 128$, donc $7$ comparaisons suffisent.

Answer

$8$ : car on divise toujours l'intervalle par $2$, ce qui prend $8$ étapes pour $128$ éléments.

Answer

$128$ : car dans le pire cas, il faut comparer chaque élément une fois.

Question 3

Quel est le résultat de l'exécution du code Python suivant ?
```python
def f(n):
    if n <= 1:
        return n
    else:
        return f(n-1) + f(n-2)

x = f(4)
```

Accepted Answer

5

Answer

3

Answer

7

Answer

9

Question 4

Quelle est la complexité temporelle dans le pire des cas de l'algorithme de tri par insertion sur une liste de $n$ éléments ?

Accepted Answer

$O(n^2)$

Answer

$O(1)$

Answer

$O(\log n)$

Answer

$O(n)$

Question 5

Quelle est la complexité temporelle dans le pire cas de l'algorithme de Dijkstra avec un tas min (priority queue) pour un graphe à $n$ sommets et $m$ arêtes ?

Accepted Answer

$O(m \log n)$

Answer

$O(n^2)$

Answer

$O(n \log n)$

Answer

$O(m + n)$

Algorithmique — Complexité et algorithmes fondamentaux

Notions à maîtriser

Teste-toi sur ce chapitre

Algorithmes : Complexité et Fondamentaux

Garder ta progression ?