Cours de robustesse a Dijon

Cours de robustesse a Dijon

65

pages

Français

Documents

Écrit par
Sylvain Pion

Publié par
Musar

Lire

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

65

pages

Français

Documents

Lire

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Publié par

Nombre de lectures

27

Langue

Français

Bases d’arithmetiquepour le calcul geometriqueSylvain PionINRIA Sophia AntipolisPlan Liens entre la geometrie et l’arithmetique Calcul ottant Calcul exact Calcul modulaire Bornes de separations Filtres arithmetiques Implantation dans CGAL1Introduction2Exemples de predicats geometriquespositiveC1orientation pqC2 C’1r p’C’2p negativeorientationx(p) Voir

Publié par

Langue

Français

Basesd’arithm´etique pourlecalculg´eom´etrique

Sylvain Pion

INRIA

Sophia

Antipolis

•

•

•

•

•

•

•

Liensentrelage´om´etrieet

Calcul ﬂottant

Calcul exact

Calcul modulaire

Bornes de separations ´

Filtresarithme´tiques

Implantation dans CGAL

Plan

l’arithm´etique

1

Intro

duction

2

Exemplesdepre´dicatsge´ome´triques

orientation(p, q, r) = sign((x(p)−x(r))×(y(q)−y(r))−(x(q)−x(r))×(y(p)−y(r)))

Pre´dicatde

Sylvain Pion

deg ´ 2 re.

3

Sylvain

Pion

Exemples

de

constructions

g´eom´etriques

4

Delage´ome´triea`l’arithm´etique

Algorithmege´om´etrique

Sylvain Pion

⇒tsurtcoisn)s(pr´edicats&congsnomoe´rte´euqi´eOptira

⇒nestﬃeic/soc´neeonrdooscleurssueqirbe´glasnoitarpOe´ √. . .)

⇒aritionseratOp´(see´mhuqit+,−,×,÷,

5

Arithme´tique⇒eetrieom´G´

Coˆuteque´ittimh’lraed⇒et´xilempComhse´goe´mteiruqesetiroglasedspmetn

Arithm´etiqueorppe´hcea⇒esemderp`lborostbuseesglroedasse´gtimhetrieom´ques

Sylvain Pion

6

Lemod`eleReal-RAM

Mode`ledecalculateurr´eel`aacce`sale´atoire(RAM=Randomaccessmachine).

Mod`eleth´eoriqueducomportementdel’arithm´etiquer´eellesurordinateur.

•Toutes lesnsiotare´poitarquti´ehmntunˆutelrseseussloc´reetemps O(1) (et sont exactes).

•cuoceslleer´esbltnepraaielvstuseoTemoire´mecapse)1(O.

Lesanalysesdecomplexit´edesalgorithmesg´eome´triquessontfaites traditionnellementdanscemode`le.

Sylvain Pion

7

Relationaveclare´alite´desordinateurs?

Deux approches :

•Calcul ﬂottant,appchro´e.

•Calcul exact,plus lent.

Pourlag´eom´etrie:quelleapprocheest-ellelameilleureenpratique?

Quelestlev´eritablecoˆutdel’approcheexacte?

8

Calcul

ﬂottant

9

Standard IEEE 754

Standardisationdesop´erationsﬂottantesdebasedesordinateurs(1985). Repre´sentationmachinede(−1)s×1.m×2eourladou(ptsbi):oisi46,npelbce´r s exposant mantisse 1 11 52

•5postion´era:+,− ×,÷,√ ,

•4 modes d’arrondisnoe(rembprrese´ebatn,)elsrevchrospluup:a0, vers+∞, vers−∞.

•Valuesrpse´iclase:+∞,−∞d´normaux, NaNs. , e

•Relativement bien suivie par l’industrie (langages, compilateurs, processeurs).

Voir ://tsvehehtt:pcom/cginollasch.feeei/gnidoc/xedltm.hatlo

Sylvain Pion

10