Séance de cours

Codage universel des sources

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

COM-404: Information theory and coding

The mathematical principles of communication that govern the compression and transmission of data and the design of efficient methods of doing so. ...

Description

Cette séance de cours couvre le concept de codage source universel, en se concentrant sur l'algorithme de codage universel Lempel-Ziv. Emre Telatar explique la théorie derrière les machines à états finis inversible et leurs applications dans la théorie de l'information.

Enseignant·e

Emre Telatar

Enseignement et PhD Doctorant·es actuel·les Serhat Emre Coban, Adway Girish, Ryan Yuanqing Song A dirigé les thèses EPFL de Aslan Tchamkerten, Stéphane Musy, Sibi Raj Bhaskaran Pillai, Robert Konsbruck, Dinkar Vasudevan, Eren Sasoglu, Mohammad Karzand, Alla Merzakreeva, Mine Alsan, Marc Desgroseilliers, Mani Bastani Parizi, Rajai Nasser, Serj Haddad, Elie Najm, Yunus Inan, Reka Inovan, Pierre Quinton A co-dirigé les thèses EPFL de Prasenjit Dey, Etienne Perron, Ayfer Özgür Aydin Cours Information theory

Source officielle

Concepts associés (32)

Transducteur fini

En informatique théorique, en linguistique, et en particulier en théorie des automates, un transducteur fini (appelé aussi transducteur à états finis par une traduction littérale de l'anglais finite state transducer) est un automate fini avec sorties. C'est une extension des automates finis. Ils opèrent en effet sur les mots sur un alphabet d'entrée et, au lieu de simplement accepter ou refuser le mot, ils le transforment, de manière parfois non déterministe, en un ou plusieurs mots sur un alphabet de sortie.

Automate fini déterministe

Un automate fini déterministe, parfois abrégé en AFD (en anglais deterministic finite automaton, abrégé en DFA) est un automate fini dont les transitions à partir de chaque état sont déterminées de façon unique par le symbole d'entrée. Un tel automate se distingue ainsi d'un automate fini non déterministe, où au contraire plusieurs possibilités de transitions peuvent exister simultanément pour un état et un symbole d'entrée donné.

Automate fini non déterministe

Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation.

Théorie algorithmique de l'information

La théorie algorithmique de l'information, initiée par Kolmogorov, Solomonov et Chaitin dans les années 1960, vise à quantifier et qualifier le contenu en information d'un ensemble de données, en utilisant la théorie de la calculabilité et la notion de machine universelle de Turing. Cette théorie permet également de formaliser la notion de complexité d'un objet, dans la mesure où l'on considère qu'un objet (au sens large) est d'autant plus complexe qu'il faut beaucoup d'informations pour le décrire, ou — à l'inverse — qu'un objet contient d'autant plus d'informations que sa description est longue.

Automate quantique

En informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis.

Afficher plus

Séances de cours associées (64)

Processus de détermination des points et extrapolation

Couvre les processus de point déterminant, le sinus-processus et leur extrapolation dans différents espaces.

Machines à états finis: bases et conception

Introduit des machines à états finis, couvrant les bases, la conception et les applications pratiques telles que les décodeurs et les encodeurs.

Compression universelle : Méthode Lempel-Ziv

Couvre la compression universelle en utilisant la méthode Lempel-Ziv et démontre sa supériorité sur les autres méthodes.

Huffman Coding

Explore le codage Huffman en le comparant à l'organisation d'une cuisine pour l'efficacité.

Systèmes logiques : circuits séquentiels et combinatoires

Couvre les concepts fondamentaux des systèmes logiques, y compris les circuits séquentiels et combinatoires, les diagrammes détat et les machines détat fini.

Afficher plus

Concepts associés (32)

Transducteur fini

Automate fini déterministe

Automate fini non déterministe

Théorie algorithmique de l'information

Automate quantique

Afficher plus