Analyser des algorithmes

Durée estimée: 90 minutes

Présentation

Expérimentation des algorithmes de recherche et de tri.
Dans cette leçon, nous allons utiliser App Inventor pour expérimenter et analyser les algorithmes de recherche et de tri que nous venons d'étudier. Vous allez faire tourner deux applications différentes, une pour évaluer les algorithmes de recherche et l'autre pour les algorithmes de tri.

Cette activité est une forme d'investigation scientifique.
Vous allez faire tourner les applications sur différentes listes de données, enregistrer les temps d'exécution, mettre ces temps dans un tableau et analyser les résultats. Saurez-vous - suite à cette analyse - reconnaitre l'algorithme utilisé à chaque fois ?

Une autre manière d'envisager cette activité, c'est celle de l'assurance qualité (AQ). Beaucoup de carrières en informatique commencent dans les métiers du contrôle ou de l'assurance qualité. C'est là que vous aidez les développeurs à tester et debugger leurs applications.

Objectifs: Dans cette leçon, nous allons apprendre à
  • conduire une investigation expérimentale des algorithmes élémentaires de recherche et de tri;
  • raisonner de façon analytique sur ces algorithmes;
  • approfondir la compréhension de ces algorithmes.

Introduction

Dans cette leçon, nous allons continuer à étudier les algorithmes, et traiter les questions suivantes.

  • Qu'est-ce que l''analyse d'un algorithme ?
  • Quels sont les principales catégories d'algorithmes du point de vue du temps calcul ?

Analyser les algorithmes de recherche

(slides)

Expérimentation et analyse des algorithmes de recherche

Analyse empirique d'un outil de recherche
Dans cette activité, nous allons utiliser une application App Inventor pour analyser les algorithles de recherche dichotomiques et séquentiels.
  1. Créez dans votre portfolio une page nommée Expé algos de recherche.
  2. Avec l''appli 'App Inventor Companion' ou avec une application permettant de scanner les Barcode, téléchargez http://onvaessayer.org/mobileCSP/ressources/searchAndSort/SortExperiment_FR.aia 'Search Experiment app (APK)' avec ce QR code:
    Si vous utilisez l'émulateur, vous pouvez télécharger ce fichier aia pour l'importer ensuite dans App Inventor. NOTE: Quand vous lancez cette application, il est possible que l'application affaiche au départ un écran blanc, le temps d'initialiser des données. Ca peut prendre une minute. Soyez patient.
  3. Vous allez conduire une analyse des algorithmes pour le pire des cas. Il correspond en l'occurrence à chercher un nombre qui n'est pas dans la liste.
  4. Testez chacun des algorithmes de recherche sur des listes de 1000, 2000, ...jusqu'à 10,000 nombres.
    NOTE: Comme ces algorithmes contiennent des boucles, vous verrez peut-être en popup des messages de type "l'application ne répond pas" qui vous proposent d'attendre ou d'arrêter l'application. Choisissez "attendre".
  5. Créez un tableau dans votre portfolio et écrivez le temps de recherche en millisecondes (ms) pour chaque cas testé.
    Vous devriez en avoir 20 au total, 10 pour chaque algorithme.
  6. Utilisez ce papier quadrillé (ou un tableur) pour enregistrer vos essais et les représenter graphiquement.
    Prenez une photo de votre graphique et joignez le à votre portfolio.
  7. Analysez vos résultats pour déterminer quel algorithme correspond à quel graphique : lequel correspond à l'algorithme de recherche dichotomique et lequel au séquentiel. Donnez une description claire, en référence à votre graphique et à vos données tabulaires, pour expliquer comment vous êtes arrivés à votre conclusion.

Expérimentation et analyse des algorithmes de tri

(slides)

Expérimentation et analyse des algorithmes de tri

Expérimentation et analyse des algorithmes de tri. Dans cette activité, vous allez utiliser App Inventor pour expérimenter et analyser les amggorithmes de tri à bulle, par fusion et par paquets.
  1. Créez dans votre portfolio une page nommée Expé algos de tri.
  2. Avec l''appli 'App Inventor Companion' ou avec une application permettant de scanner les Barcode, téléchargez SortExperiment app (APK) avec ce QR code:
    Si vous utilisez l'émulateur, vous pouvez télécharger ce fichier aia pour l'importer ensuite dans App Inventor.
  3. Testez chaque algorithme de tri sur des listes de 10, 20, ... jusqu#39;à 100 nombres.
    NOTE: Comme ces algorithmes contiennent des boucles, vous verrez peut-être en popup des messages de type "l'application ne répond pas" qui vous proposent d'attendre ou d'arrêter l'application. Choisissez "attendre".
  4. Créez un tableau dans votre portfolio et écrivez le temps de recherche en millisecondes (ms) pour chaque cas testé.
    Vous devriez en avoir 30 au total, 10 pour chaque algorithme.
  5. Utilisez ce papier quadrillé (ou un tableur) pour enregistrer vos essais et les représenter graphiquement.
    Prenez une photo de votre graphique et joignez le à votre portfolio.
  6. Analysez vos résultats pour déterminer quel algorithme correspond à quel graphique : lequel correspond à l'algorithme de tri à bulle, lequel au tri par fusion et lequel au tri par paquets. Donnez une description claire, en référence à votre graphique et à vos données tabulaires, pour expliquer comment vous êtes arrivés à votre conclusion.

Auto-contrôle

Not yet started
1 point
Pour une liste de 500 nombres, quel est le nombre maximal de tentative nécessaire pour deviner un nombre secret avec un algorithme par dichotomie (à condtions que l'on vous réponde à chaque fois si le nombre proposé est plus grand, plus petit ou égal au nombre à deviner) ?
Entrez votre réponse dans la case.
Not yet started
1 point
Selon la table suivante, combien de tentatives (lookups) seraient nécessaires dans le pire des cas, pour trouver un nombre dans une liste de 10000 éléments avec l'algorithme de recherche séquentielle ?
Entrez votre réponse dans la case.


Not yet started
1 point
Selon la table suivante, combien de tentatives (lookups) seraient nécessaires dans le pire des cas, pour trouver un nombre dans une liste de 10000 éléments avec l'algorithme de recherche dichotomique ?
Entrez votre réponse dans la case.

Not yet started
1 point
La fonction illustrée dans ce graphique s'appelle le logarithme à base 2, y = log2(x). Quel est l'algorithme de recherche qui se comporte comme cette fonction ?
'si y est le nombre de tentatives et x la longueur de la liste)
Not yet started
1 point
A propos des algorithmes de tri en général, l'efficacité d'un algorithme fait référence ______________________.
Not yet started
1 point
Dire que la tri par apquet est plus efficace que le tri à bulle, c'est équivalent à dire que _________________.
Not yet started
1 point
La ou lesquelels de ces caractéristiques est vrai pour le tri à bulles ?
Cchez toutes les réponses valides.
Not yet started
1 point
La ou lesquelels de ces caractéristiques est vrai pour le tri par paquets ?
Cchez toutes les réponses valides.

Sample AP CSP Exam Question

Not yet started
1 point
Il y a 32 étudiants dans une classe. Deux algorithmes différents sont fournis pour trouver la taille moyenne des étudiants.

Algorithme A
Step 1: Tous les étudiants se lèvent.
Step 2: Un étudiant choisi au hasard écrit sa taille sur une carte et s'assoit.
Step 3: Un étudiant choisi au hasard ajoute sa taille à la valeur précédente et l'écrit sur la carte, efface la valeur précédente et s'assoit.
Step 4: L'étape 3 est répétée jusqu'à ce que tous les étudiants soient assis.
Step 5: La somme écrite sur la carte est divisée par 32. Le résultat est donné au professeur.

Algorithm B
Step 1: Tous les étudiants se lèvent.
Step 2: Une carte est donnée à chaque étudiant. Chacun écrit sa taille sur la carte.
Step 3: LEs étudiants se mettent par goupe de 2, au hasard, mais en même temps. Chaque paire fait la somme des nombres écrits sur les 2 cartes et l'écrit sur la carte d'étudiant à la place. Le nombre précédent est effacé. L'autre étudiant s'assoit.
Step 4: L'étape 3 est répétée jusqu'à ce qu'il n y ait plus qu'un seul étudiant debout.
Step 5: La somme sur la carte du dernier étudiant est divisée par 32. Le résultat est donné au professeur.

Laquelle de ces affirmations est vraie ?


Pour votre Portfolio

Créez une page nommée : Analyse des algorithmes dans la catégorie "Réflexions" de votre portfolio, puis répondez aux questions suivantes :

  1. PRésentez les résultats et l'analyse que vous avez faite dans les expérimentations de cette leçon. -- i.e., fournissez le tableau des temps de calcul observés, les graphiques que vous avez créé et les conclusions auxquelles vous êtes arrivés sur els algorithmes de recerche et de tri. Donnez une description claire de vos graphiques et données tabulaires, quie xplique comment vous êtes arrivés à vos conclusions.