Séance de cours

Raisonnement automatisé : vérification formelle avec LISA

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours présente le laboratoire de raisonnement et d'analyse automatisés, en mettant l'accent sur la vérification formelle à l'aide de l'assistant d'épreuve LISA. Parmi les sujets abordés, mentionnons les épreuves mathématiques formelles, les assistants aux épreuves comme Coq et Isabelle, et les travaux récents sur le vérificateur d'équivalence de l'OCBSL. La séance de cours couvre le développement de LISA dans Scala, son application dans la logique, la théorie de l'ensemble et l'exactitude du programme, et l'algorithme pour vérifier l'équivalence des formules de proposition. On discute de la décidabilité du problème du mot OCBSL dans le temps log-linéaire et de la réduction à la forme normale, en soulignant son efficacité et sa prévisibilité dans la pratique.

Source officielle

Concepts associés (32)

Démonstration (logique et mathématiques)

vignette| : un des plus vieux fragments des Éléments d'Euclide qui montre une démonstration mathématique. En mathématiques et en logique, une démonstration est un ensemble structuré d'étapes correctes de raisonnement. Dans une démonstration, chaque étape est soit un axiome (un fait acquis), soit l'application d'une règle qui permet d'affirmer qu'une proposition, la conclusion, est une conséquence logique d'une ou plusieurs autres propositions, les prémisses de la règle.

Méthode formelle (informatique)

En informatique, les méthodes formelles sont des techniques permettant de raisonner rigoureusement, à l'aide de logique mathématique, sur un programme informatique ou du matériel électronique numérique, afin de démontrer leur validité par rapport à une certaine spécification. Elles reposent sur les sémantiques des programmes, c'est-à-dire sur des descriptions mathématiques formelles du sens d'un programme donné par son code source (ou, parfois, son code objet).

Formal specification

In computer science, formal specifications are mathematically based techniques whose purpose are to help with the implementation of systems and software. They are used to describe a system, to analyze its behavior, and to aid in its design by verifying key properties of interest through rigorous and effective reasoning tools. These specifications are formal in the sense that they have a syntax, their semantics fall within one domain, and they are able to be used to infer useful information.

Computer-assisted proof

A computer-assisted proof is a mathematical proof that has been at least partially generated by computer. Most computer-aided proofs to date have been implementations of large proofs-by-exhaustion of a mathematical theorem. The idea is to use a computer program to perform lengthy computations, and to provide a proof that the result of these computations implies the given theorem. In 1976, the four color theorem was the first major theorem to be verified using a computer program.

Assistant de preuve

En informatique (ou en mathématiques assistées par informatique), un assistant de preuve est un logiciel permettant la vérification de preuves mathématiques, soit sur des théorèmes au sens usuel des mathématiques, soit sur des assertions relatives à l'exécution de programmes informatiques. Beaucoup de projets ont été lancés pour formaliser les mathématiques, en 1966, Nicolaas de Bruijn lance le projet Automath, suivi par d'autres projets.

Afficher plus

Séances de cours associées (64)

Propositions inductives : comprendre l’évaluation dans Coq

Couvre les propositions inductives en Coq, en se concentrant sur les règles dévaluation pour les expressions arithmétiques et leurs applications dans la définition des fonctions partielles et non déterministes.

Coq: Vue d'ensemble

Présente Coq et se concentre sur la démonstration du théorème et du _comm étape par étape.

Introduction à Coq: Expressions arithmétiques et évaluateurs

Couvre les bases de Coq, en se concentrant sur les expressions arithmétiques, l'évaluation et les techniques de preuve.

Abstraction de données : modules et spécifications dans Coq

Discute de l'abstraction des données dans la programmation, en se concentrant sur les modules et les spécifications dans Coq.

Logique formelle: preuves et ensembles

Couvre les bases de la logique formelle, en se concentrant sur les expressions logiques et les preuves mathématiques.

Afficher plus

Concepts associés (32)

Démonstration (logique et mathématiques)

Méthode formelle (informatique)

Formal specification

Computer-assisted proof

Assistant de preuve

Afficher plus