Feuille 2 — collections, complexité, acteurs & Petri
Collections & fonctions d'ordre supérieur, complexité algorithmique, modèle d'acteurs Akka, réseaux de Petri. La boîte à outils & la théorie.
1. Collections — hiérarchie & bases
val s = Seq(5,1,3); s.head // 5; s.tail // List(1,3); s(1) // 1 (0-idx)
2 +: s // prepend : List(2,5,1,3) (": côté collection")
s :+ 9 // append : List(5,1,3,9)
s ++ Seq(4) // concat : List(5,1,3,4)
1 :: 2 :: Nil // List(1,2) ; l1 ::: l2 concatène 2 List
Set(5,1,1) // Set(5,1) ; & inter · &~ diff · ++ unionMap — accès safe : m(k) peut throw, préférer get → Option.
val m = Map("a"->1, "b"->2)
m("z") // ⚠ NoSuchElementException
m.get("z") // None (Option[Int])
m.getOrElse("z",0) // 0
m + ("c"->3) // ajout (immuable → nouvelle Map)Set/clé de Map = invariants → Set.empty[Int]. String ≡ Seq[Char].
2. Fonctions d'ordre supérieur (clé !)
| méthode | signature | exemple |
|---|---|---|
map | (T=>U) | List(1,2) map(_*10) → List(10,20) |
filter | (T=>Bool) | List(1,2,3) filter(_>1) → List(2,3) |
flatMap | (T=>It[U]) | List(1,2) flatMap(x=>List(x,x)) → List(1,1,2,2) |
flatten | — | List(List(1),List(2)).flatten → List(1,2) |
exists | (T=>Bool):Bool | List(1,2) exists(_>1) → true |
forall | (T=>Bool):Bool | List(2,4) forall(_%2==0) → true |
count | (T=>Bool):Int | List(1,2,3) count(_%2==1) → 2 |
find | (T=>Bool):Opt[T] | List(1,2,3) find(_>1) → Some(2) |
partition | (T=>Bool) | → (ceux vrais, ceux faux) |
take/drop | (n) | List(1,2,3) take 2 → List(1,2) |
groupBy | (T=>K):Map[K,Coll] | List(1,2,3) groupBy(_%2) → Map(1->List(1,3),0->List(2)) |
zip | (It[U]):It[(T,U)] | List(1,2) zip List("a","b") → List((1,a),(2,b)) |
sortBy | (T=>K) | l.sortBy(_.age) |
sum/min/max | — | List(1,2,3).sum → 6 |
Le type de retour = type d'entrée (List→List) ; l'ordre est préservé sur collection ordonnée. Comptage de mots : mots.groupMapReduce(identity)(_=>1)(_+_).
3. for-comprehension & fold
for-yield = sucre pour map / filter / flatMap (⚠ sans yield → boucle Unit).
for (x <- c) yield f(x) // ≡ c.map(f)
for (x <- c if p(x)) yield f(x) // ≡ c.filter(p).map(f)
for (x <- c1; y <- c2) yield (x,y) // ≡ c1.flatMap(x=>c2.map(y=>(x,y)))fold — agrège avec un élément neutre z (collection vide → z) :
foldLeft[U](z:U)(op:(U,T)=>U) // op(op(op(z,a1),a2),a3) — TAIL-REC ✓
foldRight[U](z:U)(op:(T,U)=>U) // op(a1,op(a2,op(a3,z))) — pas tail-rec
List(1,2,3).foldLeft(0)(_+_) // 6
List(1,2,3).foldLeft(10)(_-_) // ((10-1)-2)-3 = 4reduce = fold sans neutre (head comme départ) ; vide → exception (reduceOption → Option).
4. Complexité — O, Ω, Θ
Nb d'opérations élémentaires selon la taille n, indépendant machine/langage. On retient le pire des cas ($\max$).
- $O(g)$ (borne sup) : $\exists\,k,n_0:\forall n\ge n_0,\ 0\le f(n)\le k\,g(n)$
- $\Omega(g)$ (borne inf) : $\ldots\ 0\le k\,g(n)\le f(n)$
- $\Theta(g)$ : $k_1 g(n)\le f(n)\le k_2 g(n)$ ⟺ $O(g)\wedge\Omega(g)$
| $O$ | classe | exemple |
|---|---|---|
| $1$ | constante | accès tableau |
| $\log n$ | logarithmique | dichotomie, PGCD |
| $n$ | linéaire | parcours, factorielle |
| $n\log n$ | quasi-linéaire | tri fusion / rapide |
| $n^2$ | quadratique | tri bulles / sélection |
| $2^n$ | exponentielle | Hanoï, Fibo naïf |
| $n!$ | factorielle | permutations |
Règles : séquence = somme (max domine) · boucles imbriquées = produit · on garde le terme dominant ($12n^2{-}13n{+}17=O(n^2)$).
5. Récurrences & théorème Master
| algo | récurrence | résultat |
|---|---|---|
| factorielle | $T(n)=T(n{-}1)+c$ | $\Theta(n)$ |
| Hanoï | $T(n)=2T(n{-}1)+1$ | $2^n{-}1=\Theta(2^n)$ |
| Fibonacci | $T(n)=T(n{-}1)+T(n{-}2)$ | $\Theta(\varphi^n),\ \varphi=\frac{1+\sqrt5}{2}$ |
| PGCD (Euclide) | via Fibonacci | $O(\log n)$ |
| tri fusion | $T(n)=2T(n/2)+\Theta(n)$ | $\Theta(n\log n)$ |
Récurrence linéaire ordre 2 $u_{n+2}=a\,u_{n+1}+b\,u_n$ → éq. caractéristique $x^2-ax-b=0$ (Fibo : $x^2-x-1=0$).
6. Akka — modèle d'acteurs
Pas de mémoire partagée : on communique par messages. Chaque acteur a un état privé, une mailbox, traite ses messages un à un → pas de mutex, pas de race.
class Serveur extends Actor {
def receive: Receive = { // = PartialFunction[Any,Unit]
case Factorial(n) => sender() ! Result(fact(n)) // répond
case _ => sender() ! "?"
}
}
val sys = ActorSystem("S")
val a = sys.actorOf(Props[Serveur], "serv") // → ActorRef
a ! Factorial(5) // ! = tell, async, fire-and-forget
val fut = a ? Factorial(5) // ? = ask → Future (+ implicit Timeout)Messages = sealed trait + case class/object (exhaustivité). context.actorSelection("/user/serv") pour trouver par chemin. Hooks : preStart / postStop.
7. Philosophes & interblocage
5 philosophes, 1 fourchette entre chaque ; manger = tenir les 2 fourchettes. Deadlock : tous prennent leur gauche → personne n'a la droite.
arbitre central : donne les 2 fourchettes ou aucune (casse détention+attente).
prendre d'abord la fourchette de plus petit numéro (casse l'attente circulaire).
8. Réseaux de Petri
$N=(P,T,F,M_0)$ · places ○ (états/ressources) · transitions ▭ (actions) · arcs F (pondérés, 1 par défaut) · $M_0$ marquage initial (jetons).
t franchissable ssi chaque place d'entrée a ≥ poids de l'arc. Tirer consomme les jetons d'entrée et produit ceux de sortie (atomique).
Matriciel : Pre (arcs entrants), Post (sortants), incidence $C = Post - Pre$. Après une séquence $s$ (s[t] = nb tirages) : $M' = M + C\cdot s$.