Fiche d’exercices de Algorithmes et complexité avec corrigé

Qu'est-ce que la récursivité ?

1. AUne boucle qui ne se termine jamais
2. BUn type de structure de données
3. CUne méthode de tri
4. DUne fonction qui s'appelle elle-même sur des entrées plus petites

Quel est le grand O de 3n² + 5n + 2 ?

1. AO(5n)
2. BO(n³)
3. CO(3n²)
4. DO(n²)

Qu'est-ce qu'un algorithme de force brute ?

1. AUn algorithme qui s'exécute sur de nombreux processeurs
2. BUn algorithme qui utilise toujours la récursion
3. CUn algorithme qui essaie toutes les solutions candidates possibles
4. DUn algorithme qui devine une réponse au hasard

Le parcours en largeur (BFS) sur un graphe non pondéré trouve :

1. ALes plus courts chemins en nombre d'arêtes depuis le nœud de départ
2. BUn ordre topologique dans tous les graphes
3. CL'arbre couvrant de poids minimal
4. DLes plus courts chemins dans les graphes qui contiennent des poids d'arêtes négatifs

Quelle est la complexité temporelle de l'algorithme de Bellman-Ford sur un graphe à V sommets et E arêtes ?

1. AO(V × E)
2. BO(V + E)
3. CO(E log V)
4. DO(V³ × E)

Environ combien de comparaisons la recherche dichotomique nécessite-t-elle dans le pire cas sur un tableau trié de 1,000,000 d'éléments ?

1. AEnviron 100
2. BEnviron 20
3. CEnviron 500,000
4. DEnviron 1,000

Comment l'algorithme de Bellman-Ford détecte-t-il un cycle de poids négatif accessible depuis la source ?

1. AIl vérifie si une arête a un poids négatif
2. BAprès V − 1 tours, il vérifie si une arête peut encore être relâchée
3. CIl exécute deux fois l'algorithme de Dijkstra et compare les deux résultats de distances
4. DIl compte les cycles par un parcours en profondeur

Le problème de l'arrêt montre que :

1. ATout programme finit par s'arrêter
2. BAucun algorithme ne peut décider, pour tout programme et toute entrée, si le programme s'arrête
3. CCertains programmes s'exécutent plus vite sur des ordinateurs plus rapides, donc l'arrêt dépend du matériel
4. DIl faut éviter les boucles