1 mai 2018 · Les mathématiques et les fondements de l'informatique nombres, accéder `a une base de données, appliquer un filtre `a une image, compresser un pdf — Art of Problem Solving (en anglais seulement) : ce site web
Previous PDF | Next PDF |
[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ématiques appliquées à linformatique - Notes de cours
MATHS APPLIQUEES A L'INFORMATIQUE - Introduction à la Ce thème faisant partie du programme du cours de mathématiques appliquées à l' informatique
[PDF] DOSSIER PEDAGOGIQUE MATHEMATIQUES APPLIQUEES A L
des techniques informatiques et de s'approprier ainsi le sens des mathématiques appli- quées ; ♢ de se familiariser à la modélisation mathématique des
[PDF] Informatique et mathématiques appliquées - Université catholique
Matlab et des mathématiques en vue d'une utilisation rationnelle dans le domaine de Appliquer ces concepts afin de produire des programmes informatiques
[PDF] Mathématiques pour linformatique 1 - Mathématiques Discrètes
9 déc 2020 · But du cours : Il s'agit de donner au futur informaticien une palette d'outils En mathématiques, on parle très souvent de "condition nécessaire et suffisante" Nous allons appliquer le principe de récurrence classique sur le
[PDF] MÉTHODES MATHÉMATIQUES POUR LINFORMATIQUE
22 fév 2013 · mention informatique et mention mathématiques appliquées, des vous ai donné envie de lire un livre de Mathématiques sans y être obligé
[PDF] Mathématiques pour informaticien - Inria
1 mai 2018 · Les mathématiques et les fondements de l'informatique nombres, accéder `a une base de données, appliquer un filtre `a une image, compresser un pdf — Art of Problem Solving (en anglais seulement) : ce site web
[PDF] Informatique, Mathématiques Appliquées : `a la découverte dune
L'informatique et les mathématiques appliquées Une discipline scientifique Des métiers Des formations (UJF) Informatique, Mathématiques Appliquées : `a
[PDF] Informatique, Mathématiques et Mathématiques Appliquées
15 nov 2013 · l Méthodes Informatiques Appliquées à la Gestion des Entreprises (MIAGE) Master Mathématiques, Informatique l 4 majeures en M1 l M1 M I
[PDF] Informatique & Mathématiques Appliquées - Academie pro
14 oct 2015 · Informatique Mathématiques Appliquées Programmation Mathématique et Application J Gergaud D Ruiz 17 avril 2008
[PDF] mathématiques appliquées ? la gestion synthèse de cours et exercices corrigés
[PDF] mathématiques appliquées exercices corrigés
[PDF] mathématiques appliquées exercices corrigés pdf
[PDF] mathématiques appliquées ingénieur
[PDF] mathématiques appliquées l3 cours complet avec 500 tests et exercices corrigés
[PDF] mathématiques appliquées pdf
[PDF] mathématiques appliquées pour l'ingénieur pdf
[PDF] mathématiques avec des pouces
[PDF] Mathématiques avec frontières 3eme
[PDF] mathématiques avec histoire pour grille
[PDF] mathématiques besoin d'aide
[PDF] Mathématiques calcul d'un pourcentage
[PDF] Mathématiques Chercher un nombre
[PDF] mathématiques classe de cinquième
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. iiTable des matieres
0 Un peu de motivation
11 Theorie des ensembles
51.1 Algebre booleenne
51.1.1 Expressions booleennes
51.1.2 Operateurs booleens et tables de verite
71.1.3 Proprietes des operateurs et demonstrations par cas
111.1.4 Demonstrations par succession d'equivalences
171.1.5 Le probleme de satisabilite d'une equation booleenne
201.1.6 Exercices sur l'algebre booleenne
241.2 Ensembles
271.2.1 Egalite entre deux ensembles (Axiome d'extensionnalite). . . . . . . 27
1.2.2 Denition d'un ensemble et operateur d'appartenance
281.2.3 Diagramme de Venn et ensemble universel
311.2.4 Quanticateur universel et quanticateur existentiel
321.2.5 Operateurs ensemblistes
351.2.6 Proprietes des operateurs et demonstrations
391.2.7 Exercices sur les ensembles
451.3 Techniques de demonstration
471.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
521.3.6 Demonstrations utilisant les proprietes de l'arithmetique
531.3.7 Demonstrations avec un \:9" ou un \:8". . . . . . . . . . . . . . . 54
1.3.8 Demonstrations par contradiction
561.3.9 Exercices sur les techniques de demonstration
581.4 Relations et fonctions
59iii ivTABLE DES MATIERES
1.4.1n-uplet et produit cartesien. . . . . . . . . . . . . . . . . . . . . . . 59
1.4.2 Denitions et representations des relations
631.4.3 Operateurs sur les relations
671.4.4 Familles de relations
721.4.5 Fonctions (totales) et fonctions partielles
811.4.6 Relations d'equivalence et ordres
861.4.7 Exercices sur les relations et fonctions
921.5 Ensembles innis
961.5.1 \Avoir autant d'elements"
981.5.2 \Autant" d'elements queN: Les ensembles innis denombrables. . . 102
1.5.3 \Avoir plus d'elements"
1041.5.4jNjest la plus petite cardinalite innie. . . . . . . . . . . . . . . . . 109
1.5.5 Donnons-nous des outils
1111.5.6 \Plus d'elements" queN: Les ensembles non denombrables. . . . . . 114
1.5.7 Exercices sur les ensembles innis
1232 Relations denies par recurrence
1262.1 Suites
1262.1.1 Denition par terme general et par recurrence
1272.1.2 Notation sigma \"
1282.1.3 Temps d'execution d'un algorithme
1292.1.4 Exercices sur les suites
1332.2 Methode des substitutions a rebours
1352.2.1 Description de la methode
1352.2.2 Quelques exemples
1362.2.3 Exercices sur la methode des substitutions a rebours
1432.3 Induction mathematique
1442.3.1 Induction mathematique faible
1442.3.2 Principe d'induction mathematique a deux cas de base
1 492.3.3 Induction mathematique forte
1 522.3.4 Exercices sur l'induction mathematique
1 562.4 Cas particuliers de recurrences
1582.4.1 Les suites arithmetiques
1582.4.2 Les suites geometriques
1592.4.3 La suite des sommes de premiers termes d'une suite
1602.4.4 Relations de recurrence lineaires et homogenes
1652.4.5 Exercices sur les cas particuliers de recurrences
1682.5 Methode des series generatrices
170TABLE DES MATI
ERESv2.5.1 L'idee de la methode
1 702.5.2 Methode de resolution et modeles de series de puissances
1732.5.3 Quelques exemples de resolution de recurrences
1 752.5.4 Recurrences lineaires homogenes d'ordre 2 (demonstration)
1822.5.5 Exercices sur la methode des series generatrices
1862.6 Approximation par une integrale
1872.6.1 Description de la methode
1872.6.2 Bref rappel sur le calcul integral
1 892.6.3 Quelques exemples
1892.6.4 Exercices sur l'approximation par une integrale
1 933 Theorie des graphes
1943.1 Elements de base. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
3.1.1 Graphes et digraphes
1953.1.2 Voisins et degre d'un sommet
1973.1.3 Sous-graphes et decompositions
1973.1.4 Cha^nes, chemins et cycles
1 983.1.5 Connexite d'un graphe
1993.1.6 Arbres
2 003.1.7 Representation matricielle
2013.1.8 Exercices sur les elements de base
2033.2 Les graphes en tant que relations
2053.2.1 Operateurs sur les graphes
2053.2.2 Isomorphisme de graphes
2073.2.3 Exercices sur les graphes en tant que relations
2083.3 Degres des sommets et nombre d'ar^etes
2093.4 Arbres
2123.4.1 Sommets et ar^etes d'un arbre
2123.4.2 Proprietes des arbres binaires
2143.4.3 Exercices sur les arbres
2163.5 Graphes planaires
2173.6 Cha^nes et chemins
2223.6.1 Proprietes d'un graphe connexe
2223.6.2 Cycles d'un graphe
2223.6.3 Algorithmes de recherche du plus court chemin
2 243.6.4 Exercices sur les cha^nes et chemins
227A Alphabet grec
228viTABLE DES MATIERES
B Documents L
ATEX230
References et suggestions de lecture
235Index236
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 informaticien1. 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.
12CHAPITRE 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 algorithmes3. 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 lorsd'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.)