Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Von Neumann Extractor: Procédure d'extraction binaire optimale

Dans cours

COM-622: Topics in information-theoretic cryptography

Information-theoretic methods and their application to secrecy & privacy. Perfect information-theoretic secrecy. Randomness extraction & privacy amplification. Secret key generation from common randomness. Measures of information leakage incl. differential ...

Description

Cette séance de cours couvre l'extracteur von Neumann, visant à fournir et analyser un extracteur asymptotiquement optimal pour les chaînes binaires. Il explique la procédure d'extraction, prouvant l'uniformité, le calcul de la vitesse et la relation de récursion pour les vitesses d'extraction. La séance de cours se termine par des propositions concernant la convergence des taux d'extraction et le point fixe de l'opérateur d'extraction.

Enseignant·e

Yanina Yurina Shkel

Source officielle

Concepts associés (32)

Convergence uniforme

La convergence uniforme d'une suite de fonctions est une forme de convergence plus exigeante que la convergence simple. La convergence devient uniforme quand toutes les suites avancent vers leur limite respective avec une sorte de « mouvement d'ensemble ». Dans le cas de fonctions numériques d'une variable, la notion prend une forme d'« évidence » géométrique : le graphe de la fonction f se « rapproche » de celui de la limite. Soient X un ensemble, (Y, d) un espace métrique, et A un sous-ensemble de X.

Algorithme récursif

Un algorithme récursif est un algorithme qui résout un problème en calculant des solutions d'instances plus petites du même problème. L'approche récursive est un des concepts de base en informatique. Les premiers langages de programmation qui ont autorisé l'emploi de la récursivité sont LISP et Algol 60. Depuis, tous les langages de programmation généraux réalisent une implémentation de la récursivité. Pour répéter des opérations, typiquement, un algorithme récursif s'appelle lui-même.

Uniforme

thumb|Jeunes filles en uniforme scolaire en Gambie en 1984. L'uniforme est un habit réglementaire, que tous les membres d'un groupe doivent porter selon des règles précises. C'est une tradition qui vient de l'Empire romain. Uniforme militaire : c'est l'habit du militaire. Il est confectionné Son caractère militaire et national est affirmé par des attributs et insignes nettement définis. Uniformes scolaires : tenues d'élèves (écoliers, lycéens, étudiants, etc.) ; tenues d'enseignants (robes universitaires).

Récursivité

La récursivité est une démarche qui fait référence à l'objet même de la démarche à un moment du processus. En d'autres termes, c'est une démarche dont la description mène à la répétition d'une même règle.

Course-of-values recursion

In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. In a definition of a function f by course-of-values recursion, the value of f(n) is computed from the sequence . The fact that such definitions can be converted into definitions using a simpler form of recursion is often used to prove that functions defined by course-of-values recursion are primitive recursive.

Afficher plus

Séances de cours associées (29)

Convergence des probabilités

Explore la convergence des probabilités, discutant des conditions de convergence des séquences variables aléatoires et de l'unicité de la convergence.

Convergence et exhaustivité

Couvre la convergence, l'exhaustivité et les propriétés des espaces métriques et des espaces de Banach.

Induction magnétique

Explique l'induction magnétique, la force sur un dipôle, le couple et les applications dans les systèmes macroscopiques.

Démonstration des propriétés de compression et d'entropie des données

Couvre les propriétés de l'entropie et démontre leur application dans la compression des données.

Sans titre

Afficher plus

Concepts associés (32)

Course-of-values recursion

Afficher plus