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).

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 écrit du 04/07, 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)

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

9h45
  CM chap.3
11h15
  TD chap. 3
13h

9h45
  cours-TD chap. 1
13h
9h45
  TP chap. 1
13h
9h45
  TD-TP chap. 2
13h
 
         
14h
  TD chap. 3
15h30
  TP chap. 3
17h
14h
  cours-TD chap. 1
15h30
  TP chap. 1
17h
14h
  CM chap. 2
15h30
  TD chap. 2
17h
  13h
  Examen
15h
  Restitution FOAD
17h

Ressources

Transparents de cours


Exercices de TD

  • Complexité des algorithmes-TD (lundi 17/06 matin et après-midi) : énoncé
  • Exercices supplémentaires au TD complexité des algorithmes : énoncé
  • Algorithmes gloutons-TD (mardi 18/06 matin) : énoncé
  • Algorithmes de type diviser pour régner-TD (mardi 18/06 après-midi) : énoncé
  • Correction et terminaison des algorithmes-TD (jeudi 20/06 après-midi) : énoncé
  • Activités débranchées autour des notions d'algorithmes, de correction et de complexité (vendredi 21/06 matin)

Exercices de TP


Travail à distance


Examen


Autres