Travaux Pratiques #5
Algo & Prog avec R

Table des matières

1. Le tour de la boucle KEY
2. Alphabet
3. Table ASCII
4. Tables de multiplication
5. Épluchages de chaînes KEY
6. Code de César HARD
7. Recherche de chaînes : une perspective biologique HARD
8. Commande tr HOME HARD

1. Le tour de la boucle KEY

Foo <- function(x,a,b) {
  for (i in a:b) {
    x = x + i
  }
  return(x)
}
Foo(10,15,20)
Foo(10,20,15)

[1] 115
[1] 115

Dans un premier temps, vous pouvez supposez que a<=b, puis vous généraliserez.

Reprogrammez la fonction précédente en remplaçant la boucle for par une boucle while.

Foo <- function(x,a,b) {
  while(a <= b) {
    x <- x + a
    a <- a + 1
  }
  return(x)
}
Foo(10,15,20)

[1] 115

Reprogrammez la fonction en remplaçant la boucle for par une récursion.

Foo <- function(x,a,b) {
  if(a > b) return(x)
  else return(a + Foo(x, a + 1, b))
}
Foo(10,15,20)

[1] 115

Reprogrammez cette même fonction sans utiliser aucune boucle !
- En utilisant le calcul direct
```
Foo <- function(x,a,b) {
  return( x + (b-a+1)* ((a+b) / 2) )
}
```
```
[1] 115
```
- En utilisant des fonctions prédéfinies (vectorisation).
```
Foo <- function(x,a,b) x + sum(a:b)
Foo(10,15,20)
```
```
[1] 115
```

Maintenant, généralisez les fonctions pour traiter a>b si cela est nécessaire.

## Nécessaire pour les versions avec while et récursive.
## Par échange de paramètres
Foobar <- function(x,a,b) {
  if(a > b) return(Foo(x, b, a))
  else return(Foo(x, a, b))
}
Foobar(10,20,15)

[1] 115

2. Alphabet

## Une première solution sans passer par les codes
Alphabet <- function(upper=FALSE) {
    if (upper) return(paste(LETTERS, collapse = ''))
    else return(paste(letters, collapse = ''))
}

## Une seconde solution basée sur les codes
Alphabet <- function(upper=FALSE) intToUtf8( 0:25 + (utf8ToInt(ifelse(upper,'A','a'))))

Programmez une fonction Alphabet() dont le résultat est la chaîne : ’abcdefghijklmnopqrstuvwxyz’.

Alphabet()

[1] "abcdefghijklmnopqrstuvwxyz"

Ajoutez un paramètre optionel upper pour renvoyer l’alphabet en lettres minuscules ou majuscules.

Alphabet(upper = TRUE)

[1] "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

Indice : ne pas utiliser de boucles, mais les vecteurs prédéfinis letters et LETTERS.

3. Table ASCII

Programmez une fonction Ascii() qui renvoie une table ASCII pour les caractères dont le code est compris entre 32 et 126.

Ascii <- function(upper=FALSE) {
  sprintf("%d:%s", 32:126, intToUtf8(32:126, multiple=TRUE))
}

Ascii()

 [1] "32: "  "33:!"  "34:\"" "35:#"  "36:$"  "37:%"  "38:&"  "39:'"  "40:("
[10] "41:)"  "42:*"  "43:+"  "44:,"  "45:-"  "46:."  "47:/"  "48:0"  "49:1"
[19] "50:2"  "51:3"  "52:4"  "53:5"  "54:6"  "55:7"  "56:8"  "57:9"  "58::"
[28] "59:;"  "60:<"  "61:="  "62:>"  "63:?"  "64:@"  "65:A"  "66:B"  "67:C"
[37] "68:D"  "69:E"  "70:F"  "71:G"  "72:H"  "73:I"  "74:J"  "75:K"  "76:L"
[46] "77:M"  "78:N"  "79:O"  "80:P"  "81:Q"  "82:R"  "83:S"  "84:T"  "85:U"
[55] "86:V"  "87:W"  "88:X"  "89:Y"  "90:Z"  "91:["  "92:\\" "93:]"  "94:^"
[64] "95:_"  "96:`"  "97:a"  "98:b"  "99:c"  "100:d" "101:e" "102:f" "103:g"
[73] "104:h" "105:i" "106:j" "107:k" "108:l" "109:m" "110:n" "111:o" "112:p"
[82] "113:q" "114:r" "115:s" "116:t" "117:u" "118:v" "119:w" "120:x" "121:y"
[91] "122:z" "123:{" "124:|" "125:}" "126:~"

4. Tables de multiplication

Programmez une fonction TableMult(n) prenant un entier n compris entre 1 et 9, et affichant la table de mutliplication par n. Vérifier la validité de l’argument n en utilisant la fonction stopifnot.

TableMult <- function(n) {
  stopifnot(length(n) == 1, n > 0, n < 10, floor(n) == n)
  x <- 1:10
  cat(' ')
  cat(sprintf("%d x%2d = %3d\n",n,x,n*x))
}

## TableMult(0) ## error !
## TableMult(1.5) ## error !
TableMult(4)

4 x  1 =   4
4 x  2 =   8
4 x  3 =  12
4 x  4 =  16
4 x  5 =  20
4 x  6 =  24
4 x  7 =  28
4 x  8 =  32
4 x  9 =  36
4 x 10 =  40

5. Épluchages de chaînes KEY

En utilisant l’idée d’épluchage d’un entier, programmez les fonctions suivantes d’écriture et de lecture d’un nombre binaire.

La fonction IntToBin(n) prenant un entier n et retournant la chaîne contenant l’écriture binaire de n.

Programmez une version itérative.

IntToBin <- function(n) {
  n <- abs(n);
  acc <- "";
  while(n > 2) {
    acc <- paste(n %% 2, acc, sep="");
    n  <- n %/% 2;
  }
  return( paste(n, acc, sep=""))
  }

Programmez une version récursive.

IntToBin <- function(n) {
  n <- abs(n);
  if(n < 2) return(as.character(n))
  else return(paste(IntToBin(n %/% 2), n %% 2, sep = ""))
}

n <- 3456
nbin <- IntToBin(3456)
cat(n, "->", nbin,  "->", strtoi(nbin, base = 2), '\n')

3456 -> 110110000000 -> 3456

La fonction inverse BinToInt(s) prenant une chaîne s contenant l’écriture binaire d’un entier n, et retournant n.

Programmez la fonction avec la méthode des puissances.

BinToInt <- function(s) {
  digits <- utf8ToInt(s)-utf8ToInt("0")
  pows <- seq(from = length(digits)-1, to = 0)
  return(sum( 2**pows * digits))
}

Programmez la fonction avec le schéma de Horner qui calcule de manière optimale la valeur d’un polynôme en un point sans calcul de puissance.

BinToInt <- function(s) {
  digits <- utf8ToInt(s)-utf8ToInt("0")
  acc <- 0
  for(digit in digits) {
    acc <- 2 * acc + digit
  }
  return(acc)
}

n <- 3456
nbin <- IntToBin(3456)
## On utilise maintenant la fonction inverse
cat(n, "->", nbin,  "->", BinToInt(nbin), '\n')

3456 -> 110110000000 -> 3456

Vous avez maintenant tous les pré-requis pour commencer le mini-projet Convertisseur de base (shiny).

6. Code de César HARD

Le codage des messages secrets selon Jules César consistait à choisir une clé entière k dans [1,25] pour fabriquer à partir d’un message msg un nouveau message codé avec la technique suivante. Chaque lettre majuscule de msg est décalée de k positions vers la droite (l’alphabet est circulaire : après ’Z’ on revient sur ’A’). Les autres caractères du message sont laissés intacts.

Programmez la fonction CodeCesar(msg,k) qui retourne le message codé avec un décalage k.
Programmez la fonction DecodeCesar(msg,k) qui prend un message codé par et retourne le message en clair.
Défi urgent : décodez le message ’JLGVI XRJFZC’ dont Jules a perdu la clef !
Modifiez la fonction CodeCesar(msg,k) pour qu’elle code les majuscules et les minuscules.

CodeCesar <- function(msg, k) {
  ## traduction de la chaîne en vecteur de codes utf8
  cc <-utf8ToInt(msg)
  ## normalisation de la clé
  k <- k %% 26;
  CircShift <- function(aa) {
    aa <- utf8ToInt(aa)
    zz <- aa + 25
    enc <- cc >= aa & cc <= zz
    cc[enc] <- cc[enc] + k
    enc[enc] <- cc[enc] > zz
    cc[enc] <- cc[enc] - 26
    return(cc)
  }
  cc <- CircShift('a')
  cc <- CircShift('A')
  return(intToUtf8(cc))
}

DecodeCesar <- function(msg, k) CodeCesar(msg, -k)

TestCesar <- function(msg, k) {
  cod <- CodeCesar(msg,k)
  dcod <- DecodeCesar(cod,k)
  cat('k=', k, ":" , msg, '-->', cod,'-->', dcod, '\n')
}
TestCesar('envoyez 36 hommes !', 3)
TestCesar('ENVOYEZ 36 HOMMES !', -23)
TestCesar('ENVOyez 36 homMES !', 5)

k= 3 : envoyez 36 hommes ! --> hqyrbhc 36 krpphv ! --> envoyez 36 hommes !
k= -23 : ENVOYEZ 36 HOMMES ! --> HQYRBHC 36 KRPPHV ! --> ENVOYEZ 36 HOMMES !
k= 5 : ENVOyez 36 homMES ! --> JSATdje 36 mtrRJX ! --> ENVOyez 36 homMES !

7. Recherche de chaînes : une perspective biologique HARD

D’après le cours Python du MIT.

La recherche de chaînes (string matching) est intéressante dans plusieurs disciplines, comme la biologie, dont un problème courant consiste à comprendre la structure des molécules d’ADN, et le rôle de structures spécifiques dans le fonctionnement de la molécule. Une séquence ADN est représentée par une suite de caractères choisis parmi les quatre nucléotides : adenine (A), cytosine (C), guanine (G) et thymine (T). Par exemple, la chaîne de caractères ’AAACAACTTCGTAAGTATA’ représente un brin d’ADN. Une manière de comprendre la fonction d’un brin d’ADN consiste à y rechercher une séquence précise, avec l’idée qu’une structure identique induira des effets identiques. Nous allons pénétrer un tout petit peu dans cette idée.

Programmez une fonction CountSubstringMatch(s1,s2) qui prend deux chaînes en argument et retourne le nombre de fois où s2 apparaît comme sous-chaîne de s1.
Indice : utiliser la fonction regexpr.

CountSubstringMatch <- function(str, pattern) {
  occ = 0
  r <- regexpr(pattern,str)
  while(r > 0) {
    occ <- occ + 1
    str <- substr(str,start=r+1,stop=nchar(str))
    r <- regexpr(pattern,str)
    ## On ne peut pas utilisr gregexpr, car on autorise le chevauchement entre les motifs
  }
  return(occ)
}

CountSubstringMatch('atatata','ata')
CountSubstringMatch('atgacatgcacaagtatgcat','atgc')
CountSubstringMatch('atatata','atc')

[1] 3
[1] 2
[1] 0

8. Commande `tr` HOME HARD

La commande shell tr copie son entrée standard sur sa sortie standard en transposant ou éliminant des caractères. Par exemple, taper les commandes suivantes dans un terminal.

echo "foobar" | tr a-z A-Z
echo "foobar" | tr -d oa

FOOBAR
fbr

Programmer une fonction tr(text, str1, str2) similaire à la commande shell tr. La fonction retourne une copie de la chaîne de caractère text en effectuant l’une des manipulations suivantes :

si la chaîne str2 est vide, elle supprime les caractères de str1 ;
si la chaîne str2 n’est pas vide, elle transpose les caractères de str1 par ceux de str2.

tr <- function(text, str1, str2) {
  stopifnot(is.character(text), is.character(str1),
            length(text) == 1,length(str1) == 1)
  ## transposer ou éliminer des caractères
  textL <- utf8ToInt(text)
  if( missing(str2) || is.na(str2) || nchar(str2) == 0) {
    ## éliminer les caractères de str1
    del <- utf8ToInt(str1)
    textL <- textL[ !( textL %in% del) ]
  }else {
    ## transposer les caractères de str1 par ceux de str2
    ch1 <- utf8ToInt(str1)
    ## recyclage de str2
    ch2 <- rep_len(utf8ToInt(str2), length(ch1))
    ## recherche des caractères
    x <- match(textL, ch1)
    ## position à trasnposer
    xb <- ! is.na(x)
    ## transposition
    textL[xb] <- ch2[x[xb]]
  }
  return (intToUtf8(textL))
}

tr("foobar","oo")
tr("foobar","oa", "eu")
tr("foobar","oo", "eu")
tr("foobar","foar", "eu")

[1] "fbar"
[1] "feebur"
[1] "feebar"
[1] "euubeu"

Indice : lire la page de manuel de la commande shell tr

man tr

Travaux Pratiques #5Algo & Prog avec R