\documentclass[12pt,a4paper]{article}
\usepackage{multicol}
\usepackage[french]{babel}
\newfont{\mini}{cmssi10 scaled 480}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\euro{\mbox{\textsf{C}\kern -2.33em{\raise0.24ex\vbox{\small\it =}}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\fin{\nolinebreak \raise-0.1em\hbox{$\Box$}}
\def\stackunder#1#2{\mathrel{\mathop{#2}\limits_{#1}}}
\def\dual{ ^{\rm v}}
\def\bidual{ ^{\rm vv}}
\def\primedual{ ^{\prime \rm v}}
\def\ideal{{\cal J}}
\def\LL{{\cal L}}
\def\max{{\cal M}}
\def\quot#1#2{\mbox{\raise 0.1cm\hbox{$#1$}{\big /}\raise -0.1cm\hbox{$#2$}}}
\def\danger{{\Large \bf
    $\bigtriangleup$}\kern-0.32cm\raise0.05cm\hbox{\small
    !}\kern0.32cm\lower0.05cm\hbox{}}
%%%%%%%
\newlength{\largeurtmp}
\def\rela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.6\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.6\largeurtmp}
\def\petitrela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.4\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.4\largeurtmp}
\def\petitcomplex{{
    \settoheight{\largeurtmp}{$_C$}{\rm C}\kern -\largeurtmp
    \rule{0.25pt}{1.3\largeurtmp}\kern \largeurtmp}}
\def\complex{{
    \settoheight{\largeurtmp}{Q}{\rm C}\kern -0.66\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.66\largeurtmp}}
\def\ratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.75\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.75\largeurtmp}}
\def\petitratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.6\largeurtmp
    \rule{0.25pt}{0.6\largeurtmp}\kern 0.6\largeurtmp}}
\newcommand{\proj}{{\rm I} \! {\rm P}}
\newcommand{\reel}{{\rm I} \! {\rm R}}
\newcommand{\Fp}{{\rm I} \! {\rm F}_p}
\newcommand{\nat}{{\rm I} \! {\rm N}}
%%%%%%%%%%%%%%%Debut de macros de fiches d'exos
%%les macros sont \exo, \qu, \quskip \squ \qusqu \qusquskip
\newcounter{exo}
\newcounter{question}
\newlength{\lng}
\newcounter{sousquestion}
\setcounter{exo}{1}
\def\exo{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}:}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\exotitre#1{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}: #1}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\qu{

  \addtocounter{question}{1}\arabic{question})
  \setcounter{sousquestion}{1} }
\def\quskip{

  \bigskip
  \qu}
\def\squ{

  \settowidth{\lng}{\arabic{question})
  }\hspace{\the\lng}\alph{sousquestion}) \addtocounter{sousquestion}{1}} 
\def\qusqu{\qu\nopagebreak \vskip -1\baselineskip \squ}
\def\qusquskip{\quskip\nopagebreak \vskip -1\baselineskip \squ}

%%reference pour exos,squ \`a placer avant la question, qu est a placer apres
\def\labelexo#1{\expandafter\edef\csname refexo#1\endcsname {\Roman{exo}}}
\def\refexo#1{\csname refexo#1\endcsname}
\def\labelqu#1{\expandafter\edef\csname refqu#1\endcsname {\arabic{question})}}
\def\refqu#1{\csname refqu#1\endcsname}
\def\labelsqu#1{\expandafter\edef\csname refsqu#1\endcsname
  {\arabic{question}\alph{sousquestion})}} 
\def\refsqu#1{\csname refsqu#1\endcsname}  

%%%%%%%%%%fin de macros fiche d'exos
%%macros taille page
\newlength{\elargir}
\setlength{\elargir}{2.5cm}
\addtolength{\leftmargin}{-\elargir}
%%\addtolength{\hoffset}{-\elargir}
\addtolength{\oddsidemargin}{-\elargir}
\addtolength{\evensidemargin}{-\elargir}
\addtolength{\elargir}{\elargir}
\addtolength{\textwidth}{\elargir}
\addtolength{\textheight}{13\baselineskip}
\topmargin=-5\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit\'e de Paris 7 \hfill \framebox{\Large \bf
    \hspace{ 1cm} TP18 Codes 1(initiation)\hspace{1cm}}\hfill   agreg 2010 (F.Han\footnote{http://www.math.jussieu.fr/$\sim$han/agreg})}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
\begin{multicols}{2}
% restart;maple_mode(1);cas_setup(0,0,0,1,0,1e-10,10,[1,50,0,25],0,0,0); #radians,pas de cmplx, pas de  Sqrt
\exotitre{astuces diverses}
\qu Etudier le comportement d'xcas avec les matrices en calul modulaire, et les
priorit\'es des op\'erations. 
% !s!<c>
%xcas peut reduire les matrice modulo n, avec les regles de priorite suivantes:
%!s!
% [[1,3],[-1,5]]*[[2,7],[-1,5]] mod 5;
%([[1,3],[-1,5]]*[[2,7],[-1,5]]) mod 5;
% [[1,3],[-1,5]]+[[2,7],[-1,5]] mod 5;
%([[1,3],[-1,5]]+[[2,7],[-1,5]]) mod 5;
\qu Remarquer que la forme inerte (ie avec majuscule) \'equivaut \`a mettre
l'instruction entre \verb/'/. Par exemple comparer: \verb/gcd(x+3,x+5) mod 2;/  et
\verb/'gcd(x+3,x+5)' mod 2;/  et \verb/Gcd(x+3,x+5) mod 2;/ En d\'eduire un moyen
de r\'esoudre un syst\`eme \`a coefficients dans $\rela/2\rela$.
% gcd(x+3,x+5) mod 2;# le modulo est fait apres le calcul du pgcd
% 'gcd(x+3,x+5)' mod 2;# le pgcd est bien calcule dans F2
% Gcd(x+3,x+5) mod 2;# equivaut a l'instruction precedente.
% linsolve([[2]],[0]);
% linsolve([[2]],[0]) mod 2;
% 'linsolve([[2]],[0])' mod 2;#celui la fait bien 2x=0 dans F2
\qu Attention\footnote{Le plus simple/sur sera probablement de mettre le mod
  lorsque l'on utilise la fonction} lors de la cr\'eation d'une fonction \`a partir
d'un symbole lorsqu'il 
y a des modulo. Essayer \code{S:=2*x+y}, puis \verb/f:=unapply(S mod 2, x,y);/ et
\verb/g:=(x,y)->S mod 2;/ et   \verb/h:=(x,y)->eval(S) mod 2;/ et calculer les
images de $(1,2)$. On pourra aussi essayer de d\'efinir $g$ \`a l'interieur d'une
autre proc\'edure.
%S:=2*x+y;
%f:=unapply(S mod 2, x,y);
%f(1,2);#le mod a ete fait avant de remplacer les x et y
%f:=(x,y)->S mod 2;
%f(1,2)
%f:=(x,y)->eval(S) mod 2;
%f(1,2);
%!s!<m>
%h:=proc(a,b)
%f:=(x,y)->S mod 2;#dans une procedure l'eval est inutile
%f(a,b);end;
%!s!
%h(1,2);
%!s!<c>
%--------------------------------------Exercice texte jury 1---------------------------
%!s!
\exotitre{Texte jury1: Diff\'erentes fa\c cons de faire jouer le jury}
  \qu Niveau 0: On rentre la r\'eponse \`a la main, ainsi que la matrice.
%!s!<c>
%jeu1 du  jury   
%!s!
%  m:=[0$7];
%!s!<c>
%  ou bien m:=matrix(7,1,0); et on rentre m[k,1]:= 
%!s!
%  H:=matrix([[1,0,1,0,1,0,1],[0,1,1,0,0,1,1],[0,0,0,1,1,1,1]]);
%!s!<c>
%  entrer les valeurs non nulles (1=oui) selon les reponses Ex: m[1]:=1;  
%!s!
%  m[1]:=1;m[4]:=1;m[7]:=1;
% w:=(H*m) mod 2; #Attention mod est prioritaire sur les operations
% k:=4*w[3]+2*w[2]+w[1];
% if k<>0 then print("menti a la question:",k);m[k]:=(m[k]+1) mod 2   else print("pas menti"); fi: 
% r:=m[4]+m[3]*2+m[2]*4+m[1]*8:print("votre nombre est:",r);
\qu On am\'eliore avec une proc\'edure. (Comment faire apparaitre une fen\^etre interactive)  
% !s!<c>
%le meme dans une procedure: 1 pour oui a la question
%!s!<p>
% jeu:=proc()
% local m:=[0$7];
% H:=matrix([[1,0,1,0,1,0,1],[0,1,1,0,0,1,1],[0,0,0,1,1,1,1]]);
% input(output("est il >=8?(1 si oui, 0 sinon)"),rep);
% m[1]:=rep;// m[1] ne marche pas dans un input?
% input(output("est il dans {4,5,6,7,12,13,14,15}?(1 si oui, 0 sinon)"),rep);
% m[2]:=rep;
% input(output("est il dans {2,3,6,7,10,11,14,15}?(1 si oui, 0 sinon)"),rep);
% m[3]:=rep;
% input(output("est il impair?(1 si oui, 0 sinon)"),rep);
% m[4]:=rep;
% input(output("est il dans {1,2,4,7,9,10,12,15}?(1 si oui, 0 sinon)"),rep);
% m[5]:=rep;
% input(output("est il dans {1,2,5,6,8,11,12,15}?(1 si oui, 0 sinon)"),rep);
% m[6]:=rep;
% input(output("est il dans {1,3,4,6,8,10,13,15}?(1 si oui, 0 sinon)"),rep);
% m[7]:=rep;
% w:=(H*m) mod 2;
% k:=4*w[3]+2*w[2]+w[1];
% if k<>0 then print("menti a la question:",k);m[k]:=(m[k]+1) mod 2   else print("pas menti"); fi: 
% r:=m[4]+m[3]*2+m[2]*4+m[1]*8:print("votre nombre est:",r);
% end proc;  
%!s!
%jeu();
\qu Am\'eliorations: On va expliquer maintenant comment sont cr\'ees $H$ et les questions.
\squ Cr\'eation de  $H$ automatiquement en remarquant que les colonnes sont les
 chiffres de $1$ \`a $8$  en base $2$.
% f:=(i,j)->floor(j/2^(i-1)) mod 2;
% H:=matrix(3,7,f);
\qusqu Comment trouver un noyau modulo 2? Comment r\'esoudre un syst\`eme
affine modulo 2. 
% !s!<c>
% On trouve une famille generatrice du code:
%!s!
% C:=Nullspace(H) mod 2; 
% H*transpose(C) mod 2;#On verifie:
\squ comment obtenir  $(x,y)$ (autrement dit \code[3,1]) \`a
partir de \verb/{y=1,x=3}/? Comment \'evaluer les param\`etres des
solutions d'un syst\`eme?
% subs(y=1,x=3,[x,y]);# Attention, il ne faut PAS de {} comme sous maple 
\squ Cr\'eer une proc\'edure \code{syst(k)} qui cr\'ee une  matrice $4\times
7$ obtenue \`a partir de $H$ en rajoutant une ligne ayant $1$ sur la
colonne $k$ et $0$ ailleurs. 
%!s!<m>
% syst:=proc(i)
% HE:=augment(H,[[0$7]]);
% HE[4,i]:=1;
% HE;
% end proc;
%syst(3);
% !s!
\squ Remarquer\footnote{En mode maple. Si l'on est en mode xcas, il suffit que
  les coefficients soient des modulaires (ie du type \code{a \% 2}), et le linsolve sera correct} que lorsqu'une forme inerte n'existe pas on peut utiliser des
\verb/'/. Par exemple \code{linsolve} n'a pas sa forme inerte \code{Linsolve}.
Pour travailler modulo $2$ il nous suffira d'utiliser \verb/'linsolve()' mod 2;/
\squ Cr\'eer une proc\'edure\footnote{Attention, sous maple l'indice des param\`etres
  utilis\'es pour les solutions n'est pas toujours le m\^eme ce qui pose probl\`eme
  pour les boucles ensuite. Sous xcas je n'ai pas remarque ce Pb} \code{sol(k)}
qui retourne les solutions de \code{syst(k)}.
%!s!<m>
% sol:=proc(k)
% 'linsolve(syst(k),[0,0,0,1])' mod 2;
% end proc;
%!s!
\squ Cr\'eation des questions (ie des listes) automatiquement. 
%!s!<c>
% oui a la question k veut dire etre dans le code et m[i]=1, donc etre solution de syst(k)
% !s!
%sol(2)
% !s!<c>
% Attention, a la syntaxe f:=(C_0,C_1,C_2)-> S mod 2; S n'est pas forcement
% evalue avant (si l'on n'est pas dans une procedure forcer avec un
% eval(S)). Attention, si l'on utilise unapply(S mod 2,C_0,C_1,C_2) alors le mod
% 2 est applique aux variables formelles, et l'expression totale ne sera pas
% forcement reduite. 
%!s!
% !s!<p>
% question:=proc(k)
% S:=sol(k);
% f:=(C_0,C_1,C_2)-> S mod 2;
%// f:=unapply(S mod 2,C_0,C_1,C_2);//le mod 2 est fait avant d'evaluer les C_i
% l:=eval(seq(seq(seq((matrix([[8,4,2,1,0,0,0]])*f(a,b,c))[1],a=0..1),b=0..1),c=0..1));
% sort([l]);//le eval dans l sert a simplifier les (())
% end proc;
%!s!
% for k from 1 to 7 do print("est il dans",question(k));od;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\squ pour \'eviter les \verb/seq(seq(seq/ cr\'eer une proc\'edure
%%qui retourne le produit de 2 listes, et une
qui retourne la puissance $n$-i\`eme d'un ensemble $E$ sous forme d'une matrice dont les
lignes sont des $n$-uplets de $E$. On pourra utiliser tous les
entiers de $0$ \`a  $card(E)^n -1$ convertis en  base $card(E)$.
%purge(E,F,i,j);
% prodlist:=(E,F)->eval([seq(seq([i,j],j=F),i=E)]);
%!s!<p>
% powerlist:=proc(E,n)
%  if n=0 then [[]] else
%  aa:=prodlist(E,powerlist(E,n-1)) ; map(a->[a[1],op(a[2])],aa) fi
%  end proc;
%!s!
%!s!<c>
%Autre methode, on utilise l'ecriture binaire. convert(x,base,2) n'est pas tres
%pratique, car la longueur de la suite rendue n'est pas constante. Ex 1 donne
%[1] 3 donne [1,1]. Astuce, on ajoute [0,0,...,0] avec la taille voulue
%!s!
%!s!<p>
% powerlist2:=proc(E,n)
% local ltmp;
% if n=0 then ltmp:=[[]] ;
% else
% ltmp:=[];
% for i from 0 to nops(E)^n-1 do
% ltmp:=[op(ltmp),[seq(E[j+1],j=( convert(i,base,nops(E))+[0$n]))]];
% od;
% fi;
% ltmp;
%  end proc;
%!s!
% if evalb({op(powerlist([0,1],3))} = {op(powerlist2([0,1],3))}) then print("BON") else print("error IL Y A UN PB") fi;
%!s!<p>
% questionbis:=proc(k)
% S:=sol(k);
% L:=powerlist2([0,1],3);
% f:=(C_0,C_1,C_2)-> S mod 2;
% l:=seq((matrix([[8,4,2,1,0,0,0]])*f(op(A)))[1],A=L);
% sort([l]);
% end proc;
%!s!
% for k from 1 to 7 do print("est il dans",questionbis(k));od;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\exotitre{Codes de Hamming}
\def\F{{\rm I} \! {\rm F}}
\def\P{{\rm I} \! {\rm P}}
Il existe 2 fa\c cons de g\'en\'eraliser l'exemple pr\'ec\'edent: Augmenter le nombre de
lignes de $H$, et changer de corps. On notera $H_{r,q}$ une matrice de  taille
$r\times (q^r-1)$ dont les
colonnes sont constitu\'ees des \'el\'ements de $\P(\F_q^r)$. Le code correspondant
sera encore le noyau de cette matrice.
\qu Expliquer pourquoi on ne travaille pas modulo $4$?

\qu G\'en\'eraliser l'exemple? Etudier une g\'en\'eralisation sur $\F_4$?
\squ Cr\'eer une liste \verb/l/ de tous les \'el\'ements de $\F_4$:
% F4:=GF(2,2,['j','F4']);#pour avoir des notations plus compactes.
%jj:=F4(j);jj^3;
% l:=[0,1,jj,1+jj];
\squ Cr\'eer tous les vecteurs de $\F_4^2$
\squ Donner un vecteur directeur de chaque droite
vectorielle de $\F_4^2$ puis un vecteur directeur de chaque droite
vectorielle de $\F_4^3$. On notera $H4$ la matrice $3\times 21$ associ\'ee. 
% Hb:='Hb';
% Hb:=matrix([[0,seq(1,i=l)],[1,seq(i,i=l)]]);
% f:=(i,k)->if (i=k+1) then 1 else 0 fi;
% T:=matrix(3,2,f);
% A:=transpose(T*Hb);
% op(A);
% !s!<c>
%la generalisation du code sur F4 est le noyau de H4: (on met un eval
%pour applatir les () introduites par les seq, et pour ne pas faire
%raler matrix.
%!s!
% H4:=transpose(matrix(eval([op(A),seq(seq([1,l[u],l[v]],v=1..4),u=1..4)])));
\squ  Trouver\footnote{Sous xcas uniquement. Je ne sais pas le faire
  sous maple!} le noyau de $H4$.
% nullspace(H4); 
% !s!<c>
% -----------------------------------------------Exercice------------------------------
%!s!
\exo Dans cas d'un code non lin\'eaire sans r\`egles particuli\`eres, on n'a pas
d'autre moyen que d'utiliser les algorithmes de tri.
\qu Cr\'eer une fonction distance de hamming entre 2 vecteurs.
% distham:=(u,v)-> add(u[i]<>v[i],i=1..dim(u));
% C:=ranm(2,10,2);
%distham(C[1],C[2]);
\qu On consid\`ere un code (non forc\'ement lin\'eaire) inclus dans $\F_3^{10}$ \`a 200
\'el\'ements.
\squ Cr\'eer un tel code en tirant au hasard les coordonn\'ees de ses \'el\'ements. On
le repr\'esentera par une matrice $200\time 10$ repr\'esentant la liste de tous les
\'el\'ements du code. (Attention \`a ne pas confondre avec un code lin\'eaire o\`u la
matrice 
% C:=ranm(200,10,3);
% v:=randvector(10,3);
\squ Etudier les fonctions de tri. Comment peut on en utiliser pour extraire
d'une liste tous les \'el\'ements a distance 1 d'un vecteur donne?
% !s!<c>
%Rappel, ici la matrice C designe la liste de tous les \'el\'ements et non une base
%du code. 
%!s!
% select(x->distham(x,v)<=1,C); #ceux a distance au plus 1 de v
% select(x->distham(x,C[1])<=1,C); #ceux a distance au plus 1 de C[1]
% select(x->distham(x,C[1])<=1,C); #ceux a distance au plus 2 de v
\newpage
\end{multicols}

\end{document}

