Codage de l'information

Codage de l'information: On s'intéresse ici aux moyens de formaliser l'information afin de pouvoir la manipuler (principalement pour la transmettre). On ne s'intéressera donc pas au contenu mais seulement à la forme.

Sommaire

1 Alphabet, mot, langages

1.1 Définitions

1.2 Opérations

2 Codages et codes

2.1 Codage

2.2 Code

3 Applications, exemples

4 Articles connexes

Alphabet, mot, langages

Définitions

On définit un alphabet comme un ensemble non vide de symboles, par exemple :

A = {a,b,c,…,z}, l'alphabet latin ;

A = {0,1,2,…,9}, les chiffres dits arabes

A = {0,1,…,9,A,B,…,F}, les chiffres hexadécimaux.

A = {0,1}, l'alphabet de la logique booléenne.

A = {A,T,G,C}, les bases de l'ADN qui codent notre génome (cet alphabet est le sujet principal de la bio-informatique).

On nomme lettre un élément d'un alphabet.
On nomme mot une suite finie de lettres.
La suite de 0 lettre est nommée le mot vide, notée ε.
On nomme langage un ensemble de mots associé à certaines règles d'interprétation (sans cette dernière restriction, n'importe quelle table de valeurs aléatoires pourrait être nommée langage). Dans le cas de l'ADN, ces règles sont contenues dans le ribosome, dans les langues naturelles, elles sont contenues dans leur lexique, sur un ordinateur, elles sont présentes dans les circuits de l'unité centrale.

Opérations

Soit un alphabet $A$ et un entier naturel $n$ .
On note $A n$ l'ensemble de tous les mots de longueur $n$ sur $A$ et $A *$ l'ensemble de tous les mots de $A$ .
On dispose de : $A^* = \bigcup_{n \geq 0}^{\infty}A^n$ (fermeture de Kleene).
On définit l'opération de concaténation $\cdot : A^* \times A^* \rightarrow A^*$ qui à $(u, v)$ associe un mot $w$ qui est constitué de la suite de lettres de $u$ puis celle de $v$ .
Exemple : « marc » $\cdot$ « et sophie » = « marc et sophie » (les guillemets servent à délimiter les symboles, ce ne sont pas des éléments de $A$ ).

Propriétés :

$\cdot$ est associatif : $\forall u, v, w \in A^*, (u \cdot v) \cdot w = u \cdot (v \cdot w)$

$\cdot$ admet ε comme élément neutre : $\forall u \in A^*, u \cdot \epsilon = \epsilon \cdot u = u$

$\cdot$ n'est pas commutative.

Codages et codes

Codage

Soit L et M deux langages.
Un codage c de L dans M est un morphisme (pour l'opération $\cdot$ ) injectif. En d'autres termes, c'est une correspondance entre les mots de L et ceux de M, où à tout mot de L est associé un unique mot de M et tel que le codage de la concaténée soit égale à la concaténée des codages. ( $\forall u,v \in L, c(u.v) = c(u).c(v)$ ).

Code

Un langage L sur un alphabet A est un code si et seulement s'il n'existe pas deux factorisations différentes des mots $A *$ avec des mots de L.

Applications, exemples

codage Manchester

codage NRZ

codage Miller

code Baudot

Articles connexes

Fuite d'information

v · d · m

Informatique théorique

Théorie du calcul

Calculabilité Décidabilité et indécidabilité • Ensemble récursif • Problème de l'arrêt • Ensemble récursivement énumérable

Modèle de calcul Automate fini •Transducteur fini •Automate sur les mots infinis •Automate à pile •Automate linéairement borné • Automate cellulaire • Machine de Turing • Thèse de Church

Modes de calcul Concurrence • Parallèlisme • Théorie de l'ordonnancement

Mesure et échelle de complexité Réduction polynomiale • Problème NP-complet

Logique, syntaxe et sémantique

Logique mathématique Assistant de preuve • Calcul des prédicats • Correspondance de Curry-Howard • Fonction récursive • Lambda-calcul • Théorème d'incomplétude de Gödel • Théorie des types

Grammaire formelle et systèmes de réécriture Compilation • Expression rationnelle • Grammaire formelle • Transduction rationnelle • Langage rationnel • Langage algébrique • Langage contextuel • Théorie des langages

Sémantique Sémantique des langages de programmation • Sémantique dénotationnelle • Sémantique axiomatique • Sémantique opérationnelle

Spécifier, vérifier et concevoir des programmes Interprétation abstraite • Méthodes formelles • Model checking

Algorithmique, complexité et mathématiques discrètes

Algorithmique Algorithme génétique • Algorithme glouton • Algorithme probabiliste • Complexité algorithmique • Diviser pour régner • Heuristique • Programmation dynamique

Problèmes et algorithmes numériques Algorithme du simplexe • Géométrie algorithmique • Algorithme d'Euclide • Test de primalité

Problèmes et algorithmes non-numériques Algorithmes de la théorie des graphes • Arbre (structure de données) • Liste (informatique) • Table de hachage • Tas (informatique)

Théorie des graphes Coloration de graphe • Problèmes de cheminement

Recherche opérationnelle Optimisation • Optimisation combinatoire • Théorie de l'ordonnancement

Données et codage Combinatoire des mots •Codage • Codage de l'information • Compression de données • Cryptage • Cryptanalyse • Cryptographie • Théorie de l'information

Catégorie :
Théorie de l'information

Contenu soumis à la licence CC-BY-SA. Source : Article Codage de l'information de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

Codage De L'information — On s intéresse ici aux moyens de formaliser l information afin de pouvoir la manipuler (principalement pour la transmettre). On ne s intéressera donc pas au contenu mais seulement à la forme. Sommaire 1 Alphabet, mot, langages 1.1 Définitions 1.2 … Wikipédia en Français
Codage De Source — Le but du codage de source peut être de compresser l information répétitive du langage, sa redondance. Pour toute langue, on peut considérer l entropie d un message, c est à dire la quantité d information transmise. Ceci donne lieu au théorème du … Wikipédia en Français
Codage de source — Le but du codage de source peut être de compresser l information répétitive du langage, sa redondance. Pour toute langue, on peut considérer l entropie d un message, c est à dire la quantité d information transmise. Ceci donne lieu au théorème du … Wikipédia en Français
Codage entropique — Le codage entropique (ou codage statistique à longueur variable) est une méthode de codage de source sans pertes, dont le but est de transformer la représentation d une source de données pour sa compression et/ou sa transmission sur un canal de… … Wikipédia en Français
Codage Miller — Pour les articles homonymes, voir Miller. Pile de protocoles 7. Application 6. … Wikipédia en Français
INFORMATION (THÉORIE DE L’) — La théorie de l’information ou, de façon plus précise, la théorie statistique de la communication, est l’aboutissement des travaux d’un grand nombre de chercheurs (H. Nyquist, R.W.L. Hartley, D. Gabor...) sur l’utilisation optimale des moyens de… … Encyclopédie Universelle
Codage De Caractères — Pour l action de cacher le sens de l information, voir chiffrement. Unicode Jeux de caractères UCS (ISO/CEI 10646) ISO 646, ASCII ISO 8859 1 WGL4 UniHan Équivalences normalisées NFC (précomposée) NFD (décomposée) NFKC (compatibilité) NFKD… … Wikipédia en Français
Codage de caracteres — Codage de caractères Pour l action de cacher le sens de l information, voir chiffrement. Unicode Jeux de caractères UCS (ISO/CEI 10646) ISO 646, ASCII ISO 8859 1 WGL4 UniHan Équivalences normalisées NFC (précomposée) NFD (décomposée) NFKC… … Wikipédia en Français
Codage de caractères — Pour l action de cacher le sens de l information, voir chiffrement. Unicode Jeux de caractères UCS (ISO/CEI 10646) ISO 646, ASCII ISO 8859 1 WGL4 UniHan Équivalences normalisées NFC (précomposée) NFD (décomposée) NFKC (compatibilité) NFKD… … Wikipédia en Français
Codage du caractère — Codage de caractères Pour l action de cacher le sens de l information, voir chiffrement. Unicode Jeux de caractères UCS (ISO/CEI 10646) ISO 646, ASCII ISO 8859 1 WGL4 UniHan Équivalences normalisées NFC (précomposée) NFD (décomposée) NFKC… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Codage de l'information

Sommaire

Alphabet, mot, langages

Définitions

Opérations

Codages et codes

Codage

Code

Applications, exemples

Articles connexes

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Codage de l'information

Sommaire

Alphabet, mot, langages

Définitions

Opérations

Codages et codes

Codage

Code

Applications, exemples

Articles connexes

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link