Site des Oraux

Théorie de codage et de l'information 2004 (9) :: post
Années :: 2005 :: 2006 :: 2007 :: Toutes

Post nº9 (id728) envoyé par arnaud  le 01 Sep 2004, 20:45
J'ai du parler brièvement de ce qu'était le codage de source (à quoi ça sert en gros... à savoir compresser les données émises par la source)
Puis dire ce qu'était un code instantané, en donner un exemple et montrer en quoi c déchiffrable "instantanément"
Ca ct les 2 ptites questions.

Viens l'inégalité de Kraft + démonstration (l'inégalité est une CNS de code instantané mais j'ai juste du démontrer que ct une CN)

Puis j'ai dû déterminer la longueur moyenne optimale d'un code instantané pour une source donnée
(c'est l'histoire avec les multiplicateur de Lagrange)
Et donc on montre que la borne inférieur à la longueur moyenne est l'entropie de shannon. H(X)=< L

Il m'a demandé si on pouvait atteindre cette borne.
En toute généralité, non pcq on trouve que l_i = -log_d_(p_i) qui n'est pas entier en toute généralité et donc on doit prendre le plafond des l_i ce qui donne le code de shannon.
Mais dans le cas particulier où les p_i sont dse puissances de d (d étant le nombre de symboles de l'alphabet du code), alors oui les l_i sont des entiers. on peut atteindre la longueur moyenne minimale. On dit alors que le code est dia ... qqch

Puis il m'a demandé de lui donner une borne supérieure pour cette longueur dans le cas général.
Comme on a: l_i =< plafond de l_i =< l_i + 1
Quand on somme, on trouve: H(X) =< L =< H(X) + 1 (en tenant compte ke la somme des p_i vaut 1)

Il m'a demandé si on pouvait réduire cette borne supérieure.
Oui en codant par bloc (par extension d'ordre n de la source). Dans ce cas ce "bit de pénalité" se répartit sur les n symboles du bloc et on a une pénalité de 1/n bit par symbole qui tend vers 0 pour n très grand.

Enfin il m'a demandé un exemple de code de Hamming.
Mais ça je savais pas cmt on faisait. Il l'a pas trop mal pris.

Et à la fin il donne pas de cote, il m'a juste dit que ct bon, même sans le code de Hamming.
Il est donc pas méchant et il aide un peu.
Mais j'dois avouer que j'ai eu du bol sur les questions.

*Spécial* Post nº8 (id726) envoyé par arnaud  le 01 Sep 2004, 18:16
Résumé des questions déjà tombées:

I. ENTROPIE DE SHANON
- Entropie (déf)

II. ASYMPTOTIC EQUIPARTITION PROPERTY (AEP)
- Séquences Typiques
- Théorème d'AEP

III. DATA COMPRESSION (CODAGE DE SOURCE)
- Principe de compression de données
- Principe de codage de source
- Longueur moyenne d'un code
- Codes instantanés (déf)
- Inégalité de Kraft (+démo)
- Longueur optimale L* (code optimal)
- Code de Shanon
- Premier théorème de Shannon
- Code d'Huffman (Construction+principe)

IV. CAPACITE DE CANAL
- Capacité informationnelle + opérationnelle (déf)
- Canal Binaire Symétrique (CBS)
- Canal Binaire à effacement (CBE)
- Second Théorème de Shanon
- Séquences conjointement typiques et théorème de Shannon

V. CCE:
- Principe
- Décodeur idéal (+demo Bayes)
- Différence entre poids min & distance minimale
- Distance minimum (+démo avec sphères)
- Code de Hamming (+exemple)
- Code de Hamming Canonique (Encodage + Décodage)
- Borne de Hamming (+démo)

Post nº7 (id717) envoyé par fsamyn  le 31 Aug 2004, 16:42
Voici la suite:
- il m'a demandé dans quoi s'insérait mes trois prmière question: compression de données.
- ex de fonctionnement de code de Hamming.
ccl: il est trés sympas mais il faut tt savoir justifier, il est très pointilleux. mais il faut aussi connaitre le coiurs dans son ensemble: les grands théorèmes etc.

bonne me... pour la suite

Post nº6 (id716) envoyé par fsamyn  le 31 Aug 2004, 16:38
Je suis passé cette après midi et j'ai ey:
- code instantanné: déf et à quoi ca sert? Il m'a en plus baladé sur les code dfu.
- inégalité de Kraft: démo. il faut tt savoir justifier.
- calcul de la longueur optimal de mots codes: bien justifier et il m'a demandé de faire le lien avec le premier théorème de Shanon. +donner le code de Shanon et comparer à l'entropie.

Post nº5 (id715) envoyé par nmainil  le 31 Aug 2004, 15:57
Je suis passé ce matin et j'ai eu :

- CCE : principe
- CCE : décodeur idéal
- CCE : distance minimum d'un CCE
- CCE : borne de Hamming
- Comment utilise-t-on les séquences conjointement typiques dans le second théorème de Shannon

Post nº4 (id709) envoyé par anonyme  le 30 Aug 2004, 17:18
donc t entre, t as ton cours il te laisse seul tu remplis tes tableaux et t explique hésite pas a mettre le plus possible

moi g eu (tout le monde a eu ca cette aprem je pense)

code correcteur d 'erreur dans tous les sens :

expliquer en gros le principe d un CCE
principe du décodeur idéal
distance entre mots code <--> nb erreur (à démontrer avec les shpère)
borne de hamming démontrer
exemple d'utilisation du code de Hamming

Post nº3 (id708) envoyé par anonyme  le 30 Aug 2004, 17:01
jai passé cerf aujourd'hui. il est tres sympa comme tout le monde le dit, et il insiste vraiment sur la comprehension.

Donc ta mission en passant cet examen, c'est d'une part de recopier toute la partie du cours qui concerne les question (elles se suivent, c facile a retrouver). Veille donc a avoir un poignet bien degourdi, et ne perds pas trop de temps a contempler ton oeuvre au tableau.

Ensuite, apres une demi-heure, il arrive et te dis avec son plus beau sourire "je t'ecoute!". Tu dois donc etre capable de lui expliquer TOUT ce que tu as ecrit (chacun de tes traits!). Et il ne demande rien d'autre que ce qui a un rapport direct avec la question.

jai eu:
- capacite (def informationnelle et operationnelle)
- 2e theoreme de Shannon
- CBS et CBE (je lui ai parlé du feedback alors qu'il l'a pas demandé. ca lui a plu!)
- lien entre sequences conjointement typiques et le theoreme de Shannon

il ne cote vraiment pas vache, faut juste tout expliquer et si ya des trucs flous, il reexplique tout gentillement!

Post nº2 (id695) envoyé par anonyme  le 22 Aug 2004, 14:22
Voila un medley des questions qui se trouvent sur la mailing list 2005,

amusez vous bien

Paille


Cerf :
1. CCE principe, code idéal, distance d'un CCE
2. Borne de Hamming principe plus démo
3. Exemple avec une matrice qcq de Hamming

Il est vraiment super sympa et il s'intéresse principalement à la compréhension

J'ai passé l'exam de Cerf et il n'est pas tres complique... Il vous pose plusieurs petites que vous notez au tableau. Il vous laisse 1/2 heure avec votre cours et ous préparez la question au tableau.Vous écrivez ce que vous voulez. Il revient ensuite et vous lui expliquez tout ce que vous avez écrit. Il pose des petites quesions en plus pour voir si vous avez bien compris son cours... J'ai discuté 45 min avec lui probablement pcq j'étais tt seul à passer.
A part ca, il est très sympa mais ne donne pas la cote finale, juste une petite estimation.

En fait l'exercice qu'il donne c'est plutôt un exemple traité au cours.Rien ne vient des TP.

Principe des CCE
Decodeur Idéal: Définition & Démo des formules ( Cf Bayes... )
Différence entre poids min & distance minimale
Bornes de Hamming :Déf & Démo...
Application : Codes de Hamming ( Canonique : Encodage et décodage )-Cest la partie exercice pour celui qui veut savoir.
Tous ceux qui passent n'ont en général pas la même question.
Je ne sais pas le détail des questions des autres.Mais en tout cas il y en a qui ont été interrogés sur l'équipartition asymptotique...


Alors mes quetions

CCE
but et principe
decodeur ideal
distance de Hamming (distance d'un code correcteur d'erreur)
bornes de Hamming (démonstration)

Huffman

Construction
Principe


Je suis entré, j'ai eu 4 questions à écrire au tableau.

- Code source: objectifs et classes.

- Inegalité de Kraft = demo.

- En déduire qqch sur les codes optimaux. ( ineglaité saturé )

- Exemple au choix d'un algo de Hauffman.

Il m a laissé une demi heure pour écrire ce que je voulais au tableau, puis il est revenu et j'ai exposé mes explications.

Tout se suivait dans le cours. Pas de piège, il demande d'expliquer le cours. Il met sur la voie si on cale. Si on est bon, il ose qq questions bonus comme:

"Comment appelle t on une source dont les longeurs des codes sont entieres?" Je ne me rappelle plus , ca commence par "dia"...

Cerf
1. CCE
2. Borne de Hamming
3. Exemple avec une matrice qcq de Hamming


Pour ceux que ça intéresse.J'ai eu 4 questions:

-équipartition asymptotique
-séquence typique
-compression des données
-canal binaire symétrique

il donne une approximation du style plus de 12 ou moins.

J'ai eu :

Codage de source
Longueur moyenne d'un code
Code de Shannon

exemple de Huffman

Post nº1 (id401) envoyé par Archives  le 03 Jun 2004, 16:13
Questions de cerf (septembre 2003)

- Codage de source
- Longueur moyenne d'un code
- Code de Shannon
- exemple de Huffman
- équipartition asymptotique
- séquence typique
- compression des données
- canal binaire symétrique
- CCE principe, code idéal, distance d'un CCE
- Borne de Hamming principe plus démo
- Exemple avec une matrice qcq de Hamming

Il donne les points en comparant les étudiants. Il faut donc attendre qu'il termine d'interroger. Mais il donne une approximation du style plus de 12 ou moins.
Il est vraiment super sympa et il s'intéresse principalement à la compréhension


oraux.pnzone.net - infos - 5ms