Sujet
Le projet est à réaliser individuellement et devra être rendu d'ici la fin du semestre.
Objectifs
Les deux objectifs du projet sont les suivants :
- calculer une valeur approximative de π à l'aide d'une simulation de Monte-Carlo ;
- générer une image animée représentant la simulation comme ci-dessous.
Pour calculer une approximation de π à l'aide d'une simulation de Monte-Carlo en tirant n
points aléatoires (comme au casino), un algorithme simple est le suivant :
- initialiser un compteur à 0 ;
- pour
i
allant de1
àn
:- générer un point aléatoire
(x,y)
dans un carré de longueur 2 et de centre(0,0)
. Pour cela il suffit de générerx
dans[-1,1]
ety
dans[-1,1]
; - si le point est dans le cercle de centre
(0,0)
et de rayon1
, ajouter 1 au compteur ;
- générer un point aléatoire
- l'estimation de π/4 est la valeur du compteur divisée par le nombre
n
.
Pour en savoir plus sur le sujet, nous nous référerons au très clair billet de Bruno Tuffin sur le site interstices.info.
Pour la création de l'image animée, nous générerons des images au format PPM
puis nous les agrégerons comme expliqué dans la prochaine section.
Travail à réaliser
Le travail à réaliser se décompose en deux parties.
Première partie : simulation
La première partie du projet consiste à écrire un module Python simulator.py
qui sera le coeur de notre simulation.
Autrement dit, ce module se charge uniquement du travail en lien avec le calcul d'une approximation de π sans se préoccuper des questions de visualisation sous forme d'image.
Il est demandé que le module simulator.py
soit également un programme exécutable permettant de donner une approximation de π en utilisant un nombre de points donné sur la ligne de commande tel qu'illustré ci-dessous :
1 2 |
|
Deuxième partie : génération d'images PPM
Nous allons maintenant utiliser simulator.py
comme un module pour passer aux choses sérieuses, c'est à dire à la génération de notre image animée représentant une simulation.
Le travail demandé consiste à écrire un programme Python approximate_pi.py
qui :
- reçoit 3 arguments dans l'ordre suivant depuis la ligne de commande :
- la taille de l'image en pixels (qui est carrée, donc un seul entier) ;
- le nombre de point
n
à utiliser dans la simulation ; - le nombre de chiffres après la virgule à utiliser dans l'affichage de la valeur approximative de π.
- implémente une fonction
generate_ppm_file(...)
qui génère une image au format PPM. L'image doit montrer les points qui sont à l'intérieur du cercle d'une certaine couleur, les points qui sont à l'extérieur du cercle d'une autre couleur et la valeur approchée de π comme l'illustre l'image animée ci-dessus. Le nom de l'image doit être au formatimg0_3-13776.ppm
:0
indique le numéro de l'image dans la simulation totale (0
en l'occurrence, donc la première image) et3-13776
correspond à l'approximation courante de π en utilisant le nombre de chiffres après la virgule spécifié sur la ligne de commande (5 en l'occurrence). La signature de la fonction n'est volontairement pas donnée pour que chacun puisse réaliser sa propre solution ; - génère une image
PPM
, en utilisant la fonctiongenerate_ppm_file
, représentant l'état courant de la simulation à chaque fois qu'un dixième du nombre total de points a été tiré. Dix images seront donc générées ; - utilise le programme
convert
pour créer une image animée au formatGIF
à partir des dix imagesPPM
.
Évaluation
Critères d'évaluation
L'évaluation du projet se fera sur la base des critères suivants :
- justesse du code : le programme réalise bien ce qui est demandé ;
- qualité du code : utilisation d'au moins deux modules tel que demandé ci-dessus et utilisation de
pylint
. Le fichier de configuration pour pylint est disponible ici. Ce fichier doit être placé à la racine de votre répertoire personnel et doit être nommé.pylintrc
; - performance du programme en fonction des entrées ;
- utilisation mémoire du programme en fonction des entrées ;
- le poids des images
PPM
générées (c'est à dire le nombre d'octets sur le disque dur) ; - respect des consignes ci-dessous.
À titre d'information, le programme qui a généré l'image animée ci-dessus correspondant a une simulation avec un million de point a pris environ 9 secondes (sur un ordinateur portable récent assez haut de gamme) et a utilisé un maximum de 205 mégaoctets de mémoire à un instant donné.
Les dix images PPM
générées, d'une taille de 800 x 800, pèsent 1,9 mégaoctets chacune.
Des tests automatiques seront utilisés sur votre code afin d'évaluer ces critères.
Rendu
À la fin du projet, vous devez rendre :
- votre code, c'est à dire uniquement vos fichiers Python ;
- un rapport de deux pages maximum.
Dans le rapport vous présenterez, en argumentant, l'état de votre programme vis à vis des critères ci-dessus. Comme le rapport est limité à deux pages, il ne faut surtout pas reprendre le sujet mais présenter directement vos arguments.
Consignes à respecter
Il est demandé de respecter les consignes suivantes dans votre code :
- lancer une exception sans l'attraper si une ou plusieurs entrées incorrectes sont données par l'utilisateur sur la ligne de commande. Autrement dit, si l'utilisateur lance le programme avec
./approximate_pi.py tutu 10000 4
ou avec./approximate_pi.py -800 100000 4
il doit voir dans son terminal une erreur indiquant l'exception qui a été lancée ainsi que la pile d'appels. L'interpréteur se charge de tout cet affichage pour nous quand on lance une exception et que celle-ci n'est jamais attrapée et donc remonte jusqu'au sommet de la pile d'appels ; - utiliser des
f-string
quand cela est pertinent ; - utiliser le module
subprocess
pour générer l'image animéeGIF
à partir des imagesPPM
;
Résumé des consignes et précisions apportées au fil du projet sur le salon général BPI
- ne pas mettre son nom ni dans le rapport ni dans les fichiers Python (c'est pour corriger de façon anonyme) ;
- des valeurs raisonnables, disons entre 1 et 7, seront utilisées pour le paramètre nombre de décimales ;
- l'archive ne doit contenir que vos fichiers Python et votre rapport, rien d'autre ;
- vous pouvez utiliser des modules externes comme
numpy
, même si ce n'est pas du tout nécessaire ; - vous pouvez utiliser
PIL
ou autre chose pour rajouter le texte de π par dessus votre image, même si l'objectif premier était de le coder à la main en pensant à l'afficheur 7 segments de votre gadget électronique préféré ; - le temps d'exécution absolu de votre programme sur des entrées particulières n'est pas très important. Ce qui compte surtout, c'est l'évolution du temps en fonction des entrées, c'est à dire la complexité ;
- idem pour l'utilisation mémoire ;
- le module
simulator.py
doit fournir à minima les points aléatoires au programmeapproximate_pi.py
ainsi que la fonction indiquant si un point est dans le cercle unitaire ou non ; - idéalement, la taille du texte de π par dessus votre image s'adapte à la taille de l'image ;
- aucun problème si votre programme est capable de prendre des arguments optionnels en plus des 3 arguments obligatoires ;
- respecter scrupuleusement les noms des fichiers Python et image indiqués sur cette page un peu plus haut ;
Cliquez ici pour révéler la correction.
Correction
Voici ci-dessous deux propositions de correction.
D'autres solutions faisant des choix différents impliquant éventuellement des complexité mémoire et temps de calcul différentes, néanmoins toutes aussi raisonnables sont possibles.
On peut notamment citer une autre solution consistant à stocker toute l'image en mémoire via une list
ou un bytearray
et "écrire les pixels" directement au bon endroit dans cette list
ou ce bytearray
.
N'hésitez pas à contacter vos enseignants si vous voulez discuter d'une solution particulière.
simulator.py
Les points clés sont les suivants :
-
la fonction génératrice
simulate_iterator(nb_point)
renvoie un itérateur permettant de tirer aléatoirementnb_point
points(x, y)
avec x dans[-1, 1]
et y dans[-1, 1]
. En plus du point courant, l'itérateur renvoie un booléen indiquant si le point courant est dans le cercle ou non ainsi que le nombre de points déjà tirés appartenant au cercle ; -
lorsque
simulator.py
est utilisé comme programme principal, on crée simplement un itérateur avec la fonction génératricesimulate_iterator(nb_point)
puis on le parcours entièrement sans rien faire juste pour récupérer le nombre total de points dans le cercle. Avec cette valeur on calcul l'approximation de π. La complexité mémoire du programme est donc constante et la complexité en temps de calcul est une fonction linéaire du nombre de points.
1 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
|
approximate_pi.py
Les points clés sont les suivants :
- comme indiqué ci-dessous,
simulator.py
ne stocke jamais les points tirés aléatoirement dans une liste mais fourni un itérateur sur ces points ; - on ne stocke jamais toute l'image en mémoire mais seulement les pixels correspondant aux points déjà tirés aléatoirement par
simulator.py
; - dans l'algorithme 1, le fait de ne jamais stocker toute l'image en mémoire implique la nécessité de trier ces pixels avant de dessiner une image
PPM
pour avoir une complexité en temps de calcul raisonnable ; - dans l'algorithme 2, on utilise le fait que la recherche d'appartenance à un
set
se fait en temps constant.
1 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 |
|