Skip to content

Présentation du module

Objectifs

L'objectif du module 1 d'algorithmique est d'introduire les différents concepts de base pour l'analyse et la conception d'algorithmes. On y aborde les notions d'expression d'algorithme, de preuve et de complexité. Les algorithmes étudiés reposent dans une première partie sur le concept de séquence et dans la deuxième partie sur la structure d'arbre avec 2 applications (les arbres binaires de recherche et le codage).

  • Attention, toutes les notions vues sont au programme de 1ère et de Terminale et servent de base élémentaire pour la préparation au concours du Capes.

  • Le cours nécessite une mise en oeuvre, programmation Python, qui ne fait pas directement l'objet d'activités du cours mais se retrouvent dans le bloc de programmation.

Prérequis

Les bases de programmation (types de base, itérations, conditionnelles, fonctions,...) le cours peut se faire en même temps que l'apprentissage de la programmation.

Sommaire

3-1 Présentation du module

3-1-1 Introduction au concept d'algorithme

  • 3-1-1-1 Algorithme, vie courante, première approche ¼
  • 3-1-1-2 La conception d'un algorithme 2/4
  • 3-1-1-3 L'expression d'un algorithme ¾
  • 3-1-1-4 Algorithmique positionnement et références 4/4

3-1-2 Analyse d'algorithme

  • 3-1-2-1 Analyse d'algorithme
  • 3-1-2-2 Complexité d'un algorithme : calcul de la complexité
  • 3-1-2-3 Complexité d'un algorithme : ordres de grandeur
  • 3-1-2-4 Preuve d'algorithme

3-1-3 Le problème du tri

  • 3-1-3-1 Présentation
  • 3-1-3-2 Recherche d'un élément, recherche dichotomique (itératif récursif, (diviser pour régner)
  • 3-1-3-3 Le problème du tri : contraintes, propriétés attendues
  • 3-1-3-4 Le tri par sélection (preuve, complexité)
  • 3-1-3-5 Le tri par insertion (preuve, complexité)
  • 3-1-3-6 Autres tris (bulle,...)

3-1-4 Arbres

  • 3-1-4-1 Introduction à la séquence 1/10
  • 3-1-4-2 Types abstraits en algorithmique 2/10
  • 3-1-4-3 Pourquoi, pour qui ? 3/10
  • 3-1-4-4 La pile 4/10
  • 3-1-4-5 La file 5/10
  • 3-1-4-6 Arbres - définition, propriétés, comptage part1 6/10
  • 3-1-4-7 Arbres - définition, propriétés, comptage part2 7/10
  • 3-1-4-8 Arbres binaires 8/10
  • 3-1-4-9 Parcours d'arbre 9/10
  • 3-1-4-10 Feuilles étiquetées 10/10

3-1-5 Arbres binaires de recherche

  • 3-1-5-1 Motivation et méthodologie
  • 3-1-5-2 Principe,rechercher dans un ABR
  • 3-1-5-3 Autres opérations part1
  • 3-1-5-4 Autres opérations part2

3-1-6 Algorithmes gloutons

  • 3-1-6-1 Problème d'optimisation
  • 3-1-6-2 Allocation
  • 3-1-6-3 Preuve d'algorithme
  • 3-1-6-4 Problème des choix d'activité
  • 3-1-6-5 Résumé

3-1-7 Arbres et codage

  • 3-1-7-1 Introduction
  • 3-1-7-2 Transmission de l'information
  • 3-1-7-3 Codage
  • 3-1-7-4 Un codage optimal

Temps d'apprentissage

  • 25 heures environ + du travail personnel en fonction des objectifs de l'apprenant Ce temps est donné à titre indicatif. Il peut varier en fonction des participants.

Présentation enseignant

Jean-Marc Vincent

enseignant-chercheur au LIG, Laboratoire d'Informatique de Grenoble, Université Grenoble-Alpes et membre de l'équipe de recherche Inria/LIG Polaris