Admin CliCours
1. Generalités
1.1. Comment mesurer la performance d’un programme?
Bien entendu, la premiere vertu d’un programme est sa correction, la suivante etant sa terminaison. Une fois ces proprietes satisfaites, il reste a savoir dans quelle mesure le programme propose est efficace : c’est l’objet du domaine de l’informatique appele complexite.
On distingue surtout deux types de complexite : la complexite temporelle, qui evalue la rapidite de l’algorithme, et la complexite spatiale, qui evalue l’occupation memoire de l’algorithme.
Les progres de l’informatique ont fait perdre de l’importance a la complexite spatiale : nous nous concentrerons surtout sur la complexite temporelle.
Bien entendu, il est hors de question d’evaluer concretement cette complexite temporelle, en chronometrant un programme : cela n’aurait qu’une valeur empirique, non predictive, dependrait fortement du hardware sur lequel le programme tourne, dependrait des donnees initiales (par exemple, il est facile de tester si 2 est premier, ca l’est moins pour 2 43112609
1). Il n’est pas non plus utile de donner precisement la complexite de l’algorithme, mais plutot son ordre de grandeur.
Il nous faut donc trouver un cadre d’etude theorique pour evaluer la rapidite d’un programme.
1.2. Notion de tailles de donnees, classes de complexite
La plupart des algorithmes ont un argument entier (test de primalite, factorisation), plusieurs (algorithme d’Euclide, exponentiation) ou leur execution depend d’un entier naturel (taille d’une liste, d’un vecteur) : nous noterons n un entier, representant la taille de donnees, dont les algorithmes dependront. Pour un entier, ce peut etre le nombre de bits.
Outre la notation de Landau O, nous utiliserons egalement la notation , signi ant que deux suites ont meme ordre : u n= (vn) signi e u n= O(vn) et v n= O(u).
Selon la taille de donnees n, l’algorithme va e ectuer un certain nombre de t^aches, dont certaines auront n un poids bien plus grand dans le temps d’execution. Nous ne compterons que le nombre c de ces operations couteuses.
On dit qu’un algorithme est
{ logarithmique si c n est de l’ordre de log (n).
{ lineaire si c est de l’ordre de n.
{ quasi-lineaire si cn est de l’ordre de n log n.
{ quadratique si c nn est de l’ordre de n.
{ polynomial si c n est de l’ordre de n2 k2 , pour un entier non nul k.
{ exponentiel si c n est de l’ordre de a n, ou a > 1.
Ces classes de complexite sont donnees en ordre croissant : les algorithmes exponentiels sont tres peu utiles, les logarithmiques nissent en temps raisonnable pour n’importe quelle taille de l’entree.
Remarque : bien s^ur, il faut temperer ce jugement, puisqu’il peut y avoir des co^uts occultes (si par exemple cn 10 100 log 2(n), l’algorithme n’est pas si pratique que cela …).
1.3. Un raffinement necessaire
En realite, la vitesse d’execution d’un algorithme peut ^etre tres sensible a la valeur des donnees, pas seule-ment a la taille n de ces donnees (penser encore une fois a un test de primalite). Ceci nous conduit a introduire des complexites selon les cas : complexite dans le meilleur, le pire des cas, complexite en moyenne.
Dans ce dernier cas, il est important de preciser le contexte probabiliste, a n de pouvoir ponderer les di erentes entrees possibles..
Avant de commencer
Introduction a l’option informatique
1. Objectifs de formation
2. Choisir concretement l’option informatique
3. Bref apercu du programme de SUP
4. FAQ
partie A. Programmation en Caml
Chapitre I. Introduction
1. Le langage Caml
2. Quelques conseils
Chapitre II. Programmation en Caml
1. Breve presentation de Caml light
2. Notion d’e et de bord
3. Identi cateurs
4. Types elementaires
5. Deux exemples de types non elementaires
6. Programmation fonctionnelle
7. Introduction a la recursivite
8. Programmation imperative
9. Types prede nis en Caml
10. Bref retour sur le ltrage
11. Types de nis par l’utilisateur
partie B. Methodes de programmation
Chapitre III. Programmation imperative
1. Correction et terminaison
2. Notion d’invariant de boucle
Chapitre IV. Recursivite
1. Introduction
2. Complements sur les relations d’ordre
3. Terminaison et correction des fonctions recursives
4. Recursivite croisee
5. Gestion d’une fonction recursive
6. Ensembles inductifs, induction structurelle
partie C. Analyse des algorithmes
Chapitre V. Complexite
1. Generalites
2. Un premier exemple
3. Diviser pour régner
Chapitre VI. Tris
1. Introduction
2. Utilité du tri : recherche dans un tableau trié
3. Insertion dans une liste triée
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Cours d’informatique de MPSI (1,40 MO) (Cours PDF)
