TD2 - Conception et étude d'algorithmes

Table des matières

Introduction au TD

L’objectif de ce TD est de mettre en pratique la création d’algorithmes et d’apprendre à les analyser de manière simple, en s’appuyant sur les notions de TD1 : entrées/sorties, boucles, opérations, meilleur/pire cas.

On ne parle pas encore de récursivité avancée ou de complexité asymptotique formelle, mais plutôt de raisonnement étape par étape et logique de programme “propre”.

Description, construction et analyse

Exercice 1

On veut créer un algorithme qui compte combien de fois un nombre apparaît dans un tableau.

  1. Identifier l’entrée et la sortie de l’algorithme.
  2. Écrire une description pas à pas en français, en utilisant des phrases simples (ex : “pour chaque élément du tableau, comparer avec le nombre cherché…”).
  3. Construire l'algorithme
  4. Soit le tableau T = {3, 5, 3, 2, 1, 3}, on souhaite compter le nombre d'occurence du nombre $3$.
  5. Faire un tableau étape par étape pour chaque itérations :
  6. Valeur courante de l'élément
  7. Comparaison avec l'élément recherché
  8. Valeur du compteur
  9. Quel est le résultat final ?

Étude d'un algorithme

Exercice 2

Pour l’algorithme du maximum :

  1. Donner l'algorithme
  2. Identifier :
  3. Nombre d’affectations dans le meilleur cas.
  4. Nombre d’affectations dans le pire cas.
  5. Nombre de contrôles (tests de boucle) pour un tableau de taille N.
  6. Vérifier que l’algorithme renvoie bien un résultat pour toutes les entrées.
  7. Donner la complexité de l'algorithme.
Retour