Qu'est-ce qu'un algorithme ?
Une succession d'instructions pour obtenir un résultat souhaité.
Qu'est-ce que l'algorithmique ?
L'étude et la conception de règles pour écrire des algorithmes.
Quelles sont les trois parties d'un algorithme ?
Données en entrée, traitement particulier, données en sortie.
Que fait un algorithme avec les données en entrée ?
Il décrit un traitement particulier.
Que fournit un algorithme après traitement ?
Des données en sortie.
Quelle est l'origine du terme algorithme ?
Il vient du nom du mathématicien perse Muhammad Ibn Mūsā al-Khuwārizmī.
Qu'est-ce qu'un programme en informatique ?
La traduction d’un algorithme dans un langage de programmation.
Qui a défini les propriétés d'un algorithme en 1968 ?
Donald Knuth dans The art of computer programming.
Que doit faire un algorithme selon Donald Knuth ?
Se terminer après un nombre fini d’étapes.
Quelles actions un algorithme doit-il définir selon Knuth ?
Chaque action doit être définie précisément.
Combien d’entrées un algorithme peut-il accepter selon Knuth ?
Zéro ou plusieurs entrées.
Combien de sorties un algorithme doit-il produire selon Knuth ?
Une ou plusieurs sorties.
Combien de temps doivent durer les instructions d’un algorithme selon Knuth ?
Un temps fini exactement.
En quelle période Euclide a-t-il décrit son algorithme du PGCD ?
Vers 300 av. J.-C.
Dans quel livre des Éléments Euclide a-t-il décrit son algorithme ?
Dans le livre VII des Éléments.
Que calcule l'algorithme d'Euclide ?
Le plus grand commun diviseur de deux entiers.
Que fait l'algorithme d'Euclide après avoir calculé le reste r de m divisé par n ?
Il renvoie n si r vaut zéro.
Que fait l'algorithme d'Euclide si le reste r n'est pas zéro ?
Il remplace m et n par n et r et recommence.
Quels sont les deux entiers choisis au début de l'algorithme d'Euclide ?
Deux entiers m et n.
Qu'est-ce que la complexité d'un algorithme ?
Le nombre d'opérations élémentaires et d'affectations nécessaires à son exécution.
Comment s'écrit une complexité linéaire ?
Sous la forme avec .
Comment se note une complexité linéaire ?
Elle se note .
Comment s'écrit une complexité quadratique ?
Sous la forme avec .
Comment se note une complexité quadratique ?
Elle se note .
Comment fonctionne la recherche linéaire dans un tableau ?
Elle parcourt élément par élément jusqu'à trouver la valeur ou la fin.
Quel est le coût dans le pire cas de la recherche linéaire ?
Le coût est linéaire dans le pire cas.
Que conserve le calcul séquentiel d’un extremum ?
Il conserve une référence au premier élément.
Quand le calcul séquentiel d’un extremum remplace-t-il la référence ?
Lorsqu’un élément plus grand ou plus petit est rencontré.
Comment commence le calcul séquentiel d’une moyenne ?
Avec un accumulateur initialisé à zéro.
Que fait le calcul séquentiel d’une moyenne avec les valeurs de la liste ?
Il les ajoute successivement à l’accumulateur.
Qu'est-ce que la recherche dichotomique ?
Une méthode qui divise un espace ordonné en deux pour chercher une valeur.
Que fait la recherche dichotomique après avoir examiné l'élément central ?
Elle s'arrête si c'est la valeur cherchée ou conserve une moitié selon la comparaison.
Quelle est la complexité temporelle de la recherche dichotomique ?
Elle est logarithmique, notée .
Comment fonctionne le tri par insertion sur un tableau ?
Il insère chaque élément à sa place parmi les précédents en décalant les plus grands.
Quelle est la complexité du tri par insertion dans le pire cas ?
La complexité est quadratique, notée .
Que fait le tri par sélection pour trier un tableau ?
Il échange le plus petit élément non trié avec l'élément courant jusqu'au tri complet.
Qu'est-ce qu'un variant de boucle ?
Une quantité entière positive ou nulle qui décroît strictement à chaque itération.
Qu'impose l'existence d'un variant de boucle pour une boucle while ?
Elle garantit la terminaison de la boucle.
Pourquoi un entier positif ou nul ne peut-il pas décroître indéfiniment ?
Parce qu'il ne peut pas devenir négatif en décroissant strictement.
Quelle quantité est un variant dans la fonction de calcul de 2^n ?
La quantité .
Pourquoi est-il un variant dans la fonction de calcul de 2^n ?
Parce qu'il reste positif ou nul et décroît d'une unité à chaque itération.
Qu'est-ce qu'un algorithme glouton ?
Un algorithme glouton construit une solution pas à pas en choisissant l'option la meilleure à chaque étape sans revenir en arrière.
Un algorithme glouton fournit-il toujours la solution optimale globale ?
Non, sauf dans certaines situations canoniques.
Comment choisit-on une pièce pour rendre une somme avec un algorithme glouton ?
On choisit la plus grande pièce inférieure ou égale à la somme restante.
Que fait-on après avoir choisi une pièce dans l'algorithme glouton pour rendre une somme ?
On déduit sa valeur de la somme restante puis on recommence.
Combien de pièces l'algorithme glouton utilise-t-il pour rendre 63 euros avec 1, 2, 20 et 50 ?
Huit pièces ou billets.
Quelle est la composition de la solution optimale globale pour rendre 63 euros avec 1, 2, 20 et 50 ?
Elle est composée de 20, 20, 20, 2 et 1.
Qu'est-ce que l'algorithme des k plus proches voisins ?
Un algorithme d’apprentissage supervisé qui classe une donnée selon des données étiquetées.
Comment l'algorithme des k plus proches voisins classe-t-il une nouvelle donnée ?
Il trie les données par distance, prend les k plus proches, puis choisit la classe majoritaire.
Quelle est la complexité de l'algorithme des k plus proches voisins en Python ?
Elle est de , liée au tri des données.
Que mesure la distance de Hamming entre deux chaînes ?
Le nombre de positions où leurs caractères diffèrent.
Teste tes connaissances avec un QCM de 25 questions sur Algorithmique et complexité.
1. Qu’est-ce qu’un algorithme ?
2. Que désigne l’algorithmique ?
Révisez le cours complet dans la fiche de révision de Algorithmique et complexité.
Voir la fiche →Importe ton cours et l'IA génère des flashcards en 30 secondes.
Générateur de flashcards