[NSI Tale] Progression

Bonjour,
je n'ai pas trouvé de sujet sur ce thème, alors je me lance : quelle progression avez-vous choisie pour la spécialité NSI en terminale ?

Dans mon lycée, nous sommes deux à intervenir, pour 3h chacun.

Mon collègue a attaqué les bases de données (jusqu'à la Toussaint), puis il fera l'archi (jusqu'à Noël).

De mon côté, je suis parti sur les graphes, d'abord en papier-crayon (y compris des algorithmes), puis on se posera le problème de l'implémentation, pour déboucher sur la partie "génie logiciel" : distinction interface/implémentation, modularité, POO, puis retour sur les classes liste (y compris les algos classiques de parcours de liste, en version itérative et récursive) et dict, structures linéaires pile/file, structures récursives (arbres, ABR), puis algos de graphes (DFS, BFS en particulier), tout ça débouchant sur un projet "coder un algo de graphe et le présenter à l'oral au reste de la classe, avec un support (contrairement au grantoral)".
Tout ça risque de m'occuper au moins jusqu'à Noël.

Il restera un peu de théorie, les programmes comme données (je pense aborder ça en faisant un peu de C et parler de compilation, puis de bytecode de Python, et un peu de pseudo-assembleur avec http://robowriter.info/little-man-computer/ ).
Aussi il restera quelques algos : texte (Boyer-Moore), diviser pour régner (tri fusion, quicksort), prog dynamique (alignement de séquences).

L'idée est de finir pour les vacances de Février, vu la date de l'épreuve de bac.
En espérant garder un peu de temps pour des projets avant le bac.
Après le bac si le programme est fini on fera essentiellement du projet, avec dans l'idée qu'un projet un peu sympa pourrait être une bonne base pour le grantoral.

Et par chez vous, quelle est la progression choisie ?

Quand tu dis archi, c'est processus, routage, sécurité et le truc sur les SoC ? (je trouve qu'il n'y a pas d'archi dans la partie archi en fait...)

C'est proche chez nous, mais d'abord la récursivité (pour laisser le temps aux élèves de la "digérer"), et les structures de données linéaires avant les graphes.
DFS/BFS dans la première partie sur les graphes en essayant d'éviter d'avoir une première partie sur les graphes trop matheuse.

Par contre, ça me parait franchement optimiste niveau date ce que tu proposes. Perso, je pense que prog. dyn et Boyer-Moore ça ne sera pas fait pour l'épreuve de bac de mars. Pareil pour la calculabilité, et sûrement un truc type SoC ou sécurité.
Et même avec ces objectifs plus raisonnables, je pense que ça va être juste. Le programme me semble être fait pour tenir sur une année, pas 2 trimestres.

C'est vrai qu'on a prévu une progression optimiste avec comme objectif de finir en février, en sacrifiant les projets et en les repoussant en fin d'année.
Ce que j'ai appelé archi c'est les µC, la gestion des processus par l'OS, le routage/l'archi réseau, et la sécurité informatique, mais je mets aussi dedans la section "programme en tant que donnée" parce que j'ai l'intention de l'attaquer par l'idée de compilation.

D'accord sur le fait que la récursivité est à aborder rapidement (fin septembre en ce qui me concerne, en reprenant le type de données liste et les algos classiques associés).

J'ai l'impression que beaucoup de collègues vont commencer les types de données par piles/files, mais je pense que coder trop vite donne une idée déformée de ce qu'est l'informatique, et j'ai préféré commencer par le cas général des graphes (en introduisant la notion d'arbres à partir des parcours DFS/BFS), car le fait qu'il y ait plusieurs représentations possibles amène assez naturellement à la distinction interface/implémentation.

De plus, j'espère qu'avoir attaqué par de l'algo papier/crayon permettra de soutenir l'intérêt des élèves durant la (longue) séquence qui va nous amener des rappels sur les listes aux algos de graphes implémentés en Python, en passant par files/piles, la notion de module, la POO... En effet nous aurons un objectif : implémenter des algos de graphes en construisant les outils utiles.

Boyer-Moore, la prog dyn, franchement ça me semble assez vite traité (surtout qu'ici on a fait un peu de prog dyn l'année dernière avec le rendu de monnaie et un problème Euler avec un plus court chemin dans une matrice).

Pour finir, je ne comprends pas ce que tu entends par "une approche trop mathématique des graphes" ?

ben2510 a écrit:
Boyer-Moore, la prog dyn, franchement ça me semble assez vite traité (surtout qu'ici on a fait un peu de prog dyn l'année dernière avec le rendu de monnaie et un problème Euler avec un plus court chemin dans une matrice).

Ce n'est pas le plus long, mais si on veut un niveau de maitrise correct de la part des élèves sur ces sujets, il faut y passer quand même un peu de temps. Amener les élèves vers le fait de penser par eux-même à un algo de prog dyn, ne me parait vraiment pas évident.
Après, faire Boyer-Moore tout seul avec les élèves qui hochent la tête pour me faire plaisir, je le fais en une séance, c'est sur.

ben2510 a écrit:
Pour finir, je ne comprends pas ce que tu entends par "une approche trop mathématique des graphes" ?

C'est plus un ressenti face à des cours que j'ai pu voir, mais c'est toujours bien d'essayer d'expliciter son ressenti.
Beaucoup de définitions dès le départ, des propriétés générales sur les graphes (ex: lemmes des poignées de main), peu d'exemples d'objets que l'on peut modéliser par des graphes. Peu ou pas d'algorithmes.

Je ne suis pas contre parler de graphes eulériens/hamiltonien en NSI, mais se précipiter dessus me semble être un signe qu'on a plus envie de faire un cours de maths que d'info. Avoir transformé à la marge son cours de spé TES en cours de NSI est un autre mauvais signe.

Ce qui t'embête est d'avoir une approche un peu théorisée de la notion de graphe ?
Mais on parle d'une spécialité à 6h, on ne peut pas se contenter d'une approche expérimentale, si ?

En tout cas on a fait Welsh-Powell et une autre variante gloutonne, BFS et DFS en papier crayon, et on a dégagé la question des primitives nécessaires pour coder ces algorithmes (essentiellement sommets(G) et voisins(v,G) pour récupérer une liste des sommets/des voisins d'un sommet respectivement).
Le théorème d'Euler a été prouvé par une démonstration constructive, qui pourra être codée en Python le moment venu.
Le calcul de l'excentricité d'un sommet s'est fait de façon "visuelle" pour l'instant, sans construire un algo (c'est pour plus tard).

La séquence 3 sera très courte, essentiellement :
* trois façons de représenter un graphe en Python : mathématique G=(V,E), par liste de successeurs (un dict), par matrice d'adjacence (+liste sommets).
* écrire sommets, voisins, tableau_sd (le tableau sommets-degrés), WP, BFS, DFS, ... et des fonctions de conversion d'un format à l'autre
* valider sur un jeu de tests (je vais préparer quelques graphes un peu volumineux, disons quelques centaines de sommets)

L'idée est de dégager quelques idées, qui seront ensuite abordées dans la séquence 4 :
* modularité (ici regrouper dans un même module les fonctions utiles)
* séparation interface/implémentation, facilitée par le fait que les graphes aient naturellement plusieurs implémentations
* documentation (spécifiquement docstring, dir et help)
* jeux de tests unitaires, avec du if __name__=='__main__': assert dans le module
* quelques types d'algo : récursivité (Hanoï), glouton (WP ou bien quelques heuristiques de bin packing), prog dyn (Euler 15 ou Euler 18), diviser pour régner (tri fusion, qs), peut-être backtracking (huit reines) pour faire contrepoint aux gloutons [de quoi respirer un peu dans un chapitre assez théorique)
* retour sur TCCO terminaison correction complexité optimalité
* quelques outils de profilage (time, %timeit, @timeit (?)) / comptage du nombre d'appels ou d'opérations
* enfin POO (essentiellement en deux temps : l'OO de Python avec les méthodes et attributs, la notation pointée ; puis l'OO comme moyen d'abstraction)

La séquence 5 portera sur les structures linéaires, retour sur les listes (et les algos classiques qui vont avec : accumulation, retourner, aplatir..., en récursif et en itératif) et les dicts (comparaison avec les listes sur le `in` utilisé dans des algos de la séquence 3, en ce qui concerne la complexité), puis piles et files (déjà utilisées dans DFS et BFS, il s'agit ici d'écrire les classes correspondantes).

Séquence 6 les arbres (ABR, peut-être AST, peut-être la structure de tas) en particulier ACM et arbres d'exploration obtenus par DFS et BFS.

Séquence 7 projet algo graphe : par groupe, coder un algo de graphe classique et le présenter au reste de la classe (Dijkstra, Prim, Kruskal, Floyd-Warshall...)

Séquence 8 projet labyrinthes génération, visualisation, exploration

On a passé trois semaines sur les séquences 1 et 2, je prévois deux semaines sur la 3 et deux-trois semaines sur la 4 (il y a un peu de codage, les algos mentionnés seront dans le cours comme exemples mais il faudra quand même les coder), deux semaines sur la 5, deux sur la 6 (avec la 7 en parallèle des 5 et 6), ça laisse la 8 après Noël (en une heure par semaine + boulot perso).

Je précise que j'ai 3h/semaine puisque mon collègue a les trois autres heures.

Bon je réfléchis un peu à voix haute ici, mais je suis curieux d'avoir des retours !

ben2510 a écrit:Ce qui t'embête est d'avoir une approche un peu théorisée de la notion de graphe ?
Mais on parle d'une spécialité à 6h, on ne peut pas se contenter d'une approche expérimentale, si ?

Ça ne m'embête pas du tout, on "m'accuse" plutôt du contraire. La question, c'est plutôt, quelle théorie mettre en avant, il me semble qu'en NSI ce sont les algorithmes et leur analyse qui doivent être au premier plan. Je présenterais plutôt le théorème d'Euler comme une conséquence de l'algorithme de recherche d'un cycle solution plutôt que l'inverse.

ben2510 a écrit:
En tout cas on a fait Welsh-Powell et une autre variante gloutonne

Dsatur ? Et tu présentes comment Welsh-Powell ? En triant d'abord les sommets ?

ben2510 a écrit:
L'idée est de dégager quelques idées, qui seront ensuite abordées dans la séquence 4 :
* modularité (ici regrouper dans un même module les fonctions utiles)
* séparation interface/implémentation, facilitée par le fait que les graphes aient naturellement plusieurs implémentations
* documentation (spécifiquement docstring, dir et help)
* jeux de tests unitaires, avec du if __name__=='__main__': assert dans le module
* quelques types d'algo : récursivité (Hanoï), glouton (WP ou bien quelques heuristiques de bin packing), prog dyn (Euler 15 ou Euler 18), diviser pour régner (tri fusion, qs), peut-être backtracking (huit reines) pour faire contrepoint aux gloutons [de quoi respirer un peu dans un chapitre assez théorique)
* retour sur TCCO terminaison correction complexité optimalité
* quelques outils de profilage (time, %timeit, @timeit (?)) / comptage du nombre d'appels ou d'opérations
* enfin POO (essentiellement en deux temps : l'OO de Python avec les méthodes et attributs, la notation pointée ; puis l'OO comme moyen d'abstraction)

Pas sur de comprendre ta séquence 4, tu présentes tous les types d'algos à la suite et une bonne dose de "génie" ?

En tout cas, je suis de plus en plus convaincu que ton idée de commencer par les graphes est vraiment pas mal.

La démonstration d'Euler s'appuie précisément sur un algorithme naïf mais optimal de recherche de cycle.

Pour WP on commence par trier les sommets par degré décroissant, effectivement. La variante consiste à numéroter chaque sommet en prenant le crayon de plus petit numéro possible, dans l'ordre des degrés décroissants, alors que pour WP on colorie tous les sommets possible avec le premier crayon avant de passer au deuxième crayon (avec des craies de couleur dans les doigts, c'est très clair !).

Le chapitre 4 est un chapitre théorique de "génie logiciel", effectivement, avec de plus un retour sur ce qui a été fait pendant le confinement.
Pour les types d'algos, je vais effectivement présenter un ou deux de chaque, en pseudo-code, ce qui permettra aux élèves de respirer un peu en allant sur les PC pour coder un peu, tout en appliquant quelques préceptes : modularité, réflexion sur les prototypes des fonctions, tests, doc...

Idéalement le chapitre 4 ne devrait pas être trop long, car il se contente de mettre en place des méthodes.

Commencer par les graphes me plaisait bien parce que c'est un objet suffisamment évolué pour qu'on ait des choix de représentation à faire, qui influent sur la complexité des opérations élémentaires, ce qui illustre bien le fameux "algorithms+data structures=programming" (il me semble que c'est d'ailleurs un point de divergence important entre l'info et les maths, cette réflexion sur la représentation des données, sauf en ana nu où on réfléchit un peu sur les flottants).
Et puis j'ai fait un DEA sur les graphes, et comme tu l'as deviné j'ai fait la spé ES quelques années.

ben2510 a écrit:
Pour WP on commence par trier les sommets par degré décroissant, effectivement. La variante consiste à numéroter chaque sommet en prenant le crayon de plus petit numéro possible, dans l'ordre des degrés décroissants, alors que pour WP on colorie tous les sommets possible avec le premier crayon avant de passer au deuxième crayon (avec des craies de couleur dans les doigts, c'est très clair !).

Il y a vraiment une différence entre les deux ? Dans le sens, il y a un cas où ça ne donne pas le même coloriage ?
(j'aurai dit que la deuxième formulation est juste plus pratique quand on le fait à la main)

Ah non la deuxième est chiante pénible à la main, tu changes de crayon souvent...
Oui, il y a une différence, reste à trouver un graphe où ça se voit (je finis mon NB de SNT et je regarde ça).

Hum. Il y a une différence dans l'algo, mais peut-être pas dans son résultat effectivement. A suivre...

ben2510 a écrit:Ah non la deuxième est chiante pénible à la main, tu changes de crayon souvent...
Oui, il y a une différence, reste à trouver un graphe où ça se voit (je finis mon NB de SNT et je regarde ça).

Hum. Il y a une différence dans l'algo, mais peut-être pas dans son résultat effectivement. A suivre...

C'était de la première que je parlais alors, il y a une version chiante à la main, et l'autre "chiante pour la machine", mais pour moi il s'agit dans le fond du même algorithme, dont on a donné une variante plus pratique à la main.

Pour WP quand tu reposes le crayon c'est définitif ;
pour la variante, tu colories les sommets dans l'ordre en prenant à chaque fois le crayon de plus petit numéro (potentiellement tu changes de crayon sans arrêt, ça peut devenir vite casse-pieds).

Il semblerait que les fameuses entrées prépondérantes du programme aient été spécifiées pour NSI, ici :

https://www.enseignerlinformatique.org/2020/11/07/programme-nsi-de-terminale-entrees-preponderantes-novembre-2020/

L'introduction reste néanmoins nébuleuse.

Quelqu'un a écrit:
Le programme est composé des parties et sous-parties suivantes. Les sujets du baccalauréat garantiront que les élèves pourront choisir 3 exercices en évitant les parties en gras s’ils le souhaitent, et en se concentrant sur les « entrées prépondérantes » du programme.

VinZT a écrit:Il semblerait que les fameuses entrées prépondérantes du programme aient été spécifiées pour NSI, ici :

https://www.enseignerlinformatique.org/2020/11/07/programme-nsi-de-terminale-entrees-preponderantes-novembre-2020/

L'introduction reste néanmoins nébuleuse.

Quelqu'un a écrit:
Le programme est composé des parties et sous-parties suivantes. Les sujets du baccalauréat garantiront que les élèves pourront choisir 3 exercices en évitant les parties en gras s’ils le souhaitent, et en se concentrant sur les « entrées prépondérantes » du programme.

Ceci semble s’interpréter par "les IG de NSI ont pris sur eux d'alléger la partie du programme qui sera réellement exigible à l'examen", non ?

Selon mon collègue qui a en charge NSI en terminale, les allégements correspondent à ce qu'il pourrait traiter réellement en classe, lors une année normale, avec une échéance du bac en juin … Bref, dans les conditions actuelles (niveau des élèves + contraintes sanitaires + épreuve maintenue en mars), ça lui semble de toutes façons mal barré.

Prezbo a écrit:

Ceci semble s’interpréter par "les IG de NSI ont pris sur eux d'alléger la partie du programme qui sera réellement exigible à l'examen", non ?

Je le vois de la même façon.

VinZT a écrit:
Selon mon collègue qui a en charge NSI en terminale, les allégements correspondent à ce qu'il pourrait traiter réellement en classe, lors une année normale, avec une échéance du bac en juin …

Le programme de terminale n'est pas si énorme que ça, il y a beaucoup de chose qui vont vite quand même. Dire qu'on a besoin d'aller jusqu'à juin pour faire la version "allégée" me paraît même assez délirant.

Je ne sais pas si c'est délirant, je ne suis pas assez calé pour juger. En revanche, je sais que le groupe qu'a mon collègue est constitué d'élèves assez peu motivés, ayant choisi NSI par défaut, pas geek pour un sou, et que tout développement de point du cours prend énormément de temps. Je n'ai pas raison particulière de douter de ce que me dit le collègue, ayant moi-même ce genre de profil en maths.

VinZT a écrit:Je ne sais pas si c'est délirant, je ne suis pas assez calé pour juger. En revanche, je sais que le groupe qu'a mon collègue est constitué d'élèves assez peu motivés, ayant choisi NSI par défaut, pas geek pour un sou, et que tout développement de point du cours prend énormément de temps. Je n'ai pas raison particulière de douter de ce que me dit le collègue, ayant moi-même ce genre de profil en maths.

Je pense quand même que les élèves mous n'explique pas tout, il doit y avoir un problème sur la compréhension des limites du programme ou sur le niveau de maîtrise attendue des élèves, ce qui n'est pas surprenant vu le peu d'information que l'on a, en plus de l'absence d'expérience. Certain point comme la décidabilité par exemple demanderait des semaines pour être vaguement comprise par les élèves, alors qu'il s'agit de juste faire deux heures en mode "vulgarisation scientifique".
Je crois aussi que dans une discipline que l'on connait bien, il est plus facile de se dire, j'ai présenté correctement telle notion, j'ai passé un temps raisonnable à la traiter, si l'élève n'a pas compris, il vaut mieux lui laisser du temps ou lui dire de se mettre au travail, maintenant je passe à autre chose.
Mon expérience sur la faisabilité du programme de NSI est très différente de cela en tout cas.

Que pensez-vous du sujet zéro? Je n’ai absolument pas les compétences mais faisant de la SNT en Seconde et du Python en SNT et maths je m’y intéresse forcément, même si officiellement SNT n’a pas pour vocation à préparer NSI. En pratique, je pense tout de même qu’il ne faut pas non plus leurrer et envoyer les élèves au casse pipe et je fais déjà des petites évaluations sur Python dès la Seconde en leur disant que c’est important d’être intéressé par ça et un minimum compétent pour prendre NSI. Ça permet d’éviter l’écueil déjà signalé : énormément d’abandons de la NSI.

https://eduscol.education.fr/media/3962/download

Merci pour vos éclairages, vous qui avez des élèves en Terminale Spé NSI cette année notamment.

Je n ai pas encore de Terminale NSI. J ai donc fait le sujet avec mes souvenirs de formation.
'ex 1 sur les piles va être difficile pour eux, il faut écrire des programmes. Par contre, l exercice est présenté comme s il ne l'avait jamais vu.
Je pourrais le donner au première.
Le reste ne présente pas de difficulté particulière. Ce qui m a le plus interloqué, c'est que la plupart des exercices peuvent être fait sans jamais avoir entendu parler d arbres ou des réseaux, tout étant expliqué.
Même pas un petit exercice d'algorithmique avec un peu de complexité.

D'après mon collègue en charge de NSI — et qui tempête contre les programmes qu'il juge démesurés — c'est jouable pour les élèves, en tout cas c'est plus jouable qu'en maths où l'on doit traiter beaucoup (trop) de choses avant l'épreuve.

C'est un sujet équilibré, bien construit.
Franchement il n'y a pas de surprises dedans ; il y a juste quelques points un peu plus techniques qui risquent de devenir des classiques,
p.ex le stockage d'un arbre binaire dans une liste/la numérotation des sommets d'un arbre en binaire.
C'est ce qui manque un peu à cette nouvelle matière, un corpus d'exercices de référence...