DEUG MIAS

 

INFORMATIQUE
TD, TP

 

Algorithmique : Part 1: Mathématiques pour l'informatique

Par Philippe ROLLAND

Sommaire

 A. Ensembles ordonnés :  B. Rappel : Relations  C. Rappel : Géométrie

 

 

Définition
Réflexives
Irréflexive
symétrique
antisymétrique
transitives

 

Polygone
Convexe
Régulier

 

 A. Ensembles ordonnés

1. Relations d'ordre

Définition 1 : Une relation d'ordre large est une relation réflexive, antisymétrique et transitive. Une relation d'ordre strict est une relation irréflexive, antisymétrique et transitive.

Si R est une relation d'ordre strict sur un ensemble E, alors la relation R Identité est une relation d'ordre large. Réciproquement, si R' est une relation d'ordre large R'\Identité est une relation d'ordre strict.

Les relations d'ordre large sont généralement notées , et les relations d'ordre strict sont notées <. En vertu de la remarque précédente il est facile de passer d'un ordre large à l'ordre strict correspondant et réciproquement :

x<y est équivalent à xy et xy,
xy est équivalent à x<y ou x=y.

Retour

2. Ensembles ordonnés

Définition 2: Un ensemble ordonné (E, ) est un ensemble muni d'une relation d'ordre .
Définition 3: Un ensemble ordonné (E, ) est totalement ordonné si est un ordre total, c'est-à-dire si

x,y: xy implique xy ou yx

Il est partiellement ordonné sinon, c'est-à-dire si

x,y avec xy tel que x y et y x.

 

Retour

3. Ensembles bien fondés

Définition: Une relation d'ordre sur un ensemble E est bien fondée s'il n'y a pas de suite infinie strictement décroissante d'éléments de E. Un bon ordre est un ordre total bien fondé.

Proposition: Un ensemble ordonné (E,) est bien fondé si et seulement si toute partie non vide de E admet au moins un élément minimal.

Retour

 B. Rappel : Relations

B. Rappel : Quelques propriétés des relations binaires :

Définition : Une relation sur un ensemble E est la donnée d'une partie R de E x E. Pour indiquer qu'une paire (e,e') est dans cette partie R, on utilisera, selon les cas, l'une des notations suivantes :

(e,e') appartient à R
e R e'
R(e,e')

Exemples : Sur E=IN, les ensembles suivants sont des relations :

L'ensemble {(n,m) / nm }
L'ensemble {(n,m) / nm2n }
L'ensemble {(n,m) / nm et k : n2+m2=k2 }

Une relation binaire R dans un ensemble E est :

Réflexives, si pour tout e dans E, e R e
IrréRélexives, si pour tout e, e' dans E, e R e' implique e Différent e'
Symétrique, si pour tout e, e' dans E, e R e' implique e' R e
AntiSymétrique, si pour tout e, e' dans E, e R e' implique e' = e
Transitive, si pour tout e, e', e" dans E, e R e' et e' R e" implique e R e"

Retour

 C. Rappel : Géométrie

C. Gémétrie

Polygone : Un polygone est un contour fermé constitué d'une suite de segments appelés cotés du polygone.

Un polygone peut être croisé ou non selon que ses cotés se recoupe ou pas.

Polygone convexe (définition intuitive): Imaginons une salle de musé que l'on souhaite mettre sous surveillance d'un gardien. On peut représenter le plan de cette salle par contour polygonal fermé non croisé. Un gardien qui cherche à s'installer pour la surveillance de la salle, se mettra de préférence en un point duquel tous les autres points sont visibles sans avoir à se déplacer.

Si n'importe quel emplacement de la pièce convient on dira que le plan de la pièce est convexe. On peut encore dire que un polygone est concave si et seulement si pour tout segment [a,b] avec a,b deux points sur (ou dans) le polygone, le segment appartient tout entier au polygone, ie le segment est contenu dans le polygone. Voir un exemple figure 1.

Si tous les points ne conviennent pas mais qu'il existe au moins une position favorable, alors dira que le polygone est étoilé. Voir un exemple figure 2.

Si aucun point n'est favorable on dira que le polygone est concave. Voir un exemple figure 3.

 

Figure 1 :Polygone convexe non régulier

 

 

Figure 2 :Polygone étoilé régulier à 5 cotés

 

Figure 3 :Polygone concave

 

 

Polygone régulier : définition : Tous les cotés ont la même longueur et les angles au sommet sont tous égaux. Exemples : triangles équilatéral, carré, pentagone, hexagone, heptagone, ... Voir figure 4 et 5.

 

Figure 4 :Polygone régulier convexe : l'hexagone

 

Figure 5 :Polygone étoilé régulier à 5 cotés