Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Cette séance de cours introduit le concept d'entropie comme un lien fondamental dans les algorithmes, conduisant à des résultats d'impossibilité et guidant la conception d'algorithmes de codage source efficaces. Il couvre l'objectif du codage source, la configuration impliquant source et encodeur, des exemples de cartes d'encodage, la décodabilité et les codes sans préfixe. La séance de cours explore la relation entre les codes décodables et les codes sans préfixe, soulignant l'importance des codes instantanés pour minimiser les retards de décodage. Il s'inscrit dans l'inégalité de Kraft-McMillan comme condition nécessaire pour des codes décodables uniques, fournissant des exemples et des preuves. La séance de cours se termine par l'arbre de décodage, la longueur des mots de code, et le contraire du théorème de Kraft-McMillan.