DIU "Enseigner l'informatique au lycée" - UE 2 : Algorithmique

Présentation

Cette UE regroupe l'étude des algorithmes fondamentaux, leur preuve de correction et de terminaison. Il est fondamental pour l'enseignant, autant pour transmettre une partie de ces connaissances et méthodes que pour assurer sa pratique professionnelle en lui permettant de valider les corrigés proposés aux élèves, et d'analyser leurs productions avec le recul nécessaire.

Pré-requis

Étant donné l'aspect théorique de ce bloc, seule une connaissance générale des algorithmes classiques – algorithmes de tri, recherche par dichotomie – est supposée (voir l'UE 1 et le manuel d'ISN). Pour les TD/TP, vous aurez juste besoin d'un éditeur Python installé sur votre machine (ex. IDLE, Pyzo, PyCharm, Jupyter, ...) ainsi que les modules classiquement utilisés (matplotlib, numpy etc.).

Contenu de l'UE

  • 1. Algorithmes classiques
    • Algorithmes gloutons (sac à dos, rendu de monnaie)
    • Algorithmes de type diviser pour régner
    • Algorithme des k plus proches voisins
  • 2. Correction des algorithmes
    • Prédicats et invariants
    • Preuve de correction partielle
    • Preuve de terminaison
  • 3. Complexité des algorithmes
    • Notion de complexité
    • Complexité en temps
    • Complexité en mémoire

Adéquation avec le programme de NSI

La partie du programme de NSI liée à cette UE s’appelle “Algorithmique” dont voici la description : Le concept de méthode algorithmique est introduit ; de nouveaux exemples seront vus en terminale. Quelques algorithmes classiques sont étudiés. L’étude de leurs coûts respectifs prend tout son sens dans le cas de données nombreuses, qui peuvent être préférentiellement des données ouvertes. Il est nécessaire de montrer l’intérêt de prouver la correction d’un algorithme pour lequel on dispose d’une spécification précise, notamment en mobilisant la notion d’invariant sur des exemples simples. La nécessité de prouver la terminaison d’un programme est mise en évidence dès qu’on utilise une boucle non bornée (ou, en terminale, des fonctions récursives) grâce à la mobilisation de la notion de variant sur des exemples simples.

Contenus Capacités attendues Commentaires
Parcours séquentiel d’un tableau Écrire un algorithme de recherche d’une occurrence sur des valeurs de type quelconque. Écrire un algorithme de recherche d’un extremum, de calcul d’une moyenne. On montre que le coût est linéaire.
Tris par insertion, par sélection Écrire un algorithme de tri. Décrire un invariant de boucle qui prouve la correction des tris par insertion, par sélection. La terminaison de ces algorithmes est à justifier. On montre que leur coût est quadratique dans le pire cas.
Algorithme des k plus proches voisins Écrire un algorithme qui prédit la classe d’un élément en fonction de la classe majoritaire de ses k plus proches voisins. Il s’agit d’un exemple d’algorithme d’apprentissage.
Recherche dichotomique dans un tableau trié Montrer la terminaison de la recherche dichotomique à l’aide d’un variant de boucle. Des assertions peuvent être utilisées. La preuve de la correction peut être présentée par le professeur.
Algorithmes gloutons Résoudre un problème grâce à un algorithme glouton. Exemples : problèmes du sac à dos ou du rendu de monnaie. Les algorithmes gloutons constituent une méthode algorithmique parmi d’autres qui seront vues en terminale.

Modalités de contrôle des connaissances

L'UE est évaluée comme suit, où TP est la note obtenue au TP du jeudi 20/06 matin, EXAM est la note obtenue à l'examen final, FOAD est la note obtenue à l'évaluation du travail à distance:

DIU-EIL-UE2 = (3 * TP + 4 * EXAM + 3 * FOAD) / 10

Pour rappel, la validation du DIU se fait par UE sans compensation, le DIU étant validé si et seulement si l'ensemble des UE est validé.

Emploi du temps


Les jours de formation de cette UE sont : 20/04, 21/04, 23/04, 24/04 (matin), 30/04 (après-midi). En raison du confinement, toutes les séances ont lieu à distance, sur un serveur BigBlueButton hébergé à l'ENS Lyon. Pour vous y connectez, rendez-vous à l'adresse : https://ent-services.ens-lyon.fr/entVisio/index.php, choisissez "DIU EIL" dans "Meeting", indiquez votre nom dans "Nom d'utilisateur" et entrez le mot de passe qui vous été envoyé par email le 13/04.

LUNDI
20/04		 MARDI
21/04		 JEUDI
23/04		 VENDREDI
24/04		 JEUDI
30/04

10h
  CM chap.3
12h
  TD chap. 3
13h

 10h
  cours-TD chap. 1
13h		 10h
  TP chap. 1 maison
13h		 10h
  TD-TP chap. 2
13h		  
         
14h
  TD chap. 3
15h
  TP chap. 3
17h		 14h
  cours-TD chap. 1
15h
  TP chap. 1
17h		 14h
  CM chap. 2
15h30
  TD chap. 2
17h		   13h
  Devoir maison
17h

Ressources

Transparents de cours


Exercices de TD


Exercices de TP


Travail à distance


Examen/Devoir maison


Autres