Travaux Pratiques #6
Algo & Prog avec R

Table des matières

1. Recherche d’éléments dans un vecteur
2. Recherche de maximum
3. La baguette chanceuse
4. Flux d’élèves KEY
5. Nombres premiers KEY
6. Vectorisation ou fonction prédéfinie Filter
7. Nombres aléatoires absents
8. Compression d’un vecteur
9. Masque d’une chaîne
10. Recherche d’un motif HOME
11. Produit de nombres premiers HOME

1. Recherche d’éléments dans un vecteur

Programmez des fonctions avec boucle répondant aux questions ci-dessous.

Déterminez le nombre de 0 présent dans un vecteur.
Déterminez l’indice du premier 0 d’un vecteur.
Déterminez le plus petit élément non nul d’un vecteur.
Déterminez la valeur médiane d’un vecteur. Indice : sort.

Le code ci-dessous répond aux questions avec des fonctions prédéfinies.

Count0 <- function(vec) sum(vec == 0)
Which0 <- function(vec) head(which(vec == 0), 1)
Min0 <- function(vec) min(vec[ vec != 0])

vec <- sample(0:10,12, replace=TRUE)
print(vec)
Count0(vec)
Which0(vec)
Min0(vec)
median(vec)

2. Recherche de maximum

Recherche simple

Vous ne devez pas utiliser les fonctions prédéfinies max ou which.max dans cette partie

Programmez la fonction Max2(a, b) prenant en argument deux nombres a et b, et retournant le maximum de ces deux nombres.
Programmez la fonction Max3(a, b, c) renvoyant le maximum de trois nombres a et b, et c.
Programmez la fonction MaxV(x) prenant un vecteur numérique x et retournant le maximum de x.

Recherche à partir d’une position

Programmez la fonction MaxFrom(x,i) prenant un vecteur numérique x et retournant le maximum de x à partir de l’indice i inclus.

Avec une boucle.

print(MaxFrom(numeric(0), 1))
x <- sample(1:100, 6, replace = TRUE)
print(x)
print(MaxFrom(x,0))
print(MaxFrom(x,4))
print(MaxFrom(x,7))

[1] -Inf
[1] 51 57 98 30 19 75
[1] 98
[1] 75
[1] -Inf

Avec des fonctions prédéfinies. Indices : tail et max.

Recherche de la valeur et de la position

Programmer une fonction MaxAndIdx(x) prenant en argument un vecteur x numérique, et retournant un vecteur contenant le plus grand élément et sa position.

Avec une boucle.

x <- runif(6);
print(x)
print(MaxAndIdx(x))

[1] 0.2560613 0.7291801 0.5234866 0.2992518 0.3504035 0.4288227
[1] 0.7291801 2.0000000

Avec des fonctions prédéfinies. Indice : which.max.

Attention, l’affichage facilite la lecture, mais peut induire en erreur sur le type des données.

x <- c(0, 0.25, 0.5)
print(x)
print(x[-2])
print(x[1])
print(typeof(x[1]))

[1] 0.00 0.25 0.50
[1] 0.0 0.5
[1] 0
[1] "double"

Recherche des k plus grands éléments.

Programmez une fonction avec une boucle Max2(x) prenant un vecteur x numérique, et retournant le couple des deux plus grands éléments de x, le maximum étant en première position.
```
print(Max2(numeric(0)))
x <- runif(6);
print(x)
print(Max2(x))
```
```
[1] -Inf -Inf
[1] 0.6031135 0.1285228 0.3853113 0.7070992 0.7411141 0.9772133
[1] 0.9772133 0.7411141
```
Programmez une fonction avec des boucles MaxK(x, k) prenant un vecteur x numérique, et retournant les k plus grands éléments de x triés par ordre non croissant. Indices : inspirez-vous du tri par sélection.

Reprogrammez une fonction MaxK(x, k) avec des fonctions prédéfinies. Indices : sort et head.

x <- sample(1:100, 6, replace = TRUE)
print(x)
print(MaxK(x, 0))
print(MaxK(x, 2))
print(MaxK(x, 4))
print(MaxK(x, 7))

[1] 40 25 25 37 97 56
integer(0)
[1] 97 56
[1] 97 56 40 37
[1] 97 56 40 37 25 25

3. La baguette chanceuse

J’ai dans ma poche 2 pièces de 10 centimes, 1 pièce de 20 centimes, 3 pièces de 50 centimes, 1 pièce de 1 euro et 2 pièces de 2 euro. Quelle est la probabilité pour qu’en sortant deux pièces au hasard de ma poche, je puisse payer une baguette à 1 euro. ?

Estimez la probabilité par simulation. Indice: replicate
Calculez la probabilité théorique.

4. Flux d’élèves KEY

En l’an 2000, le lycée A compte 2 000 élèves et le lycée B compte 8 000 élèves. Une étude montre que, chaque année :

10% des élèves du lycée A quittent leur lycée pour aller au lycée B ;
15% des élèves du lycée B quittent leur lycée pour aller au lycée A.
1. Au bout de combien de temps le lycée A comptera-t-il plus d’élèves que le lycée B ?
2. Quelle est l’évolution de ce système dynamique ? Est-ce qu’il atteint un état stationnaire ? Si oui, caractèrisez-le.
3. Tracer un graphique illustrant l’évolution de ce système dynamique. Que se passe t’il ? Expliquez.
4. Que se passe t’il si 15% des élèves du lycée A quittent leur lycée pour aller au lycée B ? Que remarquez-vous ?

plot(na, type = 'b', xlab = "Année", ylab = "Effectif", lty = 1, pch = 1)
lines(nb, type = 'b', lty = 2, pch = 2)

Attention, il est possible que vous deviez spécifier les paramètres xlim et ylim. Cherchez dans la documentation.

5. Nombres premiers KEY

Reprenons le cours sur les nombres premiers. La fonction EstPremier(n) retourne False si elle trouve un diviseur non trivial (dans [2,n-1]) de n. Nous voudrions connaître ce diviseur !

Programmez avec une boucle une fonction PlusPetitDiv(n) prenant un entier n ≥ 2 et retournant son plus petit diviseur $\geq 2$. Par exemple PlusPetitDiv(35) renvoie la valeur 5. Notez au passage que le résultat de PlusPetitDiv(n) est le plus petit facteur premier de n (pourquoi ?).
En déduire une nouvelle version en une ligne de la fonction EstPremier(n).
Faites afficher tous les nombres premiers jusqu’à 100.
Il est souvent intéressant d’accélérer un algorithme. Accélérons donc PlusPetitDiv. Montrez par un raisonnement mathématique très simple que s’il n’existe aucun diviseur de n dans $[2,\sqrt{n}]$ alors PlusPetitDiv(n) == n, ce qui évite de chercher dans le gros intervalle $[\sqrt{n},n]$. Implémentez cette optimisation. Au passage, accélérez encore en évitant de considérer les nombres pairs qui à part 2, ne sont pas premiers.

6. Vectorisation ou fonction prédéfinie `Filter`

Vous ne devez utiliser aucune boucle.

Nombres non multiples d’un entier k

Programmez une fonction NoMult(k,a,b) retournant le vecteur des entiers non multiples de k dans l’intervalle [a,b]. Essayez de programmer une fonction sans boucle, en la vectorisant ou utilisant la fonction filter.

NoMult(5,10,30)

[1] 11 12 13 14 16 17 18 19 21 22 23 24 26 27 28 29

NoMult(2,11,31)

[1] 11 13 15 17 19 21 23 25 27 29 31

Nombres premiers avec un entier k HARD

Programmez une fonction CoPremiers(k,a,b) retournant le vecteur des entiers copremiers avec k dans l’intervalle [a,b].
```
CoPremiers(15,10,30)
```
```
[1] 11 13 14 16 17 19 22 23 26 28 29
```
Programmez une fonction CoPremiersPGCD(k,a,b) avec les mêmes spécifications, mais utilisant une fonction auxiliaire calculant le pgcd de deux entiers de manière itérative.
Programmez une fonction TestCoPremiers(func, n) qui affiche le résultat des tests de performance de catégorie n (à définir) pour la fonction func passée en paramètre. Comparer les performances des deux fonctions. Quelle est la plus efficace en théorie ? En pratique ?

7. Nombres aléatoires absents

Utilisez la fonction sample pour créer une liste de 100 entiers compris entre 1 et 100 tirés au hasard avec remise.
Calculer le nombre d’éléments compris entre 1 et 100 qui n’appartiennent pas à cette liste.
Recommencer cette expérience un grand nombre de fois et calculer la moyenne du nombre d’absents.
Comparer à la valeur théorique.

8. Compression d’un vecteur

Programmez une fonction Compacter(x) prenant un vecteur x et remplaçant toute suite d’éléments consécutifs x, x,…, x par le seul élément x.
```
x <- c(3,3,3,8,5,5,5,7,7)
Compacter(x)
Compacter(c(1,x,9))
Compacter(c(x,x))
```
```
[1] 3 8 5 7
[1] 1 3 8 5 7 9
[1] 3 8 5 7 3 8 5 7
```
Programmez une fonction Compacter(x) vectorisée. Indice : utiliser les fonctions diff et as.logical.
Modifiez la fonction Compacter de sorte qu’elle indique en plus la longueur de chaque sous-suite d’éléments consécutifs. HARD
La fonction renvoie une liste nommée contenant deux vecteurs.
```
Compacter(x)
```
```
$values
[1] 3 8 5 7

$lengths
[1] 3 1 3 2
```
```
Compacter(c(1,x,9))
```
```
$values
[1] 1 3 8 5 7 9

$lengths
[1] 1 3 1 3 2 1
```

9. Masque d’une chaîne

Programmez une fonction Masque(s,x) prenant un vecteur x numérique et une chaîne s, et retournant une nouvelle chaîne contenant les caractères dont les positions dans s figurent dans la liste x.

Masque("CAGCTACCTA",c(2,5,3,8))

[1] "ATGC"

Attention : les chaînes de caractères ne sont pas des vecteurs.

10. Recherche d’un motif HOME

Nous poursuivons l’exercice complémentaire du TP3, dont nous supposons que vous avez programmé la fonction CountSubstringMatch(s1,s2) dont vous allez vous inspirer. Programmez une fonction SubstringMatchExact(s1,s2) retournant le vecteur contenant les positions successives de l’apparition de s2 dans s1.

SubstringMatchExact('atatata','ata')

[1] 1 3 5

SubstringMatchExact('atgacatgcacaagtatgcat','atgc')

[1]  6 16

11. Produit de nombres premiers HOME

D’après le cours Python du MIT.

La théorie des nombres sait démontrer que si $P_n$ dénote le produit de tous les nombres premiers jusqu’à $n$, alors : \[ \lim_{n\rightarrow +\infty} \frac{P_n}{e^n}=1 \quad (\text{en maths } P_n \sim e^n) \] Mais calculer le produit d’un grand nombre d’entiers premiers va produire un très grand nombre ce qui peut nous occasionner des problèmes de calcul. Une manière d’y remédier est de remplacer les multiplications par des additions. Les logarithmes existent précisément dans ce but. Nous allons donc remplacer le produit des nombres premiers par la somme $S_n$ de leur logarithme.

Montrez que le théorème précédent s’exprime alors sous la forme : $S_n \sim n$. Attention, ne croyez pas que $f \sim g$ entraîne toujours $\log(f) \sim \log(g)$. Mais c’est vrai ici car elles tendent vers $+\infty$. Tâchez de faire une petite démonstration si possible, ou parlez-en à votre prof de maths.
La fonction logarithme (népérien) de R est log. Comment utiliseriez-vous l’ordinateur et le langage R pour vous convaincre du bien-fondé de ce théorème ?

Travaux Pratiques #6Algo & Prog avec R