Sujet du bac 2022 de NSI — Amérique du Sud, jour 2 (session de remplacement) (général)

22-NSIJ2AS1 Page BACCALAURÉAT GÉNÉRAL ÉPREUVE D’ENSEIGNEMENT DE SPÉCIALITÉ SESSION 2022 NUMÉRIQUE ET SCIENCES INFORMATIQUES Durée de l’épreuve : 3 heures 30 L’usage de la calculatrice et du dictionnaire n’est pas autorisé. Dès que ce sujet vous est remis, assurez-vous qu’il est complet. Ce sujet comporte 12 pages numérotées de à . Le candidat traite au choix 3 exercices parmi les 5 exercices proposés. Chaque exercice est noté sur 4 points. 22-NSIJ2AS1 Page Exercice 1 (4 points) Cet exercice traite de programmation, d'algorithmique et de complexité. On souhaite rechercher dans un tableau les ݇plus proches voisins d’un objet donné. On dispose pour cela d’un tableau t non vide contenant des objets d’un même type et d’une fonction distance qui renvoie la distance entre deux objets quelconques de ce type. Étant donné un objet cible du même type que ceux du tableau t, on cherche à déterminer les indices des ݇éléments du tableau t qui sont les plus proches de cet objet (c’est-à-dire ceux dont la distance à l’objet cible est la plus petite). 1. On suppose dans cette question que ݇1 . La fonction plus_proche_voisin(t, cible) ci-dessous prend en argument le tableau t et l’objet cible. Écrire sur votre copie uniquement le bloc d'instructions manquant pour que la fonction renvoie l’indice d'un plus proche voisin de cible. def plus_proche_voisin(t, cible) : dmin = distance(t[0], cible) idx_ppv = 0 n = len(t) for idx in range(1, n) : bloc à écrire return idx_ppv 2. On considère que le coût en temps du bloc manquant est constant. Quelle est la complexité de la fonction plus_proche_voisin quand ݇1 ? Dans la suite, on suppose que ≥ 1. 3. Une approche naïve consiste à parcourir le tableau t pour trouver l’indice de l’élément le plus proche de cible, puis à recommencer pour trouver l’indice du deuxième élément le plus proche de cible, et ainsi de suite. Cela implique de parcourir ݇fois tout le tableau. Afin …