Programmes et ressources en numérique et sciences informatiques - voie G
Les programmes de numérique et sciences informatiques de première et de terminale de la voie générale sont présentés en lien avec des ressources pour accompagner leur mise en œuvre.
Programme en vigueur
Le programme de spécialité de numérique et sciences informatiques de première générale est défini par arrêté du 17-1-2019 publié au BO spécial n° 1 du 22 janvier 2019.
Le programme de spécialité de numérique et sciences informatiques de terminale générale est défini par arrêté du 19-7-2019 publié au BO spécial n° 8 du 25 juillet 2019.
Le vademecum
L’enseignement des sciences numérique, informatique et technologie est essentiel pour accompagner la transformation numérique de notre société et des pratiques professionnelles actuelles. Le vademecum Sciences numériques et technologie, Numérique et sciences informatiques a vocation à servir cette ambition et s’articule autour de quatre axes :
- Un éclairage sur les enjeux et les objectifs des enseignements de SNT et NSI ;
- Les spécificités des enseignements de SNT et de NSI ;
- Des exemples concrets de scénarios pédagogiques et de projets ;
- L’apport des enseignements de SNT et NSI au parcours des élèves.
Ressources d'accompagnement pour la classe de première
Représentation des données
- p-uplets nommés et dictionnaires
- Types construits en Python
- Types mutables et problèmes associés
- Représentation des entiers naturels
- Représentation des entiers relatifs
Traitement des données
Interactions entre l'homme et la machine sur le Web
Architectures matérielles et systèmes d'exploitation
- Systèmes de type UNIX : structures de données et algorithmes
- Systèmes de type UNIX : le point de vue utilisateur
- Modèle d'architecture de von Neumann
Langages et programmation
Algorithmique
- Algorithme des k plus proches voisins
- Recherche dichotomique
- Algorithmes gloutons
- Le problème du sac à dos
Ressources transversales
Ressources d'accompagnement pour la classe de terminale
Algorithmique
Langages et programmation
- Calculabilité et décidabilité
- Le paradigme fonctionnel
- Modularité et api
- Écriture de tests
- Mise au point des programmes, gestion des bugs
- Vocabulaire de la programmation objet
- Récursivité
Structures de données
- Plus court chemin dans un graphe
- Arbres binaires de recherche
- Implantation des arbres binaires de recherche à l’aide de la pool
- Généralités sur les arbres
- Généralités sur les graphes
- Représentation des graphes
- Types abstraits de données - Présentation
- Types abstraits de données - Implantations et propositions de mise en œuvre
Architectures matérielles, systèmes d’exploitation et réseaux
Sujets d'examen
Sujets zéros de l'épreuve écrite de spécialité NSI (à compter de la session 2024)
Les épreuves écrites de spécialité NSI
Consulter la page éduscol Annales des épreuves du baccalauréat sur laquelle figurent les sujets des épreuves écrites de spécialité NSI.
Les épreuves pratiques de spécialité NSI
Les éléments relatifs à la session 2023 sont disponibles dans la banque nationale de sujets.
Volumes horaires d'enseignement
L'horaire élève pour l'enseignement de spécialité NSI est de 4h en première générale, puis de 6h en terminale générale.
Sitographie pour le programme de Terminale
La sélection de ressources proposée est organisée suivant des thématiques en lien avec le programme.
Pour bien démarrer
Adresse :http://delmas-rigoutsos.nom.fr/documents/YDelmas-histoire_informatique/index.html
Auteur : Yannis Delmas-Rigoutsos
Type de document : Livre en hyper-texte.
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.
///
Adresse :http://www.e-miage.fr/MONE2/section1/pdf/section1_1.pdf
Auteur : Réalisation collégiale
Type de document : fichier 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
Adresse :http://www.math93.com/images/pdf/NSI/terminale/NSI_Classes.pdf
Auteur : Cédric Baubeau, Maxime Charpignon, Franck Duffaud et Gilles Dalles
Type de document : cours et TD.
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.
///
Adresse :http://courspython.com/classes-et-objets.html
Auteur : David Cassagne
Type de document : Cours de programmation Python sur les classes et objets (vocabulaire, principe de la POO, syntaxe Python et exemples).
Pour aller plus loin
Adresses :http://info.blaisepascal.fr/programmation-orientee-objet et http://https://python.doctor/page-apprendre-programmation-orientee-objet-poo-classes-python-cours-debutants
Auteur : C. Faury et Django Internet web
Type de document : cours.
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
Adresse :http://pixees.fr/informatiquelycee/n_site/nsi_term_structDo_liste.html
Auteur : David Roche
Type de document : cours avec des activités non corrigées.
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.
///
Adresse :http://notebooks.azure.com/laurent-cheno/projects/nsi-public /html/Listes.ipynb
Auteur : Laurent Cheno
Type de document : cours.
Le document est à l'intention des élèves et donne la définition d'une liste. Il est directement du niveau des Terminales NSI. Avantage : le document propose à chaque fois deux implémentations (une orientée fonctionnelle, une orientée impérative), et permet de faire le lien avec le thème "paradigme".
///
Adresse :http://pixees.fr/informatiquelycee/n_site/nsi_term_structDo_dico.html
Auteur : David Roche
Type de document : cours sans activité.
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
Adresse :http://isn-icn-ljm.pagesperso-orange.fr/NSI-TLE/co/section_chapitre2.html
Auteur : Stéphan Van Zuijlen
Type de document : cours et exercices.
Ce document présente les structures de données. Il est réutilisable directement pour les cours avec des exercices et des TP pouvant conduire à des mini projets entre autres. Le document propose la création des classes Pile et File qui mettent en pratique la POO.
///
Adresse :http://math.univ-lyon1.fr/irem/Formation_ISN/formation_parcours_graphes/pilefile/file.html
Auteur : Brice Portier et Jean-Manuel Mény, membres du groupe IREM - ISN (académie de Lyon)
Type de document : cours.
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
Adresse :http://forge.univ-lyon1.fr/diu-eil/bloc4/-/tree/master/2_structures_de_donnees
Auteur : Romuald Thion
Type de document : cours avec des TD non corrigés.
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.
///
Adresse :http://blog.lesjeudis.com/structures-de-donnees-courantes-javascript
Auteur : Beau Carnes (freeCodeCamp.org)
Type de document : résumé de cours avec liens vers des exercices.
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
Adresses :http://pixees.fr/informatiquelycee/n_site/nsi_term_structDo_arbre.html et http://pixees.fr/informatiquelycee/n_site/nsi_term_algo_arbre.html
Auteur : David Roche
Type de document : cours avec des activités.
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
Adresse :http://isn-icn-ljm.pagesperso-orange.fr/NSI-TLE/co/section_chapitre3.html
Auteur : Stéphan Van Zuijlen
Type de document : cours et exercices.
Ces documents sont très complets sur les arbres. Ils sont réutilisable directement pour les cours accompagnés d'exercices et de TP.
///
Adresse :http://notebooks.azure.com/laurent-cheno/projects/nsi-public/html/ArbresBinaires.ipynb
Auteur : Laurent Chéno
Type de document : activités.
Ce document présente la construction d'une structure de données pour les arbres binaires d'entiers en utilisant la notion de classe.
Graphes
Pour bien démarrer
Adresses :http://pixees.fr/informatiquelycee/n_site/nsi_term_structDo_graphe.html et http://pixees.fr/informatiquelycee/n_site/nsi_term_algo_graphe.html
Auteur : David Roche
Type de document : cours avec activités.
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
Adresse :http://alainbusser.frama.io/NSI-IREMI-974/chap1_graphes.html
Auteur : Alain Busser
Type de document : cours.
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.
///
Adresse :http://isn-icn-ljm.pagesperso-orange.fr/NSI-TLE/co/section_chapitre4.html
Auteur : Stéphan Van Zuijlen
Type de document : cours et exercices.
Ces documents sont très complets sur les graphes. Ils sont réutilisables directement pour les cours accompagnés d'exercices et de TP.
///
Adresse :http://notebooks.azure.com/laurent-cheno/projects/nsi-public/html/graphes.ipynb
Auteur : Laurent Chéno
Type de document : cours et activités.
Ce document présente la construction des graphes à l'aide des dictionnaires ainsi que plusieurs fonctions de base sur les graphes.
Modèle relationnel
Pour bien démarrer
Adresse :http://mermet.users.greyc.fr/Enseignement/EnseignementInformatiqueLycee/Havre/Bloc4/indexBD.html
Auteur : Bruno Mermet
Type de document : cours du DIU EIL du Havre.
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.
///
Adresse :http://pixees.fr/informatiquelycee/n_site/nsi_term_bd_rela.html
Auteur : David Roche
Type de document : cours/TP avec des activités non corrigées.
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.
///
Adresse :http://isn-icn-ljm.pagesperso-orange.fr/NSI-TLE/co/section_chapitre5.html
Auteur : Stéphan Van Zuijlen
Type de document : cours de terminale NSI avec exercices et projet.
Cours assez complet et suffisamment simple pour être compréhensible par tous, allant jusqu'au développement d'une application Web en PHP. Pour les aspects SQL, trois SGBD différents sont employés (Oracle, SQLite, MySQL).
///
Adresse :http://info.blaisepascal.fr/cpge-bases-de-donnees-relationnelles
Auteur : professeur du lycée Blaise Pascal de Clermont-Ferrand
Type de document : cours de CPGE.
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
Adresse :http://wiki.inria.fr/wikis/sciencinfolycee/images/2/2e/LSICh7.pdf
Auteur : Silo (Science informatique au lycée : oui !) - Wiki de l’INRIA
Type de document : Cours pour enseignant.
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
Adresse :http://forge.univ-lyon1.fr/diu-eil/bloc4/-/tree/master/4_bases_de_donnees_normalisation
Auteur : professeurs de l’université de Lyon
Type de document : Cours de DIU EIL sous la forme d'un dépôt Git avec PDF, vidéos et TP SQL.
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
Adresse :http://https://forge.univ-lyon1.fr/diu-eil/bloc4/-/tree/master/3_bases_de_donnees_introduction
Auteur : professeurs de l’université de Lyon
Type de document : Cours de DIU EIL sous la forme d'un dépôt Git avec PDF, vidéos et TP SQL.
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
Pour bien démarrer
Adresse :http://notebooks.lecluse.fr/nsi/terminale/bases%20de%20données/sql/tp/2020/06/23/nsi_t_SQL.html
Auteur : Olivier Lécluse
Type de document : TP clé en main - document élève.
Ce TP fait directement suite au cours sur le modèle relationnel et en partant de l'exemple du cours, la base de données est construite, table par table, sur un modèle relationnel. Les premières commandes SQL sont vues à l'occasion : INSERT et SELECT simples. Ce TP est complété par deux autres décrits ci-dessous. Le système de base de données choisie est SQLite mais l'accès se fait par Jupyter qui est un outil polyvalent déjà utilisé pour Python. L'aspect base de données sous Python est volontairement laissé de côté sur cette partie. L'élève est guidé et on profite de l'aspect notebook de Jupyter pour donner les explications et les consignes au fil du TP. Des cellules de validation (à base de assert) permettent à l'élève d'avancer en relative autonomie.
///
Adresse :http://nsi4noobs.fr/-Partie-B-Bases-de-donnees-
Auteur : David Latouche et Cédric Gerland
Type de document : cours de terminale NSI avec activités.
Cours complet, avec de nombreuses capsules vidéo et activités associées expliquant les principes du modèle relationnel, des SGBDR, et du SQL (SQLite avec DB Browser et sqlite3 sous Python).
Ressources pour la classe
Adresse :http://deptfod.cnam.fr/bd/tp/
Auteur : CNAM
Type de document : exercices en ligne.
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."
///
Adresses :http://webtic.free.fr/sql/exint/q1.htm et http://info.blaisepascal.fr/wp-content/uploads/2019/01/facturation.sqlite
Auteur : Didier Boulle
Type de document : exercices en ligne.
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
///
Adresse :http://sqlitebrowser.org/dl/
Auteur : sqlitebrowser.org
Type de document : Outil.
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.
///
Adresse :http://addons.mozilla.org/fr/firefox/addon/sqlite-manager-webext/
Auteur : Lunu sur addons.mozilla.org
Type de document : Outil.
Extension pour Firefox apportant des fonctionnalités similaires à SQLiteBrowser.
Pour aller plus loin
Adresse :http://www.w3schools.com/sql/default.asp
Auteur : w3schools.com
Type de document : activités, TP et projets, cours et exercices.
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
Adresse :http://www.lecluse.fr/nsi/NSI_T/archi/soc/
Auteur : Olivier Lécluse
Type de document : cours de terminale NSI.
L’enseignant trouvera dans un premier temps un volet historique allant de la présentation de l’ENIAC à la miniaturisation des puces que nous connaissons aujourd’hui. Le fonctionnement d’un téléphone portable est ensuite pris comme exemple. Tout au long du document, les avantages des SoC en termes de vitesse et de consommation sont mis en avant. Cette ressource est directement exploitable par l’enseignant pour son cours.
///
Adresse :http://pixees.fr/informatiquelycee/n_site/nsi_term_archi_soc.html
Auteur : David Roche
Type de document : cours de terminale NSI.
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
Adresse :http://pixees.fr/informatiquelycee/n_site/nsi_term_archi_proc.html
Auteur : David Roche
Type de document : cours de terminale NSI.
Ce document présente les notions de processus et d'interblocage, accompagnées de petites activités d'application.
///
Adresse :http://www.lecluse.fr/nsi/NSI_T/archi/process/
Auteur : Olivier Lécluse
Type de document : cours de terminale NSI.
Un cours prêt à l'emploi qui aborde les notions d'arborescence, de gestion de processus, d'ordonnancement et d'interblocage.
Ressources pour la classe
Adresse :http://classic.csunplugged.org/wp-content/uploads/2014/12/10_fr_Acheminement_et_blocage.pdf
Auteur : Computer Science Unplugged
Type de document : TP.
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
Adresses :http://pixees.fr/informatiquelycee/n_site/nsi_term_archi_routage.html et http://pixees.fr/informatiquelycee/n_site/nsi_term_structDo_graphe.html et http://pixees.fr/informatiquelycee/n_site/nsi_term_algo_graphe.html
Auteur : David Roche
Type de document : Type de document : cours de terminale NSI.
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
Adresse :http://www.youtube.com/watch?v=e3I4opl8EH4&list=PLjXls-kqM6JDyMO3Llm5olS_U2I_P6OHG
Auteur : Institut Mines-Télécom
Type de document : TP.
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
Adresse :http://idum.fr/spip.php?article213
Auteur : N. Salmon
Type de document : cours.
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
Adresse :http://pixees.fr/informatiquelycee/n_site/nsi_term_archi_secu.html
Auteur : David Roche
Type de document : cours de terminale NSI.
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
Adresse :http://www.youtube.com/watch?v=jMIAoAVbcsw&list=PLYsJ-3MUn_eeYwSgJ3Z_hfrIzGqYOGAaj
Auteur : Yann Bidon
Type de document : vidéo.
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
Adresse :http://pixees.fr/informatiquelycee/n_site/nsi_term_calcu.html
Auteur : David Roche
Type de document : cours d'introduction.
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.
///
Adresse :http://www.irem.univ-bpclermont.fr/Indecidabilite-du-probleme-de-l
Auteur : Matthieu Journault, Pascal Lafourcade, Rémy Poulain, et Malika More
Type de document : activité de type "informatique sans ordinateur".
Comment montrer, sans formalisme théorique, que le problème de l’arrêt est indécidable ? L’activité suit la preuve proposée par Turing, et s'appuie sur le principe du raisonnement par l’absurde et la notion de disjonction de cas. Tout au long de l’activité, les élèves se servent d’une version papier d’un modèle simplifié d’ordinateur pour exécuter à la main des programmes. Certains programmes simples sont ensuite composés ensemble pour obtenir le résultat d’indécidabilité. L'article présente également des retours d'expérience suite à la réalisation de l'activité avec des élèves ou des enseignants en formation continue.
Pour aller plus loin
Adresse :http://www.lirmm.fr/%7Egrenet/DIUBloc5/AlgoAvancee.pdf
Auteur : Bruno Grenet
Type de document : cours de DIU (fichier 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
Adresse :http://www.enib.fr/enibook/algorithmic/learning/site/html/recursivite-0-index.html
Auteur : ENIB (École nationale d’ingénieurs de Brest)
Type de document : cours et exercices.
Cours très clair et bien détaillé, avec de nombreux exemples et exercices.
///
Adresse :http://www.lri.fr/%7Ehivert/COURS/CFA-L3/02-Recursivite.pdf
Auteur : Florent Hivert
Type de document : cours au format 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
Adresse :http://www.apprendre-en-ligne.net/info/recursivite/recursivite.pdf
Auteur : Didier Müller
Type de document : cours et exercices au format PDF.
Support mélangeant à bon escient activités en modes branché et débranché, avec des applications mathématiques et récréatives.
///
Adresse :http://projet.eu.org/pedago/sin/NSI/cours02/chap3.zip
Auteur : Didier Müller
Type de document : cours et exercices (archive 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".
Modularité
Pour bien démarrer
Adresse :http://nsi4noobs.fr/-Partie-D-Langages-et-programmation-
Auteur : David Latouche et Cédric Gerland
Type de document : cours et activités.
Avec comme fil rouge la réalisation d'une API d'analyse d'un fichier GPX permettant à partir d'un site web (Open Street Map) de cartographier des déplacements, les élèves découvrent au travers de capsules vidéos et d'activités associées, l'utilisation de l'API lxml.etree (gestion fichier GPX) et de la bibliothèque Folium.
Paradigmes de programmation
Pour bien démarrer
Adresse :http://forge.univ-lyon1.fr/diu-eil/bloc4/-/tree/master/1_paradigmes_de_programmation
Auteur : professeurs de l'université de Lyon
Type de document : cours de DIU EIL.
Cours complet avec dépôt Git du documents au format PDF et de TP en Python.
///
Auteur : Bruno Mermet
Type de document : cours de DIU EIL du Havre.
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
Adresse :http://repl.it/
Auteur : repl.it
Type de document : outil.
Un interpréteur en ligne pour de nombreux langages. Très pratique pour faire découvrir certains langages sans aucune installation.
///
Adresse :http://swish.swi-prolog.org/
Auteur : swish
Type de document : outil.
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
Adresse :http://mermet.users.greyc.fr/Enseignement/CoursPDF/coursTestL3.pdf
Auteur : Bruno Mermet
Type de document : cours de Licence 3 Informatique.
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 oeuvre pour le débuggage.
Ressources pour la classe
Adresse :http://www.college-de-france.fr/site/gerard-berry/course-2008-02-22-10h30.htm
Auteur : Gérard Berry
Type de document : vidéo du Collège de France.
À 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.
///
Adresse :http://www.college-de-france.fr/site/gerard-berry/seminar-2008-02-22-11h30.htm
Auteur : Patrick Cousot
Type de document : vidéo du Collège de France.
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
Adresse :http://pixees.fr/informatiquelycee/n_site/nsi_term_algo_arbre.html
Auteur : David Roche
Type de document : cours à destination des élèves avec des activités non corrigées
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).
///
Adresse :http://www.lirmm.fr/~grenet/DIUBloc5/AlgoAvancee.pdf
Auteur : Bruno Grenet
Type de document : cours à destination des enseignants (polycopié du DIU pages 4 à 11).
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
Adresses :http://members.loria.fr/MDuflot/files/med/marmottes.html et http://www.youtube.com/watch?v=oqMx1cuw6mo
Auteur : Marie Duflot
Type de document : activité débranchée et vidéo associée
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.
///
Adresse :http://wiki.inria.fr/wikis/sciencinfolycee/images/7/72/LSICh3.pdf
Auteur : sous la direction de Gilles Dowek
Type de document : extraits de l’ouvrage collectif dirigé par Gilles Dowek : Une introduction à la science informatique pour les enseignants de la discipline en lycée
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
Adresse :http://wiki.inria.fr/wikis/sciencinfolycee/images/7/72/LSICh3.pdf
Auteur : sous la direction de Gilles Dowek
Type de document : extraits de l’ouvrage collectif dirigé par Gilles Dowek Une introduction à la science informatique pour les enseignants de la discipline en lycée
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
Adresse :http://pixees.fr/informatiquelycee/n_site/nsi_term_algo_graphe.html
Auteur : David Roche
Type de document : cours à destination des élèves avec des activités non corrigées
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).
///
Adresse :http://www.lirmm.fr/~grenet/DIUBloc5/AlgoAvancee.pdf
Auteur : Bruno Grenet
Type de document : cours à destination des enseignants (polycopié du DIU pages 11 à 17)
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.
///
Adresse :http://alainbusser.frama.io/NSI-IREMI-974/chap2_algo_graphes.html
Auteur : Alain Busser
Type de document : synthèse de cours avec implémentation des algorithmes en langage Python, à destination des enseignants.
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é.
///
Adresse :http://perso.liris.cnrs.fr/samba-ndojh.ndiaye/fichiers/App_Graphes.pdf
Auteur : Samba Ndojh Ndiaye
Type de document : cours d'IUT, à destination des enseignants
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
Adresse :http://wiki.inria.fr/wikis/sciencinfolycee/images/7/72/LSICh3.pdf
Auteur : sous la direction de Gilles Dowek
Type de document : extraits de l’ouvrage collectif dirigé par Gilles Dowek Une introduction à la science informatique pour les enseignants de la discipline en lycée
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
Adresse :http://wiki.inria.fr/wikis/sciencinfolycee/images/7/72/LSICh3.pdf
Auteur : sous la direction de Gilles Dowek
Type de document : extraits de l’ouvrage collectif dirigé par Gilles Dowek Une introduction à la science informatique pour les enseignants de la discipline en lycée
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
Adresse :http://pixees.fr/informatiquelycee/n_site/nsi_term_algo_diviser_pour_regner.html
Auteur : David Roche
Type de document : cours pour la classe avec des activités non corrigées.
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
Adresses :http://www.lirmm.fr/%7Egrenet/AlgoComplexite/4.DpR.pdf et http://https://video.umontpellier.fr/video/3546-hlin401-chap-4-diviser-pour-regner-multiplication-dentiers/
Auteur : Bruno Grenet
Type de document : (1) diapositives de cours avec deux vidéos d’accompagnement.
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.
///
Adresses :http://www.lirmm.fr/%7Egrenet/AlgoComplexite/4.DpR.pdf et http://video.umontpellier.fr/video/3561-hlin401-chap-4-diviser-pour-regner-calcul-de-rang/ et http://www.lirmm.fr/~grenet/AlgoComplexite/19/TD4.pdf
Auteur : Bruno Grenet
Type de document : (2) diapositives de cours avec deux vidéos d’accompagnement.
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
Adresse :http://info-llg.fr/option-mpsi/pdf/08.diviser_pour_regner.pdf
Auteur : Jean-Pierre Becirspahic
Type de document : polycopié de cours avec exercices à destination de l’enseignant.
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
Adresse :http://pixees.fr/informatiquelycee/n_site/nsi_term_algo_progdyn.html
Auteur : David Roche
Type de document : cours avec des activités non corrigées.
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
Adresse :http://www-desir.lip6.fr/~spanjaard/pmwiki/uploads/ProgrammationDynamique.pdf
Auteur : Olivier Spanjaard
Type de document : diaporama de cours pour enseignants.
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.
///
Adresse :http://www.lirmm.fr/~grenet/DIUBloc5/AlgoAvancee.pdf
Auteur : Bruno Grenet
Type de document : Cours à destination des enseignants (polycopié du DIU pages 17 à 30).
À 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
Adresse :http://pixees.fr/informatiquelycee/n_site/nsi_term_algo_boyer.html
Auteur : David Roche
Type de document : cours avec des activités non corrigées.
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.
///
Adresse :http://www.lirmm.fr/~grenet/DIUBloc5/AlgoAvancee.pdf
Auteur : Bruno Grenet
Type de document : cours à destination des enseignants (polycopié du DIU pages 30 à 39).
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
Adresse :http://gitlab-fil.univ-lille.fr/jean-stephane.varre/atelier_didapro_boyer_moore
Auteur : Jean-Stéphane Varre
Type de document : activité pour la classe.
É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.
///
Adresse :http://www.math93.com/images/pdf/NSI/terminale/Boyer-Moore/NSI_Recherche_Textuelle.pdf
Auteur : Cédric Baubeau, Maxime Charpignon, Franck Duffaud et Gilles Dalles
Type de document : activité pour la classe.
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.
Exploitation de vidéos en support de cours
Ressources pour la classe
Adresse :http://media.eduscol.education.fr/file/NSI/46/0/Sitographie-Videos_1313460.pdf
Auteur : Patrick Guérangé
Type de document : Ces vidéos peuvent servir de support pour une activité en classe.