[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-quotesdbs_dbs47.pdfusesText_47

[PDF] mathématiques pour l'ingénieur 1

[PDF] mathématiques pour l'ingénieur dunod pdf

[PDF] mathématiques pour l'ingénieur exercices et problèmes

[PDF] mathématiques pour l'ingénieur pdf

[PDF] mathématiques pour la gestion dut gea

[PDF] mathématiques pour la physique dunod pdf

[PDF] mathématiques pour la physique et les physiciens pdf

[PDF] mathématiques pour la physique pdf

[PDF] mathématiques pour les sciences de l'ingénieur pdf

[PDF] Mathématiques pour vendredi

[PDF] mathématiques première stmg collection sigma corrigé

[PDF] mathématiques première stmg hachette éducation corrigé

[PDF] Mathematiques premières ,taux d'evolution et coefficient multiplicateur

[PDF] mathématiques probabilités troisième

[PDF] mathématiques problème