TD1 - Exercices en lien avec le cours

Table des matières

Introduction au TD

Ce TD a pour objectif d’accompagner le cours d’algorithmique en permettant de mettre en pratique immédiatement les notions vues en cours.

L’algorithmique repose sur des concepts parfois abstraits (finitude, efficacité, complexité, correction), qui ne prennent réellement sens qu’à travers des exemples concrets et des manipulations pas à pas.

Les exercices proposés dans ce TD visent donc à :

  • mieux comprendre le fonctionnement d’un algorithme en le déroulant étape par étape ;
  • identifier les entrées, les sorties et les opérations effectuées ;
  • distinguer les notions de meilleur cas, pire cas et ordre de grandeur ;
  • réfléchir à la terminaison et à la correction d’un algorithme sans formalisme excessif.

Ce TD ne contient aucune notion nouvelle : il s’appuie uniquement sur le cours et sert de support pour consolider les bases nécessaires à la suite de l’analyse algorithmique.

Reconnaître un algorithme

Exercice 1

Pour chacune des situations proposées, expliquer pourquoi elles désignent ou non un algorithme.

  1. Une recette de cuisine.
  2. Réfléchir jusqu'à avoir une bonne idée
  3. Un programme qui affiche les nombres de $1$ à $10$.
  4. Un programme qui affiche les nombres tant que l'utilisateur n'appuie pas sur stop.

Définir les entrées sorties

Exercice 2

Pour chacun des algorithmes ci-dessous identifier et détailler les entrées sorties possible.

  1. Algorithme qui calcule la somme de deux entiers.
  2. Algorithme qui cherche le minimum dans un tableau.
  3. Algorithme qui dit si un nombre est pair.
  4. Algorithme de recherche dichotomique.

Construction d'un algorithme et étude

Exercice 3
  1. Donner l'algorithme permettant de récupérer l'élément minimum d'un tableau.
  2. Étudier et expliquer le fonctionnement de l'algorithme
  3. Combien es-ce qu'on compte de comparaisons ? d'affectations ?
  4. Pour le cas T = {7, 3, 9, 2, 5}
  5. Dans quels cas on se trouve ? justifier.
  6. Donner un tableau possible dans le meilleur cas
  7. Donner un tableau possible dans le pire cas
  8. Le nombre de comparaisons effectués dépend-il du nombre d'éléments dans le tableau ?

Boucle et contrôles

Exercice 4

Soit l'algorithme suivant :

for i de 1 à N
    afficher(i)
  1. Combien de fois la condition $i \leq n$ est-elle testée ?
  2. Combien de fois l'instruction afficher(i) est-elle exécutée ?
  3. Que devient ce nombre lorsque $n=1$ ?
Retour