OEF Algorithmique --- Introduction ---

Ce module regroupe pour l'instant 10 exercices sur la complexité d'algorithmes et les ordres de grandeur.

Ordonner

Ordonner les expressions suivantes de manière à ce que chacune soit en O de la .

Donner l'ordre

Asymtotiquement en , l'expression est en

Complexité d'un algorithme

Donner le coût du programme suivant :

Coût et relation de récurrence

On a démontré que la fonction coût d'un algorithme en fonction d'instances de taille inférieure à vérifie

Alors, l'algorithme est en

.

Ordre de grandeur

Vous voulez évaluer le temps nécessaire pour sur un processeur à 1GHz.

Taille mémoire

On applique un pivot de Gauss à une matrice de flottants ayant 4 coefficients par ligne. Quelle taille mémoire utilise-t-on au maximum avant et après le pivot de Gauss? Quelle est en gros la taille maximale d'une telle matrice de flottants que l'on peut stocker dans un ordinateur avec 1Go de mémoire, avant et après pivot de Gauss?

Notations asymptotiques

Mettre les notations de gauche en correspondance avec leurs définitions

Comparaisons asymptotiques

Donner la conclusion :

Taille maximale

Vocabulaire asymptotique

Mettre les notations de Landau de gauche en correspondance avec leurs dénominations :

Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.