Séance de cours

Le théorème de Shannon

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-119(a): Information, calcul, communication

D'une part, le cours aborde: (1) la notion d'algorithme et de représentation de l'information, (2) l'échantillonnage d'un signal et la compression de données et (3) des aspects liés aux systèmes: ordinateur, mémoire, etc. D'autre part, le cours donne une i ...

Description

Cette séance de cours couvre les bases des codes binaires, y compris les définitions, les exemples, et le concept de codes binaires sans préfixe. Il introduit ensuite le Théorème de Shannon, indiquant que pour tout code binaire sans préfixe utilisé pour représenter une séquence donnée, l'entropie de la séquence est toujours inférieure ou égale à la longueur moyenne du code. La séance de cours explique également l'inégalité de Kraft et fournit une démonstration détaillée du théorème de Shannon, montrant la relation entre l'entropie et la longueur du code. D'autres inégalités liées à l'entropie et à la longueur du code sont discutées, soulignant les limites de la compression des données sans perte.

Dans MOOC

Information, Calcul, Communication: Introduction à la pensée informatique

Dans une première partie, nous étudierons d’abord comment résoudre de manière très concrète un problème au moyen d’un algorithme, ce qui nous amènera dans un second temps à une des grandes questions de l’informatique théorique moderne. La seconde partie du cours sera quant à elle consacrée à l’information est la communication : nous passerons en revue plusieurs sujets, comme la représentation de l'information, le traitement des signaux, la compression de données, la communication et la cryptographie.

Enseignant·e·s (3)

Olivier Lévêque

Olivier Lévêque est né en Suisse en 1971. Il a reçu le diplôme d'ingénieur-physicien de l'EPFL en 1995 et obtenu le doctorat au Département de Mathématiques de l'EPFL en 2001. Depuis lors, il travaille au Laboratoire de Théorie de l'Information à l' EPFL. Il a passé l'année académique 2006-2007 au Département d'Electricité de l'Université de Stanford, où il a été nommé chargé de cours. Ses domaines d'intérêt comprennent la théorie de l'information, les matrices aléatoires et les équations aux dérivées partielles stochastiques.

Dan-Cristian Tomozei

Mirjana Stojilovic

Mirjana Stojilović received the Dipl. Ing. and Ph.D. degrees from the School of Electrical Engineering, University of Belgrade, in 2006 and 2013, respectively. From 2010 to 2013, she was collaborating with the Processor Architecture Laboratory at EPFL, visiting periodically as a Guest Researcher. From 2013 to 2016, she was working at the University of Applied Sciences Western Switzerland as a senior researcher, and at EPFL as a lecturer. She joined Parallel Systems Architecture Lab at EPFL in October 2016. Mirjana's main research interests include electronic design automation, reconfigurable computing, electromagnetic-compatibility and signal-integrity issues, and hardware security. Mirjana Stojilović serves on the program committee of the FPGA, FPL, and FCCM conferences and as a reviewer for IEEE TCAD, TVLSI, TC, TEMC, IEEE Access and ACM TRETS. She received the Best Paper Award at 2016 International Symposium on Electromagnetic Compatibility (EMC Europe 2016), Young Scientist Award at 33rd International Conference on Lightning Protection (ICLP2016), and the Young Author Best Paper Award at the 20th Telecommunication Forum in Belgrade (TELFOR 2012). In 2015, the EPFL School of Computer and Communication Sciences (IC) presented her with the Teaching Award.

Source officielle

Quiz

Concepts associés (32)

Compression de données

La compression de données ou codage de source est l'opération informatique consistant à transformer une suite de bits A en une suite de bits B plus courte pouvant restituer les mêmes informations, ou des informations voisines, en utilisant un algorithme de décompression. C'est une opération de codage qui raccourcit la taille (de transmission, de stockage) des données au prix d'un travail de compression. Celle-ci est l'opération inverse de la décompression.

Lossy compression

In information technology, lossy compression or irreversible compression is the class of data compression methods that uses inexact approximations and partial data discarding to represent the content. These techniques are used to reduce data size for storing, handling, and transmitting content. The different versions of the photo of the cat on this page show how higher degrees of approximation create coarser images as more details are removed. This is opposed to lossless data compression (reversible data compression) which does not degrade the data.

Algorithme de compression sans perte

vignette|Comparaison de la compression d'image entre les formats JPG (à gauche) et PNG (à droite). PNG utilise une compression sans perte. On appelle algorithme de compression sans perte toute procédure de codage ayant pour objectif de représenter une certaine quantité d'information en utilisant ou en occupant un espace plus petit, permettant ainsi une reconstruction exacte des données d'origine. C'est-à-dire que la compression sans perte englobe les techniques permettant de générer un duplicata exact du flux de données d'entrée après un cycle de compression/expansion.

Théorème du codage de source

Le théorème du codage de source (ou premier théorème de Shannon, ou encore théorème de codage sans bruit) est un théorème en théorie de l'information, énoncé par Claude Shannon en 1948, qui énonce la limite théorique pour la compression d'une source. Le théorème montre que l'on ne peut pas compresser une chaine de variables aléatoires i.i.d, quand la longueur de celle-ci tend vers l'infini, de telle sorte à ce que la longueur moyenne des codes des variables soit inférieure à l'entropie de la variable source.

Compression artifact

A compression artifact (or artefact) is a noticeable distortion of media (including , audio, and video) caused by the application of lossy compression. Lossy data compression involves discarding some of the media's data so that it becomes small enough to be stored within the desired or transmitted (streamed) within the available bandwidth (known as the data rate or bit rate). If the compressor cannot store enough data in the compressed version, the result is a loss of quality, or introduction of artifacts.

Afficher plus

Séances de cours associées (64)

Compression des données et Algorithme Shannon-Fano

Explore l'algorithme Shannon-Fano pour la compression des données et son efficacité dans la création de codes binaires uniques pour les lettres.

Compression de données et théorème de Shannon: Exemple de calcul d'entropie

Démontre le calcul de l'entropie pour un exemple spécifique, résultant en une valeur d'entropie de 2,69.

Entropie et algorithmes : Applications au tri et à la pesée

Couvre l'application de l'entropie dans les algorithmes, en se concentrant sur le tri et les stratégies de prise de décision.

Compression des données et résumé du théorème de Shannon

Résumé du théorème de Shannon, soulignant l'importance de l'entropie dans la compression des données.

Théorème de codage des sources

Explore le théorème de codage source, l'entropie, le codage Huffman et l'impact du conditionnement sur la réduction de l'entropie.

Afficher plus

Concepts associés (32)

Compression de données

Lossy compression

Algorithme de compression sans perte

Théorème du codage de source

Compression artifact

Afficher plus