From: couchot Date: Fri, 24 Jun 2016 12:46:52 +0000 (+0200) Subject: modification section stopping time X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/commitdiff_plain/c7c7f9b7e2309f3817f329f4c1cd8d1588055370?ds=sidebyside modification section stopping time --- diff --git a/complexity.eps b/complexity.eps new file mode 100644 index 0000000..41e0c2b --- /dev/null +++ b/complexity.eps @@ -0,0 +1,1324 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%Title: complexity.eps +%%Creator: matplotlib version 1.5.1, http://matplotlib.org/ +%%CreationDate: Fri Jun 24 14:36:55 2016 +%%Orientation: portrait +%%BoundingBox: 18 180 594 612 +%%EndComments +%%BeginProlog +/mpldict 8 dict def +mpldict begin +/m { moveto } bind def +/l { lineto } bind def +/r { rlineto } bind def +/c { curveto } bind def +/cl { closepath } bind def +/box { +m +1 index 0 r +0 exch r +neg 0 r +cl +} bind def +/clipbox { +box +clip +newpath +} bind def +%!PS-Adobe-3.0 Resource-Font +%%Title: Bitstream Vera Sans +%%Copyright: Copyright (c) 2003 by Bitstream, Inc. All Rights Reserved. +%%Creator: Converted from TrueType to type 3 by PPR +25 dict begin +/_d{bind def}bind def +/_m{moveto}_d +/_l{lineto}_d +/_cl{closepath eofill}_d +/_c{curveto}_d +/_sc{7 -1 roll{setcachedevice}{pop pop pop pop pop pop}ifelse}_d +/_e{exec}_d +/FontName /BitstreamVeraSans-Roman def +/PaintType 0 def +/FontMatrix[.001 0 0 .001 0 0]def +/FontBBox[-183 -236 1287 928]def +/FontType 3 def +/Encoding [ /space /parenleft /parenright /plus /zero /one /two /four /six /eight /a /e /i /l /m /n /o /p /r /t /u /v /x ] def +/FontInfo 10 dict dup begin +/FamilyName (Bitstream Vera Sans) def +/FullName (Bitstream Vera Sans) def +/Notice (Copyright (c) 2003 by Bitstream, Inc. All Rights Reserved. Bitstream Vera is a trademark of Bitstream, Inc.) def +/Weight (Roman) def +/Version (Release 1.10) def +/ItalicAngle 0.0 def +/isFixedPitch false def +/UnderlinePosition -213 def +/UnderlineThickness 143 def +end readonly def +/CharStrings 23 dict dup begin +/space{318 0 0 0 0 0 _sc +}_d +/parenleft{390 0 86 -131 310 759 _sc +310 759 _m +266 683 234 609 213 536 _c +191 463 181 389 181 314 _c +181 238 191 164 213 91 _c +234 17 266 -56 310 -131 _c +232 -131 _l +183 -54 146 20 122 94 _c +98 168 86 241 86 314 _c +86 386 98 459 122 533 _c +146 607 182 682 232 759 _c +310 759 _l +_cl}_d +/parenright{390 0 80 -131 304 759 _sc +80 759 _m +158 759 _l +206 682 243 607 267 533 _c +291 459 304 386 304 314 _c +304 241 291 168 267 94 _c +243 20 206 -54 158 -131 _c +80 -131 _l +123 -56 155 17 177 91 _c +198 164 209 238 209 314 _c +209 389 198 463 177 536 _c +155 609 123 683 80 759 _c +_cl}_d +/plus{838 0 106 0 732 627 _sc +460 627 _m +460 355 _l +732 355 _l +732 272 _l +460 272 _l +460 0 _l +378 0 _l +378 272 _l +106 272 _l +106 355 _l +378 355 _l +378 627 _l +460 627 _l +_cl}_d +/zero{636 0 66 -13 570 742 _sc +318 664 _m +267 664 229 639 203 589 _c +177 539 165 464 165 364 _c +165 264 177 189 203 139 _c +229 89 267 64 318 64 _c +369 64 407 89 433 139 _c +458 189 471 264 471 364 _c +471 464 458 539 433 589 _c +407 639 369 664 318 664 _c +318 742 _m +399 742 461 709 505 645 _c +548 580 570 486 570 364 _c +570 241 548 147 505 83 _c +461 19 399 -13 318 -13 _c +236 -13 173 19 130 83 _c +87 147 66 241 66 364 _c +66 486 87 580 130 645 _c +173 709 236 742 318 742 _c +_cl}_d +/one{636 0 110 0 544 729 _sc +124 83 _m +285 83 _l +285 639 _l +110 604 _l +110 694 _l +284 729 _l +383 729 _l +383 83 _l +544 83 _l +544 0 _l +124 0 _l +124 83 _l +_cl}_d +/two{{636 0 73 0 536 742 _sc +192 83 _m +536 83 _l +536 0 _l +73 0 _l +73 83 _l +110 121 161 173 226 239 _c +290 304 331 346 348 365 _c +380 400 402 430 414 455 _c +426 479 433 504 433 528 _c +433 566 419 598 392 622 _c +365 646 330 659 286 659 _c +255 659 222 653 188 643 _c +154 632 117 616 78 594 _c +78 694 _l +118 710 155 722 189 730 _c +223 738 255 742 284 742 _c +}_e{359 742 419 723 464 685 _c +509 647 532 597 532 534 _c +532 504 526 475 515 449 _c +504 422 484 390 454 354 _c +446 344 420 317 376 272 _c +332 227 271 164 192 83 _c +_cl}_e}_d +/four{636 0 49 0 580 729 _sc +378 643 _m +129 254 _l +378 254 _l +378 643 _l +352 729 _m +476 729 _l +476 254 _l +580 254 _l +580 172 _l +476 172 _l +476 0 _l +378 0 _l +378 172 _l +49 172 _l +49 267 _l +352 729 _l +_cl}_d +/six{{636 0 70 -13 573 742 _sc +330 404 _m +286 404 251 388 225 358 _c +199 328 186 286 186 234 _c +186 181 199 139 225 109 _c +251 79 286 64 330 64 _c +374 64 409 79 435 109 _c +461 139 474 181 474 234 _c +474 286 461 328 435 358 _c +409 388 374 404 330 404 _c +526 713 _m +526 623 _l +501 635 476 644 451 650 _c +425 656 400 659 376 659 _c +310 659 260 637 226 593 _c +}_e{192 549 172 482 168 394 _c +187 422 211 444 240 459 _c +269 474 301 482 336 482 _c +409 482 467 459 509 415 _c +551 371 573 310 573 234 _c +573 159 550 99 506 54 _c +462 9 403 -13 330 -13 _c +246 -13 181 19 137 83 _c +92 147 70 241 70 364 _c +70 479 97 571 152 639 _c +206 707 280 742 372 742 _c +396 742 421 739 447 735 _c +472 730 498 723 526 713 _c +_cl}_e}_d +/eight{{636 0 68 -13 568 742 _sc +318 346 _m +271 346 234 333 207 308 _c +180 283 167 249 167 205 _c +167 161 180 126 207 101 _c +234 76 271 64 318 64 _c +364 64 401 76 428 102 _c +455 127 469 161 469 205 _c +469 249 455 283 429 308 _c +402 333 365 346 318 346 _c +219 388 _m +177 398 144 418 120 447 _c +96 476 85 511 85 553 _c +85 611 105 657 147 691 _c +188 725 245 742 318 742 _c +}_e{390 742 447 725 489 691 _c +530 657 551 611 551 553 _c +551 511 539 476 515 447 _c +491 418 459 398 417 388 _c +464 377 501 355 528 323 _c +554 291 568 251 568 205 _c +568 134 546 80 503 43 _c +459 5 398 -13 318 -13 _c +237 -13 175 5 132 43 _c +89 80 68 134 68 205 _c +68 251 81 291 108 323 _c +134 355 171 377 219 388 _c +183 544 _m +183 506 194 476 218 455 _c +}_e{242 434 275 424 318 424 _c +360 424 393 434 417 455 _c +441 476 453 506 453 544 _c +453 582 441 611 417 632 _c +393 653 360 664 318 664 _c +275 664 242 653 218 632 _c +194 611 183 582 183 544 _c +_cl}_e}_d +/a{{613 0 60 -13 522 560 _sc +343 275 _m +270 275 220 266 192 250 _c +164 233 150 205 150 165 _c +150 133 160 107 181 89 _c +202 70 231 61 267 61 _c +317 61 357 78 387 114 _c +417 149 432 196 432 255 _c +432 275 _l +343 275 _l +522 312 _m +522 0 _l +432 0 _l +432 83 _l +411 49 385 25 355 10 _c +325 -5 287 -13 243 -13 _c +187 -13 142 2 109 33 _c +76 64 60 106 60 159 _c +}_e{60 220 80 266 122 298 _c +163 329 224 345 306 345 _c +432 345 _l +432 354 _l +432 395 418 427 391 450 _c +364 472 326 484 277 484 _c +245 484 215 480 185 472 _c +155 464 127 453 100 439 _c +100 522 _l +132 534 164 544 195 550 _c +226 556 256 560 286 560 _c +365 560 424 539 463 498 _c +502 457 522 395 522 312 _c +_cl}_e}_d +/e{{615 0 55 -13 562 560 _sc +562 296 _m +562 252 _l +149 252 _l +153 190 171 142 205 110 _c +238 78 284 62 344 62 _c +378 62 412 66 444 74 _c +476 82 509 95 541 113 _c +541 28 _l +509 14 476 3 442 -3 _c +408 -9 373 -13 339 -13 _c +251 -13 182 12 131 62 _c +80 112 55 181 55 268 _c +55 357 79 428 127 481 _c +175 533 241 560 323 560 _c +397 560 455 536 498 489 _c +}_e{540 441 562 377 562 296 _c +472 322 _m +471 371 457 410 431 440 _c +404 469 368 484 324 484 _c +274 484 234 469 204 441 _c +174 413 156 373 152 322 _c +472 322 _l +_cl}_e}_d +/i{278 0 94 0 184 760 _sc +94 547 _m +184 547 _l +184 0 _l +94 0 _l +94 547 _l +94 760 _m +184 760 _l +184 646 _l +94 646 _l +94 760 _l +_cl}_d +/l{278 0 94 0 184 760 _sc +94 760 _m +184 760 _l +184 0 _l +94 0 _l +94 760 _l +_cl}_d +/m{{974 0 91 0 889 560 _sc +520 442 _m +542 482 569 511 600 531 _c +631 550 668 560 711 560 _c +767 560 811 540 842 500 _c +873 460 889 403 889 330 _c +889 0 _l +799 0 _l +799 327 _l +799 379 789 418 771 444 _c +752 469 724 482 686 482 _c +639 482 602 466 575 435 _c +548 404 535 362 535 309 _c +535 0 _l +445 0 _l +445 327 _l +445 379 435 418 417 444 _c +398 469 369 482 331 482 _c +}_e{285 482 248 466 221 435 _c +194 404 181 362 181 309 _c +181 0 _l +91 0 _l +91 547 _l +181 547 _l +181 462 _l +201 495 226 520 255 536 _c +283 552 317 560 357 560 _c +397 560 430 550 458 530 _c +486 510 506 480 520 442 _c +_cl}_e}_d +/n{634 0 91 0 549 560 _sc +549 330 _m +549 0 _l +459 0 _l +459 327 _l +459 379 448 417 428 443 _c +408 469 378 482 338 482 _c +289 482 251 466 223 435 _c +195 404 181 362 181 309 _c +181 0 _l +91 0 _l +91 547 _l +181 547 _l +181 462 _l +202 494 227 519 257 535 _c +286 551 320 560 358 560 _c +420 560 468 540 500 501 _c +532 462 549 405 549 330 _c +_cl}_d +/o{612 0 55 -13 557 560 _sc +306 484 _m +258 484 220 465 192 427 _c +164 389 150 338 150 273 _c +150 207 163 156 191 118 _c +219 80 257 62 306 62 _c +354 62 392 80 420 118 _c +448 156 462 207 462 273 _c +462 337 448 389 420 427 _c +392 465 354 484 306 484 _c +306 560 _m +384 560 445 534 490 484 _c +534 433 557 363 557 273 _c +557 183 534 113 490 63 _c +445 12 384 -13 306 -13 _c +227 -13 165 12 121 63 _c +77 113 55 183 55 273 _c +55 363 77 433 121 484 _c +165 534 227 560 306 560 _c +_cl}_d +/p{{635 0 91 -207 580 560 _sc +181 82 _m +181 -207 _l +91 -207 _l +91 547 _l +181 547 _l +181 464 _l +199 496 223 520 252 536 _c +281 552 316 560 356 560 _c +422 560 476 533 518 481 _c +559 428 580 359 580 273 _c +580 187 559 117 518 65 _c +476 13 422 -13 356 -13 _c +316 -13 281 -5 252 10 _c +223 25 199 49 181 82 _c +487 273 _m +487 339 473 390 446 428 _c +418 466 381 485 334 485 _c +}_e{286 485 249 466 222 428 _c +194 390 181 339 181 273 _c +181 207 194 155 222 117 _c +249 79 286 61 334 61 _c +381 61 418 79 446 117 _c +473 155 487 207 487 273 _c +_cl}_e}_d +/r{411 0 91 0 411 560 _sc +411 463 _m +401 469 390 473 378 476 _c +366 478 353 480 339 480 _c +288 480 249 463 222 430 _c +194 397 181 350 181 288 _c +181 0 _l +91 0 _l +91 547 _l +181 547 _l +181 462 _l +199 495 224 520 254 536 _c +284 552 321 560 365 560 _c +371 560 378 559 386 559 _c +393 558 401 557 411 555 _c +411 463 _l +_cl}_d +/t{392 0 27 0 368 702 _sc +183 702 _m +183 547 _l +368 547 _l +368 477 _l +183 477 _l +183 180 _l +183 135 189 106 201 94 _c +213 81 238 75 276 75 _c +368 75 _l +368 0 _l +276 0 _l +206 0 158 13 132 39 _c +106 65 93 112 93 180 _c +93 477 _l +27 477 _l +27 547 _l +93 547 _l +93 702 _l +183 702 _l +_cl}_d +/u{634 0 85 -13 543 547 _sc +85 216 _m +85 547 _l +175 547 _l +175 219 _l +175 167 185 129 205 103 _c +225 77 255 64 296 64 _c +344 64 383 79 411 110 _c +439 141 453 183 453 237 _c +453 547 _l +543 547 _l +543 0 _l +453 0 _l +453 84 _l +431 50 405 26 377 10 _c +348 -5 315 -13 277 -13 _c +214 -13 166 6 134 45 _c +101 83 85 140 85 216 _c +_cl}_d +/v{592 0 30 0 562 547 _sc +30 547 _m +125 547 _l +296 88 _l +467 547 _l +562 547 _l +357 0 _l +235 0 _l +30 547 _l +_cl}_d +/x{592 0 29 0 559 547 _sc +549 547 _m +351 281 _l +559 0 _l +453 0 _l +294 215 _l +135 0 _l +29 0 _l +241 286 _l +47 547 _l +153 547 _l +298 352 _l +443 547 _l +549 547 _l +_cl}_d +end readonly def + +/BuildGlyph + {exch begin + CharStrings exch + 2 copy known not{pop /.notdef}if + true 3 1 roll get exec + end}_d + +/BuildChar { + 1 index /Encoding get exch get + 1 index /BuildGlyph get exec +}_d + +FontName currentdict end definefont pop +end +%%EndProlog +mpldict begin +18 180 translate +576 432 0 0 clipbox +100000 setmiterlimit +gsave +0 0 m +576 0 l +576 432 l +0 432 l +cl +1.000 setgray +fill +grestore +gsave +72 43.2 m +518.4 43.2 l +518.4 388.8 l +72 388.8 l +cl +1.000 setgray +fill +grestore +0.500 setlinewidth +1 setlinejoin +0 setlinecap +[] 0 setdash +0.000 setgray +gsave +446.4 345.6 72 43.2 clipbox +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 -3 m +0.795609 -3 1.55874 -2.683901 2.12132 -2.12132 c +2.683901 -1.55874 3 -0.795609 3 0 c +3 0.795609 2.683901 1.55874 2.12132 2.12132 c +1.55874 2.683901 0.795609 3 0 3 c +-0.795609 3 -1.55874 2.683901 -2.12132 2.12132 c +-2.683901 1.55874 -3 0.795609 -3 0 c +-3 -0.795609 -2.683901 -1.55874 -2.12132 -2.12132 c +-1.55874 -2.683901 -0.795609 -3 0 -3 c +cl + +gsave +0.000 0.000 1.000 setrgbcolor +fill +grestore +stroke +grestore +} bind def +72 49.4208 o +109.2 72.2304 o +146.4 96.4224 o +183.6 120.96 o +220.8 146.88 o +258 173.491 o +295.2 200.794 o +332.4 228.096 o +369.6 256.09 o +406.8 285.12 o +444 313.805 o +481.2 344.218 o +518.4 374.976 o +grestore +1.000 setlinewidth +2 setlinecap +1.000 0.000 0.000 setrgbcolor +gsave +446.4 345.6 72 43.2 clipbox +72 50.736533 m +109.2 73.971248 l +146.4 98.319009 l +183.6 123.636998 l +220.8 149.813665 l +258 176.759669 l +295.2 204.401976 l +332.4 232.679839 l +369.6 261.541999 l +406.8 290.944651 l +444 320.849961 l +481.2 351.224933 l +518.4 382.040557 l +stroke +grestore +0 setlinejoin +0.000 setgray +gsave +72 388.8 m +518.4 388.8 l +stroke +grestore +gsave +518.4 43.2 m +518.4 388.8 l +stroke +grestore +gsave +72 43.2 m +518.4 43.2 l +stroke +grestore +gsave +72 43.2 m +72 388.8 l +stroke +grestore +0.500 setlinewidth +1 setlinejoin +0 setlinecap +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +72 43.2 o +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 -4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +72 388.8 o +grestore +/BitstreamVeraSans-Roman findfont +12.000 scalefont +setfont +gsave +68.179688 30.075000 translate +0.000000 rotate +0.000000 0.000000 m /four glyphshow +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +146.4 43.2 o +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 -4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +146.4 388.8 o +grestore +gsave +142.579688 30.075000 translate +0.000000 rotate +0.000000 0.000000 m /six glyphshow +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +220.8 43.2 o +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 -4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +220.8 388.8 o +grestore +gsave +216.979687 30.075000 translate +0.000000 rotate +0.000000 0.000000 m /eight glyphshow +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +295.2 43.2 o +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 -4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +295.2 388.8 o +grestore +gsave +287.559375 30.075000 translate +0.000000 rotate +0.000000 0.000000 m /one glyphshow +7.634766 0.000000 m /zero glyphshow +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +369.6 43.2 o +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 -4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +369.6 388.8 o +grestore +gsave +361.959375 30.075000 translate +0.000000 rotate +0.000000 0.000000 m /one glyphshow +7.634766 0.000000 m /two glyphshow +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +444 43.2 o +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 -4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +444 388.8 o +grestore +gsave +436.359375 30.075000 translate +0.000000 rotate +0.000000 0.000000 m /one glyphshow +7.634766 0.000000 m /four glyphshow +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +518.4 43.2 o +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +0 -4 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +518.4 388.8 o +grestore +gsave +510.759375 30.075000 translate +0.000000 rotate +0.000000 0.000000 m /one glyphshow +7.634766 0.000000 m /six glyphshow +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +4 0 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +72 43.2 o +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +-4 0 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +518.4 43.2 o +grestore +gsave +52.718750 39.887500 translate +0.000000 rotate +0.000000 0.000000 m /two glyphshow +7.634766 0.000000 m /zero glyphshow +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +4 0 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +72 112.32 o +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +-4 0 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +518.4 112.32 o +grestore +gsave +52.718750 109.007500 translate +0.000000 rotate +0.000000 0.000000 m /four glyphshow +7.634766 0.000000 m /zero glyphshow +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +4 0 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +72 181.44 o +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +-4 0 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +518.4 181.44 o +grestore +gsave +52.718750 178.127500 translate +0.000000 rotate +0.000000 0.000000 m /six glyphshow +7.634766 0.000000 m /zero glyphshow +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +4 0 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +72 250.56 o +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +-4 0 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +518.4 250.56 o +grestore +gsave +52.718750 247.247500 translate +0.000000 rotate +0.000000 0.000000 m /eight glyphshow +7.634766 0.000000 m /zero glyphshow +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +4 0 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +72 319.68 o +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +-4 0 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +518.4 319.68 o +grestore +gsave +45.078125 316.367500 translate +0.000000 rotate +0.000000 0.000000 m /one glyphshow +7.634766 0.000000 m /zero glyphshow +15.269531 0.000000 m /zero glyphshow +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +4 0 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +72 388.8 o +grestore +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 0 m +-4 0 l + +gsave +0.000 setgray +fill +grestore +stroke +grestore +} bind def +518.4 388.8 o +grestore +gsave +45.078125 385.487500 translate +0.000000 rotate +0.000000 0.000000 m /one glyphshow +7.634766 0.000000 m /two glyphshow +15.269531 0.000000 m /zero glyphshow +grestore +1.000 setlinewidth +0 setlinejoin +gsave +79.2 335.78625 m +306.899375 335.78625 l +306.899375 381.6 l +79.2 381.6 l +cl +gsave +1.000 setgray +fill +grestore +stroke +grestore +0.500 setlinewidth +1 setlinejoin +gsave +/o { +gsave +newpath +translate +0.5 setlinewidth +1 setlinejoin +0 setlinecap +0 -3 m +0.795609 -3 1.55874 -2.683901 2.12132 -2.12132 c +2.683901 -1.55874 3 -0.795609 3 0 c +3 0.795609 2.683901 1.55874 2.12132 2.12132 c +1.55874 2.683901 0.795609 3 0 3 c +-0.795609 3 -1.55874 2.683901 -2.12132 2.12132 c +-2.683901 1.55874 -3 0.795609 -3 0 c +-3 -0.795609 -2.683901 -1.55874 -2.12132 -2.12132 c +-1.55874 -2.683901 -0.795609 -3 0 -3 c +cl + +gsave +0.000 0.000 1.000 setrgbcolor +fill +grestore +stroke +grestore +} bind def +89.28 370.239 o +109.44 370.239 o +grestore +/BitstreamVeraSans-Roman findfont +14.400 scalefont +setfont +gsave +125.280000 365.199375 translate +0.000000 rotate +0.000000 0.000000 m /e glyphshow +8.843994 0.000000 m /x glyphshow +17.351074 0.000000 m /p glyphshow +26.475830 0.000000 m /e glyphshow +35.319824 0.000000 m /r glyphshow +41.229858 0.000000 m /i glyphshow +45.223694 0.000000 m /m glyphshow +59.226685 0.000000 m /e glyphshow +68.070679 0.000000 m /n glyphshow +77.181396 0.000000 m /t glyphshow +82.817688 0.000000 m /a glyphshow +91.626587 0.000000 m /l glyphshow +95.620422 0.000000 m /space glyphshow +100.189819 0.000000 m /e glyphshow +109.033813 0.000000 m /v glyphshow +117.540894 0.000000 m /a glyphshow +126.349792 0.000000 m /l glyphshow +130.343628 0.000000 m /u glyphshow +139.454346 0.000000 m /a glyphshow +148.263245 0.000000 m /t glyphshow +153.899536 0.000000 m /i glyphshow +157.893372 0.000000 m /o glyphshow +166.688232 0.000000 m /n glyphshow +grestore +1.000 setlinewidth +2 setlinecap +1.000 0.000 0.000 setrgbcolor +gsave +89.28 349.4925 m +109.44 349.4925 l +stroke +grestore +0.000 setgray +gsave +125.280000 344.452500 translate +0.000000 rotate +0.000000 0.000000 m /two glyphshow +9.145813 0.000000 m /x glyphshow +17.652893 0.000000 m /l glyphshow +21.646729 0.000000 m /n glyphshow +30.757446 0.000000 m /parenleft glyphshow +36.365662 0.000000 m /two glyphshow +45.511475 0.000000 m /x glyphshow +54.018555 0.000000 m /plus glyphshow +66.063232 0.000000 m /eight glyphshow +75.209045 0.000000 m /parenright glyphshow +grestore + +end +showpage diff --git a/complexityDisplay.py b/complexityDisplay.py new file mode 100644 index 0000000..60f2c79 --- /dev/null +++ b/complexityDisplay.py @@ -0,0 +1,40 @@ +import math as m +import numpy as np +import matplotlib.pyplot as plt + + +tb = 512 +rhugo,rwow,runiw,rcanny=[],[],[],[] +T=3 + +x = [4 , 5 , 6 , 7, 8 , 9 , 10, 11 , 12 , 13 , 14 , 15 , 16 ] +y = [21.8 , 28.4 , 35.4 , 42.5 , 50 , 57.7 , 65.6, 73.5 , 81.6 , 90 , 98.3 , 107.1 , 116] +yp = [ 2*l*m.log(2*l +8) for l in x] + + +pexp, = plt.plot(x,y,marker='o',label="L1",linestyle='None') + +n=np.linspace(4,16,1) +pd, = plt.plot(x,yp,marker=None,color='r',label="L1") +l1 = plt.legend([pexp,pd], ["experimental evaluation","2xln(2x+8)"], loc=0) + +#plt.show() +plt.savefig("complexity.eps") + +""" +n=np.linspace(512,4096,10) +phugo, = plt.plot(n,2*pow(n,2)*(343**2+np.log(n)),marker='o',label="L1") +pwow, = plt.plot(n,6*pow(n,4)*np.log(n)+pow(n,2),marker='v',label="L2") +pcanny, = plt.plot(n,pow(n,2)*(5**3+4*T+1),marker='x',label="L3") +plt.yscale('log') +plt.ylabel('nb. of primary operations') +plt.xlabel("nb of lines and of rows in each image") +#plt.legend(handles=[phugo], loc=1) +#plt.legend([phugo, pwow], ["Hugo", "Wow/Uniward"]) +l1 = plt.legend([pwow,phugo,pcanny], ["Wow/Uniward","Hugo","Stabylo"], loc=0) +plt.gca().add_artist(l1) +#plt.gca().add_artist(l2) +#plt.gca().add_artist(l3) +plt.savefig("complexity.eps") +#plt.show() +""" diff --git a/main.pdf b/main.pdf index cba5430..4f393a0 100644 Binary files a/main.pdf and b/main.pdf differ diff --git a/stopping.tex b/stopping.tex index fb0b9e0..989bb9e 100644 --- a/stopping.tex +++ b/stopping.tex @@ -376,12 +376,6 @@ number of iterations such that all elements $\ell\in \llbracket 1,{\mathsf{N}} \ by calling this code many times with many instances of function and many seeds. -Practically speaking, for each number $\mathsf{N}$,$ 3 \le \mathsf{N} \le 16$, -10 functions have been generaed according to method presented in section~\ref{sec:hamilton}. For each of them, the calculus of the approximation of $E[\ts]$ -is executed 10000 times with a random seed. The table~\ref{table:stopping:moy} -summarizes results. It can be observed that the approximation is largely -wœsmaller than the upper bound given in theorem~\ref{prop:stop}. - \begin{algorithm}[ht] %\begin{scriptsize} \KwIn{a function $f$, an initial configuration $x^0$ ($\mathsf{N}$ bits)} @@ -389,39 +383,59 @@ wœsmaller than the upper bound given in theorem~\ref{prop:stop}. $\textit{nbit} \leftarrow 0$\; $x\leftarrow x^0$\; -$\textit{visited}\leftarrow\emptyset$\; - -\While{$\left\vert{\textit{visited}}\right\vert < \mathsf{N} $} +$\textit{fair}\leftarrow\emptyset$\; +\While{$\left\vert{\textit{fair}}\right\vert < \mathsf{N} $} { - $ s \leftarrow \textit{Random}(n)$ \; + $ s \leftarrow \textit{Random}(\mathsf{N})$ \; $\textit{image} \leftarrow f(x) $\; - \If{$x[s] \neq \textit{image}[s]$}{ - $\textit{visited} \leftarrow \textit{visited} \cup \{s\}$ + \If{$\textit{Random}(1) \neq 0$ and $x[s] \neq \textit{image}[s]$}{ + $\textit{fair} \leftarrow \textit{fair} \cup \{s\}$\; + $x[s] \leftarrow \textit{image}[s]$\; } - $x[s] \leftarrow \textit{image}[s]$\; $\textit{nbit} \leftarrow \textit{nbit}+1$\; } \Return{$\textit{nbit}$}\; %\end{scriptsize} -\caption{Pseudo Code of the stoping time calculus} +\caption{Pseudo Code of stoping time calculus } \label{algo:stop} \end{algorithm} +Practically speaking, for each number $\mathsf{N}$, $ 3 \le \mathsf{N} \le 16$, +10 functions have been generaed according to method presented in section~\ref{sec:hamilton}. For each of them, the calculus of the approximation of $E[\ts]$ +is executed 10000 times with a random seed. The Figure~\ref{fig:stopping:moy} +summarizes these results. In this one, a circle represents the +approximation of $E[\ts]$ for a given $\mathsf{N}$. +The line is the graph of the function $x \mapsto 2x\ln(2x+8)$. +It can firstly +be observed that the approximation is largely +smaller than the upper bound given in theorem~\ref{prop:stop}. +It can be further deduced that the conjecture of the previous section +is realistic according the graph of $x \mapsto 2x\ln(2x+8)$. -\begin{table} -$$ -\begin{array}{|*{15}{l|}} -\hline -\mathsf{N} & 3 & 4 & 5 & 6 & 7& 8 & 9 & 10& 11 & 12 & 13 & 14 & 15 & 16 \\ -\hline -\mathsf{N} & 3 & 10.9 & 5 & 17.7 & 7& 25 & 9 & 32.7& 11 & 40.8 & 13 & 49.2 & 15 & 16 \\ -\hline -\end{array} -$$ -\caption{Average Stopping Time}\label{table:stopping:moy} -\end{table} + + +% \begin{table} +% $$ +% \begin{array}{|*{14}{l|}} +% \hline +% \mathsf{N} & 4 & 5 & 6 & 7& 8 & 9 & 10& 11 & 12 & 13 & 14 & 15 & 16 \\ +% \hline +% \mathsf{N} & 21.8 & 28.4 & 35.4 & 42.5 & 50 & 57.7 & 65.6& 73.5 & 81.6 & 90 & 98.3 & 107.1 & 16 \\ +% \hline +% \end{array} +% $$ +% \caption{Average Stopping Time}\label{table:stopping:moy} +% \end{table} + +\begin{figure} +\centering +\includegraphics[scale=0.5]{complexity} +\caption{Average Stopping Time Approximation}\label{fig:stopping:moy} +\end{figure} + + %%% Local Variables: %%% mode: latex