UP | HOME

Séance 6 : Algo & Prog avec R

Table des matières

1 Recopie et clonage

Le problème de la copie et du clonage est important dans les langages de programmation.

  1. Exécutons la session ci-dessous au toplevel R :
    x <- 1:5
    y <- x
    x[1] <- -1
    print(x)
    print(y)
    
    [1] -1  2  3  4  5
    [1] 1 2 3 4 5
    
  2. Voici le résultat de la même session en Python :
    x = range(1,6)
    y= x
    x[0]=-1
    print(x)
    print(y)
    
    [-1, 2, 3, 4, 5]
    [-1, 2, 3, 4, 5]
    

2 Le tri par fusion (mergesort)

  1. Programmez la fonction Fusion(x, y) prenant deux vecteurs croissants d’entiers x et y, et retournant un vecteur croissant mélange des deux.
    x <- c(2, 5, 6, 6, 8, 12, 20)
    y <- c(0, 2, 7, 8, 15, 19, 23)
    print(paste('x = [',paste(x,collapse=','),'] et y =',paste(y,collapse=',')))
    print(paste('Fusion : [',paste(Fusion(x,y),collapse=','),']'))
    
    [1] "x = [ 2,5,6,6,8,12,20 ] et y = 0,2,7,8,15,19,23"
    [1] "Fusion : [ 0,2,2,5,6,6,7,8,8,12,15,19,20,23 ]"
    
  2. Le principe du tri par fusion suit le diagramme dichotomique ci-dessous, dans lequel la scission coupe en deux sous-listes de même longueur ou presque [à 1 élément près] :
        L = [8, 5, 2, 3, 1, 5, 4, 9, 2]
                   /             \
                  /               \
    LT1 = [1, 2, 4, 5, 8]   LT2 = [2, 3, 5, 9]
                  \               /
                   \             /
         LT = [1, 2, 2, 3, 4, 5, 5, 8, 9]
    
  3. Utilisez la fonction Fusion pour programmer par récurrence une fonction TriFusion(x) prenant un vecteur de nombres réels x et retournant une copie triée en ordre croissante de ce vecteur.
    x <- sample(1:100, 10, replace = TRUE)
    print(paste('Test du tri fusion : L = [',paste(x,collapse=','),']'))
    print(paste('Test du tri fusion : LT = [',paste(TriFusion(x),collapse=','),']'))
    
    [1] "Test du tri fusion : L = [ 10,22,19,93,76,78,25,53,14,97 ]"
    [1] "Test du tri fusion : LT = [ 10,14,19,22,25,53,76,78,93,97 ]"
    
  4. Comparez les temps d’exécution des fonctions TriFusion et sort grâce à system.time.
  5. Calcul de la complexité
    1. Définissez par récurrence la suite C(N) donnant le nombre d’opérations élémentaires en fonction du nombre d’éléments à trier N.
    2. Donnez le terme général de la suite en supposant que N=2p.

3 Crible d’Eratosthène

Il s’agit d’un algorithme célèbre permettant de construire les entiers premiers jusqu’à n :

  1. On commence par construire le vecteur x des entiers de 2 jusqu’à n inclus.

Nous allons maintenant rayer les nombres non premiers de ce vecteur !

  1. Le premier nombre non rayé est premier (pourquoi ?). Je raye tous ses multiples. Et je répète cette étape jusqu’à avoir examiné tous les nombres du vecteur.

Exemple, n = 26 :

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26
2  3  .  5  .  7  .  9   .  11   .  13   .  15   .  17   .  19   .  21   .  23   .  25   .
2  3  .  5  .  7  .  .   .  11   .  13   .   .   .  17   .  19   .   .   .  23   .  25   .
2  3  .  5  .  7  .  .   .  11   .  13   .   .   .  17   .  19   .   .   .  23   .   .   .

Programmez la fonction Crible(n) retournant la liste des nombres premiers de [2,n].

  1. Analyse des performances

    Comparez sur machine les temps de calcul pour construire la liste des nombres premiers jusqu’à 50000 :

    1. En utilisant le crible d’Eratosthènes vu ci-dessus.
    2. En utilisant la fonction estPremier du TP2.

4 Dichotomie

Reprenons la recherche par dichotomie du cours 6. Le programme donné en cours utilise beaucoup de constructions de tranches qui sont des recopies coûteuses de portions de listes.

Pour les éviter et accélérer la recherche, vous allez travailler sur place (sans utiliser de listes supplémentaires) en gérant deux indices a et b. Au départ a=0 et b=length(L)-1. Vous allez faire se rapprocher les curseurs a et b, en abandonnant la moitié de l’intervalle [a,b] chaque fois. À vous !

5 Exceptions [d’après IUT Orsay].

  1. Définissez la fonction \(f(x) = sin(x)/x\).
  2. Calculez les valeurs de f pour les entiers compris entre -3 et 3
  3. Levez une erreur en cas de division par 0.
  4. Lancez un avertissement quand x devient très petit.
  5. Traitez les erreurs en renvoyant la limite de f(x) en 0.
  6. Traitez les avertissements en utilisant le developpement limité d’ordre 3 au voisinage de 0 de la fonction \(sin(x) \simeq x - \frac{x^3}{6}\).

Created: 2018-09-17 lun. 21:26