Séance de cours

Encodeur et décoder pour les codes sans préfixe

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 couvre la mise en œuvre et la vérification de l'encodeur et du décodeur pour les codes sans préfixe, y compris les classes et les types, les lemmas sur les arbres, le théorème principal, les conditions préalables et postconditions, une feuille de route, la preuve du décodage et de l'encodement. Les instructeurs discutent de la vérification formelle des codes sans préfixe, de l'arbre optimal produit par l'algorithme de Huffman, et des défis rencontrés dans la mise en œuvre et la vérification de l'encodeur et du décodeur.

Source officielle

Concepts associés (32)

Postcondition

In computer programming, a postcondition is a condition or predicate that must always be true just after the execution of some section of code or after an operation in a formal specification. Postconditions are sometimes tested using assertions within the code itself. Often, postconditions are simply included in the documentation of the affected section of code. For example: The result of a factorial is always an integer and greater than or equal to 1.

Arbre splay

Un arbre splay (ou arbre évasé) est un arbre binaire de recherche auto-équilibré possédant en outre la propriété que les éléments auxquels on a récemment accédé (pour les ajouter, les regarder ou les supprimer) sont rapidement accessibles. Ils disposent ainsi d'une complexité amortie en O(log n) pour les opérations courantes comme insertion, recherche ou suppression. Ainsi dans le cas où les opérations possèdent une certaine structure, ces arbres constituent des bases de données ayant de bonnes performances, et ceci reste vrai même si cette structure est a priori inconnue.

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).

Self-balancing binary search tree

In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing".

Vérification formelle

In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics. Formal verification can be helpful in proving the correctness of systems such as: cryptographic protocols, combinational circuits, digital circuits with internal memory, and software expressed as source code.

Afficher plus

Séances de cours associées (64)

Conceptions de chisel vérifiées de façon formelle

Examine la vérification formelle des conceptions de Chisel à l'aide de résolveurs SMT et couvre des exemples tels que les assertions différées et les preuves par induction.

Compression: Inégalité de Kraft

Explique la compression et l'inégalité Kraft dans les codes et les séquences.

Raisonnement automatisé : vérification formelle avec LISA

Examine la vérification formelle à l'aide de l'assistant d'épreuve LISA et du vérificateur d'équivalence OCBSL.

Algorithmes Préparation à l'examen

Offre un récapitulatif avant l'examen Algorithmes, couvrant les stratégies de résolution de problèmes et la mise en œuvre de l'algorithme avec des problèmes d'échantillon.

Groupes fondamentaux

Explore les groupes fondamentaux, les classes d'homotopie et les revêtements dans les variétés connectées.

Afficher plus

Concepts associés (32)

Postcondition

Arbre splay

Méthode formelle (informatique)

Self-balancing binary search tree

Vérification formelle

Afficher plus