[PDF] Assistant de preuve Coq - Université dOrléans





Previous PDF Next PDF



Qui est Jules Regnault

statistique des cours de la rente 3% du calcul des probabilités ainsi que d'une UMR 6586



Curriculum Vitae

Post-Doctorat `a l'université du KwaZulu Natal (Afrique du sud) dans l'équipe de T.D de probabilité et de théorie de la mesure (Licence 3).



ÉCOLE DOCTORALE MATHÉMATIQUES INFORMATIQUE

6 mars 2019 I am also grateful to Orleans University International Central ... Definition 1.1.3 (The LDP) The family of probability measures {µn} ...



secret parfait

Le résultat du calcul de A(x) n'est plus nécessairement unique il possède une certaine probabilité. Page 6. Chiffrement par ?. Exercice Formalisons le 



La théorie des probabilités et lInstitut Henri Poincaré (1918-1939

4 févr. 2021 1.3 Enjeux des savoirs probabilistes pour les étudiants à l'université de Paris . 40. 1.3.1 Des étudiants en probabilités dans un cursus ...



Assistant de preuve Coq - Université dOrléans

31 mars 2015 Programmes al´eatoires. ? Important d'un point de vue théorique et pratique. ? Théorie des probabilités. ? espace probabiliste.



LE STATUT DE LAPPRENTI LAIDE AU PERMIS DE CONDUIRE L

un mode de formation qui allie théorie et pratique. • une forte probabilité d'embauche à la fin du cursus



Probabilités et Statistiques

4 févr. 2010 Université d'Orléans. Nils Berglund ... La théorie des probabilités sert `a modéliser des situations dont notre connaissance est imparfaite.



Support du cours de Probabilités et Statistiques IUT dOrléans

IUT d'Orléans Département Informatique. Laboratoire MAPMO (Bât. de Mathématiques UFR Sciences) email: pierre.andreoletti@univ-orleans.fr 



THÈMES DE RECHERCHE EQUIPEMENTS ET TECHNOLOGIES

contact.idp@univ-tours.fr. L'Institut Denis Poisson est un laboratoire de Mathéma- tiques et Physique Théorique bilocalisé sur Orléans et Tours.

Assistant de preuve COQ

une boite `a outils pour l"ing´enierie des preuves

Christine Paulin-Mohring

Universit

´e Paris Sud & INRIA Saclay -ˆIle-de-France

31 mars 2015

C. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 1 / 61

Introduction

Objectifs

I

Introduction`a l"assistant de preuve COQI

COQhttp://coq.inria.fr

I s"applique`a d"autres syst`emes de la mˆeme famille HOL, Isabelle, PVS, Agda, Matita... I Comprendre les concepts mis en oeuvre : langage & architecture I

Int´erˆet d"une utilisation pour vos activit´es de recherche?C. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 2 / 61

Introduction

Plan

Introduction

Langage

Objets & Types

Formules & Preuves

Syst `eme de preuveProgrammes al

´eatoiresRepr

´esentationBiblioth

`eque ALEAConclusion C. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 3 / 61

Introduction

Motivations

Pourquoi s"int

´eresser auxassistants de preuv e?

S"assurer que quelque chose est

vr aiI Limitations li´ees`a l"ind´ecidabilit´eet la comple xit´e I

G´erer des preuvesinf aisables`a la main

I ordinateurs : meilleurs que nous en activit´esroutini `eres

Ifavorisent le travailcollabor atif

I

Int´egrerr aisonnementet calcul

I

Maximiser la

confiance I parler aux humains autant qu"aux machines I Emergence d"une nouvelle activit´e : G´enie/Ing´enierie des preuvesOn a d

´esappris`a calculer

Pourra-t-on d

´esapprendre la construction/v´erification de preuves?C. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 4 / 61

Introduction

Outils pour le calcul

calculatrice op

´erations de basecalcul formel

langage sp

´ecialis´e,

fonctions avanc

´ees,

interfacefeuille de calcul pr

´esentation,´editionprogrammation

langage universel, biblioth `eques, sp´ecialistesprobl

`eme :mod´eliser, combiner les m´ethodesC. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 5 / 61

Langage

Plan

Introduction

Langage

Objets & Types

Formules & Preuves

Syst `eme de preuveProgrammes al

´eatoiresRepr

´esentationBiblioth

`eque ALEAConclusion C. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 6 / 61

Langage

Propri

´et´e du langage

I Il ne suffit pas que le calcul soit juste, il faut avoir pos´e les bonnes equations I les sp´ecifications doivent pouvoirˆetreremises en question : relecture, confronter plusieurs d

´efinitions, tester, ex´ecuter, prouver

I Un probl`eme bien pos´e est`a moiti´e r´esolu I un programme bien sp´ecifi´e est`a moiti´e prouv´e... Ichoix desstr ucturesde donn ´ees/d´efinitions Ile langage comme support`a l"expression des besoins

Icompr´ehensible par l"homme et la machineC. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 7 / 61

Langage

Choix du langage

La logique est un langage

univ ersel pour repr

´esenter des propri´et´es

I les constructions de basevrai(>),faux(?), pour tout(8),il existe(9) I

Qu"en est-il des objets et propri´et´es atomiques?C. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 8 / 61

LangageObjets & Types

Repr

´esentation des objets

I

Vision

axiomatique I nouveaux symboles et axiomes

Irisques d"incoh´erence

I Th´eorie desensemb les4 f;;f;g;f;;f;gg;f;;f;g;f;;f;gggg I

Arithm´etique deP eano( 0;S();+;)

I codage des suites par des entiers I2n=m9e;jej=n+1^e(0) =1^ 8iConcevoir les langages moder nesde la logique C. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 9 / 61

LangageObjets & Types

Le point de vue informatique

I

Mots binaires

de taille bor n´ee I Code = suite finie d"instr uctions I une recette pour calculer des valeurs Imoyen fini de d´ecrire des objets potentiellement infinis

Id´efinition intentionnelle calculatoire

Iabstraction(lambda-calcul)/f ermeture(langages f onctionnels) I

Organisation de la m´emoire enb locs

I entˆete: taille ,´etiquettepour organiser les b locs

Itermes,signature (symboles associ ´es`a des arit´es), alg`ebre libreC. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 10 / 61

LangageObjets & Types

Types

Classifier finement les objets

I Des e xpressions ( ) pour repr´esenter des ensembles d"objets I

Une relationt:

bool

´eens, entiers, fonctions, arbres ...

I

Reconnaissable

statiquement ( `a la compilation, avant le calcul) I

En g´en´eral untype canonique par objet

I

Stable par calculsit:etts"´evalue enualorsu:

I limite les erreurs automatiquement (terminaison) I

Mais forc´ement des limitationsN

1:Nx22x+1:N?

les types ne sont pas des ensembles! C. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 11 / 61

LangageObjets & Types

Types simples

I

Types fonctionnels :!f:!p:f p:[f(x)def=t]x:`t:f:!

I

Types de base :bool;nat

I

constructeurs avec leur arit´e (typ´ee)Inductivebool := true : bool | false : bool.Inductivenat := O : nat | S : nat!nat.C. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 12 / 61

LangageObjets & Types

D

´efinition de fonctions

I propri´et´es des types construits (alg`ebre initiale) I valeurs constructibles : viennent des constructeurs

Iconstructeurs distincts

I analyse par casDefinitionisz (n:nat) :=matchnwithO)true | S m)falseend.I

point-fixe structurelFixpointexp2 (n:nat) :=matchnwithO)1 | S m)2*exp2 mend.C. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 13 / 61

LangageObjets & Types

Des objets qui calculent

Evalcomputeinexp2 4.= 16 : nat

I

Tester (sur des valeurs closes)

I Si on peut calculerf(n)enmalorsf(n) =mest trivial.Limitations I

Toutes les fonctions ne peuvent pas se calculer

I minimiser une fonctionf:N!N8x:N;f(min(f))f(x) I

Une valeur bool´eenne secalcule

Une propri

´et´e logique seprouv ebool6=PropC. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 14 / 61

LangageObjets & Types

Quels programmes dans la logique?

Pas n"importe quel calcul dans la logique

I probl`eme de terminaison8n;n=0_n6=0 06=1 f(x) =iff(x) =0then1else0 f(x) =0,f(x)6=0 I calculs impurs I p=pnon valide sipfait des effets de bord(x++ ==x++)random==randomSolutions I fonctions repr´esent´ees intentionnellement (relationslogiques) I expliciter les effets des constructions imp´eratives (monades) I ´etats, exception, entr´ees-sorties, al´eatoire, non-d´eterminisme I notationsC. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 15 / 61

LangageObjets & Types

Types

´etendus

I types polymorphes :list;treet:8;[]t[] :[]Inductivetree A :=leaf | node : A!tree A!tree A!tree A.I

types indic´es :vecnt:8x:;[x]p:t p:[p]Inductivevec A : nat!Type:=nil : vec A O | add :8n,A!vec A n!vec A (S n).I

branchement indic´eInductiveBDT := T|F| var: nat!(bool!BDT)!BDT.InductiveW A B := sup:8(a:A),(B a!W A B)!W A B.C. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 16 / 61

LangageObjets & Types

Typage d

´ependant du match

I Forme´el´ementairematchiinI xreturnP x iwithc1 x1...xn1)t1( *:P u1 ( c1x1 ...xn1)*)|... |cp x1...xnp)tp( *:P up ( cpx1 ...xnp)*)end I ExempleFixpointapp A n (v: vec A n) m (w:vec A m): vec A (n+m)

:=matchvinvec _ nreturnvec A (n+m)withnil)w| add p a v")add a (app v" w)end.C. Paulin (Paris-Sud)Assistant de preuve COQ31 mars 2015 17 / 61

LangageObjets & Types

Types d

´ependants

quotesdbs_dbs5.pdfusesText_9
[PDF] 1 LE MODÈLE DES RESSOURCES ET DES COMPÉTENCES: UN

[PDF] Retour sur la théorie des ressources - Hal

[PDF] Chapitre 1 Psychologie différentielle de la personnalité : introduction

[PDF] EL JOUHARI Exercices SMC5-M17-E2 - Faculté des Sciences de

[PDF] Les aspects théoriques du commerce international et de la protection

[PDF] Microéconomie - Faculté des Sciences Economiques et de Gestion

[PDF] Innovation et développement chez Schumpeter - (CEIM) | UQAM

[PDF] La théorie du producteur - Paris School of Economics

[PDF] APPRENTISSAGE ET TRAITEMENT DE L 'INFORMATION

[PDF] Théorie et Pratique de la traduction III La Traduction littéraire L

[PDF] APPORTS ET LIMITES DE LA THEORIE INSTITUTIONNELLE - Hal

[PDF] Théorie keynésienne - Comptabilité nationale

[PDF] Théorie de la littérature - Université Paris-Sorbonne

[PDF] Théorie positive de la comptabilité - Hal

[PDF] Théorie psychanalytique de la personnalité - ULB