[PDF] Mathématiques pour informaticien - Inria PDF mathinfo2012.pdf

1 mai 2018 · Les mathématiques et les fondements de l'informatique pdf — Art of Problem Solving (en anglais seulement) : ce site web contient des

9 déc 2020 · But du cours : Il s'agit de donner au futur informaticien une palette d' En logique mathématique et en informatique, on souhaite formaliser ce

[PDF] Mathématiques pour informaticien - Inria

1 mai 2018 · Les mathématiques et les fondements de l'informatique pdf — Art of Problem Solving (en anglais seulement) : ce site web contient des

[PDF] MÉTHODES MATHÉMATIQUES POUR LINFORMATIQUE

22 fév 2013 · CHAPITRE 1 • LA NOTION D'ENSEMBLE 1 1 1 Ensembles 1 1 2 Éléments 3 1 3 Sur les façons de définir un ensemble 4 1 4 Fonctions et

[PDF] Mathématiques appliquées à linformatique - Cours Tech Info

Mathématiques appliquées à l'informatique Luc De Mey Ces notes de cours sont disponibles à l'adresse : www courstechinfo be/Math_Info pdf Dernière

[PDF] Math´ematiques pour Informaticiens

Math´ematiques pour Informaticiens Ernst Hairer Universitщ de Gen`eve Ce polycopiщ accompagne le cours “Mathщmatiques pour informaticiens” ( wavelets) dans beaucoup d'applications en informatique (compression de sons,

[PDF] Mathématiques linformatique - livre gratuit

pour l'informatique Pour le BTS SIO Rappels de cours Exercices corrigés Mathématiques pour l'informatique IV Chapitre 7 • L'examen de mathématiques

[PDF] Mathématiques pour linformatique - Université catholique de Louvain

Université catholique de Louvain - Mathématiques pour l'informatique - cours- 2017-lsinf1250 UCL - cours-{ANAC}-lsinf1250 - page 1/3 lsinf1250 2017

[PDF] Fondamentaux des mathématiques 1

beaucoup de rigueur, le résultat peut s'avérer désastreux Un autre exemple peut se trouver en informatique, où, si l'on ne respecte pas le cahier des charges, si

[PDF] Mathématiques appliquées à linformatique - Notes de cours

Cours de MATHS APPLIQUEES A L'INFORMATIQUE - Introduction à la Un graphe est un objet mathématique qui permet de modéliser un grand nombre de

[PDF] Mathématiques pour linformatique 1 notes de cours sur la - IGM

▷ Le cours est en deux parties : 3 séances au début du semestre, et 3 autres au milieu du semestre ▷ Pour ne pas rater une séance de cours ou de TD,

Mathematiques pour informaticien

MAT-1919

Francois Laviolette, Josee Desharnais,

Pascal Germain

Hiver 2012

Remerciements

Une partie de la matiere de ce cours etait autrefois enseignee dans le cadre du cours Logique et techniques de preuve. Merci a Jules Desharnais de nous avoir permis d'emprunter certains elements et exercices des notes de cours qu'il a lui-m^eme redigees. Nous remercions egalement les etudiants des sessions precedentes qui nous ont souligne des coquilles dans les notes de cours, contribuant ainsi a la qualite du document que vous avez sous les yeux : Simon Arsenault, Michael Audet, Abdoul Aziz A. LOM, Vincent Blais, Charles-Alexandre Cantin, Sylvain Fillion, Olivier Garant, Jean Bruno Jauvin, Charles Joly Beauparlant, Patrick Landry, Benjamin Lemelin, Olivier Petit, Karim Sghari, Sandra Sirois et Joel Trottier-Hebert. Finalement, les commentaires et corrections des auxiliaires d'enseignement Jean-Francis Roy et Gildas Syla Deogratias Kouko furent aussi d'une aide considerable. ii

Table des matieres

0 Un peu de motivation

1 Theorie des ensembles

1.1 Algebre booleenne

1.1.1 Expressions booleennes

1.1.2 Operateurs booleens et tables de verite

1.1.3 Proprietes des operateurs et demonstrations par cas

1.1.4 Demonstrations par succession d'equivalences

1.1.5 Le probleme de satisabilite d'une equation booleenne

1.1.6 Exercices sur l'algebre booleenne

1.2 Ensembles

27
1.2.1 Egalite entre deux ensembles (Axiome d'extensionnalite). . . . . . . 27

1.2.2 Denition d'un ensemble et operateur d'appartenance

1.2.3 Diagramme de Venn et ensemble universel

1.2.4 Quanticateur universel et quanticateur existentiel

1.2.5 Operateurs ensemblistes

1.2.6 Proprietes des operateurs et demonstrations

1.2.7 Exercices sur les ensembles

1.3 Techniques de demonstration

1.3.1 Structure des demonstrations d'un quanticateur universel \8". . . . 48

1.3.2 Structure des demonstrations d'un quanticateur existentiel \9".. . . 49

1.3.3 Une demonstration avec une implication \)". . . . . . . . . . . . . 49

1.3.4 Une demonstration avec un ssi \,". . . . . . . . . . . . . . . . . . . 51

1.3.5 Demonstration par cas

1.3.6 Demonstrations utilisant les proprietes de l'arithmetique

1.3.7 Demonstrations avec un \:9" ou un \:8". . . . . . . . . . . . . . . 54

1.3.8 Demonstrations par contradiction

1.3.9 Exercices sur les techniques de demonstration

1.4 Relations et fonctions

59
iii ivTABLE DES MATIERES

1.4.1n-uplet et produit cartesien. . . . . . . . . . . . . . . . . . . . . . . 59

1.4.2 Denitions et representations des relations

1.4.3 Operateurs sur les relations

1.4.4 Familles de relations

1.4.5 Fonctions (totales) et fonctions partielles

1.4.6 Relations d'equivalence et ordres

1.4.7 Exercices sur les relations et fonctions

1.5 Ensembles innis

1.5.1 \Avoir autant d'elements"

1.5.2 \Autant" d'elements queN: Les ensembles innis denombrables. . . 102

1.5.3 \Avoir plus d'elements"

104

1.5.4jNjest la plus petite cardinalite innie. . . . . . . . . . . . . . . . . 109

1.5.5 Donnons-nous des outils

111

1.5.6 \Plus d'elements" queN: Les ensembles non denombrables. . . . . . 114

1.5.7 Exercices sur les ensembles innis

123

2 Relations denies par recurrence

126

2.1 Suites

126

2.1.1 Denition par terme general et par recurrence

127

2.1.2 Notation sigma \"

128

2.1.3 Temps d'execution d'un algorithme

129

2.1.4 Exercices sur les suites

133

2.2 Methode des substitutions a rebours

135

2.2.1 Description de la methode

135

2.2.2 Quelques exemples

136

2.2.3 Exercices sur la methode des substitutions a rebours

143

2.3 Induction mathematique

144

2.3.1 Induction mathematique faible

144

2.3.2 Principe d'induction mathematique a deux cas de base

1 49

2.3.3 Induction mathematique forte

1 52

2.3.4 Exercices sur l'induction mathematique

1 56

2.4 Cas particuliers de recurrences

158

2.4.1 Les suites arithmetiques

158

2.4.2 Les suites geometriques

159

2.4.3 La suite des sommes de premiers termes d'une suite

160

2.4.4 Relations de recurrence lineaires et homogenes

165

2.4.5 Exercices sur les cas particuliers de recurrences

168

2.5 Methode des series generatrices

170

TABLE DES MATI

ERESv

2.5.1 L'idee de la methode

1 70

2.5.2 Methode de resolution et modeles de series de puissances

173

2.5.3 Quelques exemples de resolution de recurrences

1 75

2.5.4 Recurrences lineaires homogenes d'ordre 2 (demonstration)

182

2.5.5 Exercices sur la methode des series generatrices

186

2.6 Approximation par une integrale

187

2.6.1 Description de la methode

187

2.6.2 Bref rappel sur le calcul integral

1 89

2.6.3 Quelques exemples

189

2.6.4 Exercices sur l'approximation par une integrale

1 93

3 Theorie des graphes

194
3.1 Elements de base. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

3.1.1 Graphes et digraphes

195

3.1.2 Voisins et degre d'un sommet

197

3.1.3 Sous-graphes et decompositions

197

3.1.4 Cha^nes, chemins et cycles

1 98

3.1.5 Connexite d'un graphe

199

3.1.6 Arbres

2 00

3.1.7 Representation matricielle

201

3.1.8 Exercices sur les elements de base

203

3.2 Les graphes en tant que relations

205

3.2.1 Operateurs sur les graphes

205

3.2.2 Isomorphisme de graphes

207

3.2.3 Exercices sur les graphes en tant que relations

208

3.3 Degres des sommets et nombre d'ar^etes

209

3.4 Arbres

212

3.4.1 Sommets et ar^etes d'un arbre

212

3.4.2 Proprietes des arbres binaires

214

3.4.3 Exercices sur les arbres

216

3.5 Graphes planaires

217

3.6 Cha^nes et chemins

222

3.6.1 Proprietes d'un graphe connexe

222

3.6.2 Cycles d'un graphe

222

3.6.3 Algorithmes de recherche du plus court chemin

2 24

3.6.4 Exercices sur les cha^nes et chemins

227

A Alphabet grec

228
viTABLE DES MATIERES

B Documents L

ATEX230

References et suggestions de lecture

235

Index236

Chapitre 0

Un peu de motivation

Computer science is no more about computers

than astronomy is about telescopes.Edsger W. Dijkstra (1930 { 2002) A l'epoque ou vous entreprenez un programme d'etudes en informatique, il serait super- u de commencer ce cours en faisant l'eloge de l'utilite de l'informatique, tellement l'usage des ordinateurs est desormais repandu dans toutes les spheres de l'activite humaine. Ce- pendant, il nous parait important d'expliquer que les mathematiques sont d'une utilite cru- ciale pour quelqu'un qui s'interesse a l'informatique en tant que science. En eet, il subsiste chez plusieurs etudiants l'impression que l'informatique et les mathematiques sont deux do- maines d'etudes independants, et qu'il n'est pas necessaire de posseder des connaissances mathematiques pour ^etre un bon informaticien

1. Cela s'explique possiblement par le fait que

la plupart des utilisations que nous faisons d'un ordinateur ne requierent pas, ou peu, de connaissances mathematiques. En eet, tant que nous utilisons des programmes crees par d'autres (que ce soit des outils destines a tous, tels les traitements de textes, ou des outils plus specialises, telles les librairies hauts niveaux de certains langages de programmation), les connaissances mathematiques sont souvent facultatives. Cela dit, quiconque s'interesse a comprendre le fonctionnement de l'ordinateur, a analyser le comportement des algorithmes ou a concevoir des programmes pour resoudre des nouvelles t^aches a besoin d'outils pour guider son raisonnement logique. Les prochains paragraphes ont comme ambition de vous convaincre que, dans chacune de ces circonstances, les mathematiques s'imposent comme la

\bo^te a outils" de predilection.1. Curieusement, il n'existe pas de telles remises en question dans les diverses branches de l'ingenierie.

2CHAPITRE 0. UN PEU DE MOTIVATION

Les mathematiques et les fondements de l'informatique Les ordinateurs sont, d'abord et avant tout, des calculatrices tres sophistiquees. Les pre- miers ordinateurs ont d'ailleurs ete imagines par des mathematiciens desireux d'automatiser leurs calculs. De m^eme, le langage binaire a la base des ordinateurs est issu de la logique booleenne, que nous presenterons des le debut du premier chapitre. Le langage mathematique fut donc a la base du developpement de l'informatique, et il represente toujours un outil es- sentiel aux informaticiens qui travaillent a l'informatique du futur 2. Notons aussi que, malgre la grande diversication des t^aches que peut accomplir un ordina- teur personnel comme outil de travail ou objet de divertissement, il demeure essentiellement une puissante machine a calculer pour plusieurs scientiques. En eet, les \superordina- teurs" sont utilises dans tous les domaines (physique, meteorologie, economie, biologie, ...) comme des outils permettant de resoudre des problemes mathematiques comprenant un grand nombre de variables.

Les mathematiques et l'analyse d'algorithmes

Dans certaines circonstances, peu de connaissances mathematiques sont requises pour concevoir un programme informatique. Par exemple, les actions de trier un tableau de nombres, acceder a une base de donnees, appliquer un ltre a une image, compresser un video ou crypter un texte font appel a des techniques deja existantes. Un programmeur peut implementer ces techniques sans trop se creuser la t^ete. Parfois, il peut aussi trouver une strategie pour accomplir la t^ache desiree sans necessairement re echir dans un formalisme mathematique. Cependant, un informaticien serieux souhaitera analyser le comportement de son nouveau programme, pour repondre a l'une ou l'autre des questions suivantes : Est-c eque le temps d'ex ecutionrequis par mon programme est raisonnable, m ^eme quand le nombre de donnees a traiter est tres grand? Q uelest l'espace m emoirerequis par mon programme ? Pui s-jefournir la garan tieque mon programme accomplira la t^ achedemand eedans tous les cas? Est-c eque mon programme comp ortedes failles de s ecurite?

Dependamment du contexte, il est tres dicile d'obtenir des reponses completes a ces ques-2. Il sut de citer l'exemple d'une compagnie commeGoogle, qui a b^ati son empire sur des idees novatrices

developpees majoritairement en utilisant les outils qu'orent les mathematiques. 3 tions. Plusieurs domaines de recherche en informatique etudient des methodes pour analyser les algorithmes

3. On peut presumer que s'il y a, encore de nos jours, autant de failles dans

les logiciels, c'est en partie parce que ces methodes ne sont pas encore assez evoluees pour benecier de toute la logique et de la rigueur des mathematiques. Le deuxieme chapitre de ce cours donne un avant-go^ut de l'analyse d'algorithmes en introduisant les outils de base qui permettront d'evaluer le temps d'execution d'un algorithme.

Les mathematiques et la conception d'algorithmes

L'informatiqueetant une science relativement jeune, il existe encore beaucoup de problemes a resoudre relies a une grande variete de domaines dierents : l'intelligence articielle, la vi- sion numerique, la creation d'horaires, les previsions economiques, la simulation des systemes climatiques, l'assemblage de genomes, la comprehension du langage naturel, la verication automatique de logiciels, etc. Tous ces problemes complexes necessitent d'^etre formules rigoureusement avant de pouvoir ^etre resolus a l'aide d'un programme informatique. La plupart du temps, ce sont les mathema- tiques qui se revelent le langage approprie pour formuler ces problemes. Une fois le probleme bien formule, on peut proter des theories mathematiques deja existantes pour mieux le comprendre, pour le simplier ou pour trouver des pistes de solutions possibles. Cette approche est mise en evidence dans le troisieme chapitre de ces notes de cours, dedie a la theorie des graphes. En eet, un graphe est une structure mathematique simple qui a ete abondamment etudiee. Dans plusieurs cas, il sut d'exprimer un probleme comme un graphe pour avoir acces a plusieurs algorithmes ecaces pour le resoudre.

Ce qu'il faut retenir de ce cours

Le cours sera l'occasion d'introduire plusieurs concepts mathematiques et, bien s^ur, vous serez evalues sur la ma^trise des dierentes notions. Cependant, la comprehension sera tou- jours privilegiee plut^ot que le \par coeur". Comme plusieurs notions abordees ici serviront lors

d'autres cours du programme, ces notes de cours pourront aussi servir de reference ulterieure.3. Bien que nous n'irons pas si loin dans le cours, la branche de la recherche nommee la \theorie de la

complexite" s'interesse a des questions encore plus \fondamentales", telles :

{Etant donne un probleme, est-ce qu'il existe un algorithme capable de le resoudre en temps raisonnable?

{ Si je trouve un algorithme ecace pour resoudre le probleme A, est-ce que ca me permet de resoudre le

probleme B ecacement? (m^eme si les problemes A et B sont en apparence de natures tres dierentes.)

4CHAPITRE 0. UN PEU DE MOTIVATION

Tout le long du cours, nous accorderons une grande importance aux demonstrations mathematiques. Il s'agit d'un concept qui n'est pas aussi simple qu'on peut le croire au depart. L'ecriture d'une demonstration mathematique requiert beaucoup de rigueur, et sou- vent une certaine creativite. De m^eme, il faut lire et ecrire plusieurs demonstrations pour bien en comprendre l'esprit. Les etudiants qui poursuivront leurs etudes aux cycles superieurs se- ront appeles a lire et rediger des demonstrations lors de leurs travaux de recherche. Cela dit, l'accent mis sur les demonstrations mathematiques ne sera pas seulement utile aux etudiants qui poursuivront une carriere en recherche, mais permettra a tous d'exercer leur raisonnement et leur capacite de deduction face a certains problemes demandant une dose de re exion. Finalement, si ce cours peut vous convaincre que les mathematiques en informatique sont utiles et agreables, nous aurons atteint notre but!

Chapitre 1

Theorie des ensembles

1.1 Algebre booleenne

Pour debuter, nous introduisons les bases de la logique booleenne, nommee en l'honneur du mathematicien et philosophe britannique George Boole (1815 { 1864), qui souhaitait developper un formalisme pour traduire des concepts et des pensees en equations. Comme nous le verrons, ce paradigme est tres pres du langage binaire utilise en electronique et en informatique.

1.1.1 Expressions booleennes

Uneexpression booleennecorrespond a un regroupement d'armations. On designe par le termeexpression booleenne atomiqueune expression booleenne contenant une seule armation. Une armation est une phrase, generalement de la forme \sujet-verbe- complement", a laquelle il est possible d'attribuer unevaleur de verite. Autrement dit, il est possible de determiner si l'armation est vraie ou fausse. Par exemple, les quatre armations suivantes peuvent ^etre considerees comme des expressions booleennes atomiques : |Manille est la capitale des Philippines. |Cinq est un nombre impair. |La distance entre la terre et la lune est inferieure a trois kilometres. |Dix est plus petit que sept. Les deux premieres armations sont vraies tandis que les deux dernieres sont fausses. On peut aussi exprimer des expressions booleennes par des formules mathematiques. Par 5

6CHAPITRE 1. THEORIE DES ENSEMBLES

exemple :

5 + 5 + 5 = 3 5 .

10 <7 .

Dans ce dernier exemple, la premiere expression est toujours vraie et la deuxieme est tou- jours fausse. Remarquons que ces deux expressions mathematiques correspondent aussi a des phrases de la forme \sujet-verbe-complement". Pour la premiere expression, le membre de gauche fait oce de sujet, \=" est le verbe et le membre de droite est le complement. Similairement, pour la deuxieme expression, on a que \10" est le sujet de la phrase, \est plus petit que" represente le groupe verbe et \7" le complement". Notez egalement qu'on peut reecrire ces expressions sous forme d'un texte francais : \Cinq plus cinq plus cinq egale trois fois cinq." et \Dix est plus petit que sept.". Certaines expressions booleennes changent de valeur de verite dependamment du contexte dans lequel elles sont evaluees. Par exemple : |La capitale de ma province est la ville de Quebec. |x <7 . La valeur de la premiere expression depend de la province identiee par les termes \ma province". De m^eme, la deuxieme expression depend de la valeur de la variablex. Si aucune valeur n'est attribuee a la variablex, on dit qu'il s'agit d'unevariable libre, auquel cas il est impossible d'assigner une valeur de verite a l'expression \x <7". Cependant, pour chaque valeur dexpossible, on peut assigner une valeur de verite a l'expression. Ainsi, l'expression est fausse six7, sinon elle est vraie. Nous nous interessons maintenant a la combinaison d'expressions booleennes atomiques en expressions booleennes plus complexes. Nous eectuons de telles combinaisons dans nos conversations de tous les jours, notamment a l'aide des mots \et", \ou" et \si-alors". Par exemple : |J'habite a Chicoutimi et la capitale de ma province est la ville de Quebec. |Si j'habite a Chicoutimi, alors la capitale de ma province est la ville de Quebec. |Mon prenom contient la lettre P ou mon prenom contient la lettre S. Pour verier la veracite de ces expressions booleennes, il sut d'evaluer separement la veracite de chacune des expressions booleennes atomiques les constituant. Ainsi, dans le cas du premier exemple, nous evaluons d'abord la veracite de l'expression \J'habite a Chicou- timi.", puis nous evaluons ensuite la veracite de l'expression \La capitale de ma province est la ville de Quebec.". Nous pouvons enn juger de la veracite de l'expression booleenne

1.1. ALG

quotesdbs_dbs47.pdfusesText_47

[PDF] [PDF] Mathématiques pour informaticien - Inria

Mathematiques pour informaticien

MAT-1919

Francois Laviolette, Josee Desharnais,

Pascal Germain

Hiver 2012

Remerciements

Table des matieres

0 Un peu de motivation

1 Theorie des ensembles

1.1 Algebre booleenne

1.1.1 Expressions booleennes

1.1.2 Operateurs booleens et tables de verite

1.1.3 Proprietes des operateurs et demonstrations par cas

1.1.4 Demonstrations par succession d'equivalences

1.1.5 Le probleme de satisabilite d'une equation booleenne

1.1.6 Exercices sur l'algebre booleenne

1.2 Ensembles

1.2.2 Denition d'un ensemble et operateur d'appartenance

1.2.3 Diagramme de Venn et ensemble universel

1.2.4 Quanticateur universel et quanticateur existentiel

1.2.5 Operateurs ensemblistes

1.2.6 Proprietes des operateurs et demonstrations

1.2.7 Exercices sur les ensembles

1.3 Techniques de demonstration

1.3.1 Structure des demonstrations d'un quanticateur universel \8". . . . 48

1.3.2 Structure des demonstrations d'un quanticateur existentiel \9".. . . 49

1.3.3 Une demonstration avec une implication \)". . . . . . . . . . . . . 49

1.3.4 Une demonstration avec un ssi \,". . . . . . . . . . . . . . . . . . . 51

1.3.5 Demonstration par cas

1.3.6 Demonstrations utilisant les proprietes de l'arithmetique

1.3.7 Demonstrations avec un \:9" ou un \:8". . . . . . . . . . . . . . . 54

1.3.8 Demonstrations par contradiction

1.3.9 Exercices sur les techniques de demonstration

1.4 Relations et fonctions

1.4.1n-uplet et produit cartesien. . . . . . . . . . . . . . . . . . . . . . . 59

1.4.2 Denitions et representations des relations

1.4.3 Operateurs sur les relations

1.4.4 Familles de relations

1.4.5 Fonctions (totales) et fonctions partielles

1.4.6 Relations d'equivalence et ordres

1.4.7 Exercices sur les relations et fonctions

1.5 Ensembles innis

1.5.1 \Avoir autant d'elements"

1.5.2 \Autant" d'elements queN: Les ensembles innis denombrables. . . 102

1.5.3 \Avoir plus d'elements"

1.5.4jNjest la plus petite cardinalite innie. . . . . . . . . . . . . . . . . 109

1.5.5 Donnons-nous des outils

1.5.6 \Plus d'elements" queN: Les ensembles non denombrables. . . . . . 114

1.5.7 Exercices sur les ensembles innis

2 Relations denies par recurrence

2.1 Suites

2.1.1 Denition par terme general et par recurrence

2.1.2 Notation sigma \"

2.1.3 Temps d'execution d'un algorithme

2.1.4 Exercices sur les suites

2.2 Methode des substitutions a rebours

2.2.1 Description de la methode

2.2.2 Quelques exemples

2.2.3 Exercices sur la methode des substitutions a rebours

2.3 Induction mathematique

2.3.1 Induction mathematique faible

2.3.2 Principe d'induction mathematique a deux cas de base

2.3.3 Induction mathematique forte

2.3.4 Exercices sur l'induction mathematique

2.4 Cas particuliers de recurrences

2.4.1 Les suites arithmetiques

2.4.2 Les suites geometriques

2.4.3 La suite des sommes de premiers termes d'une suite

2.4.4 Relations de recurrence lineaires et homogenes

2.4.5 Exercices sur les cas particuliers de recurrences

2.5 Methode des series generatrices

TABLE DES MATI

2.5.1 L'idee de la methode

2.5.2 Methode de resolution et modeles de series de puissances

2.5.3 Quelques exemples de resolution de recurrences

2.5.4 Recurrences lineaires homogenes d'ordre 2 (demonstration)

2.5.5 Exercices sur la methode des series generatrices

2.6 Approximation par une integrale

2.6.1 Description de la methode