Syllabus2012 2013 NotesDeCours .pdf



Nom original: Syllabus2012-2013-NotesDeCours.pdfTitre: AVERTISSEMENTAuteur: Leruste

Ce document au format PDF 1.5 a été généré par Conv2pdf.com, et a été envoyé sur fichier-pdf.fr le 18/09/2012 à 20:23, depuis l'adresse IP 87.64.x.x. La présente page de téléchargement du fichier a été vue 2248 fois.
Taille du document: 1.4 Mo (83 pages).
Confidentialité: fichier public


Aperçu du document


HAUTE ECOLE DE BRUXELLES
Catégories Economique et Technique

haute école de bruxelles

Rue Royale 67 - 1000 Bruxelles
: 02/219.15.46 - : 02/219.48.47
: esi@heb.be

Mathématique :Notes de Cours
1ère année bachelier en informatique

BEJ – CLR – CUV – JVM – LBC – MWA – NPX – NVS - YPR

2012 – 2013

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Table des matières
Pages
Avertissement …………………………………………………………………

3

Introduction ……………………………………………………………………

5

Première partie : Eléments de mathématique discrète ……….………….

12

Chapitre 1 - Arithmétique et écriture binaire ou dans d'autres bases ……..…...

13

Chapitre 2 - Logique mathématique …………………………………………...

25

Chapitre 3 – Ensembles - Relations et fonctions ...…………………………….

35

Chapitre 4 - Graphes ………………………….……………………………….

38

Chapitre 5 - Analyse combinatoire ……………………...……………………..

41

Deuxième partie : Introduction à l’analyse numérique …………………

44

Chapitre 6 – Notions basées sur les fonctions réelles ……...……………….....

45

Chapitre 7 - Suites et séries de nombres réels …………………………………

63

Chapitre 8 - Méthodes d'approximations ……..…………………………..……

69

Chapitre 9 - Séries de Fourier …………………………..……………………...

73

Chapitre 10 - Systèmes d'équations linéaires – Mise en équation

78

………….

Formulaires …………………………………………………………………….

81

Bibliographie …………………………………………………………………..

82

2

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

AVERTISSEMENT
Attention !!! Avec ce syllabus, nous n’avons pas l’ambition de vous fournir un
document détaillé mais un document squelette qui vous permettra de structurer
vos propres notes et de travailler activement le cours de mathématique en ayant
bien compris ses objectifs.
Notre intention, avec ce syllabus, n’est pas de fournir une matière détaillée qu’il suffirait
d’étudier « en suivant le guide » pour réussir l’examen. Nous voulons fournir une armature
pour un cours interactif où les étudiants peuvent développer leur capacité d’autonomie et de
réflexion personnelle dans la pratique de notions mathématiques de base, et où l’échange
avec les condisciples et avec l’enseignant est encouragé. L’étudiant volontaire utilisera le
syllabus pour organiser ses propres notes et s’orienter dans les différents aspects du cours de
mathématique (rappels et explications, travaux dirigés, résolution de problèmes).
Dans un soucis de cohérence avec cette vision du cours, nous tenons à fournir des aides à
l’étude et une bibliographie, pour aider l’étudiant volontaire à trouver une méthode de travail
efficace et à combler ses lacunes. A ce titre, il lui sera nécessaire d’avoir, à côté d’un lexique
informatique de base facile à trouver sur internet, du dictionnaire de langue française, de la
grammaire et du dictionnaire traductif anglais-français, le livre suivant:
DELEDICQ A., maths LYCÉE, éditions de la Cité (collection manuel+, 2004).
Ce livre lui permettra de trouver les notions mathématiques de base utiles non seulement pour
le cours de mathématique mais aussi pour les autres cours; il sera également un bon ouvrage
de référence après ses études.
Ce soucis de cohérence nous amènera à évaluer, lors des épreuves, la capacité de l’étudiant à
justifier ses réponses en montrant clairement par quel raisonnement il est arrivé à un résultat
cohérent avec l’énoncé proposé.
Nos choix relatifs au cours et au syllabus sont conditionnés non seulement par les intentions
décrites ci-dessus mais aussi par deux contraintes incontournables. D’une part, les étudiants
qui s’inscrivent à l’ESI ont un bagage mathématique antérieur très variable. D’autre part, le
programme ne permet pas beaucoup d’heures de mathématique sur l’ensemble du cursus ; un
certain nombre de notions sont donc pratiquées dans le cadre des laboratoires d’informatique,
ce qui ne pose pas vraiment de problème puisque l’ESI a une tradition de travail en équipe
depuis le début des années 1980.
Le cours et le syllabus sont les fruits d’une réflexion nourrie de beaucoup d’apports extérieurs
venant de différents horizons, notamment de collègues ou d’anciens collègues qui doivent être
remerciés ici pour les idées échangées lors de nombreuses concertations et pour les pages
rédigées par certains d’entre eux.
La rédaction, relecture et révision de ce syllabus ont été réalisées par :
- Laurent Beeckmans ;
- Jonas Beleho (Coordinateur) ;
- Catherine Leruste ;
- Claude Misercque ;
- Didier Willame ;
- Yves Pierseaux.
Qu’ils soient particulièrement remerciés pour ce travail.

3

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Extrait de l’avertissement, attribué à Dominique Joseph GARAT, qui figure dans l’édition,
publiée en 1799 par Madame CONDORCET, de l’ouvrage « Moyens d’apprendre à compter
sûrement et avec facilité. » écrit par CONDORCET peu avant sa mort.
« Les formules sont un secours admirable pour l’esprit; avec ce secours,
l’esprit peut, en quelque sorte, se dispenser de toute attention pénible : il
n’a qu’à suivre les formules; elles ne le dirigent pas seulement; elles le
portent. Il n’a besoin, pour arriver sûrement à son but, que du degré
d’attention nécessaire pour être certain qu’il ne manque pas à la formule et
à ses règles; et cette attention est presque matérielle; elle est des yeux,
plutôt que de l’esprit.
Les formules, en un mot, sont des espèces de machines avec lesquelles
on opère presque machinalement.
C’est un grand avantage; mais c’est aussi un grand danger; dans
l’habitude de s’appuyer sur cette espèce de force artificielle, on laisse ses
forces naturelles sans exercice; on en perd d’abord l’usage; on en perd
ensuite ses forces même.
La perte seroit plus grande que l’acquisition; et il faudroit rejeter ce
funeste secours, si on ne pouvoit pas le séparer des inconvéniens qui
l’accompagnent.
Il y a un moyen de l’en séparer; il est le seul; et c’est celui que
Condorcet a cherché, trouvé, et enseigné dans ce Traité de Calcul.
Il consiste à rendre tellement sensibles tous les motifs et tous les pas qui
ont conduit à la recherche et à l’invention des formules, qu’il soit
impossible de se servir des formules, sans que l’esprit repasse sur tous les
motifs et sur tous les secrets de leur artifice : alors, l’esprit et la main
opèrent ensemble : tantôt la main précède l’esprit; tantôt l’esprit précède la
main : mais jamais ils ne sont éloignés; toujours ils se suivent de près; et le
génie qui a créé les formules, environne toujours de sa lumière des
opérations exposées à devenir plus méchaniques qu’intellectuelles. »
Cet extrait, souligné par l’auteur du syllabus, a été recopié, en respectant l’orthographe de
l’époque, à partir du fac simile paru dans :
CONDORCET, Moyens d’apprendre à compter sûrement et avec facilité,
Art, Culture, Lecture - Editions (Paris, 1988)

4

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

INTRODUCTION
1. Objectifs du cours
-

Développer l’aptitude à définir avec précision des idées ou des concepts afin de
favoriser une communication plus sûre ;
Développer l’aptitude à formaliser ou modéliser des raisonnements ou des processus ;
Acquérir des méthodes de travail adaptées aux matières nécessitant plus de capacités
d’abstraction ;
Acquérir des aptitudes mathématiques nécessaires d’une part, aux besoins spécifiques
du bachelier en informatique dans le monde professionnel, et d’autre part, à la
poursuite d’éventuelles études complémentaires.

Le cours de mathématique doit également faire percevoir, au travers d'exemples simples, que
l'ordinateur possède des limitations non seulement d'ordre technique mais aussi d'ordre
théorique.
2. Moyens
Nous insisterons sur la capacité à utiliser et à mettre en œuvre des notions mathématiques de
base pour résoudre des problèmes inattendus:
- les techniques apprises pour résoudre certains problèmes courants
- des termes, concepts, énoncés et méthodes souvent employés
Le cours sera dispensé de manière interactive, ce qui exigera de la part de chaque étudiant
qu’il soit actif d’une manière judicieuse. Soutenu par l’échange avec ses condisciples et
l’enseignant, il pratiquera les notions lui-même en insistant sur les démarches.
3. Structure du cours
Introduction à la mathématique discrète (support conceptuel au monde numérique):
- arithmétique et écriture binaire ou dans d’autres bases
- logique mathématique : logique propositionnelle (orientée vers la conduite de
raisonnements et vers la compréhension du fonctionnement de l’ordinateur),
introduction à la logique prédicative et à la quantification de prédicats, récurrence
(outil pour la démonstration et pour la programmation)
- ensembles, relations et fonctions
- graphes
- analyse combinatoire
Eléments d’analyse numérique (support conceptuel au monde analogique et à sa mise en
œuvre numérique):
- notions basées sur les fonctions d’une variable réelle
- suites et séries de nombres réels
- méthodes d’approximation (séries de Mac-Laurin, Taylor et méthode de Newton)
- séries de Fourier
- systèmes d’équations linéaires

5

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

4. Prérequis nécessaires
Le vocabulaire et les notions supposés connus correspondent aux compétences et aux savoirs
requis à la fin de l’enseignement secondaire en mathématiques générales (cf. le document
édité par le Ministère de la Communauté française). Les lacunes pourront être comblées tout
au long de l’année en utilisant notamment l’ouvrage de référence ([1]).
Il faut donc, au minimum, que les notions suivantes et le vocabulaire qui y est attaché soient
bien assimilés :
-

en arithmétique et en algèbre :
écriture des nombres décimaux (unités, dizaines, ...),
calcul élémentaire en décimal (tables de multiplication et table des carrés jusqu’à 10*10,
addition, soustraction, multiplication et preuve par 9, division, division euclidienne et caractères
de divisibilité), calcul élémentaire appliqué à des expressions contenant des variables, calcul et
simplification de fractions (où le numérateur et le dénominateur peuvent être des nombres ou des
expressions contenant des variables), manipulation de puissances où interviennent des nombres
ou des expressions contenant des variables ( a n  a m  a n  m , a n  a n.m , a  n 
m

1

1
, an 
an

n

a ),

signe de sommation, définition de la notion de logarithme, produits remarquables, racines de
polynômes des premier et deuxième degrés, factorisation de polynômes;
-

en trigonométrie :
définitions sur le cercle trigonométrique, retrouver les sinus et cosinus des angles remarquables
à partir de ce cercle, définition de tgx et cotgx à partir de sinx et cosx,
sin2x+cos2x, relations trigonométriques élémentaires dans un triangle rectangle;

-

en analyse :
fonctions d’une variable réelle à valeurs réelles, domaine de définition et image d’une fonction,
représentation cartésienne et diagramme sagittal d’une fonction, représentation cartésienne et
définition analytique d’une fonction monotone, limites finies et infinies, cas d’indétermination,
représentation cartésienne et définition analytique d’une fonction continue ou d’une fonction
discontinue, fonction réciproque (diagramme sagittal, définition analytique et représentation
cartésienne), représentation cartésienne et définition analytique du zéro d’une fonction,
représentation cartésienne des fonctions élémentaires, transformations du graphique induites par
des modifications de la variable ou de la fonction, pente d’une droite, équation d’une droite
passant par deux points ou d’une droite de pente donnée passant par un point, sommet et axe de
symétrie d’une parabole, représentation cartésienne et définition analytique de la dérivée en un
point et de la fonction dérivée d’une fonction, formules de dérivation simples, représentation
cartésienne et définition analytique d’un extremum (maximum ou minimum) et d’un point
d’inflexion, lien entre la dérivée première et les extrema d’une fonction, lien entre la dérivée
seconde et les points d’inflexion d’une fonction, définition et représentation cartésienne des
asymptotes, démarche pour étudier une fonction, formules élémentaires d’intégration et calcul
d’intégrales simples.

5. Supports de cours et ouvrages de référence
Il est indispensable d’utiliser les notes prises au cours, le présent syllabus, et le livre d’aide à
combler les lacunes ([1]).
Pour l’étudiant qui désire revoir certaines notions élémentaires ou compléter le cours par une
explication différente, il est préférable de consulter un dictionnaire de mathématiques ou une

6

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

encyclopédie de mathématiques que de se perdre dans des manuels ou des logiciels. Des
références figurent dans la bibliographie.
L’étudiant qui désire approfondir la matière peut éventuellement consulter les ouvrages cités
dans la bibliographie.
6. Charge de travail
Du point de vue de la quantité de travail, il faudra prévoir environ cent heures de travail
personnel, réparties en un temps de mise en ordre et révision régulière du cours (au moins
deux heures par semaine) et un temps d’étude pour préparer l’examen. Cette indication vise,
bien entendu, l’étudiant motivé, présentant des aptitudes moyennes et possédant les prérequis
indiqués plus haut.
Du point de vue de la qualité du travail, il ne suffit pas de relire son cours et de refaire les
exercices proposés au cours. Il faut travailler de manière plus active : tester ses connaissances
et sa capacité à expliquer les notions vues, trouver des exemples et des contre-exemples,
inventer, résoudre et vérifier de nouveaux exercices, analyser les démarches qui permettent de
résoudre certains problèmes. Il peut être très utile de faire une partie de ce travail en petit
groupe et il est recommandé de profiter du caractère interactif donné au cours.
7. Aide à l’étude
Elle est continue. Elle permettra à l’étudiant d’apprendre à se tester et, ainsi, de mieux faire
face à l’évaluation.
Elle est constituée de diverses formes de simulation d’évaluation et elle peut donner lieu à un
bonus d’au maximum 10% du total des points prévus pour le cours. Ce bonus reflète une
estimation de l’importance et de la qualité de la participation à ces simulations.
8. Evaluation
L’évaluation portera pour moitié sur de la restitution de ce qui a été vu au cours (définitions,
exemples, exercices et problèmes exemplaires avec justification) et pour moitié sur la
résolution de problèmes inattendus.
Elle respecte par ailleurs le document officiel affiché dans les valves, conformément aux
décrets de la Communauté française.

9. Conseils pour une bonne assimilation
Attention : ces conseils sont issus, non pas d’une compilation de livres sur les méthodes de
travail, mais bien d’expériences heureuses ou malheureuses vécues par les étudiants de l’ESI
depuis de nombreuses années.

7

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Remarque importante :
il ne faut pas s’imaginer que suivre un cours suffit pour comprendre une matière en
profondeur;
même si on a l’impression d’avoir tout compris, il faut tester ses connaissances pour
être sûr de posséder une compréhension profonde de la matière;
et même si on a l’impression de n’avoir rien compris, ce n’est pas une raison pour
décider que ce n’est pas la peine d’approfondir : on a toujours compris certaines choses à
partir desquelles on peut essayer de comprendre, par soi-même, d’autres choses et on a
toujours la possibilité de discuter de la matière avec d’autres étudiants et de poser des
questions au professeur.

A lire et à méditer:
- les deux pages intitulées « Quelques méthodes de travail » dans [5],
- le livre [3].

Au préalable :
- connaître le nom de votre enseignant (cela permet une convivialité nécessaire à un bon
apprentissage dans un cadre interactif)
- organiser votre syllabus et classer vos notes pour retrouver rapidement la structure et les
notions fondamentales du cours
- commencer un formulaire en y indiquant les prérequis

Avant le cours :
-

se remettre en tête la structure du cours
se remettre en tête l’essentiel de ce qui a été vu jusque-là
consulter le syllabus pour savoir de quoi on va parler, pour essayer de comprendre déjà
en partie les définitions, propriétés et exemples qui vont être abordés

Entre autres moments, les minutes qui précèdent l’arrivée de l’enseignant peuvent être
utilement employées à cette tâche.

Pendant le cours :
-

-

autant que possible, être assis à l’avant de l’auditoire pour améliorer la convivialité et
pour être plus attentif
prendre note pour s’aider à rester concentré
prendre note en réfléchissant (ne pas attendre une compréhension parfaite pour noter les
explications du professeur mais essayer, en notant, d’extraire mentalement le mieux
possible des points essentiels)
ne pas noter mot à mot, aérer les notes, souligner et encadrer pour mettre la structure en
évidence
utiliser:

8

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

-

-

-

-

-

-

-

du papier
un crayon et une gomme (le crayon suit la craie du professeur, la gomme son
éponge)
- une petite latte et un Bic 4 couleurs
- pas d’autre matériel : on dessinera les schémas à main levée (on a besoin d’une
précision mathématique, pas d’une précision de dessinateur)
- utilisation exceptionnelle de la calculatrice pour vérifier ou affiner un calcul (on
manipulera le plus souvent des fractions et de « bonnes estimations »)
ne pas troubler par des attitudes intempestives l’atmosphère de concentration nécessaire
à l’enseignant lorsqu’il explique une notion ou un exercice et aux étudiants qui doivent
pouvoir suivre
lorsque l’on aborde une période d’exercice, écrire proprement la solution à laquelle
vous pensez de manière à ce que vous fassiez apparaître explicitement des aspects que
vous ne voyiez pas clairement et de manière à ce que le professeur puisse vous
comprendre plus sûrement
quand la démarche n’est pas bonne, ne pas hésiter à recommencer en tenant compte des
remarques de l’enseignant
oser poser les questions qui vous préoccupent (il n’y a pas de question idiote; il y a
tout au plus des questions intempestives lorsqu’un étudiant, qui ne sait pas attendre la
fin d’une explication, interrompt cette explication pour poser une question dont la
réponse se trouve dans la suite de cette explication ou lorsqu’un étudiant, pour se rendre
intéressant, pose des questions qui n’ont rien à voir avec le sujet traité)
trouver le bon moment pour poser vos questions (ne pas interrompre constamment le
développement d’une idée parce que des points vous semblent obscurs : il faut d’abord
saisir la globalité de l’idée puis poser vos questions à la fin de l’explication quitte à y
revenir durant les périodes de travaux dirigés)
adopter une attitude d’échange avec vos condisciples lors des travaux dirigés, ne les
« pompez » pas systématiquement mais ne fermez pas la possibilité d’échanger des
idées
se plier sans honte et de bonne grâce aux exigences des simulations d’évaluation

"Celui qui ne comprend pas,
et qui le dit,
est celui qui fait le plus évidemment
preuve d'intelligence,
car il a compris qu'il n'a pas compris
et c'est ce qui est le plus difficile à comprendre.
Remercions-le, car il fait un cadeau
à tous ceux qui, autour de lui, croyaient,
à tort, avoir compris."
Raymond Devos

9

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Après le cours :
- remettre ses notes en ordre au fur et à mesure (cela ne veut pas nécessairement dire
« comprendre les moindres détails après chaque leçon » mais cela veut dire « organiser
suffisamment vos notes et retenir suffisamment la structure de ce qui a été enseigné
jusque là pour ne pas être perdu à la leçon suivante »)
- remettre de l’ordre dans les notes en y ajoutant des couleurs pour mettre en évidence les
définitions, les propriétés, les exemples de base, les conseils pour une bonne assimilation,
etc….
- faire un formulaire et l’étudier au fur et à mesure de l’avancement du cours
- refaire les exercices vus au cours en analysant la démarche et voir comment adapter cette
démarche à d’autres exercices
- inventer des exercices et les résoudre puis les vérifier en appliquant les stratégies de
vérification mises en évidence au cours
- tester sa capacité à définir les notions vues au cours, à trouver des exemples et contreexemples illustrant ces notions vues au cours, à résoudre des exercices et des problèmes
(ceci peut se faire par écrit ou oralement chez soi et au calme, mentalement dans les
transports en commun par exemple, en jouant alternativement le rôle du prof et de l’élève
dans un échange avec vos condisciples, etc.…
Exploitez l’oubli :
Il faut oublier plusieurs fois pour connaître.
C’est pourquoi il faut s’y prendre longtemps à l’avance et pratiquer régulièrement
la séquence de révision suivante :
test – refixation – oubli.
On constatera qu’à chaque séquence appliquée sur une même matière, le test
révèle un peu moins d’oubli et c’est ainsi que les notions deviendront de plus en
plus familières.

10. Problèmes et exercices
Le fascicule d’exercices propose, d’une part, des problèmes et des exercices exemplaires et,
d’autre part, des activités complémentaires (exercices d’entraînement pour assimiler une
technique, problèmes reposant sur la pratique de démonstrations et de méthodes de
raisonnements classiques pour assimiler des démarches classiques, problèmes plus inattendus
mais résolubles à l’aide des prérequis ou de la matière vue au cours pour développer la
capacité de compréhension d’énoncés et la capacité d’autonomie dans le choix des démarches
à mettre en œuvre).
Chaque professeur complétera en proposant des exercices et des problèmes qui lui paraissent
utiles aux étudiants dont il a la charge.
Chaque professeur guidera ses étudiants pour qu’ils apprennent à imaginer eux-mêmes des
exercices et des problèmes, à les résoudre et à les vérifier dans des travaux de groupes où
chacun peut simuler alternativement le rôle du professeur et celui de l’élève. Cette activité
aide souvent à développer une compréhension plus profonde.

10

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

11. De la résolution de problèmes
La résolution de problèmes doit être vécue comme une aventure avec tous les risques que
cela comporte, notamment celui de ne pas y arriver. La résolution de problèmes ressemble
beaucoup à une enquête policière. Elle est au cœur de l’activité mathématique comme de
l’activité informatique et c’est en la pratiquant que l’on pourra se familiariser de plus en plus
jusqu’à atteindre l’expertise.
Pour les étudiants qui ne se sentent pas à l’aise avec cette pratique (mais aussi pour ceux qui
croient l’être), il peut être utile de dégager trois étapes de base dans le processus de résolution
de problèmes.
La compréhension de l’énoncé qui est un processus éventuellement long et difficile et qui
nécessite de poser des actes volontaires comme par exemple:
- chercher dans l’énoncé la réponse à des questions du type « Où sont les données ?»,
« Qu’est-ce qui décrit le cadre dans lequel on travaille? », « Que demande-t-on? »,
« Quelles sont les indications concernant la présentation du résultat? », etc…;
- pour rendre l’énoncé plus familier et se donner plus de chances de trouver une idée de
solution, chercher des exemples et contre-exemples, construire des représentations sous
forme de schéma, dessins, graphiques, etc.
La modélisation du problème à l’aide de calcul-type, de formules, d’équations ou systèmes
d’équations, de graphiques sera possible grâce à l’« intériorisation » du problème effectuée
lors de sa compréhension active et grâce à un appel aux notions qui font partie du bagage
mathématique requis (utilisation de la mémoire).
Enfin, la rédaction finale de la solution doit faire apparaître une synthèse claire du
raisonnement qui a été retenu, après les différents tâtonnements nécessaires, et le résultat
auquel ce raisonnement conduit.
Ces trois étapes peuvent être compliquées de retours en arrière, de vérifications, ...
Pour être cohérent avec ce qui précède, il est évident que l’évaluation d’une résolution de
problème prendra en considération la démarche suivie, ainsi que le contenu des tâtonnements
nécessaires pour y arriver.

11

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Première partie

Eléments de mathématique
discrète

12

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Chapitre 1
ARITHMETIQUE ET ECRITURE BINAIRE OU DANS D’AUTRES
BASES

ATTENTION !!!
L’expérience montre que les étudiants qui ont des difficultés de compréhension et de
calcul dans un système de numération non décimal ont, en fait, une pratique totalement
insuffisante du système de numération décimal. Il sera donc souvent utile de partir
d’exemples en base 10 pour s’aider dans les autres bases.

1. Les ensembles de nombres

. 3i – 4

. 2i + 1


.i

. –2i + 6

. 2i
. 3Π/2



. –i – 1





. 2

.e
. 3/2

. –2/5 …

. –311/4092






.-1

.-2

.-3



.0

.1


.2

.3
.9999999

.-9999





ℕ est l’ensemble des naturels, c’est-à-dire les entiers positifs (0 compris)
ℤ est l’ensemble des nombres entiers, positifs et négatifs. On les appelle aussi entiers relatifs.
ℚ est l’ensemble des nombres rationnels, c’est-à-dire ceux qui peuvent s’exprimer comme le
quotient de deux nombres entiers
ℝ est l’ensemble des nombres réels, il complète ℚ par l’ensemble des nombres irrationnels.
ℂ est l’ensemble des nombres complexes ; il contient tous les nombres de la forme a + bi où a
et b sont des réels et i est le nombre imaginaire, définit par i2 = –1.

13

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

2. Multiples et diviseurs
-

Multiple : on dit qu'un entier a est multiple d'un entier b s'il existe un entier c tel
que a = b*c.
Diviseur (dans une division entière) : dans une division entière, le diviseur est le
nombre entier par lequel on divise un autre nombre entier (appelé dividende).
Reste : le reste d'une division entière est la différence entre le dividende et le
produit du diviseur par le quotient.
Diviseur (d’un nombre) : Soient a et b deux entiers relatifs. S'il existe un entier
relatif x tel que a = b*x, on dit que b est un diviseur de a.

3. Nombres premiers
-

Définition : un nombre premier n est un entier naturel ne possédant que deux
diviseurs entiers naturels, 1 et n lui-même.
Pour tester si un nombre n est premier, il suffit de vérifier qu’il ne possède pas de
diviseur premier compris entre 2 et n .
La suite des nombres premiers commence par 2, 3, 5, 7, 11, 13, 17, 19, 23, …
Cette suite est irrégulière, on ne connait pas à ce jour une formule donnant
directement le nème nombre premier. On sait cependant qu’il en existe une infinité.

Le monde des nombres premiers est un monde passionnant qui a donné et qui donne encore
beaucoup de résultats notamment utiles en informatique (codage, sécurité, …).
La méthode la plus simple pour déterminer la suite des nombres premiers inférieurs à un
entier N donné est le crible d’Eratosthène. Le mécanisme consiste à écrire tous les naturels
compris entre 2 et N et à rayer les uns après les autres, en commençant par le plus petit, les
entiers qui ne sont pas premiers de la manière suivante : dès que l'on trouve un entier qui n'a
pas encore été rayé, il est déclaré premier, et on raye tous les autres multiples de celui-ci.
Lorsque le premier entier non rayé dépasse N , le processus est terminé, et les entiers non
rayés forment l’ensemble des nombres premiers cherché.
4. Opérateurs
-

div (quotient de la division entière) : si a et b sont des entiers, alors a div b délivre
le quotient entier par défaut de a/b.
mod (reste de la division entière) : si a et b sont des entiers, alors a mod b délivre
le reste par défaut de a/b.
ppcm (plus petit commun multiple) : le ppcm d'entiers naturels est le plus petit
multiple non nul commun à ces deux entiers.
pgcd (plus grand commun diviseur) : le pgcd d'entiers naturels est le plus grand
diviseur commun à ces deux entiers.

5. Factorielle d’un nombre
Le produit des n premiers entiers naturels 1 * 2 * 3 * 4 * … * n s'écrit n! et se nomme
factorielle de n.
Par exemple : 5! = 5 * 4 * 3 * 2 * 1 = 120
6! = 6 * 5 * 4 * 3 * 2 * 1 = 720
Attention, par définition, 0! = 1.
14

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

6. Le signe de sommation
C’est le symbole Σ. Il permet d’écrire de façon condensée une somme de termes semblables à
un élément i près qui varie de 1 en 1 entre deux nombres entiers m et n (m<n). Il est important
de bien le comprendre et de pouvoir le manier correctement. De plus, il s’apparente à la
boucle de type « pour » en informatique.
n

Exemples :

n

i

n

 ai

im

 ai

im

im

n

 2aki

3

k m

7. Puissances
7.1. Condenser une multiplication
Si b est un nombre non nul quelconque et n un entier naturel, l'écriture bn désigne le produit
b*b*b*b*…*b
n facteurs
et se lit "b puissance n" ou encore "b exposant n".
cas particuliers :
Pour n  0 :
Pour b  0 :

0n = 0
1n = 1
b0 = 1
b1 = b

7.2. L'inverse
L'inverse de b,

1
1
, peut se noter b-1 et n se note b-n .
b
b

7.3. Propriétés des puissances :

b n * b m  b nm
bn
 b nm
m
b

b 

n m

 b n*m

1
 b n
n
b
a * b n  a n * b n
n

an
a

 
bn
b

15

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

7.4. Puissances fractionnaires :
1
2

a  a
1
3

a 3 a
1
n

a n a

7.5. Puissances de 10
Dans notre système de numération, elles sont particulièrement intéressantes pour simplifier
l'écriture des grands et des petits nombres.
103 = 10 * 10 * 10 = 1000
10n = 1000…0
n zéros
1
1
10-3 = 3 
 0,001
10 1000
10-n = 0, 00…01
n zéros
7.6. Préfixes scientifiques
Dans le langage scientifique, une puissance de 10 s'indique par des préfixes grecs ou latins :
10-12
10-9
10-6
10-3
10-2
10-1
101
102
103
106
109
1012

: pico
: nano
: micro
: milli
: centi
: déci
: déca
: hecto
: kilo
: méga
: giga
: téra

8. Les bases 2 et 16 et leur utilité en informatique
La plupart des éléments électroniques que comporte un ordinateur sont bistables par nature,
cela signifie qu'ils peuvent être dans l'un ou l'autre des deux états (tels que : en service / hors
service, magnétisés positivement ou négativement, vrai ou faux, …). Ces deux états sont
généralement notés par 0 et 1, qui sont également les chiffres correspondant au système de
numération binaire.

16

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Pour être traité par l'ordinateur, l'information doit être codée d'une manière quelconque en
séquence de bits, c'est-à-dire en nombres binaires. Cependant, les informaticiens considèrent
que des chaînes telles que 110100110110 ou encore 110101100110 … sont difficiles à
mémoriser et/ou à distinguer. Les systèmes octal (base=8) et hexadécimal (base=16) ont été
développés pour lire très facilement le langage machine et « débugger » les programmes. En
effet, d'une part, 8 et 16 sont tous les deux des puissances de 2, ce qui assure (comme nous le
verrons) une conversion presque immédiate entre ces systèmes et le système binaire et, d'autre
part, parce que les systèmes octal et hexadécimal sont comparables au système décimal en ce
qui concerne la compacité.
Imaginons que, comme les pionniers de l’informatique, nous construisions avec des lampes,
des fils, des interrupteurs, etc, un calculateur que nous nommons X. Ceux qui ont visité des
expositions scientifiques ont peut-être pu voir des réalisations de ce type. Pour simplifier,
nous construisons une mémoire faite de mots de 4 « bits ». Nous imaginons ensuite des
opérations (recopier, =, ¬, +, -, etc) que nous voudrions faire réaliser par X sur le contenu des
mots de la mémoire et nous construisons l’unité arithmétique et logique. On remarquera
d’abord que, en fonction de l’opération qui est réalisée, le contenu du mot sera « compris »
différemment (contenu alphabétique si l’opération recopie, contenu logique si l’opération est
une négation, etc.). Les opérations arithmétiques « comprendront » le contenu du mot comme
un nombre. Quels nombres peuvent être représentés sur 4 bits ? Certaines opérations
« verront » les nombres entiers de 0 à 15, d’autres, les nombres entiers de –8 à 7. On se
familiarisera avec les notions de base 2, de base 16 et de complément à 2 en base 2 en jouant
avec X.

Il n’a pas fallu attendre l’ordinateur, pour que l’homme dû employer les notions de chiffre et de base.
Dès que le problème s’est posé de représenter les nombres, ces notions se sont précisées
progressivement.

Quand la notion de nombre est-elle apparue ? On pense souvent que cette apparition
est liée au besoin de compter ses troupeaux et ses richesses, compter les jours pour les
semailles, etc. ... En réalité, cette vision des choses est très schématique et peut-être
fausse, au moins en partie; les découvertes archéologiques et les travaux
d’interprétation historique semblent apporter constamment de nouvelles questions à ce
sujet.
Une autre question est de savoir quand on a commencé à écrire les nombres :
vraisemblablement au moment de l’apparition de l’écriture, au Proche-Orient, durant
le quatrième millénaire avant Jésus-Christ.
Toutes les grandes civilisations ont utilisé un ou plusieurs systèmes de numération (on
retrouve notamment les bases 10, 20, 60). La plupart ont adopté un système de
numération de position; il est à remarquer que les romains ne l’ont pas fait.

En base binaire, on représente les nombres (quantités) selon le même principe qu'en base
décimale; la différence est que, au lieu de considérer des dizaines, on considère des
"deuzaines"; au lieu de considérer des centaines, on considère des "quatraines", …

17

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Par exemple : Soit la quantité représentée par 2310 = 2 * 10 + 3 = 2 * 101 + 3 * 100 .
1 dizaine

1 dizaine

**********

**********

1 * 16 = 1 * 24

1*4 = 1*22

3 unités

***
1*21 1*20

2310 = 1*24 + 0*2³ + 1*2² + 1*21 + 1*20 = 101112 .
= 1*161 + 7*160 = 1716 .

décimal
0

Binaire
0

hexadécimal
0

quantité

1

1

1

2

10

2

3

11

3

4

100

4

5

101

5

6

110

6

7

111

7

8

1000

8

9

1001

9

10

1010

A

11

1011

B

12

1100

C

13

1101

D

14

1110

E

15

1111

F

16

10000

10

17

10001

11

18

10010

12

19

10011

13

20

10100

14

.
..

….
…..
……
…….
……..
………
……….
………..
…………
………….
…………..
……………
…………….
……………..
………………
……………….
………………..

9. Définitions
9.1.Système de numération
C’est un ensemble de conventions d’écriture qui permet de représenter et, éventuellement, de
manipuler des nombres.
18

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Remarque : on ne peut pas toujours utiliser le système de représentation des nombres pour les
additionner. Par exemple :

+

321
51

=

372

+

CCCXXI
LI
???

9.2.Système de numération de position
Remarque préliminaire : deux prérequis indispensables pour la suite sont, d’une part, les
propriétés des puissances et, d’autre part, le signe de sommation .
Pour définir un système de numération de position, on doit se donner un nombre entier positif
différent de 0 et 1 appelé BASE (que nous noterons a) et un ensemble de caractères appelés
CHIFFRES (nous les noterons bi ) qui permettent de représenter les nombres de 0 à a 1 (il y a
donc bien a nombres).
Un nombre entier positif sera représenté par bn bn1 ... b1b0 .
En se rappelant comment on a appris l’écriture des premiers nombres entiers au début de
l’enseignement primaire, on verra que l’on peut exprimer par la formule suivante le lien qui
existe entre l’écriture du nombre et l’expression de la quantité qui lui correspond dans un
système de numération donné :
à comprendre:
n

(bn bn 1 ...b1b0 ) a  bi a i
i 0

Par exemple, dans 23510, b0=5, b1=3, b2=2,
2

car

 b 10
i 0

i

i

 b0 *10 0  b1 *10 1  b2 *10 2

 5 *100  3 *101  2 *102 .

On citera les systèmes les plus courants : binaire (base=2), octal (base=8), décimal (base=10),
duodécimal (base=12), hexadécimal (base=16), sexagésimal (base=60).
10. Conversions entre les différents systèmes
Convertir un nombre d’une base a dans une base a’ signifie chercher la représentation de
ce nombre dans le système en base a’ à partir de sa représentation en base a. La quantité
n’est pas modifiée.
10.1.Conversion en décimal d’un nombre entier donné en base a
n

On calcule, en décimal, la somme

 bi a i .
i0

Par exemple, 2A816 = 2*16² + 10*161 + 8*160
= 2*256 + 160 + 8 = 680.

19

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

10.2.Conversion en base a (resp. an) d’un nombre entier donné en base an (resp. a)
Cette conversion très simple repose sur la constatation suivante : un chiffre en base a n est écrit
avec n chiffres en base a.
Par exemple, convertissons 1001011012 en base 16 :
1001011012

= 1*28 + 0*27 + 0*26 + 1*25 + 0*24 + 1*23 + 1*2² + 0*21 + 1*20

Mettons en évidence les puissances de 16 :
= 1*28 + (0*23 + 0*22 + 1*21 + 0*20)*24
+ (1*23 + 1*2² + 0*21 + 1*20) *20
²
= 1*(24) + (0*23 + 0*22 + 1*21 + 0*20)*24
+ (1*23 + 1*2² + 0*21 + 1*20) *20
= 1*162+ 2*161 + 13 *160
= 12D16
Nous pouvons donc en déduire que pour passer de la base 2 à la base 16 = 24, nous pouvons
regrouper par paquets de 4 :
1 0 0 1 0 1 1 0 12

=

0 0 0 1 0 0 1 0 1 1 0 12

=

1
1 2 D16.

2

13 = D

10.3.Conversion en base a d’un nombre entier donné en décimal
On cherche combien de « paquets » de a unités on peut trouver dans la quantité désignée par
le nombre donné ; les unités qui restent fournissent le dernier chiffre du résultat. On cherche
ensuite le nombre de « paquets » de a « paquets de a » que l’on peut mettre en évidence ; etc.
On utilise donc l’algorithme de division à plusieurs reprises comme dans l’exemple qui suit.
Convertissons 12510 en base 8 :
125
-8
45
-40
5

8

15
-8
7

15

Donc 12510 = 1758

car

8
1

1
-0
1

8
0

12510 = 15*8 + 5
= (1*8 + 7)*8 + 5
= 1*8² + 7*8 +5

20

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

11. Conversion de la partie non entière :
11.1 Conversion en décimal de la partie non entière donnée en base a
On utilise la même formule que précédemment, en faisant intervenir des exposants négatifs de
la base.
Par exemple : 0,1012 = 1*2-1 + 1*2-3 = 1/2 + 1/8 = 5/8 = 0,625
11.2 Conversion de base a en base an et vice versa (de la base an en base a)
Elle fonctionne suivant le même principe que précédemment : à n chiffres consécutifs de la
base a correspond un chiffre en base an. Attention, pour la partie non entière, les groupements
en paquet de n chiffres commencent à droite de la virgule et doivent, le cas échéant, être
complétés par des 0.
Exemple : écrire en base 8 le nombre binaire 0,10111012
0,10111012 = 0,101 110 1002 = 0,5648
11.3 Conversion de base 10 en base a
Un partie décimale représente un nombre inférieur à 1, c’est-à-dire un nombre inférieur à a de
« a-ièmes » additionné à un nombre inférieur à a de « a2-ièmes », etc.
On utilise donc l’algorithme de multiplication comme dans les exemples qui suivent.
Exemple 1 : écrire 0,37510 en binaire :
0,375
0,75
1,5
1

(on multiplie par 2)
(on multiplie à nouveau par 2)
(on multiplie par 2 uniquement la partie non entière, càd 0,5)

On obtient un entier, l’algorithme s’arrête et on obtient en lisant les parties entières obtenues :
0,0112
Exemple 2 : écrire 0.410 en base 3
0,4
(on multiplie par 3)
1,2
(on multiplie uniquement la partie non entière, càd 0,2)
0,6
1,8
2,4
on retrouve la partie non entière initiale (c-à-d 0,4).Une boucle
1,2
infinie débute ici…

On obtient un nombre illimité périodique en base 3 : 0,410 = 0,101210121012…3
12. Opérations arithmétiques en base quelconque
Nous montrerons ici comment transposer dans une autre base les algorithmes connus en base
10 pour calculer l’addition et la soustraction ainsi que les techniques pour vérifier ces calculs.
Nous verrons aussi ce que deviennent dans une base a quelconque des algorithmes tels que la
multiplication, la preuve par 9, la division euclidienne.

21

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

13. Critères de divisibilité
13.1. Critère qui concerne les diviseurs de la base :
En base a, un nombre n est divisible par un diviseur d de a si le dernier chiffre de n est un
multiple de d.
13.2. Critère qui concerne les diviseurs de la (base - 1) :
En base a, un nombre n est divisible par un diviseur d de (a-1) si la somme des chiffres de n
est un multiple de d.
13.3. Critère qui concerne ak
En base a, un nombre n est divisible par ak si le nombre n se termine par au moins k zéros.
13.4. Remarque :
Un caractère de divisibilité sert essentiellement à « échapper » à la division euclidienne. [En
informatique, une application directe de ceci est la reconnaissance d’un demi-mot, d’un mot
ou d’un double-mot dans un dump en langage machine.]
14. Manipulation de nombres en compléments à 2, à 16, à a
But : Manipuler des nombres positifs et négatifs à l’aide d’un nombre limité de chiffres (un
nombre limité de digits).
Les compléments arithmétiques interviennent dans deux situations différentes mais qui ont
néanmoins des rapports.
Tout d'abord, dans le cas du rangement des nombres dans l'ordinateur. Alors que les humains
utilisent les signes + et – pour noter les nombres positifs et négatifs, l'ordinateur ne peut traiter
des informations que sous forme de bits. Bien qu'il soit possible de réserver un bit pour
affecter un signe à un nombre (disons 0 pour + et 1 pour –), de nombreux ordinateurs rangent
les nombres sous la forme de leurs compléments.
Les compléments interviennent également au cours de l'opération de soustraction. En fait, les
compléments peuvent être utilisés pour réduire la soustraction à une addition. Cela est
particulièrement utile pour éviter la possibilité de retenues répétées d'une colonne à une autre.
Il existe deux types de compléments : le complément à la base moins un et le complément à la
base.
Nous allons commencer par examiner ces compléments dans le cadre du système décimal, où
ils sont respectivement appelés complément à 9 et complément à 10. Nous passerons ensuite
au système binaire où ils sont respectivement appelés complément à 1 et complément à 2.
14.1. Notion de complément à 10
Soit A un nombre décimal. Le complément à 9 de A est obtenu en soustrayant de 9 chaque
chiffre de A. Et le complément à 10 de A est le complément à 9 de A auquel on ajoute 1.
Par exemple :
Nombre décimal
Complément à 9
Complément à 10

4308
5691
5692

123123

9672

751620

22

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

14.2. Notion de complément à 2
En informatique, la nécessité d’utiliser la notion de complément à 2 apparaît lorsqu’on veut
réaliser des opérations arithmétiques. En effet, on doit pouvoir représenter les éléments d’un
ensemble fini de nombres entiers positifs et négatifs sur un nombre fixe n de positions. En
outre, on doit trouver un mode de représentation qui fournit des résultats corrects. Enfin, la
notion de complément à 2 permet de concevoir un seul circuit (l’additionneur) pour réaliser
aussi bien l’addition que la soustraction, et donc toutes les opérations arithmétiques.
La terminologie et les principes de la complémentation en système décimal peuvent être
facilement appliqués au système binaire, le complément à 1 de A est obtenu en soustrayant de
1 chaque chiffre de A, le complément à 2 de A est le complément à 1 de A auquel on a ajouté
1.
Par exemple :
Nombre binaire
Complément à 1
Complément à 2

111100001111 110011001100 111000111000
000011110000
000011110001

Notons qu'en prenant le complément à 1, nous avons simplement interverti chaque chiffre,
c'est-à-dire que les 0 sont remplacés par des 1 et inversement.
La machine X définie plus haut avec des mots de 4 bits nous permet d’expérimenter assez
simplement le comportement des nombres de -8 à 7, en complément à 2 sur 4 positions. Cette
manipulation concrète devrait aider à mieux se familiariser avec la généralisation en base a.
14.3. Généralisation en base a
La notion de complément à 2 peut être généralisée en la notion de complément à a en base a
sur n positions (par abus de langage: « complément à a »). L’algorithme de calcul du
complément à a d’un nombre entier à n positions X comporte deux étapes:
1°) remplacer chaque chiffre de X par son complément à a-1 (ce qui donne (a n  1)  X );
2°) ajouter 1 à ce résultat (ce qui donne le complément à a: a n  X ).
Le complément à a du complément à a d’un nombre est ce nombre et les opérations
arithmétiques sont respectées lorsqu’on n’est pas en situation de dépassement de capacité.
[En machine, il existe plusieurs types de représentation des nombres, notamment le binaire
absolu et le binaire en complément à 2; ce sont les instructions qui indiquent comment telle
zone mémoire doit être interprétée.
En pratique, le programmeur utilise couramment le complément à 2 et le complément à 16
lorsqu’il veut décoder des portions de mémoire, notamment dans certaines situations de
debugging.]
14.4. Soustraction en complément à 2
Comme dans le cas du système décimal, nous effectuons la soustraction binaire en ajoutant le
complément à 1 auquel on ajoute 1 ou en ajoutant le complément à 2.
Exemple 1 : Calculer Y = B – A où A = 10001110 et B = 11110000,

23

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

a) Par la méthode usuelle de soustraction :
0 1 1 10

11110000
-10001110
01100010
Notons qu'il a fallu opérer une retenue jusqu'au troisième chiffre à gauche.
b) En ajoutant le complément à 1 de A, soit 01110001 :
1 1 1

11110000
+ 01110001
1

101100001
+
1
01100010
Nous supprimons le 1 de tête, puis nous ajoutons 1 à la somme.
c) En ajoutant le complément à 2 de A, soit 01110010 :
1 1 1

11110000
+ 01110010
101100010
Il suffit alors de supprimer le 1 en tête pour obtenir la solution.
Exemple 2 : Calculer Y = B – A où A = 110011 et B = 101010, le complément à 2 de A est
001101 qui, ajouté à B donne :
1

101010
+ 001101
110111

=Z

Notons qu'il n'y a pas de 1 de tête à supprimer, par conséquent, le résultat Z obtenu n'est pas la
différence Y cherchée. La raison en est que A est plus grand que B. Pour obtenir Y, il faut
prendre la valeur négative du complément à 2 de Z, c'est-à-dire –001001.
14.5. Généralisation : soustraction en complément à a
La notion de soustraction en complément à a consiste soit à ajouter le complément-à-a-moinsun auquel on ajoute 1 soit à ajouter le complément-à-a. Il suffit alors de supprimer le 1 de
tête, ce qui conduirait de toute façon à un dépassement de capacité dans le cas de registres ou
de prendre le complément-à-a du résultat obtenu si le terme à soustraire était plus grand que le
terme de départ.

24

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Chapitre 2

LOGIQUE MATHEMATIQUE
1. Proposition
1.1. Définition :
Une proposition est une affirmation qui est soit vraie, soit fausse.
Exemples:

- "La carotte est un légume." est une proposition.
- "Je mens" n'est pas une proposition.

En logique propositionnelle (comme en arithmétique, en algèbre, ...), on raisonne la plupart du
temps sur des propositions quelconques que l’on note p, q, r, ... Comme on ne connaît pas à
priori la valeur de vérité de la proposition, on doit envisager tous les cas possibles, ce qui
nécessitera l’utilisation de tables de vérité.
1.2. Connecteurs usuels
Soient p, q des propositions quelconques. On peut les connecter et la valeur de vérité de la
formule ainsi obtenue est exprimée par une table de vérité.
Négation
p
1
0

p
0
1
Conjonction
p
0
0
1
1

q
0
1
0
1

pq
0
0
0
1

p
0
0
1
1

q
0
1
0
1

pq
0
1
1
1

p
0
0
1
1

q
0
1
0
1

p q
0
1
1
0

Disjonction

Disjonction exclusive

25

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Equivalence
p
0
0
1
1

q
0
1
0
1

p q
1
0
0
1

Exemples:
- La négation de "Il pleut" est "Il ne pleut pas".
- Que signifie "vous n'êtes pas sans ignorer que ..."?
- L'affirmation "Il pleut OU l'orage éclate" est fausse s’il n'y a ni pluie ni orage.
Remarque: on fera le parallèle avec les notations employées en algèbre des circuits.
On peut construire des formules en connectant des propositions, mais aussi en connectant
d’autres formules. La valeur de vérité de la formule obtenue dépend des valeurs de vérité des
propositions qui y figurent.
Exemple:
On peut construire la formule  p  q   p  q en connectant les propositions p et q.
Si on calcule la table de vérité de cette formule, on obtiendra la valeur de vérité de cette
formule pour les différents cas de valeurs de vérité de p et q.
p
0
0
1
1

q
0
1
0
1

pq
0
1
1
1

p
1
1
0
0

q
1
0
1
0

p  q (pq)(pq)
1
0
1
1
1
1
0
0

Remplaçons les propositions p et q par les occurrences « La carotte est un légume » et « La
pomme est un fruit » et trouvons la valeur de vérité de la formule ainsi obtenue.
1.3. Tautologie
Définition :
Une tautologie est une formule toujours vraie (c'est-à-dire dont la dernière colonne de la table
de vérité ne contient que des 1) quelles que soient les valeurs de vérité des propositions qui y
figurent. Le très grand intérêt des tautologies est de fournir des méthodes de raisonnement
sûres; quelques exemples suivent.
Exemples: Soient p, p1,..., pn, q, r, des propositions quelconques, V la proposition vraie et F la
proposition fausse ; les équivalences suivantes sont des tautologies :
- commutativité de  :

(p  q)  (q  p)
si on remplace dans cette formule  par ,  , ou , on obtient aussi une tautologie;
- neutres pour  et :
- V est absorbante pour  :

(p  V)  p et (p  F)  p
(p  V)  V

26

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

- F est absorbante pour  :
(p  F)  F
- distributivité:
(p  (q  r))  ((p  q)  (p  r))
(p  (q  r))  ((p  q)  (p  r))
- contradiction et tiers-exclu :
(p  p)  F et (p  p)  V
- idempotence pour  et  :

(p  p)  p et (p  p)  p

- double négation:
(p)  p

- associativité de  et de  :

(p  (q  r))  ((p  q)  r)
(p  (q  r))  ((p  q)  r)
- lois de de Morgan (dualité) :
(p  q)  (p  q)
(p  q)  (p  q)
- généralisation :
(p1  p2 ... pn)  (p1  p2 ... pn)
(p1  p2 ... pn)  (p1  p2 ... pn)
- l’équivalence de deux propositions peut être remplacée par l’équivalence de leurs
négations :
(p  q)  (p  q)
Les tautologies ci-dessus donnent des propriétés qui permettent de simplifier les formules. En
informatique, la conception de circuits logiques digitaux, mais aussi la construction de
programmes efficaces, exploitent ces lois.
Remarque: une antilogie (ou contradiction) est une formule toujours fausse quelles que soient
les valeurs de vérité des propositions qui y figurent.
1.4. Implication
L’implication (en anglais : logic implication) exprime le fait que, à partir d’une hypothèse ou
prémisse, on déduit une conclusion. On note l’implication  et la table de vérité est :
p
0
0
1
1

q
0
1
0
1

pq
1
1
0
1

27

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Remarque: vous aurez une meilleure intuition de cette table en réfléchissant au fait que, par
exemple, l'affirmation "quand il pleut, je reste chez moi" est un mensonge dans le seul cas où
je sors quand il pleut.
En informatique, « si ... alors ... » ou « if ... then ... » expriment l’implication.
Propriétés :
1) Expression de l’implication à l’aide de la négation et de la disjonction :
( p  q )  (p  q )
Cette formule permet de faciliter certains raisonnements mais aussi de construire un circuit
réalisant le « if ... then ... »:

2) Bi-implication :
(p  q)  ((p  q)  (q  p))
3) Contraposée de l’implication ( modus tollens ) :
La contraposée de (p  q) est l’implication q  p
L’implication est équivalente à sa contraposée :
(p  q)  (q  p)
4) Réciproque de l’implication :
La réciproque de (p  q) est l’implication q  p
L’implication n’est pas équivalente à sa réciproque.
5) Négation de l’implication :
La négation d’une implication s’exprime à l’aide d’une conjonction :
 (p  q)  (p  q)
6) Inverse de l’implication :
L’inverse de (p  q) est l’implication (p  q)
Noter que la contraposée de l’inverse est la réciproque.
7) Raisonnement par l'absurde :
(p  q)  ((p  q)  F)
8) Règle de déduction (Modus ponens ou plus exactement modus ponendo ponens):
((p q)  p)  q)
9) Syllogisme :
((p  q)  (q  r))  (p  r)

1.5. Forme normale disjonctive
Toute formule du calcul propositionnel classique peut s'écrire, d'une et une seule façon à
l'ordre près, sous forme normale disjonctive, c'est-à-dire sous la forme d'une disjonction de
termes comprenant chacun toutes les variables ou leur négation réunies par une conjonction.
Des applications de cette propriété sont vues au cours qui traite de la structure des
ordinateurs.

28

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

2. Prédicat ou condition
2.1. Rappel sur les ensembles
Définitions :
Un ensemble E est une collection d’objets.
Chaque objet est appelé un élément.
On dit qu'un élément x appartient (ou n'appartient pas) à l'ensemble E et est noté
xE et xE.
On peut aussi dire alors que E comprend (ou ne comprend pas) x, ce qui est noté
E  x.
Cardinal :
Le cardinal de E est le nombre d’éléments appartenant à l’ensemble E.
Il est noté E ou E. Le cardinal d’un ensemble peut être fini ou infini (notamment
dénombrable ou continu).
Ensemble vide : C’est l’ensemble qui ne contient aucun élément. On le note Ø ou {}
Définition en extension et en compréhension :
Il est possible de décrire un ensemble de 2 façons :
- Soit on décrit l'ensemble en donnant tous ses éléments séparés par des virgules :
{ a, b, c, d }
Exemple : E = {BEJ, NVS, LBC, YPR, CLR}
- Soit on décrit l'ensemble en donnant la/les caractéristiques de ses éléments:
{ x | x obéit à une caractéristique bien précise }
Exemple : E = {profs | profs de l'ESI qui donnent le cours de math}
Egalité et inclusion de deux ensembles :
Deux ensembles sont égaux s'ils contiennent les mêmes éléments.
Un ensemble A peut être contenu dans un ensemble B plus grand, on dit alors que A est inclus
à B (ce qui est noté A  B) ou encore que B contient A ( B  A).
Remarque : Dans le cas d'égalité possible entre A et B, nous noterons
A  B ou encore B  A.
Opérations sur les ensembles
- l'union : A  B = l’ensemble des éléments qui appartiennent à A ou à B.
- l'intersection : A  B= l’ensemble des éléments qui appartiennent à A et à B.
- la différence : A \ B = l’ensemble des éléments qui appartiennent à A mais pas à B.
- la différence symétrique : A  B Il s'agit de l'union privée de l'intersection.
Représentation à l’aide des diagrammes de Venn :
Soient A et B deux ensembles, représentons les différents opérateurs à l'aide des diagrammes
de Venn :
-

l'union : A  B
A

B

29

ESI (HEB)

-

Bachelor en Informatique

-

Mathématique

B

la différence : A \ B
A

-

Année académique : 2012 -2013

l'intersection : A  B
A

-

-

A\B

B

la différence symétrique : A  B
A

B

Complémentaire d’un ensemble A :
Le complémentaire de A est l’ensemble des éléments qui n’appartiennent pas à A dans un
ensemble de référence E. Il est noté CE(A) ou A
E

CEA
A

L'ensemble des parties de E :
P(E) = {A | A  E } est appelé l'ensemble des parties de E.
Exemple : E={a, b, c}
P(E)= { Ø , {a},{b},{c},{a,b},{a,c},{b,c},{a,b,c} }
2.2. Définition d’un prédicat et exemples
Une fonction propositionnelle, un prédicat ou une condition est une expression dont la valeur
de vérité (vraie ou fausse) dépend d'une ou de plusieurs variables.
On a les exemples suivants:
p(x) : x > 5
q(x,y) : x + y = 3
Définition:
Le domaine de définition d’un prédicat est l’ensemble sur lequel le prédicat peut être vérifié
(pour simplifier, on supposera toujours ce domaine non vide).
La classe de vérité de ce prédicat est l'ensemble des éléments du domaine de définition où il
prend la valeur vrai.

30

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Exemples :
Soient ℝ et ℝ2 respectivement les domaines des fonctions p(x) et q(x,y), on a:
classe de vérité de p(x):

{x∈ℝ | x>5}

classe de vérité de q(x,y):

{(x,y)∈ℝxℝ | y = -x+3 }

2.3. Connexion des prédicats
Soient p(x) et q(x) des prédicats dont le domaine de définition est E, on peut les connecter
entre eux et la valeur de vérité de la fonction résultat est obtenue en utilisant les tables de
vérités.
Soient A et B respectivement les classes de vérité de p(x) et q(x), on a :
classe de vérité de p(x) :
CEA
classe de vérité de p(x)  q(x) :
AB
classe de vérité de p(x)  q(x) :
AB
classe de vérité de p(x)  q(x) :
CE(A  B)
classe de vérité de p(x)  q(x) :
(CEA)  B
Remarques:
- p(x)  q(x) est vraie xE ssi A = B
- p(x)  q(x) est vraie xE ssi A  B
- Si on remplace dans une tautologie toutes les occurrences des propositions p, q, r, ...
respectivement par les fonctions p(x), q(x), r(x), ..., on obtient TOUJOURS un prédicat vrai
sur tout le domaine de définition (attention: si on remplace dans un prédicat vrai sur tout le
domaine de définition toutes les occurrences des fonctions p(x), q(x), r(x), ...respectivement
par les propositions p, q, r, ..., on n'obtient PAS TOUJOURS une tautologie).
Exemple :
On considère p(x) et q(x) deux prédicats définis comme suit :
p(x) : 2 ≤ x < 7
q(x) : 5 < x < 9
cherchons la classe de vérité de ( p(x)  q(x) ).
- on fait une analyse par la méthode ensembliste ou en établissant une table de vérité à partir
d'une analyse de tout intervalle où p(x) et q(x) ne varient pas.
- on dessine la droite réelle et on y place les classes de vérité.
a) Travaillons d'abord dans ℝ : Dom p(x) = ℝ et dom q(x) = ℝ.

1

2

3

4

5

6

7

8

9 10 11 12
classe de vérité de p(x)
classe de vérité de q(x)
classe de vérité de p(x)  q(x).

31

ESI (HEB)

Bachelor en Informatique

-

x
]-∞, 2[
[2, 5]
]5, 7[
[7, 9[
[9, +∞[

Mathématique

P(x)
0
1
1
0
0

-

Année académique : 2012 -2013

p(x)  q(x)
0
1
1
1
0

q(x)
0
0
1
1
0

En résumé, la classe de vérité de p(x)  q(x) = [2, 9[ = { xℝ | 2 ≤ x < 9}
b) Travaillons maintenant dans ℕ : Dom p(x) = ℕ et Dom q(x) = ℕ.
Au lieu d'une droite continue, nous avons maintenant :

.

.

.

.

.

.

.

.

.

.

.

. …ℕ

0

1

2

3

4

5

6

7

8

9

10

11

classe de vérité de p(x)

classe de vérité de q(x)

.

.

.

.

.

.

.

.

. …ℕ

0

1

2

3
4
5
6
7
classe de vérité de p(x)  q(x)

8

9

10

11

.

.

.

En résumé, si le domaine est ℕ, la classe de vérité de ( p(x)  q(x) ) = {2, 3, 4, 5, 6, 7, 8}

2.4. Quantification
2.4.1. Définition et exemple:
On quantifie un prédicat en utilisant les quantificateurs universels. Notons les deux
quantificateurs universels :  (pour tout) et  (il existe).
Exemples de quantification où p(x) et q(x,y) sont des prédicats:
x p(x)
 x p(x)
x y q(x,y)
x y q(x,y)
etc.
La quantification permet de transformer une fonction propositionnelle en proposition. Elle
permet aussi de transformer un prédicat à n variables en prédicat à n-1, n-2, ... variables.
On a, par exemple, (xℝ) (x>5) qui est une proposition vraie.
On a les propriétés suivantes:
 x p(x) est vraie ssi classe de vérité de p(x)  
 x p(x) est vraie ssi classe de vérité de p(x) = domaine de définition de p(x)

32

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

2.4.2. Négation des prédicats quantifiés :
Lorsqu’on nie les quantificateurs, on a les tautologies suivantes:
1)

(x p(x))  (x p(x))
(x p(x))  (x p(x))

2)

(x y q(x,y))  (x y q(x,y))
(x y q(x,y))  (x y q(x,y))
(x y q(x,y))  (x y q(x,y))
(x y q(x,y))  (x y q(x,y))

3. Récurrence
3.1. Motivation
Le raisonnement par récurrence (ou par induction) est à la base d’un type de démonstration en
mathématique, mais aussi d’un type de conception de programme en informatique [on pense
par exemple au calcul par récurrence -les mots « récursion » ou « récursivité » sont aussi
employé en informatique- de la factorielle d’un nombre et d’autres problèmes qui seront
résolus au cours de « logique et techniques de programmation »].
3.2. Principe
La récurrence ne peut être appliquée qu’à des propriétés ou des processus qui concernent des
ensembles dénombrables et ordonnés. En mathématique, on démontrera ainsi certaines
propriétés sur des ensembles infinis dénombrables et ordonnés de la même manière que
l’ensemble des nombres entiers naturels. Attention, cette technique N'est PAS valable pour
des ensembles continus.
La démonstration par récurrence comporte deux parties et une conclusion:
- partie1 : la démonstration de la propriété pour la valeur initiale c’est-à-dire la valeur la plus
petite de l’ensemble de référence (par exemple 0 pour l’ensemble ℕ),
- partie2 : l’induction (aussi appelée « l’hérédité ») qui consiste à démontrer que SI la
propriété est vraie pour un élément quelconque k de l’ensemble, ALORS elle est vraie pour
l’élément suivant k+1 (on doit donc bien utiliser l’hypothèse qui dit que cette propriété est
vraie pour k pour démontrer qu’elle est vraie pour k+1).
- conclusion : C’est lorsque ces deux parties sont démontrées que l’on peut affirmer
automatiquement que la propriété est vraie pour tout l’ensemble.
Pour appliquer la logique prédicative, on remarquera que l’on peut résumer ce principe de
récurrence, en prenant ℕ comme référentiel, par une formule que l’on appelle règle
d'induction :
((0)  nℕ ((n)  (n+1))  nℕ (n) est vraie.

33

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Tout raisonnement par récurrence, tout processus récurrent (ou « récursif » comme disent
erronément certains informaticiens), aura toujours cette même structure.
[En informatique, par exemple, on concevra un programme récurrent de la manière suivante:
programmer, d’une part, la valeur initiale et, d’autre part, le calcul, à partir d’une valeur
quelconque, de la valeur suivante. Le programme pourra ainsi calculer toute valeur sur
l’ensemble de référence en s’appelant lui-même.]

3.3. Exemple : Démontrer par récurrence que : 2n  n+1 nℕ
Cas initial :
Prouvons que cette propriété est vraie pour n=0 :
20  0+1 ?
1  1 ? ok.
Induction (ou Hérédité):
Supposons que pour un élément kℕ : 2k  k+1,
montrons alors que 2k+1  (k+1) +1 c'est-à-dire 2k+1  k+2.
Preuve:
2k+1 = 2k * 2
Or, par hypothèse d'induction, 2k  k+1, donc
2k+1  (k+1) * 2
2k+1  2k + 2
Or, kℕ, 2k  k, donc
2k+1  k + 2.
CQFD
Conclusion : p(0) vrai et n p(n)  p(n+1). Donc  nℕ p(n) vrai.
3.4. Exemple qui montre l’importance de l’initialisation (du cas initial)
Voici un exemple où l’induction ( l'hérédité ) marche, mais pas l'initialisation.
p(n): L'entier 10n+1 est divisible par 9.
Cas initial : ? ? ?
Induction :
Supposons p(n) vraie, cela veut dire qu’il existe un entier k tel que 10n+1=9k ;
Montrons alors que p(n+1) est vraie, c’est-à-dire qu’il existe un entier k’ tel que 10n+1+1=9k’.
Preuve :
10n+1+1=10×10n+1=10(10n+1-1)+1
Or, par hypothèse 10n+1=9k, donc 10n+1+1=10(9k-1)+1=90k-9
10n+1+1=9(10k-1)=9k’ avec k’=10k-1 ; 10n+1+1 est bien divisible par 9 !!!

Bien entendu la propriété est FAUSSE !!!

34

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Chapitre 3

ENSEMBLES - RELATIONS et FONCTIONS
1. Couple
- Définition : suite finie de longueur 2 dont les première et deuxième composantes sont
souvent appelées respectivement « origine » et « image ».
- Notation : (a,b) où a est l’origine et b est l’image.
- Couple identique : (a,b) où a=b
- Couple réciproque de (a,b) : (b,a)
- On peut généraliser la notion de couple en définissant des triples (a1,a2,a3), des quadruples
(a1,a2,a3,a4) ou ... des n-uples (a1,a2,...an).
2. Produit cartésien
Le produit cartésien des ensembles A et B est l’ensemble de tous les couples (a,b) où a
appartient à A et b appartient à B. On le note A  B



a A   b B

A  B  a, b

Par exemple, prenons A = {0, 1} et B = {2, 3, 4}.
Leur produit cartésien vaut A x B = { (0, 2) , (0, 3) , (0, 4) , (1, 2) , (1, 3) , (1, 4)}
Pour pouvoir résoudre plus facilement certains problèmes qui font intervenir des produits
cartésiens ou leurs sous-ensembles, il est souvent utile de les schématiser.
On emploie couramment une des trois représentations suivantes :
a) la représentation sagittale :
A

B
0.

.2

Les flèches sont la
représentation des couples

.3
1.

.4

b) la représentation en tableau :
B

2

3

4

0

(0,2)

(0,3)

(0,4)

1

(1,2)

(1,3)

(1,4)

A

35

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

c) la représentation cartésienne :
4
3
2
0

1

On définit également le produit cartésien à n dimensions en se basant sur la notion de n-uple :



 a 1 A 1    a 2 A 2   ...   a n A n 
1  i  n a i A 

A 1  A 2  ...  A n   a 1 , a 2 , ... a n 

An 

 a , a
1

2

, ... a n  i

3. Relation
Définitions :
- Une relation (binaire) est un sous-ensemble d’un produit cartésien de deux ensembles A
et B : R  A  B .
- Si le couple (a,b) appartient à la relation R, on dit que a est en relation R avec b et on
note aRb.
- On définit le domaine de la relation R :
Dom R  x A y B :  x, y R



- On définit l’image de la relation R :
Im R  y B x A :  x, y R







-1

- On définit la relation réciproque R d’une relation R :
x R 1 y  y R x
- On définit la relation complémentaire R d’une relation R :
R  a, b a, b A  B  a, b R





Propriétés d’une relation de A A :
Une relation de A A peut être :
réflexive : a∈A aRa
symétrique : a, b ∈A aRb  bRa
antisymétrique : a, b ∈A (aRb  bRa )  a  b
transitive : a, b, c ∈A ( aRb  bRc  aRc )
circulaire : a, b, c ∈A ( aRb  bRc  cRa )
4. Fonctions
- Une fonction est une relation dont les origines des couples qui la composent ont au plus une
image.
La relation f, contenue dans A  B , est une fonction si :
a A, b1 , b 2 B a f b1   a f b 2   b1  b 2  .

36

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

- Pour exprimer a f b , on écrira en général f(a)=b et on dira que f(a) est la valeur de f en a ou
l'image de a par f .
Rappel : en analyse (mathématique), on emploie beaucoup les fonctions contenues
dans ℝxℝ et on écrit f(x)=y où xℝ et yℝ.
- Une application est une fonction dont les origines des couples qui la composent ont
exactement une et une seule image.
La fonction f, contenue dans A  B , est une application si : Dom(f)=A.
Remarque : En informatique notamment, le mot « fonction » est généralement utilisé pour
désigner des applications.
Propriétés d’une application :
L’application f , contenue dans A  B , peut être :
une injection (tout élément de B est image d’au plus un élément de A) ;
une surjection (tout élément de B est image d’au moins un élément de A) ;
une bijection (tout élément de B est image d’un et un seul élément de A).

37

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Chapitre 4

GRAPHES
1. Introduction
1.1. Définitions
Un graphe est structuré par un ensemble de sommets (ou nœuds) reliés par des arêtes. Le
nombre de sommets est l’ordre du graphe. Une arête est une paire non ordonnée de sommets
reliés, représentée par une ligne joignant ces deux sommets. Une boucle est une arête joignant
un sommet à lui-même.
Exemple : soit le graphe  = {s1, s2, s3, s4, s5}.
Ce graphe est d’ordre 5 et possède 4 arêtes {s1, s4}, {s2, s4}, {s2, s5} et {s4, s5}.

1.2. Types de graphe
Un graphe simple est un graphe sans boucle dans lequel deux sommets distincts sont rejoints
par au plus une arête.
Un multigraphe est un graphe dans lequel deux sommets distincts peuvent être rejoints par
plusieurs arêtes. Lorsque deux arêtes joignent la même paire de sommets, on les qualifie
d’arêtes parallèles.
Un digraphe est un graphe orienté, c’est-à-dire un graphe dont les arêtes sont des arcs. Un
arc est une paire ordonnée (ou couple) de deux sommets reliés, représenté par une flèche
joignant ces deux sommets.
1.3. Adjacence et incidence
Deux sommets sont adjacents lorsqu’ils sont reliés par une arête (ou par un arc dans un
graphe orienté). De même, deux arêtes sont adjacentes si elles possèdent un sommet
commun. On dira qu’une arête est incidente à un sommet. Le degré d’un sommet est le
nombre d’arêtes incidentes à ce sommet.
La matrice d’adjacence d’un graphe est une matrice booléenne dont les lignes et colonnes
correspondent à un ordre donné des sommets de ce graphe et dont les éléments expriment
l’adjacence ou non des sommets. En d’autres termes, si M est la matrice d’adjacence du
graphe  = {s1, s2, …, sn}, mij est vrai ssi {si, sj} est une arête de .

38

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Par exemple, la matrice d’adjacence du graphe ci-dessus est :

2. Chemins, circuits et cycles
Un chemin est une suite d’arêtes adjacentes distinctes. Un chemin peut passer plusieurs fois
par le même sommet, mais pas plusieurs fois par la même arête. Un graphe est connexe si
toute paire de sommets est reliée par un chemin.
La longueur d’un chemin est le nombre d'arêtes de ce chemin. La distance entre deux
sommets est la longueur du plus court chemin entre ces deux sommets. Le diamètre d’un
graphe connexe est la distance maximum entre les sommets d’un graphe.
Un cycle (ou circuit) est un chemin fermé, qui revient a son point de départ, c’est à dire un
chemin dont la première et la dernière arête sont incidentes au même sommet. Un graphe sans
cycle ni boucle est un arbre.
Un cycle eulérien est un cycle qui passe par toutes les arêtes d'un graphe une et une seule
fois. Tous les graphes ne possèdent pas un tel cycle, mais si c’est le cas, on dit que le graphe
est un graphe eulérien. Euler a démontré qu’une condition nécessaire pour qu’un graphe soit
eulérien est que tous ses sommets soient de degré pair.
De façon analogue, un cycle hamiltonien est un cycle qui passe par tous les sommets d'un
graphe une et une seule fois. Un graphe possédant un tel cycle est un graphe hamiltonien.
3. Coloration d’un graphe et nombre chromatique
Colorer un graphe consiste à affecter une couleur à chacun de ses sommets de sorte que 2
sommets adjacents ne portent pas la même couleur.
Le nombre chromatique d’un graphe est le plus petit nombre de couleurs permettant de le
colorer.
Remarque : Une application de ces notions se retrouve dans les problèmes d’optimisation sous
certaines contraintes (exemples : ouverture d’un nombre maximum de magasins sous
certaines conditions à respecter, coloration des pays sur une carte géographique).
4. Isomorphismes de graphes
Un graphe n’est structuré que par la relation d’adjacence de ses sommets. La forme donnée au
graphe sur le papier n’a donc pas d’importance. Par exemple, les trois graphes suivants
contiennent la même information et sont donc équivalents, ce sont trois représentations
différentes sur le papier d’une même réalité mathématique :

39

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

On dit aussi que ces graphes sont isomorphes.
Définition :
Deux graphes  et ’ sont isomorphes s’il existe une bijection de l’ensemble des sommets de
 vers l’ensemble des sommets de ’ tels que si deux sommets de  sont adjacents, leurs
sommets-images par la bijection sont encore adjacents dans ’.
Il n’est pas toujours simple de décider de l’isomorphisme de deux graphes. Si la réponse
semble négative, on essayera de détecter une propriété présente dans un graphe et pas dans
l’autre (longueur de chemin, degré d’un sommet, etc). Dans le cas affirmatif, on établira une
bijection mettant l’isomorphisme en évidence et on comparera les matrices d’adjacence des
deux graphes.

40

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Chapitre 5

ANALYSE COMBINATOIRE
L’analyse combinatoire concerne les ensembles finis; elle s’occupe de dénombrements.
Entre autres choses, on dénombre les sous-ensembles qu’il est possible de constituer dans un
ensemble de référence en respectant certains critères et on introduit ainsi, notamment, les
notions d’arrangement, de permutation et de combinaison.
Remarque méthodologique :
Ces dénombrements seront souvent facilités en construisant un arbre qui
permet de visualiser les possibilités.

Plus ou moins liée à de nombreuses branches des mathématiques pures, l’analyse
combinatoire joue un rôle important en probabilité et statistique. Ses domaines d’application
sont nombreux : physique, économie, médecine, recherche opérationnelle, démographie, et,
bien entendu, informatique.
1. Arrangements.
On appelle arrangements (sans répétition) de m objets pris p à p (mp) tous les groupements
de p objets distincts pris parmi m où deux groupements diffèrent soit par la nature des objets
soit par l’ordre dans lequel ils sont rangés.
Par exemple, prenons E = { a, b, c, d, e, f } ; m = 6 ; observons différents arrangements de ces
6 objets pris 4 à 4 :
abcd≠acbd
≠abce…
Comment compter les arrangements? On peut compter les arrangements en supposant que l'on
met ces 6 objets dans un pot et qu'on en tire 4.
Pour le premier objet, nous avons 6 possibilités (a, b, c, d, e ou f). Pour le second objet, nous
n'avons plus que 5 possibilités car une possibilité a déjà été prise pour le premier objet. Pour
le troisième objet, nous avons 4 possibilités. Et enfin, pour le quatrième objet, nous avons 3
possibilités.
1er objet :

a
b
c
d
e
f

2ème objet :

a
c
d
e
f

3ème objet :

a
c
e
f

4ème objet :

a
c
f

6
*
5
*
4
*
3
Nous aurons donc 6 * 5 * 4 * 3 = 360 arrangements de 6 objets pris 4 à 4.
Le nombre d’arrangements de m objets pris p à p est noté A pm .
On a
m!
A pm  m ( m  1) ( m  2)...( m  p  1) 
.
( m  p)!

41

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

On remarque que
A pm  mA pm11 ;
Cette formule de récurrence permet de construire une table d’arrangements.
On remarque aussi que
A mm  m! .

Lorsqu’on accepte qu’un ou plusieurs objet(s) se répète(nt) dans les arrangements, on parle
d’arrangements avec répétitions (par opposition, on dira parfois « arrangements simples » ou
« arrangements sans répétition » au lieu de « arrangements »).
Par exemple, prenons E = { a, b, c, d, e, f } ; m = 6 ; prenons 4 objets avec remise parmi les 6
1er objet :

a
b
c
d
e
f

2ème objet :

a
b
c
d
e
f

3ème objet :

4ème objet :

a
b
c
d
e
f

a
b
c
d
e
f

6
*
6
*
6
*
6
Nous aurons donc 6 * 6 * 6 * 6 = 1296 arrangements avec répétition de 6 objets pris 4 à 4.
Le nombre d’arrangements avec répétitions de m objets pris p à p est parfois noté  pm .
On a
 pm  mp .
La formule de récurrence
 pm  m  pm1
permet aussi de construire une table d’arrangements avec répétitions.
Exemple de problèmes à résoudre par les arrangements :
On dispose de cinq cases et de deux jetons. De combien de manières différentes peut-on
placer les deux jetons dans les cinq cases :
- si les deux jetons sont distincts et qu’on peut placer un seul jeton par case ;
- si les deux jetons sont distincts et qu’on peut placer plusieurs jetons par case.
2. Permutations.
On appelle permutations de m objets tous les groupements de m objets distincts où deux
groupements diffèrent par l’ordre dans lequel ces objets sont rangés.
Par exemple, prenons E = { a, b, c, d, e, f } ; m = 6 ; observons différentes permutations de
ces 6 objets : a b c d e f ≠ a c b d e f ≠ a b c e d f …
Le nombre de permutations de m objets est noté Pm .
On a :
Pm  m!
et la formule de récurrence
Pm  mPm1

.
42

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Lorsque les m objets comprennent  fois l’objet a,  fois l’objet b, etc. ..., on parle de
permutations avec répétitions.
Le nombre de permutations avec répétitions de m objets est parfois noté Pm,,...,1 .
On a :
Pm
Pm ,,...,1 
.
P P ... P1
Exemple de problèmes à résoudre par les permutations :
De combien de manières peut-on classer l’ensemble {a,b,c}?
De combien de manières peut-on classer l’ensemble {a,a,b}?
3. Combinaisons.
On appelle combinaisons de m objets pris p à p (mp) tous les groupements de p objets
distincts pris parmi m où deux groupements diffèrent par la nature des objets.
Le nombre de combinaisons de m objets pris p à p est noté C pm .
On a :
Ap
m!
C pm  m 
Pp ( m  p )! p !
et la formule de récurrence
m
C pm  C pm11 .
p
On remarque que
C0m  1 ,
Cmm  1
et
Cpm  Cmm p
Les propriétés
C0m  Cmm  1
et
Cpm  Cpm11  Cpm1

.

permettent de construire le triangle de Pascal qui fournit les valeurs de C pm .
Exemple de problème à résoudre par les combinaisons :
On dispose de cinq cases. De combien de manières peut-on placer deux jetons identiques si on
ne peut mettre qu’un jeton à la fois dans une case?
Exercice dirigé : utiliser les propriétés ci-dessus pour construire le triangle de Pascal.
4. Binôme de Newton
La formule du binôme de Newton (formule à comprendre et à fixer)
m

a  b m   Cmia mib i  Cm0 a m  ...  Cmp a m p b p  ...  Cmm b m

m N0

i 0

est particulièrement utile lorsqu’on doit calculer la puissance entière positive d’une somme de
deux termes.

43

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Seconde partie

Introduction à l’analyse numérique

44

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Chapitre 6

NOTIONS BASÉES SUR LES FONCTIONS RÉELLES
1. Rappels
1.1. Représentation cartésienne d’une fonction réelle
Une fonction réelle fait correspondre un nombre réel x à son image y = f(x). L’ensemble des
couples (x, y) ou (x, f(x)) de la fonction peut être représenté dans un repère cartésien pour
former le graphe de la fonction. C’est la courbe constituée des points représentant les couples
de la fonction.

Pour rappel, les coordonnées d’un point (x, y) du plan cartésien sont appelées respectivement
abscisse et ordonnée.
L’ensemble des valeurs de x qui possèdent une image f(x) est le domaine de la fonction, et est
noté Dom(f). C’est l’ensemble des valeurs pour laquelle f est définie.
1.2. Monotonie et croissance
Une fonction monotone est une fonction qui est soit constamment croissante, soit
constamment décroissante sur tout intervalle de son domaine de définition ; on visualise ces
notions facilement sur un graphique cartésien, ce qui permet de comprendre les définitions
formelles :
I étant un intervalle de Dom(f), f est une fonction






croissante sur I
  x1, x2  I : x1 < x2  f(x1)  f(x2)
strictement croissante sur I
  x1, x2  I : x1 < x2  f(x1) < f(x2)
décroissante sur I
  x1, x2  I : x1 < x2  f(x1)  f(x2)
strictement décroissante sur I
  x1, x2  I : x1 < x2  f(x1) > f(x2)
monotone sur I si et seulement si elle soit croissante ou soit décroissante sur I.

45

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

1.3. Parité d'une fonction
Soit f une fonction réelle et Dom(f) son domaine. Alors :


f est une fonction paire si et seulement si x  Dom(f), f(–x) = f(x). Le graphe
d’une fonction paire est symétrique par rapport à l’axe des y.



f est une fonction impaire si et seulement si x  Dom(f), f(–x) = – f(x). Le graphe
d’une fonction impaire est symétrique par rapport à l’origine.

1.4. Périodicité d'une fonction
Une fonction f est périodique s’il existe un réel T non nul tel que :
f ( x  T )  f ( x) x  ℝ

La période est la plus petite valeur de T pour laquelle la fonction possède cette propriété. Les
fonctions périodiques apparaissent naturellement en physique et en mécanique dans l’étude
des signaux et des phénomènes périodiques. Les fonctions périodiques les plus connues sont
les fonctions trigonométriques cosinus, sinus et tangente (voir ci-dessous).

1.5. Fonctions continues et discontinues
Une vision intuitive de la notion de fonction continue est une fonction dont le graphique
cartésien est dessiné sans lever le crayon, ce qui n’est pas le cas pour une fonction
discontinue. Cette visualisation permet de mieux comprendre les définitions formelles
suivantes. Soit a un point appartenant à Dom(f), alors :


f est continue en a 

lim f ( x)  f (a)
xa

46

ESI (HEB)

Bachelor en Informatique

-

Mathématique



f est continue à gauche en a 

lim f ( x)  f (a)



f est continue à droite en a 

lim f ( x)  f (a)

-

Année académique : 2012 -2013

xa
x a

xa
x a

Ces définitions de la continuité en un point conduisent aux définitions plus générales :


f est continue sur un intervalle ]a, b[ si et seulement si f est continue en tout point
de cet intervalle



f est continue sur un intervalle [a, b] si et seulement si f est continue sur ]a, b[,
continue à droite en a et continue à gauche en b.

1.6. Asymptotes
Intuitivement, une asymptote est une droite vers laquelle le graphe d’une fonction tend à se
rapprocher à mesure que l’abscisse ou l’ordonnée tend vers l’infini. Trois types sont
généralement étudiés : l’asymptote verticale, l’asymptote horizontale et l’asymptote oblique.
Nous ne reverrons que les deux premiers cas dans le cadre de ce cours.
 L’asymptote verticale
Lorsque les valeurs d’une fonction f tendent vers l’infini en s’approchant d’un point a (que ce
soit par la gauche ou par la droite), on dit que le graphe de f admet une asymptote verticale au
point a.

lim f ( x)    f possède une asymptote verticale d’équation x = a
xa

 L’asymptote horizontale
Lorsque les valeurs d’une fonction f tendent vers un réel a lorsque x tend vers l’infini, on dit
que le graphe de f admet une asymptote horizontale d’équation y = a.

lim f ( x)  a  f possède une asymptote horizontale d’équation y = a

x

Remarque : une fonction peut posséder plusieurs asymptotes verticales, et au plus 2
asymptotes horizontales (c’est le cas lorsque les limites en –∞ et +∞ donnent deux valeurs
réelles distinctes).
Exemple : la fonction ci-dessous possède une asymptote verticale d’équation x = 3 et une
asymptote horizontale d’équation y = 0.

47

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

2. Fonctions élémentaires
2.1. La fonction identique
Il s'agit de la fonction f : ℝ→ℝ : x → x

Cette fonction est définie sur ℝ, elle est impaire, continue et strictement croissante.
2.2. Fonctions du premier degré
Il s'agit des fonctions de la forme f : ℝ→ℝ : x → ax + b
Une fonction du premier degré a comme graphique une droite, deux points suffisent pour la
représenter. Cette droite passe par le point (0, b), et donc par (0,0) si b est nul; on dit que b est
l’ordonnée à l’origine. Nous rappelons quelques propriétés importantes des droites :
 La pente de la droite y = ax + b (ou coefficient angulaire) est la valeur de a
 L’angle  que fait la droite avec l’axe horizontal est donné par a = tg 
Y
a
y
(x,y)

0

1

1

x

X

48

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

 Deux droites sont parallèles si et seulement si elles ont le même coefficient angulaire
 Deux droites sont perpendiculaires si et seulement si leurs coefficients angulaires sont
inversés et opposés, c’est-à-dire si le produit de leurs coefficients angulaires vaut – 1
 Équation cartésienne d'une droite passant par 2 points (x1, y1) et (x2, y2) :
y  y1 

y 2  y1
( x  x1 )
x 2  x1

 Équation cartésienne d’une droite passant par un point (x0, y0) et de pente m
y  y0  m( x  x0 )

2.3. La fonction valeur absolue
Il s'agit de la fonction f : ℝ→ℝ+ : x → |x|

Son domaine est ℝ, elle est continue, paire, strictement décroissante sur ] –∞, 0[ et strictement
croissante sur ]0, +∞ [.
2.4. La fonction carré
Il s'agit de la fonction f : ℝ→ℝ+ : x → x².

49

ESI (HEB)

Bachelor en Informatique

-

Mathématique

-

Année académique : 2012 -2013

Son domaine est ℝ, elle est continue, paire, strictement décroissante sur ] –∞, 0[ et strictement
croissante sur ]0, +∞ [. Son graphique est une parabole de sommet (0,0).
2.5. La fonction racine carrée
Il s'agit de la fonction f : ℝ+ → ℝ+ : x → x .

Son domaine est ℝ+, elle est continue et strictement croissante sur ℝ+.
2.6. La fonction cube
Il s'agit de la fonction f : ℝ→ℝ : x → x³.

Son domaine est ℝ, elle est continue, impaire et strictement croissante.
2.7. La fonction racine cubique
Il s'agit de la fonction f : ℝ→ℝ : x → 3 x .

50


Aperçu du document Syllabus2012-2013-NotesDeCours.pdf - page 1/83
 
Syllabus2012-2013-NotesDeCours.pdf - page 2/83
Syllabus2012-2013-NotesDeCours.pdf - page 3/83
Syllabus2012-2013-NotesDeCours.pdf - page 4/83
Syllabus2012-2013-NotesDeCours.pdf - page 5/83
Syllabus2012-2013-NotesDeCours.pdf - page 6/83
 




Télécharger le fichier (PDF)


Syllabus2012-2013-NotesDeCours.pdf (PDF, 1.4 Mo)

Télécharger
Formats alternatifs: ZIP



Documents similaires


syllabus2012 2013 notesdecours
analyse reelle cours et exercices corriges premiere annee maths et informatique
operations research
www mathovore fr ensembles de nombres et calculs cours maths 48
pdf boole
polys c mm

Sur le même sujet..