1)

La classe Naturel utilisera un tableau de chiffres, de la moins significative à la plus significative.
Une chiffre peut être représentée par un entier ou un caractère, mais le choix d'un intier est plus
générale.

La classe devrait avoir un certain nombre de constructeurs pour :
- construir le Naturel 0
- construir un objet Naturel à partir d'un entier
- construir un objet Naturel à partir d'une chaîne de caractères contenant la représentation décimale d'un nombre naturel
- construir un objet Naturel à partir d'un autre objet Naturel (constructeur de copie)

Des méthodes que la classe doit offrir sont :
- les quatre opérations arithmétiques :
  
  Naturel addition(Naturel n),
  Naturel soustraction(Naturel n) [n doit être inférieur ou égal au naturel représenté par l'objet],
  Naturel multiplication(Naturel n),
  (Naturel, Naturel) division(Naturel n) [n ne doit pas être égal à zéro ; renvoie quotient et reste] 

- une opération de comparaison :

  entier compare(Naturel n) [0 si égal, <0 si inférieur, >0 si supérieur]
  
- d'autres opérations :

  chaîne représentationDécimale()
  booléen premier()
  
2.1)

    Naturel addition(Naturel self, Naturel n)
        entier taille <- max(self.taille(), n.taille()) + 1;
        entier temp[taille]
        entier carry <- 0
        pour i de 1 à taille
            carry <- carry self.chiffre[i] + n.chiffre[i]
            temp[i] <- carry (mod BASE)
            carry <- carry/BASE
        tant que temp[taille] = 0 et taille>1)
            taille <- taille - 1;
        Naturel resultat <- Naturel()
        resultat.chiffre <- entier[taille]
        pour i de 1 à taille
            resultat.chiffre[i] <- temp[i]
        renvoyer resultat
	
2.2)

Soient n et m les naturels sommés. Les tailles de leurs représentations sont O(log n) et O(log n) respectivement.
Complexité en temps : O(max{log n, log m}).
Complexité en espace : O(log n + log m + max{log n, log m}).

2.3)

    intier compare(Naturel self, Naturel n)
        si self.taille() < n.taille()
            renvoyer -1
        si self.taille() > n.taille()
            renvoyer 1
        pour i de taille à 1
            entier diff <- chiffre[i] - n.chiffre[i]
            si diff!=0 renvoyer signe(diff)
        # si on est arrivés ici, les deux nombres sont identiques !
        renvoyer 0

2.4)

Pire cas : les deux nombres sont égaux ou ils diffèrent que pour la chiffre la moins significative : O(log n)
Meilleur cas : nombres de taille différente : O(1)
Cas moyen : (1 - epsilon)O(1) + epsilon O(log n).
Puisque étant donnés deux naturels aléatoires la probabilité qu'ils soient égaux ou qu'ils diffèrents
que pour la chiffre la moins significative sera très petite (pour l'estimer il faudrait supposer une
distribution de probabilité sur les naturels), pratiquement le cas moyen coïncide avec le meilleur cas ;
l'incidence du pire cas serait donc négligeable et le meilleur cas serait le plus pertinent.

2.5)

Il suffit d'adopter une représentation en base 1000 au lieu d'en base 10.

3.1)

On peut représenter un rationnel comme un signe (+ ou -), un numérateur neturel et un dénominateur naturel.

3.2)

Pour faire l'addition de deux rationnels (du même signe), il faut multiplier le numérateur de l'un
par le dénominateur de l'autre, sommer les deux naturels ainsi obtenus pour obtenir le numérateur du
résultat, puis faire la multiplication des dénominateurs pour obtenir le dénominateur du résultat.
Cela fait trois multiplication et une additions de naturels. En plus, on pourrait simplifier le
résultat en divisant et le numérateur et le dénominateur par leur pgdc.

3.3)

Pour faire la comparaison de deux fractions, il faut d'abord les rammener au dénominateur commun,
comme on fait pour l'addition (= deux multiplications de naturels) ; ensuite, on pourra comparer les deux
naturels ainsi obtenus (= même complexité de la comparaisons des naturels).
Donc, la complexité sera du même ordre que deux multolications et une comparaisons de naturels.