Programmes et ressources en numérique et sciences informatiques - voie G

Introduction

Pour bien démarrer

Accéder au livre en hyper-texte de Yannis Delmas-Rigoutsos : https://delmas-rigoutsos.nom.fr/documents/YDelmas-histoire_informatique/index.html    
Ce document vise à présenter rapidement l'histoire de l'informatique, d'Internet et du Web. Il sert de support au cours de même nom délivré en depuis 2009-2010 aux premières années des masters Web éditorial, esDoc, Ingénierie des médias pour l'éducation et Livres et médiation de l'Université de Poitiers.

Accéder au fichier pdf - réalisation collégiale : https://www.e-miage.fr/MONE2/section1/pdf/section1_1.pdf    
Une brève histoire de l'informatique à travers l'évolution des technologies numériques. Citons aussi le livre Histoire illustrée de l'informatique d'Emmanuel Lazard et Pierre Mounier-Kuhn aux éditions Edp Sciences, ISBN 2759818195.

Vocabulaire de la programmation objet : classes, attributs, méthodes, objets

Ressources pour la classe

Accéder au cours et TD de Cédric Baubeau, Maxime Charpignon, Franck Duffaud et Gilles Dalles : https://www.math93.com/images/pdf/NSI/terminale/NSI_Classes.pdf  
Ce document permet d’introduire le vocabulaire de la programmation objet (classe, attributs, méthodes, objets). Les notions d’accesseurs, mutateurs et d’agrégation sont également présentées. Un exemple est traité tout au long du document : il s’agit d’implémenter en Python une classe Carte, qui permet de créer une carte à jouer, puis une classe JeuDeCartes. Ce document sur la POO est prêt à l’emploi : il propose à la fois un cours clair, des exercices rapides permettant une application directe des notions présentées et des TD plus conséquents. Les exercices et les TD sont corrigés à la fin.

Accéder au cours de David Cassagne : https://courspython.com/classes-et-objets.html  
Cours de programmation Python sur les classes et objets (vocabulaire, principe de la POO, syntaxe Python et exemples).

Pour aller plus loin

Accéder au cours de C. Faury et Django Internet web : https://info.blaisepascal.fr/programmation-orientee-objet 
Présentation de la programmation orientée objet et syntaxe Python. Présente la notion d’héritage et de polymorphisme (hors-programme).

Listes, piles, files : structures linéaires. Dictionnaires, index et clé

Pour bien démarrer

Accéder au cours avec des activités non corrigées de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_structDo_liste.html  
Ce document présente sous la forme d’un cours les notions abstraites de listes, piles et files, puis donne un exemple d’implémentation du type abstrait « liste » sous Python. Des petites activités d’application, appelées « à faire vous-même » sont proposées à la suite des notions présentées. Le document peut être directement utilisé par le professeur pour son cours.

Accéder au cours sans activité de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_structDo_dico.html  
Ce document présente sous la forme d’un cours le type abstrait de données « dictionnaire ». Ce court document peut être utilisé par le professeur comme base pour son cours. Un lien renvoie le lecteur sur le cours de NSI de première du même auteur sur les dictionnaires en Python.

Ressources pour la classe

Accéder au cours de Brice Portier et Jean-Manuel Mény, membres du groupe IREM - ISN (académie de Lyon) : https://math.univ-lyon1.fr/irem/Formation_ISN/formation_parcours_graphes/pilefile/file.html  
Ce document présente une implémentation d’une file en python en utilisant soit le type liste, soit une liste doublement chaînée. Dans les deux cas, une file est un objet d’une classe File dans laquelle les méthodes correspondent aux opérations sur les files (enfiler, défiler, savoir si la file est vide ou non). Une application est proposée en bas du document : il s’agit du problème de Josèphe. Le professeur peut directement utiliser ce support pour son cours. Les algorithmes sont implémentés en langage Python et peuvent être utilisés tels quels.

Pour aller plus loin

Accéder au cours avec des TD non corrigés de Romuald Thion : https://forge.univ-lyon1.fr/diu-eil/bloc4/-/tree/master/2_structures_de_donnees  
Ces documents sont hébergés sur Gitlab, et compilent plusieurs ressources du DIU EIL. Les documents sont à l'intention des professeurs, mais peuvent être adaptés assez rapidement pour les élèves pour former un cours. Le plus c'est que les notions sont présentées via le prisme du programme NSI.

Accéder au résumé de cours avec liens vers des exercices de Beau Carnes (freeCodeCamp.org) : https://blog.lesjeudis.com/structures-de-donnees-courantes-javascript  
Dans cette page l'auteur survole 10 structures de données vues en Première NSI , en Terminale NSI et hors programme (tas, tables de hashage). Le document donne un bon aperçu compréhensible par les élèves. Il fournit des liens vers freecodeCamp.org qui propose des exercices sur chaque type de structure (en anglais, mais facilement adaptable).

Arbres

Pour bien démarrer

Accéder au cours avec des activités de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_structDo_arbre.html et https://pixees.fr/informatiquelycee/n_site/nsi_term_algo_arbre.html  
Ce document présente sous la forme d’un cours le type de données abstrait « arbres » et définit le vocabulaire relatif aux arbres binaires. Le document peut être directement utilisé par le professeur pour présenter les arbres. Il est à mettre en lien avec le document du même auteur concernant les algorithmes sur les arbres binaires

Ressources pour la classe

Accéder au cours et exercices de Stéphan Van Zuijlen : https://isn-icn-ljm.pagesperso-orange.fr/NSI-TLE/co/section_chapitre3.html  
Ces documents sont très complets sur les arbres. Ils sont réutilisable directement pour les cours accompagnés d'exercices et de TP.

Graphes

Pour bien démarrer

Accéder au cours avec activités de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_structDo_graphe.html et https://pixees.fr/informatiquelycee/n_site/nsi_term_algo_graphe.html  
Ce document présente le type de données abstrait « graphes » sous la forme d’un cours dans lequel il définit le vocabulaire relatif à cette notion. Ce document se termine par deux exemples d’implémentation en Python (tableaux de tableaux ou dictionnaires). Des petites activités d’application, appelées « à faire vous-même » sont proposées à la suite des notions présentées. Le document peut être directement utilisé par le professeur pour son cours. Il est à mettre en lien avec le document du même auteur concernant les algorithmes sur les graphes

Ressources pour la classe

Accéder au cours de Alain Busser : https://alainbusser.frama.io/NSI-IREMI-974/chap1_graphes.html  
Ce document aborde la notion de graphe (orienté et non orienté), introduit le vocabulaire associé (sommets, arcs, arêtes, matrice d’adjacence) et propose différentes implémentations d’un graphe. Le logiciel Graphviz est utilisé pour créer facilement une représentation graphique d’un graphe. Le professeur peut directement utiliser ce support pour son cours. Les algorithmes sont implémentés en langage Python et peuvent être utilisés tels quels.

Modèle relationnel

Pour bien démarrer

Accéder au cours du DIU EIL du Havre - Bruno Mermet : https://mermet.users.greyc.fr/Enseignement/EnseignementInformatiqueLycee/Havre/Bloc4/indexBD.html  
Cours agrémenté d'exercices corrigés. Tout en allant plus loin que le programme de NSI (conformément au programme du DIU), ce cours reste assez proche du programme de NSI. Le SGBD choisi est SQLite, qui présente l'avantage de ne pas nécessiter d'installation particulière, mais qui reste assez sommaire en termes de fonctionnalités implantées.

Accéder au cours/TP avec des activités non corrigées de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_bd_rela.html  
Ce document se présente sous la forme d’un cours les bases de données relationnelles. À travers un exemple d’une base de données restreinte, la plupart des concepts sont introduits.

Accéder au cours de CPGE de professeur du lycée Blaise Pascal de Clermont-Ferrand : https://info.blaisepascal.fr/cpge-bases-de-donnees-relationnelles  
La partie sur le modèle relationnel est en parfaite adéquation avec le programme de NSI. Ce n'est en revanche pas le cas de la partie sur SQL, qui n'envisage que l'aspect LID (Langage d'Interrogation de Données), mais qui sur ce point, va plus loin que ce qu'on peut attendre d'élèves de Terminale (INNER JOIN, LEFT JOIN, etc.).

Pour aller plus loin

Accéder au cours pour enseignant de Silo (Science informatique au lycée : oui !) - Wiki de l’INRIA : https://wiki.inria.fr/wikis/sciencinfolycee/images/2/2e/LSICh7.pdf  
Support de cours relativement complet sur la matière, qui va bien au-delà du cours de NSI, mais il permet d'avoir un bon recul sur le domaine général que constituent les bases de données relationnelles.

Base de données relationnelle

Pour bien démarrer

Accéder au cours de DIU EIL sous la forme d'un dépôt Git avec PDF, vidéos et TP SQL des professeurs de l’université de Lyon : https://forge.univ-lyon1.fr/diu-eil/bloc4/-/tree/master/4_bases_de_donnees_normalisation  
Il s'agit d'un cours sur la normalisation des bases de données qui va bien au-delà du programme de la classe de terminale. Cependant, il permet à l'enseignant de pouvoir mieux justifier des normalisations "intuitives" qu'il faudra sans nul doute demander aux élèves de réaliser.

Système de gestion de bases de données relationnelles

Pour bien démarrer

Accéder au cours de DIU EIL sous la forme d'un dépôt Git avec PDF, vidéos et TP SQL de professeurs de l’université de Lyon : https://forge.univ-lyon1.fr/diu-eil/bloc4/-/tree/master/3_bases_de_donnees_introduction  
Les bases de données au format sqlite peuvent être téléchargées pour une utilisation hors ligne, ou une utilisation dans Python.

Langage SQL : requêtes d’interrogation et de mise à jour d’une base de données

Ressources pour la classe

Accéder aux exercices en ligne du CNAM : https://deptfod.cnam.fr/bd/tp/  
Base d'exercices corrigés sur des tables d'une base de données de films (elle-même issue du site TMDB), les schémas des tables étant donnés. Un onglet "Jeux de données" permet également de récupérer le fichier sql reprenant l'intégralité des tables, si l'on souhaite travailler en local sans accès aux corrections, directement importable dans MySQL (il faudra le modifier pour l'utiliser avec sqlite). Ce type d'exercices permet notamment de suivre le commentaire présent dans le programme : "On privilégie la manipulation de données nombreuses et réalistes."

Accéder aux exercices en ligne de Didier Boulle : https://webtic.free.fr/sql/exint/q1.htm et https://info.blaisepascal.fr/wp-content/uploads/2019/01/facturation.sqlite  
Base d'exercices corrigés sur des relations d'une base de données de comptabilité (articles, fournisseurs, bon de commande). La ressource est identique à la précédente, mais le format de la base utilisée est différent. La base de données au format sqlite peut être téléchargée en suivant le lien

Accéder à l'outil de sqlitebrowser.org : https://sqlitebrowser.org/dl/  
Permet de créer et d'importer des bases de données, et d'exécuter des requêtes SQL directement dans une fenêtre. C'est un outil très pratique, car il permet de travailler uniquement sur les requêtes SQL, sans passer par une interface Python (au moins dans un premier temps). L'outil fonctionne sans installation (version portable), donc pratique dans les environnements de lycée. Il existe pour un environnement Windows, Linux et MacOs. Il dispose aussi d'une fonction d'enregistrement des différentes requêtes SQL, ce qui semble pratique pour l'interaction enseignant-élève.

Accéder à l'outil de Lunu sur addons.mozilla.org : https://addons.mozilla.org/fr/firefox/addon/sqlite-manager-webext/  
Extension pour Firefox apportant des fonctionnalités similaires à SQLiteBrowser.

Pour aller plus loin

Accéder aux activités, TP et projets, cours et exercices de w3schools.com : https://www.w3schools.com/sql/default.asp  
Un tutoriel en ligne (et en anglais) qui permet de découvrir pas-à-pas SQL avec exécutions interactives de requêtes. Va bien au-delà du programme de la classe de terminale.

Composants intégrés d'un système sur puce

Pour bien démarrer

Accéder au cours de terminale NSI de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_archi_soc.html  
Ce document présente sous la forme d’un cours illustré par des schémas et photos les systèmes sur puces. Il peut être utilisé comme base par le professeur pour son cours.

Gestion des processus et des ressources par un système d’exploitation

Pour bien démarrer

Accéder au cours de terminale NSI de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_archi_proc.html  
Ce document présente les notions de processus et d'interblocage, accompagnées de petites activités d'application.

Ressources pour la classe

Accéder au TP de Computer Science Unplugged : https://classic.csunplugged.org/wp-content/uploads/2014/12/10_fr_Acheminement_et_blocage.pdf  
Un TP prêt à l'emploi en mode débranché qui présente la problématique du blocage de réseaux et les stratégies d'évitement.

Protocoles de routage

Pour bien démarrer

Accéder aux cours de terminale NSI de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_archi_routage.html et https://pixees.fr/informatiquelycee/n_site/nsi_term_structDo_graphe.html et https://pixees.fr/informatiquelycee/n_site/nsi_term_algo_graphe.html  
Cours sur la notion de protocole de routage. Deux exemples sont donnés (protocole RIP et protocole OSPF). Des petites activités d’application, appelées « à faire vous-même » sont proposées à la suite des notions présentées. Le document peut être utilisé directement par le professeur pour son cours. Il peut être mis en lien avec le cours de terminale NSI du même auteur sur les graphes ou les algorithmes de graphes

Ressources pour la classe

Accéder au TO de l'nstitut Mines-Télécom : https://www.youtube.com/watch?v=e3I4opl8EH4&list=PLjXls-kqM6JDyMO3Llm5olS_U2I_P6OHG  
Une série de 6 courtes vidéos ayant servi de support au MOOC « Routage et qualité de service dans l'Internet » proposé par l’IMT (Institut Mines-Télécom) sur la plateforme FUN-MOOC. Ces vidéos incluent notamment une présentation généraliste des protocoles de routage, ainsi qu’une présentation des protocoles RIP et OSPF.

Pour aller plus loin

Accéder au cours de N. Salmon : https://idum.fr/spip.php?article213  
Expose le principe de fonctionnement du routage RIP, ainsi que le fonctionnement de la table de routage, des temporisations et de la métrique. Certaines parties, très techniques, sont au-delà des attendus de NSI.

Sécurisation des communications

Pour bien démarrer

Accéder au cours de terminale NSI de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_archi_secu.html  
Cours sur la notion de protocole de routage. Il présente sous la forme d’un cours le problème de la sécurisation des communications. Le chiffrement symétrique, le chiffrement asymétrique et le protocole HTTPS sont évoqués. Des petites activités d’application, appelées « à faire vous-même » sont proposées à la suite des notions présentées.

Ressources pour la classe

Accéder à la vidéo de Yann Bidon : https://www.youtube.com/watch?v=jMIAoAVbcsw&list=PLYsJ-3MUn_eeYwSgJ3Z_hfrIzGqYOGAaj  
L’objectif général de l’auteur est de faire comprendre le SSL. Il propose pour cela une série de vidéos dont la première permet de comprendre la différence entre la cryptographie symétrique et la cryptographie asymétrique. Des exemples historiques s’appuyant sur la méthode de chiffrement symétrique sont donnés. Pour le chiffrement asymétrique, l’auteur cite l’exemple du chiffrement RSA pour lequel il consacre une vidéo complète : il s’agit de la troisième vidéo de sa playlist « Comprendre le SSL/TLS ».

Notion de programme en tant que donnée, calculabilité, décidabilité

Pour bien démarrer

Accéder au cours d'introduction de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_calcu.html   
Ce document introduit sous la forme d’un cours concis la notion de décidabilité et de calculabilité. En particulier, il explique pourquoi le problème de l’arrêt est indécidable.

Pour aller plus loin

Accéder au cours de DIU (fichier PDF) de Bruno Grenet : https://www.lirmm.fr/%7Egrenet/DIUBloc5/AlgoAvancee.pdf   
Cours complet sur le bloc 5 du DIU. Les pages concernant cette partie du programme sont les pages 39 à 68. On y retrouve toutes les notions clés pour avoir un certain recul par rapport au sujet.

Récursivité

Pour bien démarrer

Accéder au cours au format PDF de Florent Hivert : https://www.lri.fr/%7Ehivert/COURS/CFA-L3/02-Recursivite.pdf   
Cours clair et concis sur la notion de récursivité qui s'appuie sur la notion de pile d'appels. Introduit notamment le concept de récursivité terminale (notion qui n'est pas au programme de NSI).

Ressources pour la classe

Accéder au cours et exercices au format PDF de Didier Müller : https://www.apprendre-en-ligne.net/info/recursivite/recursivite.pdf   
Support mélangeant à bon escient activités en modes branché et débranché, avec des applications mathématiques et récréatives.

Accéder au cours et exercices (archive ZIP) de Didier Müller : https://projet.eu.org/pedago/sin/NSI/cours02/chap3.zip   
Cours et TD prêts à l'emploi avec une partie sur la récursivité (et les algorithmes de tri récursifs), ainsi que sur les algorithmes de type "diviser pour régner".

Paradigmes de programmation

Pour bien démarrer

Accéder au cours de DIU EIL des professeurs de l'université de Lyon : https://forge.univ-lyon1.fr/diu-eil/bloc4/-/tree/master/1_paradigmes_de_programmation   
Cours complet avec dépôt Git du documents au format PDF et de TP en Python.

Accéder au cours de DIU EIL du Havre de Bruno Mermet : https://mermet.users.greyc.fr/Enseignement/EnseignementInformatiqueLycee/Havre/Bloc4/indexParadigmes.html   
Cours qui présente un certain nombre de paradigmes de programmation (fonctionnelle, logique, événementielle, parallèle) avec des exemples et des exercices faisables en ligne. Il s'agit essentiellement d'un cours de culture générale, qui va bien au-delà du programme de la classe de terminale. Cependant, chacun des paradigmes évoqués peut être présenté en Terminale à l'occasion d'un projet.

Ressources pour la classe

Accéder à l'outil swish : https://swish.swi-prolog.org/   
Un interpréteur en ligne pour prolog. Pratique pour un TP de découverte de la programmation logique.

Mise au point des programmes, gestion des bugs

Pour bien démarrer

Accéder au cours de Licence 3 Informatique de Bruno Mermet : https://mermet.users.greyc.fr/Enseignement/CoursPDF/coursTestL3.pdf   
Cours de Licence Informatique d'introduction au test. La première partie (transparents 1 à 5) présente quelques exemples de bugs marquants montrant l'importance de la "mise au point" d'un programme. Le coeur du document, consacré à la définition des tests, est hors sujet par rapport à NSI (mais peut donner une culture générale sur les principes de constructions des tests pour les enseignants). La partie sur les "tests humains" (transparents 73) permet de trouver des principes généraux qu'il est possible de faire passer aux élèves pour éviter les bugs (check-list et inspection) et pour mieux comprendre le fonctionnement des programmes (pas-à-pas surtout, mais aussi relecture par les pairs). Enfin, les transparents 74 à 80 donnent quelques grands principes à mettre en œuvre pour le débuggage.

Ressources pour la classe

Accéder à la vidéo du Collège de France - Gérard Berry : https://www.college-de-france.fr/fr/agenda/lecture/why-and-how-the-world-is-going-digital/la-chasse-aux-bugs-la-verification-des-programmes-et-circuits  
À la chasse aux bugs : la vérification des programmes et circuits. Vérifier les programmes et les circuits. Il n’y a pas de différences ici entre programmes et circuits. Cela pose une intéressante réflexion sur la dichotomie logicielle / matérielle. La vérification c’est 70% des coûts. L’enjeu c’est d’automatiser la vérification des circuits et programmes. Des programmes pour tester d’autres programmes. La difficulté de modéliser l’environnement dans lequel le test est réalisé est signalée.Le conférencier a le souci de toujours relier la théorie de la vérification aux applications industrielles. Sont abordés : les techniques fondamentales de tests et leurs limitations, le problème de l’arrêt. Les preuves de programmes associées aux modèles récursifs et impératifs. Les invariants de boucles sont exploités.

Accéder à la vidéo du Collège de France - Patrick Cousot : https://www.college-de-france.fr/fr/agenda/seminar/why-and-how-the-world-is-going-digital/la-verification-des-programmes-par-interpretation-abstraite  
La vérification des programmes par interprétation abstraite. La présentation de bugs de calcul numérique liés à la représentation des nombres entiers ou flottants est excellente. L’explication suivante sur le principe de fonctionnement des analyseurs statiques est assez théorique. Les résultats des analyseurs statiques utilisés dans l’industrie sont intéressants.

Algorithmes sur les arbres binaires et sur les arbres binaires de recherche

Pour bien démarrer

Accéder au cours à destination des élèves avec des activités non corrigées de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_algo_arbre.html  
Ce document présente sous la forme d’un cours et d’activités les différents algorithmes présents dans le programme de NSI de terminale sur les arbres binaires et les arbres binaires de recherche (calcul de la hauteur d’un arbre, parcours d’un arbre dans l’ordre infixe, préfixe, et suffixe, parcours d’un arbre en largeur d’abord, recherche d’une clé, et insertion d’une clé dans un arbre binaire de recherche).

Accéder au cours à destination des enseignants (polycopié du DIU pages 4 à 11) de Bruno Grenet : https://www.lirmm.fr/~grenet/DIUBloc5/AlgoAvancee.pdf  
Après quelques notions basiques sur les arbres, le vocabulaire et les notions utiles (p. 4), les algorithmes de parcours infixe (p. 5), parcours infixe et suffixe (p. 6), calcul de la hauteur et du nombre de nœuds (p. 6), parcours en largeur (p. 7), recherche d'une clé et insertion d'une clé (p. 9) la recherche du plus court chemin (p. 13 à 15) et la détection de cycles sont introduits (p. 15 à 17). Des exercices (sans correction) sont proposés. Chaque complexité est démontrée.

Ressources pour la classe

Accéder à l'activité débranchée et vidéo associée de Marie Duflot : https://members.loria.fr/MDuflot/files/med/marmottes.html et https://www.youtube.com/watch?v=oqMx1cuw6mo  
Cette ressource présente une activité débranchée : les marmottes au sommeil léger. Les galeries des marmottes sont modélisées par un arbre binaire. On souhaite minimiser le nombre de trajets des marmottes selon leur fréquence de sortie. La laborieuse résolution manuelle permet d’introduire l’algorithme de Huffman qui fournit une solution optimale.

Accéder aux extraits de l’ouvrage collectif dirigé par Gilles Dowek Une introduction à la science informatique pour les enseignants de la discipline en lycée  : https://wiki.inria.fr/wikis/sciencinfolycee/images/7/72/LSICh3.pdf  
Outre une présentation générale de l’algorithmique, on y trouvera à partir de la page 170 divers exercices corrigés et commentés et non corrigés (p 176).

Pour aller plus loin

Accéder aux extraits de l’ouvrage collectif dirigé par Gilles Dowek Une introduction à la science informatique pour les enseignants de la discipline en lycée e : https://wiki.inria.fr/wikis/sciencinfolycee/images/7/72/LSICh3.pdf  
Outre une présentation générale de l’algorithmique, on y trouvera à partir de la page 152, une partie sur les algorithmes classiques sur les arbres, et l'algorithme de parcours en largeur (p. 156), parcours infixe (p. 157), insertion d'un nombre à une feuille (p. 158), ainsi que la recherche dans un arbre binaire de recherche (p. 160). Enfin, des conseils et réflexions sur l’enseignement de l’algorithmique sont développés à partir de la page 177.

Algorithmes sur les graphes

Pour bien démarrer

Accéder au cours à destination des élèves avec des activités non corrigées de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_algo_graphe.html  
Ce document présente sous la forme d’un cours et d’activités les différents algorithmes présents dans le programme de NSI de terminale sur les graphes (parcours en largeur d’abord, parcours en profondeur d’abord, détection de cycles, recherche d’une chaîne et une vidéo sur l’algorithme de Dijkstra).

Accéder au cours à destination des enseignants (polycopié du DIU pages 11 à 17) de Bruno Grenet : https://www.lirmm.fr/~grenet/DIUBloc5/AlgoAvancee.pdf  
Après quelques notions basiques sur les graphes, le vocabulaire et les notions utiles (p. 11 et 12), les algorithmes de parcours en largeur (p. 12 et 13), en profondeur (p. 15 à 17), la recherche du plus court chemin (p. 13 à 15) et la détection de cycles sont introduits (p. 15 à 17). Des exemples simples permettent de comprendre le principe de ces algorithmes et des exercices (sans correction) sont proposés. Chaque complexité est démontrée.

Accéder à la synthèse de cours avec implémentation des algorithmes en langage Python, à destination des enseignants, de Alain Busser : https://alainbusser.frama.io/NSI-IREMI-974/chap2_algo_graphes.html  
L'algorithme du parcours en largeur est abordé au travers d'un exemple illustré et une implémentation en langage Python est donnée. Un programme de parcours en profondeur est proposé, ainsi qu'une version récursive. Pour la cherche d'un chemin entre deux sommets, une implémentation récursive est fournie. Un programme en langage Python pour déterminer certains cycles est proposé.

Accéder au cours d'IUT, à destination des enseignants, de Samba Ndojh Ndiaye : https://perso.liris.cnrs.fr/samba-ndojh.ndiaye/fichiers/App_Graphes.pdf  
Après quelques notions sur les graphes, le vocabulaire et les notions utiles dont certaines hors programme en NSI (p. 1 et 7), les algorithmes de parcours en largeur (p. 9 et 10), en profondeur (p. 11 à 13 et version récursive p. 12), la recherche du plus court chemin (p. 10 et p. 15 à 18) et la détection de cycles sont introduits (p. 12 sans l'algorithme). Chaque complexité est proposée, ainsi que des corrections d'algorithmes. Cette ressource à destination de l'enseignant est particulièrement complète, mais aborde des notions hors programme.

Ressources pour la classe

Accéder aux extraits de l’ouvrage collectif dirigé par Gilles Dowek Une introduction à la science informatique pour les enseignants de la discipline en lycée  : https://wiki.inria.fr/wikis/sciencinfolycee/images/7/72/LSICh3.pdf  
Outre une présentation générale de l’algorithmique, on y trouvera à partir de la page 173 des exercices corrigés et non corrigés (p 176).

Pour aller plus loin

Accéder aux extraits de l’ouvrage collectif dirigé par Gilles Dowek Une introduction à la science informatique pour les enseignants de la discipline en lycée : https://wiki.inria.fr/wikis/sciencinfolycee/images/7/72/LSICh3.pdf  
Outre une présentation générale de l’algorithmique, on y trouvera à partir de la page 161, une partie sur les algorithmes classiques sur les graphes, parcours en largeur (p. 163), parcours en profondeur (p. 167) ainsi que divers exercices corrigés et commentés (à partir de la p 170) et non corrigés (p 176). Enfin, des conseils et réflexions sur l’enseignement de l’algorithmique sont développés à partir de la page 177.

Méthode « diviser pour régner »

Pour bien démarrer

Accéder au cours pour la classe avec des activités non corrigées de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_algo_diviser_pour_regner.html  
Ce document présente sous la forme d’un cours la méthode « diviser pour régner » à partir d’un exemple détaillé d’algorithme utilisant cette méthode (le tri-fusion). Des activités, appelées « à faire vous-même » permettent à l’élève d’appréhender cette méthode.

Ressources pour la classe

Accéder aux diapositives de cours avec deux vidéos d’accompagnement de Bruno Grenet : https://www.lirmm.fr/%7Egrenet/AlgoComplexite/4.DpR.pdf ; https://www.lirmm.fr/%7Egrenet/AlgoComplexite/4.DpR.pdf ; https://video.umontpellier.fr/video/3561-hlin401-chap-4-diviser-pour-regner-calcul-de-rang/ et https://www.lirmm.fr/~grenet/AlgoComplexite/19/TD4.pdf  
Cette ressource contient une introduction de la méthode avec trois exemples : un tri fusion, l'algorithme de multiplication d’entiers de Karatsuba, et le calcul de médiane.

Pour aller plus loin

Accéder au polycopié de cours avec exercices à destination de l’enseignant de Jean-Pierre Becirspahic : https://info-llg.fr/option-mpsi/pdf/08.diviser_pour_regner.pdf  
Cette ressource présente un cours avec des exercices d’un niveau assez élevé, avec des analyses mathématiques.

Programmation dynamique

Pour bien démarrer

Accéder au cours avec des activités non corrigées de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_algo_progdyn.html  
Il présente sous la forme d’un cours l’intérêt de la programmation dynamique, puis l’utilise pour résoudre le problème du rendu de monnaie. Des activités, appelées « à faire vous-même » permettent à l’élève de travailler la programmation dynamique à partir de programmes écrits en Python.

Ressources pour la classe

Accéder au diaporama de cours pour enseignants de Olivier Spanjaard : https://www-desir.lip6.fr/~spanjaard/pmwiki/uploads/ProgrammationDynamique.pdf  
Introduction de la difficulté d’une mise en œuvre récursive sur l’exemple de la suite de Fibonacci. La mémoïsation puis une approche « du bas vers le haut » sont proposées. Le problème de la complexité spatiale et la conception d’algorithmes de programmation dynamique sont évoqués. Le jeu du huit américain, la recherche d’un plus grand carré blanc, l’ordonnancement d’intervalles pondérés ainsi que la distance d’édition, sont des problèmes présentés et résolus.

Accéder au cours à destination des enseignants (polycopié du DIU pages 17 à 30) de Bruno Grenet : https://www.lirmm.fr/~grenet/DIUBloc5/AlgoAvancee.pdf  
À partir de l’exemple du rendu de monnaie, les algorithmes naïfs, la mémoïsation et la programmation dynamique sont introduits. Chaque complexité est proposée et démontrée. Le problème de la mémoire et la conception de tels algorithmes sont présentés en détails. L’alignement de séquences est ensuite étudié en détails. Les problèmes de reconstruction des solutions sont présentés, ainsi que leur contradiction avec l’occupation mémoire.

Recherche textuelle

Pour bien démarrer

Accéder au cours avec des activités non corrigées de David Roche : https://pixees.fr/informatiquelycee/n_site/nsi_term_algo_boyer.html  
Cette ressource présente sous la forme d’un cours le problème de la recherche d’un motif dans un texte (exemple de l’analyse de l’ADN) puis explicite l’algorithme de Boyer-Moore. Un programme écrit en Python est proposé. Quelques activités rapides permettent aux élèves de réfléchir à cet algorithme.

Accéder au cours à destination des enseignants (polycopié du DIU pages 30 à 39) de Bruno Grenet : https://www.lirmm.fr/~grenet/DIUBloc5/AlgoAvancee.pdf  
Après quelques notations sur la recherche de motifs, une recherche naïve est proposée, la règle du mauvais caractère et du bon suffixe et enfin une version simplifiée et l’algorithme de Boyer et Moore. Des exercices (sans correction) sont proposés. Chaque complexité est proposée et démontrée.

Ressources pour la classe

Accéder à l'activité pour la classe de Jean-Stéphane Varre : https://gitlab-fil.univ-lille.fr/jean-stephane.varre/atelier_didapro_boyer_moore  
Étude exhaustive et progressive de l’algorithme de recherche textuelle en quatre activités (activites.pdf). Des documents de travail pour les élèves sont proposés (bandes.pdf). Successivement, l’algorithme naïf, l’algorithme du bon caractère, celui du bon suffixe, le mauvais caractère et enfin l’algorithme complet de Boyer-Moore sont évoqués. Quatre activités très détaillées avec un travail papier qui permet l’appropriation.

Accéder à l'activité pour la classe de Cédric Baubeau, Maxime Charpignon, Franck Duffaud et Gilles Dalles : https://www.math93.com/images/pdf/NSI/terminale/Boyer-Moore/NSI_Recherche_Textuelle.pdf  
Ce document présente des algorithmes naïfs de Horspool et de Boyer-Moore et l’implémentation en Python à faire par les élèves. Des exemples de tables de sauts sont présentés. Dans l’activité, des liens vers des diaporamas d’illustration des algorithmes naïf, de Horspool et de Boyer-Moore sont proposés. L’illustration du gain de temps grâce à des fonctions Python est demandée aux élèves. Des propositions de corrections avec des commentaires sont disponibles à la fin du document.