<jupyter_start><jupyter_text>notebook consultable, exécutable, modifiable et téléchargeable en ligne :         	- se rendre à : https://github.com/nsi-acot/continuite_pedagogique_premiere- cliquer sur l'icone "launch binder" en bas de page- patienter quelques secondes que le serveur Jupyter démarre- naviguer dans le dossier `"./algorithmique/k_plus_proches_voisins/"`- cliquer sur le nom de ce notebook   Algorithme des k plus proches voisins.L'algorithme des k plus proches voisins est un algorithme de base en intelligence artificielle.Voici une illustration de cet algorithme dans une situation facilement représentable :Les données sont sous forme d'une liste de personnes caractérisées par un nom, une abscisse, une ordonnée et un type ( homme ou femme ) :|nom |abscisse $x$  | ordonnée $y$  | type ||:-:|:-:|:-:|:-:||A|1|3|homme||B|3|2|femme||C|4,5|0,5|homme||D|4,5|4|femme||E|0,5|1|homme|Les 2 plus proches voisins de B sont A et C, la distance considérée étant la distance vue en seconde.Pour rappel : $AB=\sqrt{(x_B-x_A)^2+(y_B-y_A)^2}$Les 3 plus proches voisins de B sont A, C et D.On va programmer l'algorithme des k plus proches voisins que l'on appliquera sur des tableaux comme ci-dessous :<jupyter_code>data=[['A',4,2,5,1],['B',0,4,2,3],['C',2,3,0,5],['D',1,2,5,0]]<jupyter_output><empty_output><jupyter_text>Question 1 :Compléter la fonction `creation` suivante, prenant comme paramètre un entier  `n`; et qui renvoie un tableau à deux dimensions de `n` lignes et 5 colonnes, similaire au tableau `data` précédent, les  valeurs étant des entiers aléatoires compris entre 0 et 5.<jupyter_code>import random
import math

def creation(n):
    tab=[]
    #à compléter
    return tab

data2=creation(20)
print(data2)<jupyter_output><empty_output><jupyter_text>Question 2 :Compléter la fonction `distance`, prenant comme paramètres deux entiers  `indice1` et `indice2`,  un tableau `tab`, similaire à `data`; et qui renvoie la distance entre les lignes d'indices `indice1` et `indice2`.La distance entre deux lignes A et B étant calculée à l'aide de la formule suivante :distance$=\sqrt{(x_B-x_A)^2+(y_B-y_A)^2+(z_B-z_A)^2+...}$où $x$, $y$, $z$, ... étant les grandeurs numériques de ces deux lignes.Par exemple,  `distance(1,2,data)` doit renvoyer 3,61 ( valeur approchée au centième ).<jupyter_code>def distance(indice1,indice2,tab):
    resultat=0
    # à compléter
    return resultat

print(distance(1,2,data))<jupyter_output><empty_output><jupyter_text>Question 3 :Compléter la fonction `tabDistances`, prenant comme paramètres un entier  `indice` et  un tableau `tab`, similaire à `data`; et qui renvoie le tableau des 2-uples composés des lettres et des distances avec la ligne d'indice `indice`.Par exemple,  `tabDistances(1,data)` doit renvoyer le tableau suivant :`[('A', 5.74), ('C', 3.61), ('D', 4.8)]`.<jupyter_code>def tabDistances(indice,tab):
    resultat=[]
    # à compléter
        
    return resultat


tabD=tabDistances(1,data)
print(tabD)<jupyter_output><empty_output><jupyter_text>Il faut désormais trier par ordre croissant sur les distances, les tableaux de type précédent. Question 4 :Compléter la fonction `tri`, prenant comme paramètre un tableau de 2-uples `tab`, similaire à `tabD`; et qui renvoie ce tableau trié par ordre croissant par rapport à la seconde coordonnée.Par exemple,  `tri(tabD)`, doit renvoyer le tableau suivant: `[('C', 3.61), ('D', 4.8), ('A', 5.74)]`. RemarquePour trier ce tableau,  programmer le tri par sélection, dont on rappelle les différentes étapes :* On recherche la plus petite valeur, puis on échange le 2-uple correspondant avec le premier 2-uple.* On recommence le processus, mais en recherchant à partir du deuxième 2-uple.* On continue le processus, mais en recherchant à partir du troisième 2-uple, et ainsi de suite.<jupyter_code>def tri(tab):
    # à compléter
    return tab

tabTrie=tri(tabD)
print(tabTrie)<jupyter_output><empty_output><jupyter_text>Remarque En cas de difficulté la fonction suivante permet de réaliser le tri ( mais pas par sélection ).<jupyter_code>def tri(tab):
    tab.sort( key=lambda x: x[1])        
    return tab

tabTrie2=tri(tabD)
print(tabTrie2)<jupyter_output><empty_output><jupyter_text>Question 5 :Compléter la fonction `k_plus_proches_voisins`, prenant comme paramètres deux entiers  `k` et `indice`,  un tableau `tab`, similaire à `data`; et qui renvoie le tableau des noms des `k` plus proches voisins de X, X étant le nom correspondand à la ligne `indice`.Par exemple, `k_plus_proches_voisins(2,1,data)`, doit renvoyer le tableau suivant: ['C', 'D'].<jupyter_code>def k_plus_proches_voisins(k,indice,tab): 

    tabTrie= tri(tabDistances(indice,tab))
    
    # à compléter
    
    return resultat



resultat1=k_plus_proches_voisins(2,1,data)
print(resultat1)



resultat2=k_plus_proches_voisins(7,5,data2)
print(resultat2)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11051876153372975, 'fraction_numerical': 0.020709452532294444, 'mean_word_length': 5.418421052631579, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 29, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '394438', 'license': 'CC0-1.0', 'n_tokens_mistral': 1819, 'n_tokens_neox': 1795, 'n_words': 548, 'path': 'algorithmique/k_plus_proches_voisins/knn_version_1/k_plus_proches_voisins_eleve.ipynb', 'repo_name': 'herve-vasseur/python-lycee', 'size': '4877'}