[PDF] Mathématiques pour informaticien

View - Download Mathématiques pour informaticien

Previous PDF

Next PDF

Mathematiques pour informaticien

MAT-1919

Francois Laviolette, Josee Desharnais,

Pascal Germain

Automne 2014

(Derniere modication : 2 septembre 2014)

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 ont signale des co- quilles dans les notes de cours ou suggere des ameliorations a celles-ci, contribuant ainsi a la qualite du document que vous avez sous les yeux : Simon Arsenault, Michael Audet, Ab- doul Aziz A. LOM, Vincent Blais, Charles-Alexandre Cantin,

Eric Chamberland, Pier-Luc

Cormier-Maltais, Sylvain Fillion, Olivier Garant, Jean Bruno Jauvin, Charles Joly Beaupar- lant, Patrick Landry, Alexandre Laroche, Benjamin Lemelin, Christian Martin, Olivier Petit, Karim Sghari, Sandra Sirois et Joel Trottier-Hebert. Finalement, les commentaires et corrections des auxiliaires d'enseignement Jean-Francis Roy, Gildas Syla Deogratias Kouko et Catherine Bedard furent aussi d'une aide considerable. ii

Table des matieres

0 Un peu de motivation

1

1 Theorie des ensembles

5

1.1 Algebre booleenne

6

1.1.1 Expressions booleennes

6

1.1.2 Operateurs booleens et tables de verite

7

1.1.3 Proprietes des operateurs et demonstrations par cas

12

1.1.4 Demonstrations par succession d'equivalences

19

1.1.5 Le probleme de satisabilite d'une equation booleenne

24

1.1.6 Exercices sur l'algebre booleenne

28

1.2 Ensembles

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

1.2.2 Denition d'un ensemble et operateur d'appartenance

33

1.2.3 Diagramme de Venn et ensemble universel

36

1.2.4 Quanticateur universel et quanticateur existentiel

37

1.2.5 Operateurs ensemblistes

41

1.2.6 Proprietes des operateurs et demonstrations

44

1.2.7 Exercices sur la logique du premier ordre

51

1.2.8 Exercices sur les ensembles

53

1.3 Techniques de demonstration

55

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

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

1.3.3 Demonstrations utilisant les proprietes de l'arithmetique

59

1.3.4 Demonstrations avec un \:9" ou un \:8". . . . . . . . . . . . . . . 60

1.3.5 Une demonstration avec une implication \)". . . . . . . . . . . . . 62

1.3.6 Une demonstration avec un ssi \," et en passant, un \^". . . . . . 62

1.3.7 Demonstration par cas, dont le \_". . . . . . . . . . . . . . . . . . . 64

1.3.8 Demonstrations par contradiction

66

1.3.9 Autres facons d'attaquer une demonstration!

69
iii ivTABLE DES MATIERES

1.3.10 Exercices sur les techniques de demonstration

73

1.4 Relations et fonctions

75

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

1.4.2 Denitions et representations des relations

79

1.4.3 Operateurs sur les relations

83

1.4.4 Familles de relations

88

1.4.5 Fonctions (totales) et fonctions partielles

96

1.4.6 Exercices sur les relations et fonctions

1 02

1.5 Ensembles innis

107

1.5.1 \Avoir autant d'elements"

1 09

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

1.5.3 \Avoir au moins autant d'elements"

114

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

1.5.5 Donnons-nous des outils

119

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

1.5.7 Exercices sur les ensembles innis

127

1.6 Ensembles de fonctions

129

1.6.1 Fonctions a valeur de sortie binaire

130

1.6.2 Denombrabilite des ensembles de fonctions

135

1.6.3 Exercices sur les ensembles de fonctions

1 38

1.7 Relations d'equivalences et ordres

140

1.7.1 Relations d'equivalences

140

1.7.2 \Autant d'elements" est une relation d'equivalence

142

1.7.3 Relations d'ordres

144

1.7.4 \Au moins autant d'elements" est un ordre complet

1 47

1.7.5 Exercices sur les relations d'equivalences et ordres

149

2 Relations denies par recurrence

150

2.1 Suites

150

2.1.1 Denition par terme general et par recurrence

151

2.1.2 Notation sigma \"

152

2.1.3 Temps d'execution d'un algorithme

153

2.1.4 Exercices sur les suites

157

2.2 Methode des substitutions a rebours

159

2.2.1 Description de la methode

159

2.2.2 Quelques exemples

160

2.2.3 Exercices sur la methode des substitutions a rebours

167

2.3 Induction mathematique

168

TABLE DES MATI

ERESv

2.3.1 Induction mathematique faible

168

2.3.2 Principe d'induction mathematique a deux cas de base

1 73

2.3.3 Induction mathematique forte

1 76

2.3.4 Induction structurelle

179

2.3.5 Exercices sur l'induction mathematique

1 82

2.4 Cas particuliers de recurrences

184

2.4.1 Les suites arithmetiques

184

2.4.2 Les suites geometriques

185

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

186

2.4.4 Exercices sur les cas particuliers de recurrences

192

2.5 Methode des series generatrices

194

2.5.1 L'idee de la methode

1 94

2.5.2 Methode de resolution et modeles de series de puissances

197

2.5.3 Quelques exemples de resolution de recurrences

2 00

2.5.4 Application aux relations de recurrence lineaires et homogenes

207

2.5.5 Exercices sur la methode des series generatrices

212

2.6 Approximation par une integrale

214

2.6.1 Description de la methode

214

2.6.2 Bref rappel sur le calcul integral

2 16

2.6.3 Quelques exemples

216

2.6.4 Exercices sur l'approximation par une integrale

2 20

3 Theorie des graphes

221
3.1 Elements de base. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

3.1.1 Graphes et digraphes

222

3.1.2 Voisins et degre d'un sommet

223

3.1.3 Sous-graphes et decompositions

224

3.1.4 Cha^nes, chemins et cycles

2 25

3.1.5 Connexite d'un graphe

226

3.1.6 Arbres

2 27

3.1.7 Representation matricielle

228

3.1.8 Exercices sur les elements de base

230

3.2 Les graphes en tant que relations

232

3.2.1 Operateurs sur les graphes

232

3.2.2 Isomorphisme de graphes

234

3.2.3 Exercices sur les graphes en tant que relations

235

3.3 Degres des sommets et nombre d'ar^etes

236

3.4 Arbres

239
viTABLE DES MATIERES

3.4.1 Sommets et ar^etes d'un arbre

239

3.4.2 Proprietes des arbres binaires

241

3.4.3 Exercices sur les arbres

243

3.5 Graphes planaires

244

3.6 Cha^nes et chemins

249

3.6.1 Proprietes d'un graphe connexe

249

3.6.2 Cycles d'un graphe

249

3.6.3 Algorithmes de recherche du plus court chemin

2 51

3.6.4 Exercices sur les cha^nes et chemins

254

A Alphabet grec

255

B Documents L

ATEX256

References et suggestions de lecture

261

Index262

Solutions aux exercices

266

Solutions des exercices section

1.1.6 266

Solutions des exercices section

1.2.7 281

Solutions des exercices section

1.2.8 284

Solutions des exercices section

1.3.10

291

Solutions des exercices section

1.4.6 298

Solutions des exercices section

1.5.7 313

Solutions des exercices section

1.6.3 326

Solutions des exercices section

1.7.5 332

Solutions des exercices section

2.1.4 333

Solutions des exercices section

2.2.3 338

Solutions des exercices section

2.3.5 340

Solutions des exercices section

2.4.4 347

Solutions des exercices section

2.5.5 350

Solutions des exercices section

2.6.4 359

Solutions des exercices section

3.1.8 364

Solutions des exercices section

3.2.3 367

Solutions des exercices section

3.4.3 369

Solutions des exercices section

3.6.4 372

Aide memoire chapitre 1

376

TABLE DES MATI

ERESvii

Synthese denitions et theoremes, annexee aux examens 380
viiiTABLE DES MATIERES

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.

1

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. Les mathematiques ne sont donc pas qu'unoutilen informatique. Bien s^ur, les mathema- tiques se retrouvent dans toutes les branches de la conception d'outils par les humains (toutes les branches du genie, en particulier). Elles fournissent la plupart du temps un langage et des regles de manipulation des donnees qui sont desapproximationsdu langage et des regles de la nature. On etudie le mouvement d'un objet a l'aide d'une fonction mathematique, mais pour cela, on suppose souvent l'absence de friction. Les exemples sont nombreux : en economie, on dessine une courbe d'ore et de la demande en utilisant une fonction continue m^eme si une foule de valeurs n'ont pas de sens dans cette fonction. L'approximation est necessaire, on ne peut faire mieux sans compliquer trop les choses (ou on ne peut faire mieux, point). Pour l'informatique, c'est dierent. L'informatique est nee des mathematiques, les programmes sont des langages entierement crees par l'Homme, ilssontmathematiques! Quand on \utilise" des outils mathematiques pour raisonner sur un programme informatique, on utilise le m^eme langage! L'informatique est uneapplication exactedes mathematiques, et peut-^etre la seule a ^etre vraiment exacte!

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-ce que 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 ? 3 Pui s-jefournir la garan tieque mon programme accomplira la t^ achedemand eedans tous les cas? Est-ce que mon programme comp ortedes failles de s ecurite? Dependamment du contexte, il est tres dicile d'obtenir des reponses completes a ces ques- tions. Plusieurs domaines de recherche en informatique etudient des methodes pour analyser les algorithmes

2. 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'informatique etant une science relativement jeune, il existe encore beaucoup de pro- blemes a resoudre relies a une grande variete de domaines dierents : l'intelligence arti- cielle, la vision 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 3. 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.2. 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.)

3. Ainsi, les equipes de recherche des universites et des compagnies qui travaillent a l'informatique du

futur se servent des mathematiques tous les jours. Il sut de citer l'exemple de compagnies commeGoogle

ouAmazon, qui b^atissent leur empire gr^ace a idees novatrices developpees notamment a l'aide des outils

qu'orent les mathematiques.

4CHAPITRE 0. UN PEU DE MOTIVATION

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. Tout le long du cours, nous accorderons une grande importance aux demonstrations mathematiques; c'est l'un des objectifs du cours. 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 souvent une certaine creativite. De m^eme, il faut lire et ecrire plu- sieurs demonstrations pour bien en comprendre l'esprit. Les etudiants qui poursuivront leurs etudes aux cycles superieurs seront 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.

Chapitre 1

Theorie des ensembles

C'est a travers la theorie des ensembles que nous introduirons les dierentes techniques de demonstration qui devront ^etre ma^trisees dans ce cours. Nous faisons d'une pierre deux coups : pour apprendre comment demontrer, il faut des propositions a demontrer, ce qui est l'occasion d'introduire un sujet, la theorie des ensembles.

A la section1.2 , nous introduirons

des denitions sur la theorie des ensembles et ensuite des proprietes associees, que nous demontrerons a l'aide de techniques de demonstration. Nous appliquerons ces techniques (et une nouvelle) par la suite dans les chapitres suivants. C'est Aristote (-384 { -322) qui a developpe l'art de la demonstration. Son exemple celebre est le suivant :

Tous les hommes sont mortels

Or Socrate est un homme

Donc Socrate est mortel

Cette conclusion, appelee syllogisme, nous est naturelle, et toute technique de demonstration s'appuie sur un tel raisonnement naturel. Toutefois, quand de nombreux arguments sont necessaires pour arriver a une conclusion correcte, il est facile de s'embourber si on n'uti- lise pas une technique rigoureuse. Le but de ce cours est de vous donner des habitudes et techniques de demonstration qui vous aideront a \garder le l"!

Voici un autre exemple de syllogisme :

Quand il pleut sur le campus, Xavier a toujours son parapluie sur lui

Je constate qu'il pleut sur le campus

Donc Xavier a son parapluie aujourd'hui.

Par ce raisonnement, on a reussi aextraireune information, \Xavier a son parapluie aujour-quotesdbs_dbs30.pdfusesText_36

[PDF] que veut dire stt en sms

[PDF] mathématiques pour linformatique avec 309 exercices corrigés pdf

[PDF] philosophie de voltaire

[PDF] dictionnaire philosophique voltaire analyse

[PDF] la matiere et l'esprit def philo

[PDF] mathématique discrète exercice corrigé

[PDF] environnement fle a2

[PDF] fiche pedagogique environnement fle

[PDF] cornériser définition

[PDF] la démocratie dans le monde daujourdhui pdf

[PDF] arguments pour la démocratie

[PDF] vocabulaire environnement fle

[PDF] signifiant signifié référent

[PDF] signifiant signifié semiologie

[PDF] machine pour fabrication de bonbon