UP | HOME

Séance 9 : Algo & Prog avec R

Table des matières

1 Ensembles et Dictionnaires

1.1 Ensemble d’entiers aléatoires

  1. Définissez deux ensemble e2 et e3 de 10 entiers aléatoires de [0,20].
  2. Faites afficher la réunion, l’intersection, la différence asymétrique, et la différence symétrique de e2 et e3.
e2 <- sample(0:20, 10, replace=FALSE)
e3 <- sample(0:20, 10, replace=FALSE)
print(e2)     
print(e3)     
union(e2,e3)
intersect(e2,e3)
setdiff(e2,e3)
union(setdiff(e2,e3),setdiff(e3,e2))
 [1] 17  7 11  4 20  0 12 13 16  1
 [1] 12 20 14  0 16 10 13  3 18 15
 [1] 17  7 11  4 20  0 12 13 16  1 14 10  3 18 15
[1] 20  0 12 13 16
[1] 17  7 11  4  1
 [1] 17  7 11  4  1 14 10  3 18 15

1.2 Histoire de s’amuser !   HOME

Supposons que R ne dispose pas des fonctions ensemblistes. Comment programmeriez-vous les fonctions Union(x,y), Intersection(x,y), et Difference(x,y) (asymétrique) sur des vecteurs non triées avec répétitions.

Union <- function(x, y) unique(append(x,y))
Intersection <- function(x, y) x[ x %in% y ]
Difference <- function(x, y) x[ !(x %in% y) ]
x <- sample(1:5)
y <- sample(4:8)
print(x)
print(y)
print(Union(x,y))
print(Intersection(x,y))
print(Difference(x,y))
[1] 5 1 4 2 3
[1] 5 6 4 7 8
[1] 5 1 4 2 3 6 7 8
[1] 5 4
[1] 1 2 3

1.3 Dictionnaire simple

Créez un petit dictionnaire d1 ayant trois couples var:val dont les valeurs ont des types distincts.

  1. Faites afficher le type de d1.
  2. Faites afficher la liste des clés de d1.
  3. Faites afficher l’ensemble des valeurs de d1.
  4. Demandez la valeur de la clé « toto ».
d1 <- list("foo"=0, "bar"=1:2, "team"="foobar")
class(d1)
names(d1)
print(paste(d1))
d1["foo"]
d1["toto"]
[1] "list"
[1] "foo"  "bar"  "team"
[1] "0"      "1:2"    "foobar"
$<NA>
NULL

$foo
[1] 0

1.4 Dictionnaire aléatoire

  1. Programmez une fonction RandomDict(), retournant un dictionnaire aléatoire de longueur 10.
    • Les 10 clés distinctes seront choisies au hasard parmi les entiers de [0,20].
    • Les valeurs associées à ces clés (non nécessairement distinctes) seront choisies parmi les voyelles ’a’,’e’,’i’,’o’,’u’,’y’.
  2. Posons ensuite d2 <- RandomDict().
  3. Faites afficher le nombres de clés paires de d2.
  4. Faites afficher les valeurs distinctes de d2.
RandomDict <- function() {
  res <- sample(c('a','e','i','o','u','y'),10,replace=TRUE)
  names(res) <- sample(0:20,10,replace=FALSE)
  return(res)
}
d2 <- RandomDict()
print(d2)
sum(as.integer(names(d2)) %% 2 == 0)
unique(d2)
 15   4   5  19   8  16   0   6   3  14 
"o" "u" "y" "e" "y" "e" "u" "e" "y" "y" 
[1] 6
[1] "o" "u" "y" "e"

1.5 Filtrage des clés par valeur

Programmez une fonction GetKeys(d,v) retournant l’ensemble des clés d’un dictionnaire quelconque d, dont la valeur associée est v.

Rappel : les clés sont uniques, mais pas les valeurs!

d1 <- list('a'=5, 'b'=6, 'c'=5, 'd'='b', 'e'=0:1, 'f'=list(0,1))
GetKeys <- function(d, v) {
  ind <- logical(length(d))
  for(i in seq_along(d)) {
    if(all(d[[i]] == v) ) {ind[i]=TRUE}
  }
  return(names(d)[ind])
}

GetKeys(d1,5)     
GetKeys(d1,'b')     
GetKeys(d1,0:1)
GetKeys(d1,0:2)
[1] "a" "c"
[1] "d"
[1] "e" "f"
character(0)

2 Memo-Fonctions

2.1 Une récurrence simple

On considère la suite définie par récurrence de la manière suivante : \(u_0=2\) et \(u_n = \frac{1}{2} u_{n-1} + 3\).

  1. Programmez la fonction u(n) par récurrence et afficher la liste des termes de 0 à 10.
    u <- function(n) ifelse(n == 0, 2, u(n-1)/2 + 3)
    sapply(0:10,u)
    
    [1] 2.000000 4.000000 5.000000 5.500000 5.750000 5.875000 5.937500 5.968750
    [9] 5.984375 5.992188 5.996094
    
  2. Reprogrammez-la par une boucle.
    vec <- numeric(11)
    vec[1] <- 2
    for(i in 1:10) {
      vec[i+1] <- vec[i]/2 + 3
    }
    print(vec)
    
    [1] 2.000000 4.000000 5.000000 5.500000 5.750000 5.875000 5.937500 5.968750
    [9] 5.984375 5.992188 5.996094
    
  3. Quel est le coût du calcul de cette liste en fonction de N ?
  4. Reprogrammez la fonction u(n) sous la forme d’une mémo-fonction, qui se souvienne des calculs qu’elle a déjà effectués.
    make_u <- function() {
      terms <- c(2)
      u <- function(n) { 
        m <- length(terms)
        if(n >= m) {
          ## print(terms)
          for(i in m:n) {
            terms <<- append(terms, terms[i]/2 + 3) ## opérateur <<- au lieu de <- !
          }
        }
        return(terms[n+1])
      }
      return(u)
    }
    
    u <- make_u()
    sapply(0:10,u)
    
    [1] 2.000000 4.000000 5.000000 5.500000 5.750000 5.875000 5.937500 5.968750
    [9] 5.984375 5.992188 5.996094
    

2.2 Coefficients binomiaux

Vous connaissez tous le Triangle de Pascal [sinon : Google!]. Il est bâti sur les coefficients \(C_n^p\) et se construit à la main par des additions :

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
...

Autrement dit : \[ C_n^p = C_{n-1}^p + C_{n-1}^{p-1} \qquad (10 = 4 + 6 = 6 + 4) \] Nous nous proposons de programmer la fonction binomial(n,p) retournant \(C_n^p\).

  1. Vérifiez que la fonction ci-dessous conduit à une pauvre programmation.
    binomial <- function(n,p) {
      if(p == 0 || p == n) {return(1)}
      else return(binomial(n-1,p)+binomial(n-1,p-1))
    }
    

    Demandez par exemple à calculer \(C_5^3\), puis \(C_{52}^{13}\) qui représente le nombre de mains de 13 cartes parmi 52 au bridge.

  2. Programmez binomial sous la forme d’une mémo-fonction qui se souvient des calculs déjà effectués. Vérifiez qu’alors le calcul de \(C_{52}^{13}\) est immédiat !
    make_binomial <- function() {
      ## a list of vectors
      binodict <- list(c(1),c(1,1))
      binomial <- function(n, p) {
        m <- length(binodict)
        n1 <- n + 1
        p1 <- p + 1
        if(n >= m) {
          ## Increase Dictionary size
          binodict <<- append(binodict, lapply((m+1):(n1), rep, x=NA))
        }
    
        if(is.na(binodict[[n1]][p1])) {
          if(p == 0 || p == n) {
            binodict[[n1]][1] <<- 1
            binodict[[n1]][n1] <<- 1
          } else {
            binodict[[n1]][p1] <<- binomial(n-1,p) + binomial(n-1,p-1)
          }
        }
        return(binodict[[n1]][p1])      
      }
      return(binomial)
    }
    
    binomial <- make_binomial()
    triangle_pascal(6)
    binomial(52,13)
    
    make_binomial <- function() {
      ## a named vector
      key <- function(n,p) paste(n,p,sep="_")
      binodict <- c(1)
      names(binodict) <- key(0,0)
    
      binomial <- function(n, p) {
        knp <- key(n,p) 
           if(is.na(binodict[knp])) {
             if(p == 0 || p == n) {
               binodict[knp] <<- 1
             } else {
               binodict[knp]<<- binomial(n-1,p) + binomial(n-1,p-1)
             }
           }
           return(unname(binodict[knp]))      
      }
      return(binomial)
    }
    
    binomial <- make_binomial()
    triangle_pascal(6)
    binomial(52,13)
    
  3. Faîtes afficher le Triangle de Pascal jusqu’à la ligne 10 incluse. Tâchez d’avoir des colonnes bien alignées !
    triangle_pascal <- function(m) {
      for(n in 0:m) {
        cat(format(sapply(0:n, binomial, n=n), width=3),sep=" ")
        cat("\n")
      }
    }
    
  4. N.B. Il existe une autre formule pour \(C_n^p\), basée sur des factorielles et utilisée en combinatoire :

    \[ C_n^p = \frac{n!}{p!(n-p)!} \] Vous pouvez la programmer en R, en vous posant quand même la question : ne suis-je pas en train de faire trop de multiplications ?

3 Fréquence des mots dans une chaîne   HOME

Vous êtes invités à essayer la méthode strsplit qui renvoie une liste de vecteurs de character séparés par un séparateur split :

txt <- 'le chien et le loup font la course'
strsplit(txt,' ')
txt <- 'Nice, Antibes, Monaco'
unlist(strsplit(txt,split=', '))
txt <- 'foo   bar'
unlist(strsplit(txt,' '))
unlist(strsplit(txt,' +',fixed=FALSE))
[[1]]
[1] "le"     "chien"  "et"     "le"     "loup"   "font"   "la"     "course"

[1] "Nice"    "Antibes" "Monaco" 
[1] "foo" ""    ""    "bar"
[1] "foo" "bar"
  1. Utilisez les méthodes strsplit et table pour programmer une fonction Frequences(str) prenant une chaîne str et retournant un vecteur nommé contenant les fréquences d’apparition de chaque mot de str.
  2. Modifiez votre solution pour que le résultat soit une liste de couples triée par la fréquence en utilisant la fonction sort.
  3. En déduire une fonction PlusFrequents(str) retournant les mots les plus fréquents.
Frequences <- function(str) {
  words <- unlist(strsplit( trimws(str),' +',fixed=FALSE))
  res <- table(words)
  res <- sort(res, decreasing=TRUE)
  return(res)
}

PlusFrequents <- function(str) {
  r <- Frequences(str)
  names(r[ r == r[1] ])
}
Frequences(" ")
str <- "do re do mi do la la mi la"
Frequences(str)
PlusFrequents(str)
integer(0)
words
do la mi re 
 3  3  2  1
[1] "do" "la"

Created: 2017-12-07 jeu. 12:27