Algorithmique (séance 1)

Qu'est ce qu'un algorithme ? Comment comparer deux algorithmes ?

Fichier contenant le cours

Exercice 3 : croissance comparée

Télécharger le fichier croissance_comparee.py et classer par ordre croissant les diverses possibilités de croissance. Ecrire le résultat dans votre cours, c'est un point important de l'algorithmique.

Exercice 4 : comparaison de 2 implémentations différentes de la même tâche

La tâche à effectuer est le tri d'un tableau de valeurs (une liste en python) selon un certain critère qui ne nous préoccupe pas pour cet exercice. Le tri s'effectue sur un tableau contenant 10 millions d'entiers codés sur 8 octets chacun. Deux implémentations de cette tâche (ou algorithme) ont été faites sur deux ordinateurs différents :

• Ordinateur A : le temps d'exécution de l'algorithme croît en n² et c'est un ordinateur rapide pouvant faire 10 milliards d'opérations par seconde. Nombre d'instructions à exécuter : 2*n²
• Ordinateur B : le temps d'exécution de l'algorithme croît en n*lg n et c'est un ordinateur lent ne pouvant faire que 10 millions d'opérations par seconde. Nombre d'instructions à exécuter : 50*n*lg n

Questions :

1. Quelle taille en Mo représentent les 10 millions d'entiers codés sur 8 octets?
2. En combien de temps l'ordinateur A va-t-il exécuter son algorithme ?
3. Idem pour l'ordinateur B.
4. Reprendre les deux dernières questions si on a maintenant 100 millions d'entiers au lieu de 10 millions d'entiers.

Recherche d'une valeur dans un tableau

Voici le fichier de travail avec les exercices.

Exercice 5 : recherche d'un extremum dans un tableau

1. Ecrire un programme (exercice_D01.py) qui recherche une valeur extremum (minimum ou maximum, à vous de choisir) dans un tableau en utilisant la même forme que celle utilisée en cours (parties entrées, sorties, procédure) (ce qui revient à préciser les pré et post-conditions)
2. Appliquer votre algorithme sur le tableau : A=[-2,3,-4,5,-6,7]
3. Caractériser le temps d'exécution de votre algorithme en utilisant la notation grand O dans un commentaire à la fin de votre programme.

Exercice 6 : calculer la moyenne d'un tableau

1. Ecrire un programme (exercice_D02.py) qui calcule la moyenne des valeurs d'un tableau. On supposera que le tableau ne contient que des valeurs numériques. Utiliser la même forme que celle utilisée en cours (parties entrées, sorties, procédure) (ce qui revient à préciser les pré et post-conditions)
2. Appliquer votre algorithme sur le tableau : A=[2,3,4,5,6,7]
3. Caractériser le temps d'exécution de votre algorithme en utilisant la notation grand O dans un commentaire à la fin de votre programme.

Exercice 7

Ecrire le programme python (exercice_D03.py) correspondant l'algorithme 2 du fichier Algo 1