Partagez
Voir le sujet précédentAller en basVoir le sujet suivant
ben2510
ben2510
Expert

[NSI Tale] Progression Empty [NSI Tale] Progression

par ben2510 le Sam 12 Sep 2020 - 13:28
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 ?

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
Simeon
Simeon
Niveau 9

[NSI Tale] Progression Empty Re: [NSI Tale] Progression

par Simeon le Sam 12 Sep 2020 - 15:45
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.
ben2510
ben2510
Expert

[NSI Tale] Progression Empty Re: [NSI Tale] Progression

par ben2510 le Sam 12 Sep 2020 - 16:13
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" ?

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
Simeon
Simeon
Niveau 9

[NSI Tale] Progression Empty Re: [NSI Tale] Progression

par Simeon le Dim 13 Sep 2020 - 9:50
@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.
ben2510
ben2510
Expert

[NSI Tale] Progression Empty Re: [NSI Tale] Progression

par ben2510 le Dim 20 Sep 2020 - 11:47
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 !

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
Simeon
Simeon
Niveau 9

[NSI Tale] Progression Empty Re: [NSI Tale] Progression

par Simeon le Dim 20 Sep 2020 - 19:42
@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.
ben2510
ben2510
Expert

[NSI Tale] Progression Empty Re: [NSI Tale] Progression

par ben2510 le Dim 20 Sep 2020 - 20:26
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.

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
Simeon
Simeon
Niveau 9

[NSI Tale] Progression Empty Re: [NSI Tale] Progression

par Simeon le Dim 20 Sep 2020 - 20:59
@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)
ben2510
ben2510
Expert

[NSI Tale] Progression Empty Re: [NSI Tale] Progression

par ben2510 le Dim 20 Sep 2020 - 22:27
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...

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
Simeon
Simeon
Niveau 9

[NSI Tale] Progression Empty Re: [NSI Tale] Progression

par Simeon le Lun 21 Sep 2020 - 10:59
@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.
ben2510
ben2510
Expert

[NSI Tale] Progression Empty Re: [NSI Tale] Progression

par ben2510 le Lun 21 Sep 2020 - 12:54
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).

_________________
On fait la science avec des faits, comme on fait une maison avec des pierres : mais une accumulation de faits n'est pas plus une science qu'un tas de pierres n'est une maison. Henri Poincaré  La notion d'équation différentielle est le pivot de la conception scientifique du monde. Vladimir Arnold
Voir le sujet précédentRevenir en hautVoir le sujet suivant
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum