profilage de fonction avec scilab

Quand on s'intéresse à la complexité des algorithmes il est intéressant de pouvoir confronter la théorie avec la pratique en vérifiant  quel est le temps d'exécution réel d'un programme et comment ce temps est réparti entre les différentes opérations. Il existe des outils de profilage de code qui permettent d'analyser le coût de chaque ligne de code dans un programme (coût du temps de calcul du processeur ou en mémoire).  Scilab possède quelques fonctionnalités dédiées à ce sujet, que j'avais documenté il y a plus de 10 ans , mais qui ont été complètement remanié. Le développement de Scilab semblant retrouver de l'activité, je me suis donc intéressé aux capacités des nouvelles fonctions de profilage et à l'exploitation graphique des résultats.

 

Divergences entre matlab et octave

Matlab™ ©®  est un des premiers logiciel de calcul numérique créé à la fin des années 80, il reste très utilisé dans le domaine industriel  malgré une syntaxe parfois archaïque et l'existence d'alternatives libres comme GNUoctave, Scilab, ou même Python! Chaque année quand je dois utiliser ce logiciel pour illustrer des cours de calcul numérique, je prépare mes scripts avec GNUoctave et évidement lors des TP je découvre de nouvelles  aberrations "fonctionnalités" toujours plus stupéfiantes  ...

comportement différent entre matlab et GNUoctave
lors de la résolution d'un système linéaire 

Diagrammes de Voronoï et Algorithm de Lloyd

Il m'arrive souvent de voir passer de jolies animations avec des diagrammes de Voronoï, mais je n'avais jamais trouvé l'occasion d'en faire une par moi même,. c'est bien dommage car la manipulation des diagramme de Voronoï est excellent un exercice de modélisation, qui peut se faire avec des structures de données très simples et permet ensuite d'obtenir des sorties graphiques amusantes. Donc aujourd'hui je vous propose d'explorer ce sujet avec l'algorithme de Lloyd.

tracé d'une surface et noeud de trèfle

L'informatique fait souvent croire qu'a l'aide d'un ordinateur on peut réaliser  des opérations très complexes sans comprendre où maîtriser les théories mises en œuvre. Ce mythe est très populaire quand il s'agit de mathématique, a tel point que Claude Allègre, alors ministre de l'éducation nationale, déclarait dans le journal France-soir, du 29/11/99 : "Les maths sont en train de se dévaluer de manière quasi inéluctable. Désormais, il y a des machines pour faire les calculs". Pourtant tracer le graphe  d'une simple surface demande un minimum de compréhension mathématique quelque soit le logiciel utilisé. Petit exemple avec la jolie surface  engendrée par un cercle se déplaçant le long d'un nœud de trèfle!

Tracer l'ensemble de Mandelbrot

Quand on parle de fractale on pense immédiatement à l'ensemble de Mandelbrot. Si cet ensemble a été découvert au début du XXième siècle par Gaston Julia et Pierre Fatou, mais c'est Benoît Mandelbrot qui va en donner les premières représentation graphiques dans les années 1980 ! Aujourd'hui on peut tracer ce mystérieux ensemble en quelques lignes de code (avec Scilab par exemple) et un joli argument mathématique  ...

le stade de Bunimovich et autres billards

mon dernier billet   sur le  billard de Sinaï m'a donné l'envie de continuer mon exploration de ce domaine, par exemple avec le stade de Bunimovich .  

le stade de Bunimovich

billard de Sinaï

Le mathématicien Français Jean-Christophe Yoccoz est décédé le 3 septembre 2016. C'était un spécialiste des systèmes dynamiques et il avait reçu la médaille Fields en 1994  pour ses travaux sur le sujet. Ce domaine de recherche est assez jeune puisqu'on considère  que c'est Henri Poincaré qui a ouvert la voie avec ses travaux sur le problème des trois corps, mais il englobe beaucoup d'autres exemples comme celui des billards. Dans la version la plus simple  un billard est juste un domaine compact du plan (par exemple un polygone) contenant éventuellement des obstacles dans lequel se déplace une particule  animée d'un mouvement uniforme et rebondissant sur les bords . Un des exemples les plus célèbre est le billard de Sinaï  qui modélise  le comportement d'un gaz  parfait et permet de mettre en évidence  les propriétés des billards dispersifs :

une trajectoire dans un billard de Sinaï

premiers pas avec Xcos

Dans le monde de l’ingénierie Matlab est  considéré comme un outil incontournable entre autre par ce qu'il intègre un outil de modélisation de systèmes complexes appelé Simulink. Ce type de logiciel permet, par exemple, de créer virtuellement  un circuit électronique en assemblant  sur un diagramme des composants de base (résistances, diodes, transistors, voltmètres oscilloscopes  ... tous appelés "blocs" )   pour ensuite simuler son  fonctionnement . Scilab possède lui aussi son éditeur de Blocs-Diagrammes,   nommé XCOS, qui permet de simuler  toute sorte de circuits et de faire ses premiers pas en électronique.

la bouteille de Klein

Cela faisait un moment que je cherchais les bonnes formules pour dessiner la représentation usuelle d'une bouteille de Klein  obtenue par recollement non-trivial des  bords d'un cylindre . J'ai fini par y arriver (non sans mal) mais les formules utilisées  gardent encore une part de mystère :

Le serpent Vietnamien et profilage sous Scilab

voici un  petit problème de mathématiques qui a attiré l'attention de nombreux internautes il y a 2 mois de cela : il s'agit de trouver comment placer  les nombres de 1 à 9 (une et une seule fois chacun)  dans les 9 cases  vides  du "serpent" ci-dessous (notées a(i))  pour que le résultat  de la formule obtenue  soit égal à  66 :

a(1)+13*a(2)/a(3)+a(4)+12*a(5)-a(6)-11+a(7)*a(8)/a(9)-10=66

les 128 solutions du serpent vietnamien

L'origine du buzz autour de ce casse tête  vient du fait que cet exercice aurait été donné  par un instituteur Vietnamien  à ses élèves de 8 ans, élèves qui seraient donc en classe de CE2 en France. Etant donné l'effort considérable qu'ont du fournir  les quelques adultes à avoir essayé de trouver "manuellement" une solution au problème (qui en comporte exactement 128)  ce puzzle a vite été considéré  comme une preuve des faiblesses de notre système éducatif en mathématiques  !?!?

Produire des figures en png et eps avec scilab et LaTeX

Pour illustrer mes cours  je dois souvent  créer des   figures  et suivant leur utilisation je dois pouvoir les convertir en différents formats, sans perte de qualité.  Comme j'utilise LaTeX j'ai commencé par créer des images postscript , mais avec l'apparition de pdflatex et  beamer ce choix de format n'est plus suffisant ...  Au fils des années j'ai du choisir un format complémentaire, et parmi tous les formats possibles  j'en ai choisi  un semble s'imposer de plus en plus sur le net : le format png.

une belle figure pour un cours de calcul différentiel !

Surface de Boy, surface Romaine et espace projectif

Lors de mes études de mathématiques j'ai pris beaucoup de plaisir à étudier La topologie algébrique et la géométrie différentielle. Plusieurs choses m'attiraient dans ces deux domaines  :

• l'étude de concepts issus de la géométrie plane ou spatiale mais généralisés de manière très abstraite à d'autres dimensions (groupe fondamental, homotopie, homéomorphisme, difféomorphisme)  
• la résolution problèmes géométriques d’apparence simple  mais difficile à se représenter (même en petite dimension) et aux résultats parfois contre-intuitifs (retournement de la sphère, théorème de la boule de billard chevelue)
• le tout se faisant sans  "calcul" littéral ou numérique, en tout cas  pas au sens de ce que j'avais appris à faire en algèbre ou en analyse jusque là !

Ce dernier point était un peu déroutant pour moi  à l'époque,  mais c'était certainement le point le plus important! Depuis la lecture cet été d'une biographie de Grigori Perelman (célèbre pour avoir démontré la conjecture de Poincaré) je redécouvre avec plaisir ces domaines et je m'amuse à les réexplorer avec l'aide de Scilab, exemple avec la surface de Boy :

en traçant cette surface en trois dimensions on peut essayer d'en comprendre la structure même lorsqu'on a pas l'esprit géométrique d'un Perelman ou d'un Louis Antoine .

Le flocon de Von Koch

voici une courbe fascinante sur laquelle je trouve intéressant de faire travailler mes étudiants. En effet cela permet, sans en avoir l'air, de les faire travailler sur des concepts géométriques très simples : points, vecteurs, coordonnées, un peu de trigonométrie ... souvent mal maîtrisés par manque d’entraînement. Pour y arriver on joue sur la motivation d'aboutir à un  résultat intéressant : obtenir l'animation de la construction d'une fractale assez esthétique, que beaucoup d'étudiants on déjà vu  là ou ailleurs  sans savoir comment la faire 

Approximation polynômiale : le match !

De nombreux chapitres des programmes de mathématiques de l'enseignement supérieur sont consacrés aux problèmes d'approximation avec la question :

" comment approcher une fonction quelconque par une fonction simple comme un polynôme ?"

le cloisonnement des modules d'enseignement et l'hétérogénéité des formations précédemment suivies par les étudiants rend souvent difficile la comparaison entre ces différentes méthodes. C'est bien dommage car ce sujet est un bon exemple pour montrer comment un problème donné peut conduire à différentes méthodes  avec chacune leurs avantages et leurs inconvénients. Je me suis amusé à bâtir une petite comparaison de différentes méthodes pour la fonction $f(x)={5x\sin(x)\over 1+x^2}$  en utilisant le logiciel scilab:

Dessins d'épicycloides avec Scilab

Peut être avez joué au spirographe quand vous étiez petits ? Ce jeux consiste en un assortiment d'engrenages permettant de tracer des épicycloides  : courbe obtenue  à partir d'un crayon attaché à un cercle (appelé épicycle)  roulant sans glissement le long d'un autre cercle.  Ce type de courbe est un excellent moyen pour trouver des problèmes intéressants  à base de courbes paramétrées et de fonctions trigonométriques!   Voici quelques exemples   dessinés avec scilab :

Surfaces de niveaux avec scilab

Tracer une représentation graphique des niveaux d'une fonction quelconque n'est pas un problème anodin les quelques fois où je tombe sur cette question je ne peux m'en sortir que sur des cas particulier où l'on peut séparer les variables. Pour une fonction à deux variables $f:{\mathbb R}^2\longmapsto {\mathbb R}$, suffisamment régulière, les niveaux $S=\{(x,y)\vert f(x,y)=C\}$ sont des courbes du plan,  Scilab possède des fonctions prédéfinies contour et contourf pour tracer ces courbes de niveaux. Mais ces fonctions ne peuvent pas traiter le cas de fonctions à trois variables $f:{\mathbb R}^3\longrightarrow{\mathbb R}$, où les niveaux $S=\{(x,y,z)\vert f(x,y,z)=C\}$ sont des surfaces dans l'espace ... heureusement j'ai trouvé un code intéressant sur Scilab File Exchange définissant une fonction contour3d capable de tracer des surfaces de niveaux juste à partir de la fonction  f et de la valeur  C, petit aperçu en vidéo :

Le livre Scilab de la théorie à la pratique

Les lecteurs réguliers de ce blog auront remarqué que j'ai été beaucoup moins actifs ces derniers mois. Ceci n'est pas du à un manque d'inspiration mais au temps que j'ai du consacrer à la finalisation d'un projet entamé il y a près d'un an et demi : la rédaction d'un livre sur Scilab.  Le scilabTEC (journée des utilisateurs de scilab) organisée sur le campus de l'école Polytechnique  la dernière semaine de Juin  était l'occasion idéale de présenter mon travail, en particulier à l'équipe des développeurs du logiciel :

(edit 01/10/13 :  vous pouvez lire le premier chapitre du livre en ligne à lire aussi  une critique du livre sur le site developpez.com ).

Chemins Euleriens et Algorithme de Fleury

La théorie des graphes est un domaine des mathématiques que j'ai la chance d'enseigner à l'IUT de Lannion . Ce domaine est de plus en plus en vogue actuellement, certainement par ce que c'est un très bon outil de modélisation qui peut s'adapter pour résoudre de nombreux problèmes concrets. Cette caractéristique se retrouve dès l'origine de la théorie des graphes avec la résolution du problème des sept ponts de Königsberg  posé par Euler en 1735. Ce problème fait apparaître une notion très importante de théorie des graphes, la notion de graphe Eulerien  :

Définition un graphe G est

• Eulerien   s'il existe un cycle/circuit passant exactement une fois par chaque arc/arête de G.
• semi-Eulerien s'il existe un chemin/chaîne passant exactement une fois par chaque arc/arête de G.

Voici un exemple G0 de graphe non-orienté possédant un chemin Semi-Eulerien :

G0 Graphe non-orienté abvec un chemin Semi-Eulerien C=(1,2,3,1,4,5,6,4)

Algorithme génétique et algèbre linéaire

Quand on pense aux algorithmes génétiques on pense d'abord au problème du voyageur de commerce (PVC). Pourtant d'un point de vue pédagogique il existe des problèmes plus simples pour débuter avec la manipulation des algorithmes génétiques, par exemple la résolution de systèmes d'équations linéaires. Voici un petit exemple de résolution approchée d'un système linéaire d'équations $Ax=y$  basé sur cette méthode :

résolution d'un système d'équations linéaires par algorithme génétique

Du ruban de Möbius à la Bouteille de Klein

La bouteille de Klein  est un exemple étonnant de surface sans-bord et compacte (non-orientable) qui ne peut pas être plongée dans  ${\mathbb R}^3$ sans provoquer d'auto-intersections . Une manière de le voir est d'essayer de construire une bouteille de Klein en partant d'un ruban de Möbius et en essayant de recoller les faces opposées de son bord (qui est homéomorphe à un cercle)   ... ceci n'est pas possible en dimension 3 sans déchirer le Ruban de Möbius!

Une anecdote amusante a propos de la bouteille de Klein : au départ elle fût nommée  "Kleinsche Fläche" (qui signifie  « surface  de Klein » ) par les mathématiciens allemands, mais rapidement il y  eu des erreurs de traduction (par les mathématiciens français?) entre les mots    Fläche (« surface ») et Flasche (« bouteille ») erreur qui finit par imposer le nom  « Bouteille de Klein » ... y compris en Allemand!