Le programme du lycée

Le programme officiel de spécialité NSI

Le programme officiel de l’enseignement de spécialité numérique et sciences informatiques (NSI) est paru au Journal officiel du 20 septembre 2019. Il est consultable à cette adresse : https://www.education.gouv.fr/pid285/bulletin_officiel.html?cid_bo=138157.

Le ministère conseille largement la démarche projet et la met au centre de l’enseignement de l’informatique afin de permettre aux élèves de s’approprier les notions vues en cours en développant des projets applicatifs. Ce livre met largement en avant cette pédagogie et chaque chapitre propose plusieurs projets du plus simple au plus complexe pour que chacun puisse trouver un défi à son niveau.

Le programme proposé par le ministère est assez vaste, car il couvre des matières très diverses de l’informatique. Voici les différents thèmes proposés que nous avons déjà traités dans les chapitres précédents :

types ;
conditions ;
tuples ;
liste et indexation ;
langages de programmation.

Les thèmes suivants ne sont pas abordés dans notre livre, car ils ne sont pas propres au langage Python et ils vont être normalement traités avec d’autres environnements et d’autres langages :

base de données ;
architecture web ;
réseau...

La complexité des algorithmes

Nous vous proposons une boîte à outils assez riche pour étudier la complexité des algorithmes. Pour avoir enseigné cette matière pendant plusieurs années, il est possible d’avoir quelques repères permettant de traiter ces questions avec une certaine précision. Sans cette approche, les exercices d’analyse de complexité ressemblent malheureusement à une émission du Juste Prix où il s’agit de lancer une proposition en espérant faire mouche.

En espérant démystifier cette notion de complexité qui ne mérite pas cette réputation de science obscure et élitiste, nous vous proposons des descriptions assez complètes dans les exercices de ce chapitre. Nous étudions uniquement la complexité dans le pire cas, cette notion étant la plus simple à mettre en œuvre. D’autres approches de l’évaluation de la complexité existent, comme la complexité en moyenne. Vous ne devez pas ajouter des complexités dans le pire cas avec des complexités en moyenne. Même si elles partagent la même notation en O, elles sont rattachées à des concepts différents.

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...

Les méthodes de tri

Trier un ensemble de nombres est un problème historique de l’informatique, qui a fait phosphorer les cerveaux de beaucoup de chercheurs dans les années 1960 à 1990. Nous avons vu pourquoi trier est important : lorsqu’une base de données est triée, on peut rechercher à l’intérieur avec un temps logarithmique, et non plus linéaire. Le gain de performances est phénoménal et cela ne requiert qu’un unique tri préalable.

Dans le cas d’un dictionnaire de langue, par exemple, les mots sont triés par ordre alphabétique. Si ce n’était pas le cas, il faudrait parcourir toutes les pages du dictionnaire pour une recherche, personne ne ferait cela.

Inconsciemment, nous associons la recherche dans une grande base de données (le dictionnaire) à la notion de tri, cela semble naturel.

Les algorithmes de tri sont pédagogiquement très intéressants pour plusieurs raisons :

Ils ne nécessitent pas une connaissance approfondie du langage : nous avons besoin de savoir manipuler les boucles, les conditions et les lectures/écritures dans une liste/un tableau. Ainsi, après quelques heures de programmation, nous pouvons commencer à coder des méthodes de tri.
Ils ne requièrent pas la connaissance de librairies supplémentaires, comme les accès disque ou les affichages graphiques. Un simple print() peut servir à déboguer et à afficher les résultats.
Le problème du tri nécessite 10 secondes pour être expliqué et autant pour être compris. On dit parfois des meilleurs jeux de société que ce sont ceux avec les règles les plus simples qui sont les plus amusants.
Ils sont variés : il existe au moins huit méthodes de tri classiques, plus les méthodes exotiques propres à des situations particulières. Intellectuellement, cela développe un esprit d’analyse et d’organisation qui permet d’envisager l’idée que plusieurs méthodes sont disponibles pour résoudre un même problème.
Les algorithmes de tri font en général autour de 20 lignes. Un algorithme a donc une chance d’être traité sur une séance de 2 h. Ainsi...

Projets

1. Apprentissage et k plus proches voisins images/etoile.png

La correction de ce projet est disponible en téléchargement sur le site de l’éditeur 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...