Exercice 1 :

Q1 : écrire un algorithme itératif qui permet de calculer la suite de fibonarcci d’une entrée n

Q2 : Calculer le nombre d’instruction élémentaire T exécuter par l’algorithme en pire des cas et en meilleur des cas (en précisant la complexité asymptotique). 

Exercice 2:

Q1 : Ecrire un algorithme qui permet de calculer le nombre des élément paire (P) et le nombre des éléments impaire (R) dans une matrice de taille (m,n).

Q2 : Calculer le nombre d’instruction élémentaire T exécuter par l’algorithme en pire des cas et en meilleur des cas (en précisant la complexité asymptotique). 

Exercice 3:

Q1 : écrire un algorithme qui permet de réaliser une recherche séquentielle d’un élément X dans un tableau.

Q2 : Calculer le nombre d’instruction élémentaire T exécuter par l’algorithme en pire des cas et en meilleur des cas (en précisant la complexité asymptotique).  

Exercice 4:

Q1 : Ecrire un algorithme qui permet de réaliser une recherche dichotomique d’un élément x dans un tableau trier.

Q2 : Calculer le nombre d’instruction élémentaire T exécuter par l’algorithme en pire des cas et en meilleur des cas (en précisant la complexité asymptotique). 

Exercice 6 :

Q1 : Ecrire  six  algorithmes  différents  pour  déterminer  si  un  nombre  entier  est  premier  ou composé. Evaluer la complexité pour chacun des algorithmes proposés.

Q2 : Calculer le nombre d’instruction élémentaire T exécuter par l’algorithme en pire des cas et en meilleur des cas (en précisant la complexité asymptotique). 

Exercice 5:

Considérer le théorème suivant sur le pgcd ou le plus grand commun diviseur :

                         pgcd(a,b) = pgcd(b, a mod b)

Q1 : Utiliser le théorème pour écrire un algorithme de calcul itératif du pgcd de deux entiers a et b

Q2 : Calculer la complexité asymptotique de l’algorithme

Q3 : Ecrire un algorithme pour calculer le ppcm de deux nombres a et b et calculer sa complexité asymptotique