Séance de cours

Problème d'appariement booléen caché

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.

Dans cours

CS-448: Sublinear algorithms

In this course we will define rigorous mathematical models for computing on large datasets, cover main algorithmic techniques that have been developed for sublinear (e.g. faster than linear time) data processing. We will also discuss limitations inherent t ...

Description

Cette séance de cours couvre le problème booléen de correspondance cachée, où Alice et Bob s'engagent dans un jeu de correspondance avec des messages de différentes tailles, visant à les distinguer avec une probabilité négligeable. La séance de cours explore diverses conditions et définit le problème, en soulignant le défi de faire la distinction entre les messages. Il fournit des informations sur la fonction d'indicateur et les implications pour la plupart des correspondances. La séance de cours conclut en soulignant la difficulté de faire la distinction entre les messages, même avec de petites différences, et la probabilité négligeable de succès.

Enseignant·e

Mikhail Kapralov

Enseignement et PhD Doctorant·es actuel·les Weronika Wrzos-Kaminska, Guy Weissenberg, Davide Mazzali, Ekaterina Kochetkova, Kshiteej Jitesh Sheth A dirigé les thèses EPFL de Amir Zandieh, Aidasadat Mousavifar, Navid Nouri, Jakab Tardos, Grzegorz Adam Gluch, Makarov Mikhail A co-dirigé les thèses EPFL de Paritosh Garg Cours Algorithms II CS-450 Un premier cours de 2eme cycle sur les algorithmes, ce cours a peu de prerequis, mais va vite. Il couvre les techniques principales d'analyse et de

Source officielle

Concepts associés (32)

Algèbre de Boole (logique)

Lalgèbre de Boole, ou calcul booléen, est la partie des mathématiques qui s'intéresse à une approche algébrique de la logique, vue en termes de variables, d'opérateurs et de fonctions sur les variables logiques, ce qui permet d'utiliser des techniques algébriques pour traiter les expressions à deux valeurs du calcul des propositions. Elle fut lancée en 1854 par le mathématicien britannique George Boole. L'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques.

Complexité de la communication

La complexité de la communication ou complexité de communication est une notion étudiée en informatique théorique. Le dispositif abstrait classique est le suivant : Alice et Bob ont chacun un message, et ils veulent calculer un nouveau message à partir de leurs messages, en se transmettant un minimum d'information. Par exemple, Alice et Bob reçoivent un mot chacun, et ils doivent décider s'ils ont reçu le même mot ; ils peuvent bien sûr s'envoyer leur mot l'un à l'autre et comparer, mais la question est de minimiser le nombre de messages.

Couplage (théorie des graphes)

En théorie des graphes, un couplage ou appariement (en anglais matching) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun. Soit un graphe simple non orienté G = (S, A) (où S est l'ensemble des sommets et A l'ensemble des arêtes, qui sont certaines paires de sommets), un couplage M est un ensemble d'arêtes deux à deux non adjacentes. C'est-à-dire que M est une partie de l'ensemble A des arêtes telle que Un couplage maximum est un couplage contenant le plus grand nombre possible d'arêtes.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Fonction booléenne

vignette|Arbre de décision binaire Une fonction booléenne est une fonction prenant en entrée une liste de bits et donnant en sortie un unique bit. Les fonctions booléennes sont très utilisées en informatique théorique, notamment en théorie de la complexité et en cryptologie (par exemple dans les boîtes-S et les chiffrements par flot -- fonction de filtrage ou de combinaison de registres à décalage à rétroaction linéaire). Une fonction booléenne est une fonction de dans où désigne le corps fini à 2 éléments.

Afficher plus

Séances de cours associées (33)

Synthèse logique : Concevoir des circuits numériques efficaces Connectez-vous à Mediaspace pour regarder cette vidéo

Discute des techniques de synthèse logique pour concevoir des circuits numériques efficaces en utilisant des minterms, des maxterms et de nouvelles portes comme XOR et XNOR.

Nombres et booléens

Introduit des nombres et des booléens en Python, couvrant les types numériques, les opérations arithmétiques, les opérations logiques et les comparaisons.

Type booléen: Erreurs courantes

Résiste aux erreurs courantes avec le type booléen en Java et comment les éviter.

Systèmes finis exprimés avec des formules

Explore les systèmes de transition finis, la logique propositionnelle, l'interprétation de la vérité, la satisfaction et la représentation des fonctions booléennes avec des circuits.

Théorie de calcul : Problèmes Définition et comptage (Dnumérabilité)

Explore la théorie du calcul, mettant l'accent sur la définition des problèmes, le comptage et les limites du calcul algorithmique.

Afficher plus

Concepts associés (32)

Algèbre de Boole (logique)

Complexité de la communication

Couplage (théorie des graphes)

Computational complexity

Fonction booléenne

Afficher plus