Skip to content

Sommaire du Bloc 3 ALGO

Objectif : Algorithmique : exemples, fondamentaux, correction et complexité

L'algorithmique est l'une des quatre facettes de la discipline informatique. Elle a pour objectif de fournir des méthodes et des outils d'analyse permettant de résoudre des problème de traitement de l'information. Elle forme une part importante des programmes de première et terminale, en lien avec les autres domaines de l'informatique. Par suite elle est fortement représentée dans les différents sujets d'écrit et d'oral, proposé au Capes NSI. Le contenu du bloc 3 couvrira l'essentiel des programmes de première et terminale, mais nécessitera des approfondissements pour atteindre le niveau requis au Capes (niveau licence, des références seront fournies).

En algorithmique on distingue deux types d'activités :

  • l' analyse d'algorithme qui permet d'établir les propriétés vérifiées par un algorithme. Partant des spécifications du problème et d'une proposition d'algorithme on vérifiera que l'algorithme est correct (il fournit bien les réponses attendues) et on évaluera son coût en nombre d'opérations effectuées pour exécuter l'algorithme sur des données d'entrées.
  • la conception d'algorithme qui consiste, à partir de la spécification d'un problème de traitement de l'nformation, à proposer un ou plusieurs algorithmes et les structures de données adaptées permettant la résolution du problème. Ces algorithmes doivent être "opérationnels" c'est-à-dire que l'on peut les "traduire" facilement dans un langage de programmation.

Dans la première partie du bloc sont expliqués les outils fondamentaux d'analyse en lien avec des problèmes classiques (cf programme de première et Terminale). L'analyse d'algorithme sera appliquée aux algorithmes de tris classiques (schémas itératifs, preuves et complexité). Dans un deuxième temps on aborde un concept fondamental en informatique, le concept d'arbre, qui sera appliqué avec les arbres binaires de recherche. Dans un troisième temps on développera le principe d'algorithme glouton que l'on appliquera aux arbres de codage pour la compression de données.

La deuxième partie du bloc abordera des concepts plus avancés, également au programme de NSI, mais qui met l'accent sur le paradigme diviser pour régner, la compréhension fine de la récursivité et des applications sur des problèmes de graphe. Enfin, pour l'ouverture, la notion de calculabilité sera évoquée ainsi que des notions sur les classes de complexité.

Quelques liens vers les textes officiels :
Le programme officiel de première
Le programme officiel de terminale

Temps d'investissement :

  • 20h à 30 h

Note

ici nous changeons de décors nous abandonnons le clavier en quelques sortes et nous prenons un papier et un crayon pour suivre un vrai cours académique sur la partie la plus théorique de cet enseignement, imaginez que l'enseignant -Jean-Marc- est venu chez vous et commence à vous raconter cette grande histoire ...

Attention : Jean-Marc relève un double défi ici, d'une part il fournit les bases dont vous avez besoin pour être à niveau sur le sujet et au-delà préparer le CAPES. Il a aussi formulé les choses de manière à ce que cela corresponde à ce que vous-même allez transmettre à vos élèves en première et en terminale. Simple exercice de restitution ? Non ! Bien entendu, dans le MOOC2 vous verrez que nous travaillerons ensemble sur la manière de transmettre. En choisissant - entre adultes - un mode cathédrale (présentation sous forme de cours), Jean-Marc nous fait gagner du temps pour absorber tous les savoirs, illustrés par beaucoup d'exemples réutilisables.

L'algorithmique alors c'est des maths ou de l'informatique ? En un sens c'est plus que des mathématiques parce que c'est une science formelle mais dont l'objet final est une machine comme on le verra dans le bloc 4, mais ce n'est pas cloisonné et c'est ici que nous réutiliserons le plus de notions communes aux mathématiques appliquées.