L'environnement bancaire

ian Tanasa ou ` moi-mˆme. e a a e

1

5.4

5.5

Multiset . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 OGF . . . . . . . . . . . . . . . . . . . . . . 5.4.2 EGF . . . . . . . . . . . . . . . . . . . . . . S´ries rationnelles (rep´sentations lin´aires et aspect e e e 5.5.1 Produit de Hadamard . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . automatique) . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

25 25 25 25 27 27 27 28 29 31 32 35 36 36 36 37 37 38 38 40 40 40 40 40 40 41 41 42 43 43 46 46 46 46 46 46

6 G´n´ration al´atoire e e e 6.1 Engendrer le hasard . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 G´n´rateurs ` un pas . . . . . . . . . . . . . . . . . . . . . . . . e e a 6.2.1 Param`tres . . . . . . . . . . . . . . . . . . . . . . . . . e 6.2.2 Algorithmes de Brent et Floyd . . . . . . . . . . . . . . . 6.2.3 G´n´rateurs congruentiels lin´aires . . . . . . . . . . . . e e e 6.3 G´n´rateurs ` deux pas . . . . . . . . . . . . . . . . . . . . . . . e e a 6.3.1 Vectorisation et param`tres . . . . . . . . . . . . . . . . e 6.4 G´n´rateurs du type GL2P . . . . . . . . . . . . . . . . . . . . . e e 6.4.1 G´n´ralit´s . . . . . . . . . . . . . . . . . . . . . . . . . e e e 6.4.2 Combinaison de deux g´n´rateurs . . . . . . . . . . . . . e e 6.4.3 D´composition et calcul de la p´riode d’un GL2P (m = p e e 6.4.4 Carr´s et ´quations du second degr´ dans Fp . . . . . . . e e e 6.4.5 Calcul de la p´riode d’un GCL2 . . . . . . . . . . . . . . e 6.5 Autres g´n´rateurs . . . . . . . . . . . . . . . . . . . . . . . . . e e 6.6 G´n´rateurs ` k pas . . . . . . . . . . . . . . . . . . . . . . . . . e e a ´ 6.7 Enum´rer, classer, indexer . . . . . . . . . . . . . . . . . . . . . e 6.8 R´partitions ´quitables et moins ´quitables . . . . . . . . . . . . e e e ´ 7 Evaluation de graphes. 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 7.2 Description de la structure d’automate . . . . . . . 7.2.1 Graphe pond´r´ . . . . . . . . . . . . . . . . ee 7.2.2 Structure et comportement des automates . 7.2.3 Premiers automates . . . . . . . . . . . . . . 7.2.4 Composition des automates . . . . . . . . . 7.3 S´ries . . . . . . . . . . . . . . . . . . . . . . . . . . e 7.3.1 Exemple : Comportement d’un automate . . 7.3.2 Op´rations sur les s´ries . . . . . . . . . . . e e 7.3.3 Lien avec les grammaires et les structures de ´ 7.3.4 Enum´ration . . . . . . . . . . . . . . . . . e 7.3.5 Rudiments de Calcul Modulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . donn´es e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . premier). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 Annexe : Fonctions g´n´ratrices. e e 46 8.1 Une variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 8.2 Application au calcul de complexit´ . . . . . . . . . . . . . . . . . . . . . . 46 e 8.3 Plusieurs variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 9 TD et TP (E. Laugerotte & J-P. Dubernard) 10 TD 47 55

2

11 S´ries e 11.1 Introduction . . . . . . . . . . . 11.2 Les s´ries sont des fonctions . . e 11.3 S´ries li´es ` des statistiques . . e e a 11.3.1 La formule exponentielle 11.3.2 Multisection de s´ries . . e 11.4 Types courants (de s´ries) . . . e 11.5 Exemples . . . . . . . . . . . . 11.6 Produit scalaire s´rie|polynˆme e o

. . . . . . . . . . . . . . et

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . premi`res op´rations e e

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

57 57 57 57 57 58 58 59 59 60 60 60 60 61 66 67

12 S´ries d’une variable (C[[z]]) e 12.1 Op´rations sur les s´ries . . . . . . . . . . . . . . . . . . . . . . . . . . . . e e 12.2 Les deux produits : Convolution (produit de Cauchy) et produit de Hadamard 12.2.1 Produit de Cauchy . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.2.2 S´ries rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . e 12.2.3 S´ries rationnelles (rep´sentations lin´aires et aspect automatique) . e e e 12.2.4 Produit de Hadamard . . . . . . . . . . . . . . . . . . . . . . . . .

13 Syst`mes de Calcul Formel et structures de donn´es e e 68 13.1 R´vision num´ration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 e e 13.1.1 Quelques exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 14 S´ries e 14.1 Introduction . . . . . . . . . . . 14.2 Les s´ries sont des fonctions . . e 14.3 S´ries li´es ` des statistiques . . e e a 14.3.1 La formule exponentielle 14.3.2 Multisection de s´ries . . e 14.4 Types courants (de s´ries) . . . e 14.5 Exemples . . . . . . . . . . . . 14.6 Produit scalaire s´rie|polynˆme e o . . . . . . . . . . . . . . et . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . premi`res op´rations e e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 68 69 69 69 69 70 71 71 72 72 72 72 73 78 79

15 S´ries d’une variable (C[[z]]) e 15.1 Op´rations sur les s´ries . . . . . . . . . . . . . . . . . . . . . . . . . . . . e e 15.2 Les deux produits : Convolution (produit de Cauchy) et produit de Hadamard 15.2.1 Produit de Cauchy . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.2.2 S´ries rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . e 15.2.3 S´ries rationnelles (rep´sentations lin´aires et aspect automatique) . e e e 15.2.4 Produit de Hadamard . . . . . . . . . . . . . . . . . . . . . . . . .

1

Pr´ambule e

Ce cours est commun aux ´tudiants originaires des fili`res Physique et chimie. Il est con¸u e e c de fa¸on ` permettre aux ´tudiants des deux sensibilit´s de pouvoir s’entraˆ c a e e ıner tant au niveau de la programmation (TP - TD - libre service) qu’au niveau conceptuel : outils analytiques, num´riques et symboliques de l’informatique &/ou utilis´s en informatique e e

3

moderne (s´curit´, simulation, algorithmique rapide). Les T.D. se font en maple, mais le e e contenu de l’enseignement est ind´pendant du langage. e Le poly correspond ` un programme maximal. Seule une partie de celui-ci sera trait´e a e cette ann´e. Les exercices qui sont l` pour aider ` la compr´hension du cours. e a a e II se peut que vous ne compreniez pas certains ´nonc´s, dans ce cas choisissez que les quese e tions que vous ˆtes capables d’aborder ... et contactez-moi rapidement pour le d´codage. e e Ceci vaudra aussi lorsque vous vous exercerez sur annales. Les parties en petits caract`res sont des suppl´ments et ne sont pas obligatoires. e e

2

Introduction

Le Calcul √ Symbolique est l’art de manipuler (scientifiquement) les symboles (exacts : 4/7, π 2 /6, 10 ou bien litt´raux x,y,z,t,u,v) selon certaines r`gles dites “de calcul” (ou e e 1 bien de d´rivation ). En fait, cette activit´ est tr`s ancienne et remonte ` la num´ration e e e a e puisque celle-ci consiste ` symboliser des quantit´s par des symboles et que les quatre a e op´rations arithm´tiques ne sont autres que le calcul symbolique attach´ ` des probl`mes e e ea e concrets (ajout ou retrait de quantit´s, calcul de longueur, de surface, de volume, mesure e d’une grandeur) et donnent lieu aux alogorithmes de l’arithm´tique ´l´mentaire. e ee De mˆme que la math´matique (quand elle n’est pas autog`ne) d´veloppe des mod`les e e e e e pour les sciences de la nature (´quations de la physique, lois ..), de mˆme l’Informatique e e Th´orique a d´velopp´ des mod`les et des concepts pour les ordinateurs (machines de e e e e Turing, calculabilit´, automates, s´ries g´n´ratrices, complexit´, grammaires..). e e e e e 2 Le Calcul Formel est n´ d`s que l’on a essay´ de traiter automatiquement certains