Le programme du lycée

1. Le nerf de la guerre : les IHM

Vous ne vous en rendez pas compte, mais chaque librairie d’IHM se rattache souvent à un système et à un langage. Par exemple pour macOS, on trouve la librairie Cocoa écrite en Objective C. Pour Android, c’est la bibliothèque UIControls accompagnée du langage Java. Sur PC, on trouve les composants graphiques .NET en C#. Pourquoi tant d’offres ? En fait, vous n’en êtes pas tout à fait conscient même si vous êtes les premiers utilisateurs : l’interface d’un téléphone ou d’un ordinateur portable fait partie des premiers critères de confort. Ainsi, les librairies graphiques représentent une zone de compétition intense du développement informatique, car il faut fournir aux utilisateurs l’interface la plus conviviale possible.

Le copier-coller n’a pas toujours existé ! De même, la touche...

1. Tracer des fonctions

La correction de cet exercice est disponible en téléchargement depuis l’onglet Compléments avec le nom de fichier : PLT_tracer des fonctions_Presentation.py.

Le tracé d’une fonction sur les calculatrices scientifiques ou sur les ordinateurs requiert l’échantillonnage de la fonction sur un certain nombre de points. Ainsi, comme nous le ferions pour un tracé sur une feuille, nous choisissons certaines valeurs de x et nous calculons les valeurs f(x) correspondantes afin de déterminer certains points (x,f(x)) de la courbe. Le tracé est effectué en reliant ces différents points un à un.

Nous allons tracer la courbe f(x) = x². Pour cela, il faut d’abord choisir plusieurs valeurs pour les abscisses. Pour simplifier les choses, nous pouvons choisir des valeurs entre deux bornes avec un intervalle régulier comme X = [-1, 0, 1, 2, 3, 4]. Ensuite, il suffit de calculer les valeurs de f(x) correspondantes et de les stocker dans une liste Y = [1, 0, 1, 4, 9 ,16]. Ainsi, pour tracer l’échantillonnage de la fonction y=x², nous écrivons :

import matplotlib.pyplot as plt 
 
X = [-1, 0, 1, 2, 3, 4] 
Y = [1, 0, 1, 4, 9 ,16] 
 
plt.plot(X,Y) 
plt.show() 

Voici le tracé obtenu :

Nous reconnaissons la position des points que nous avons calculés car ils correspondent aux endroits sur la courbe où se situent des cassures. Entre deux points, le logiciel dessine un segment, ce qui donne cet air "cabossé" à la courbe. Notre échantillonnage est médiocre, car nous avons pris vraiment peu de points. Ceci dit, cela est suffisant pour reconnaître la forme de la parabole.

Pour générer une liste d’abscisses de manière automatique, nous pouvons utiliser une fonction très pratique de la librairie Numpy : numpy.arange(debut, fin, pas).

Il suffit alors de calculer les valeurs f(x) pour chaque abscisse x disponible et de les stocker dans la liste Y :

import matplotlib.pyplot as plt 
import numpy 
 
X = numpy.arange(-1,5,0.1) 
 
Y = [] 
for x in X : 
 Y.append(x**2) 
 
plt.plot(X,Y) 
plt.show() 

Cette fois-ci, le graphique obtenu est d’une qualité impressionnante. La courbe est lisse et correspond parfaitement à la courbe attendue. Dans le tableau X se trouvent 60 valeurs d’abscisse de -1 à 5 par pas de 0.1. Cela semble suffisant pour obtenir un tracé de qualité.

Le graphique manque...

1. La notion de complexité

Cette thématique est chère à l’histoire de l’informatique, car historiquement elle a été au centre du cassage du code de cryptage Enigma utilisé par l’armée allemande durant la Seconde Guerre mondiale. L’équipe anglaise menée par Alan Turing, un des pionniers et des pères de l’informatique, a réussi à la fois à créer un des premiers ordinateurs et à concevoir un programme de décryptage suffisamment rapide. Alan Turing, génie de l’informatique théorique et technique, contrairement à Marc Zuckerberg diplômé de psychologie, ne connaîtra pas une fin heureuse. Peu d’hommes étaient capables à l’époque de mettre en place de tels outils de décryptage. Dans une époque de conflits permanents entre les blocs de l’Est et de l’Ouest où les affaires d’espionnage et de contre-espionnage battaient leur plein, un esprit comme Turing représentait un problème pour les deux camps.

Pourquoi s’intéresse-t-on à la complexité ? Si l’on prend le problème de la cryptographie, la réponse est évidente. Si l’on dispose d’un ordinateur d’une puissance inimaginable, on peut décrypter n’importe quel message. En effet, les méthodes de cryptage sont aujourd’hui connues et utilisées par tout un chacun. Le seul secret restant est la clé utilisée dans la méthode de codage. Ainsi, n’importe quel ordinateur peut générer des clés au hasard et essayer de déchiffrer un message avec. La principale contrainte est finalement le temps passé à effectuer les essais.

Lorsque nous calculons x²+3x+6 avec un ordinateur, quel est le temps utilisé par ce calcul ? La réponse est difficile, car cela dépend du processeur. Certains ont des fréquences...

La correction de ce projet est disponible en téléchargement depuis l’onglet Compléments sous le nom de fichier : NSI PR k plus proches voisins.py.

L’algorithme des k plus proches voisins est un algorithme d’apprentissage qui permet de prédire la catégorie d’un élément à partir d’éléments de caractéristiques et de classes déjà connues.

Supposons que nous étudions un problème avec trois catégories : trois types de fleurs ou trois familles de microbes… Pour chacune de ces catégories, nous extrayons deux paramètres (x,y) : comme la taille et le poids, ou l’âge et le taux d’un marqueur sanguin. En partant d’échantillons servant de vérité terrain, nous allons essayer de prédire la catégorie de nouveaux échantillons.

Pour pouvoir travailler, nous construisons tout d’abord nos échantillons de référence virtuels en tirant aléatoirement des groupes d’échantillons :

import matplotlib.pyplot as plt 
import random 
 
points= [] 
N = 50   # nombre d'échantillons par catégorie 
 
Centre = [ (20,20), (80,50), (10,80)] 
 
for categorie in range(3): 
 for i in range(N): 
    x = random.normalvariate(Centre[categorie][0],20) 
    y = random.normalvariate(Centre[categorie][1],20) 
    if 0 < x < 100 and 0 < y < 100 : 
      points.append((x,y,categorie)) 
 
c2 = ('darkred','darkgreen','lightblue' ) 
for point in points: 
   x,y,cat = point 
   plt.scatter(x,y, s=20, c=c2[cat],  marker='o') 
 
plt.show() 

Nous générons à partir du centre de chaque catégorie 50 points servant de vérité terrain. Nous générons des coordonnées autour de ces centres avec un tirage aléatoire gaussien. Si le point est en dehors de notre fenêtre de mesure [0,100]x[0,100], il n’est pas inséré dans la liste. Nous remplissons la liste nommée points avec des tuples contenant trois valeurs : x, y et l’identifiant de la catégorie.

Les dernières lignes permettent grâce à Matplotlib et à la fonction scatter() de représenter l’ensemble de ces points dans un graphique en utilisant la couleur associée à chaque catégorie :

La question de la classification se pose maintenant simplement. On a nouvel échantillon de caractéristiques (20,20), quelle est sa catégorie ? Sur le graphique, ce point est entouré de points rouges, il est fort probable que sa catégorie soit rouge aussi. Si ses caractéristiques sont (40,60), il est entouré de deux points rouges et d’un point vert, on aurait tendance à dire qu’il appartient plutôt à la classe rouge.

Ainsi fonctionne l’algorithme des k plus proches voisins. Pour un point donné correspondant à un nouvel échantillon...