cours
retour au chapitre

Quiz · Algorithmique

auto-évaluation

0/20 questions réussie

Réponses conservées dans ce navigateur uniquement.

Parcours séquentiel d'un tableaucours
  1. 1/2 · parcours-sequentiel-c1voir dans le cours

    Combien d'éléments la fonction contient examine-t-elle au pire (taille n) ?

  2. 2/2 · parcours-sequentiel-c2voir dans le cours

    L'invariant de la boucle dans maximum parle des éléments :

Bases de la complexitécours
  1. 1/2 · complexite-bases-c1voir dans le cours

    Si un algo en O(n²) met 1 seconde pour n=1000, combien de temps environ pour n=10000 ?

  2. 2/2 · complexite-bases-c2voir dans le cours

    Au mieux, combien d'opérations effectue une recherche linéaire qui trouve sa cible ?

Tris par sélection et par insertioncours
  1. 1/2 · tris-c1voir dans le cours

    Dans le tri par sélection, après le tour i, qu'y a-t-il dans t[0..i] ?

  2. 2/2 · tris-c2voir dans le cours

    Le tri par insertion sur un tableau déjà trié coûte :

Recherche dichotomiquecours
  1. 1/2 · dichotomie-c1voir dans le cours

    Pour un tableau trié de 1 000 000 d'éléments, combien d'étapes au pire pour la dichotomie ?

  2. 2/2 · dichotomie-c2voir dans le cours

    Le prérequis indispensable pour appliquer la dichotomie est :

Algorithmes gloutonscours
  1. 1/2 · gloutons-c1voir dans le cours

    Sur le système de pièces (1, 6, 10), pour rendre 12, le glouton donne :

  2. 2/2 · gloutons-c2voir dans le cours

    Quelle propriété un algorithme glouton ne garantit-il pas ?

Les k plus proches voisins (k-NN)cours
  1. 1/2 · knn-c1voir dans le cours

    Pourquoi choisit-on souvent k impair ?

  2. 2/2 · knn-c2voir dans le cours

    Le k-NN appartient à quelle famille d'apprentissage ?

Algorithmique : synthèse de chapitremémo
  1. 1/8 · ph-algorithmique-1-q1voir dans le mémo

    La recherche linéaire d'une valeur dans un tableau de taille nn a pour complexité au pire :

  2. 2/8 · ph-algorithmique-1-q2voir dans le mémo

    La recherche dichotomique dans un tableau trié a pour complexité au pire :

  3. 3/8 · ph-algorithmique-1-q3voir dans le mémo

    Parmi les affirmations suivantes sur le tri par sélection, laquelle est correcte ?

  4. 4/8 · ph-algorithmique-1-q4voir dans le mémo

    Parmi les énoncés suivants sur les algorithmes gloutons, lesquels sont corrects ? (plusieurs réponses)

  5. 5/8 · ph-algorithmique-1-q5voir dans le mémo

    Pour appliquer la recherche dichotomique, le tableau doit absolument être…

  6. 6/8 · ph-algorithmique-1-q6voir dans le mémo

    La complexité de la dichotomie est \mathcal{O}(\\_\\_\\_\\_\\_ \, n). Quel mot (ou abréviation) manque entre les espaces ?

  7. 7/8 · ph-algorithmique-1-q7voir dans le mémo

    Ordonner les étapes d'une recherche dichotomique d'une cible dans un tableau trié :

    Glisser-déposer pour réordonner (ou utiliser les flèches).

    • 1. Initialiser gauche = 0 et droite = n - 1
    • 2. Calculer m = (gauche + droite) // 2
    • 3. Comparer t[m] à la cible
    • 4. Mettre à jour gauche ou droite selon la comparaison
    • 5. Recommencer tant que gauche <= droite
    • 6. Retourner l'indice trouvé ou -1
  8. 8/8 · ph-algorithmique-1-q8voir dans le mémo

    Ordonner les étapes de l'algorithme k-NN pour classer un nouveau point :

    Glisser-déposer pour réordonner (ou utiliser les flèches).

    • 1. Calculer la distance entre le nouveau point et chaque exemple étiqueté
    • 2. Trier les exemples par distance croissante
    • 3. Sélectionner les kkk plus proches
    • 4. Voter à la majorité et retourner la classe obtenue