Tronc Commun Informatique

Dominique Perrin

X & Université de Marne la Vallée
perrin@univ-mlv.fr

Menu

1. Amphi 0
2. 12 petites classes
3. 12 t.p.
4. une composition HC
5. une composition
6. un projet

Bibliographie

Danièle Beauquier, Jean Berstel, Philippe Chretienne, Elements d'Algorithmique, Masson, 1992.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Algorithms, MIT Press, 1990.

Donald E. Knuth, The Art of Computer programming, vol. 1: Fundamental Algorithms, vol. 2: Seminumerical Algorithms, vol. 3: Sorting and Searching, Addison Wesley, 1973.

Jan van Leeuwen,Handbook of Theoretical Computer Science, vols. A et B, Elsevier, 1990.

Robert Sedgewick, Algorithms, Addison Wesley, 1991 (aussi: Algorithms in C).

P.C. 1
Introduction

Objectifs généraux et orientations de l'algorithmique:

• Conception de stuctures de données
• Construction d'algorithmes simples et efficaces
• Evaluation de la complexité des problèmes

Ecriture des algorithmes:

• en pseudocode
• dans un langage de programmation (ici: Pascal ou C)

Un exemple : le développement en fraction continue

Un développement en fraction continue d'un nombre réel positif est une suite d'entiers naturels telle que:

Quand est un nombre rationnel m/n, la suite des quotients obtenus en appliquant l'algorithme d'Euclide à (m,n) est un développement en fraction continue de .

En effet si m=qn+r, on a

On en déduit la procédure suivante, en Pascal, qui affiche les termes successifs du développement :

procedure cont(m,n: integer);
 begin
  if n <> 0 then
   begin
    writeln(m div n);
    cont( n, m mod n)
   end
 end;

Pour le développement d'un nombre réel , on aura :

procedure cont(alpha : real; n : integer);
 var 
  a,i : integer;
 begin
  for i := 1 to n do begin
   a:=trunc(alpha);
   writeln(a);
   alpha:= 1/(alpha-a)
  end
 end;

Le résultat de l'appel de cont(3.14159,4) est

3
7 
15 
1

Complexité des algorithmes

Donnée de taille n

• Temps de calcul T(n)
• Espace mémoire utilisé E(n)

Evaluation:

• En moyenne
• Au pire des cas

Calcul à une constante multiplicative près: pas d'unité de temps ou d'espace.

Notation O

Pour deux fonctions réelles positives f,g, on écrit

si f ne croit pas plus vite que g; formellement:

Exemples de classes de complexité:

Autres notations utilisées:

pour g=O(f)

pour f=O(g) et g=O(f).

La notation f=O(g) est un abus désigant mais commode pour écrire

Un exemple : le calcul du pgcd

Le calcul du pgcd de m et n par l'algorithme d'Euclide obéit, en posant m=nq+r, à la règle :

La complexité est logarithmique. En effet, on a, en supposant les inégalités

ou encore

d'où la conclusion.

Calcul de complexité

• Concaténation d'instructions:

• Itération:

• Règles de calcul:

  Si f=O(g) et f'=O(g') alors

  Si et si alors

Dichotomies

Solution:

Solution:

Démonstration : il suffit de vérifier que l'on a

avec a=T(1).

Exemple : tri par fusion

On considère le problème du tri d'un tableau .

procedure TriFusion(i,j:integer);
 var
  k:integer;
 begin
  if i<j then begin
   if j=i+1 then tri(a[i],a[j])
   else begin 
    k:=(i+j) div 2;
    TriFusion(i,k);
    TriFusion(k+1,j);
    Fusion(i,j);
   end;
  end;
 end;

• About this document ...