INFO614 : Mathématiques pour l'informatique

Ce wiki est un complément de cours pour le cours "info-614, mathématiques pour l'informatique". La participation au wiki n'est pas obligatoire mais fortement encouragée. Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Utilisez votre vrai nom...)

Vous pouvez aller voir ce guide pour vous familiariser avec les wikis.

Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)

Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)

Détails techniques sur le cours

Nouvelles

Les nouvelles récentes sont en haut de la liste...

• 13 février 2008 à 14:01 (CET) : cinquième et sixième séance (suite du cours, TD1)
• 5 février 2008 à 10:09 (CET) : quatrième séance (cours : arithmétique, rappels, Euclide et nombres de Bezout, nombres premiers)
• 29 janvier 2008 à 16:32 (CET) : troisième séance (fin TD0 : addition et multiplication des grands entiers, complexité, calcul de puissance)
• 22 janvier 2008 à 10:28 (CET) : deuxième séance (rappels sur les "grands O", suite du TD0)
• 22 janvier 2008 à 10:28 (CET) : première séance (TD0 : récurrences...)
• 14 janvier 2008 à 15:50 (CET) création du wiki

Les support de TD et TP

• le TD 0 : fichier pdf

• le TD 1 : fichier pdf

• le TD 2 : fichier pdf

Compléments de TD et TP

multiplication de grands entiers en C

à rajouter ici

Codes à decrypter

Ib kbteczg, yb ahbygzs gt zig fgme-oeitg f'gbz-fg-veg pzg j'bvbew dzg gi
bdbifniibit yg vbewwgbz, tnzt agyb m'graetb b fnsmes. Yg mg anzahbe wzs
y'hgsdg, pze gtbet tsgw keig, nz jg kzw degitnt giwgvgye fbiw zi osnknif
wnmmgey, pze fzsb igzk hgzsgw. Az dnzt fg ag tgmow-yb, m'gtbit gvgeyyg,
j'gwwbBbe fg mg ygvgs; mbew ag kzt gi vbei. Yg m'gtbew anzahg wzs yg fnw; jg
tsnzvbe mgw dsbw gt mgw jbmdgw bttbahgw b yb tgssg fg y'zi gt fg y'bztsg antg,
gt mgw ahgvgzr bttbahgw fg yb mgmg mbiegsg. Yg tsnzvbe mgmg oyzwegzsw
yecbtzsgw tsgw meiagw pze gitnzsbegit mni ansow, fgozew mgw bewwgyygw jzwpz'b
mgw azewwgw. Yg ig onzvbew pzg sgcbsfgs gi hbzt; yg wnygey anmmgiabet b gtsg
knst ahbzf, gt wb csbifg aybstg dygwwbet mgw Bgzr. Y'gitgifew zi dszet anikzw
bztnzs fg mne, mbew, fbiw yb onwtzsg nz j'gtbew, jg ig onzvbew segi vnes pzg
yg wnygey. Fegitnt jg wgitew sgmzgs pzgypzg ahnwg wzs mb jbmdg cbzahg, gt
agttg ahnwg, bvbiabit fnzagmgit wzs mb onetseig, mnitgs osgwpzg jzwpz'b mni
mgitni. Wzgy kzt mni gtniigmgit ynswpzg j'bogsazw zig ogtetg keczsg fg
asgbtzsg hzmbeig hbztg tnzt bz oyzw fg tsnew onzagw, zi bsa gt zig kygahg b yb
mbei, bvga zi abspznew wzs yg fnw! Y'gi vew gi mgmg tgmow bz mneiw pzbsbitg
bztsgw fg yb mgmg gwogag. Yg mg mew wnzfbei b jgtgs fgw asew we hnssedygw, pzg
tnzw agw ogtetw biembzr wg sgtesgsgit tsbiwew fg ogzs; gt ey B gi gzt mgmg
pzgypzgw-ziw, anmmg jg y'be boosew giwzetg, pze kzsgit fbicgsgzwgmgit dygwwgw
obs ygw ahztgw osgaeoetggw pz'eyw kesgit gi wbztbit fg fgwwzw mni ansow b
tgssg.

et

ymgxj u gbn.g,nfol ea gyngxj gofulegojycjgymgmfgc uxbyngxjbxgnfgu bmfnbtl ghbn
cfslegefstxgyx?gxjymgrs mxyfnpgojycjgbxgiyumxgmyajxghyajxgnfxgm  hgeyiiycslxp
ymgu bll.gfn gfigxj ghfmxgeyiiycslxgxjbxgcbngt gbm, evgoj ngo gjbw gu blyk e
xj gftmxbcl mgyngxj gob.gfigbgmxubyajxifuobuegbnegcfniye nxgbnmo upgo gmjbll
t go llglbsncj egfngxj gmxse.gfigqjylfmfqj.--ifugqjylfmfqj.gymgh u l.gxj
bxx hqxgxfgbnmo ugmscjgslxyhbx grs mxyfnmpgnfxgcbu l mml.gbnegefahbxycbll.pgbm
o gefgyngfueynbu.glyi gbneg w ngyngxj gmcy nc mpgtsxgcuyxycbll.pgbix u
 zqlfuynagbllgxjbxghb, mgmscjgrs mxyfnmgqskklynapgbnegbix ugu blykynagbllgxj
wbas n mmgbnegcfnismyfngxjbxgsne uly gfsugfueynbu.gye bmv

yngebyl.glyi pgo gbmmsh gbmgc uxbynghbn.gxjynamgojycjpgfngbgclfm ugmcusxyn.p
bu gifsnegxfgt gmfgisllgfigbqqbu nxgcfnxubeycxyfnmgxjbxgfnl.gbgau bxgbhfsnxgfi
xjfsajxg nbtl mgsmgxfg,nfogojbxgyxgymgxjbxgo gu bll.ghb.gt ly w vgyngxj
m bucjgifugc uxbynx.pgyxgymgnbxsublgxfgt ayngoyxjgfsugqu m nxg zq uy nc mpgbne
yngmfh gm nm pgnfgefstxpg,nfol ea gymgxfgt ge uyw egiufhgxj hvgtsxgbn.
mxbx h nxgbmgxfgojbxgyxgymgxjbxgfsugyhh eybx g zq uy nc mghb, gsmg,nfogymgw u.
ly, l.gxfgt goufnavgyxgm  hmgxfgh gxjbxgygbhgnfogmyxxynagyngbgcjbyupgbxgb
xbtl gfigbgc uxbyngmjbq pgfngojycjgygm  gmj  xmgfigqbq ugoyxjgouyxynagfu
quynxvgt.gxsunynagh.gj begygm  gfsxgfigxj goynefogtsyleynamgbnegclfsemgbnegxj
msnvgygt ly w gxjbxgxj gmsngymgbtfsxgnyn x.-xju  ghyllyfnghyl mgiufhgxj
 buxj;gxjbxgyxgymgbgjfxgalft ghbn.gxyh mgtyaa ugxjbngxj g buxj;gxjbxpgfoynagxf
xj g buxj'mgufxbxyfnpgyxguym mg w u.ghfunynapgbnegoyllgcfnxyns gxfgefgmfgifu
bngyne iynyx gxyh gyngxj gisxsu vgygt ly w gxjbxpgyigbn.gfxj ugnfuhblgq umfn
cfh mgynxfgh.guffhpgj goyllgm  gxj gmbh gcjbyumgbnegxbtl mgbnegtff,mgbne
qbq umgbmgygm  pgbnegxjbxgxj gxbtl gojycjgygm  gymgxj gmbh gbmgxj gxbtl gojycj
ygi  lgqu mmynagbabynmxgh.gbuhvgbllgxjymgm  hmgxfgt gmfg wye nxgbmgxfgt
jbuel.gofuxjgmxbxynapg zc qxgyngbnmo ugxfgbghbngojfgefstxmgoj xj ugyg,nfo
bn.xjynavgg. xgbllgxjymghb.gt gu bmfnbtl.gefstx epgbnegbllgfigyxgu rsyu mghscj
cbu islgeymcsmmyfngt ifu go gcbngt gmsu gxjbxgo gjbw gmxbx egyxgyngbgifuhgxjbx
ymgojfll.gxus

utilitaires

La commande tr permet de changer des caracteres. Par exemple,

tr "abcdefghijklmnopqrstuvwxyz" "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

agit comme un filtre que passe toutes les lettres en majuscules

On obtient l'encodage "rot13" avec

tr "abcdefghijklmnopqrstuvwxyz" "nopqrstuvwxyzabcdefghijklm"

Le script perl suivant permet de compter les frequences de chaque symbole dans un fichier texte

#!/usr/bin/perl
while(<>) {
 chomp;
 foreach $lettre (split //) {$H{$lettre}++;}
}
foreach $lettre (sort(keys %H)) { print "\"$lettre\" :: $H{$lettre}\n"; }

---

---

Introduction

Edsger Wybe Dijkstra, un grand monsieur de l'informatique a dit "Computer Science is not about computers, any more than astronomy is about telescopes." Autrement dit l'informatique ne peut pas se réduire à l'étude des ordinateurs.

Le but de de ce cours est de regarder comment deux domaines des mathématiques pures sont devenues incontournables dans la société de l'internet et du multimédia :

• la cryptographie, issue de la théorie des nombres,
• les codes correcteurs d'erreur, issus des l'algèbre sur les corps finis.

Les technologies résultantes sont utilisées lors de chaque transaction électronique, pour l'échange de mails ou à chaque fois que vous écoutez un CD. La plus grosse partie du cours est un cours de mathématiques. Si le temps le permet, nous déménageront une ou deux séances de TP en salle machine pour appliquer le cours, mais nous n'aurons pas suffisamment de temps pour regarder les détails d'implantation. Je vous encourage à tester, programmer ou utiliser les concepts mentionnés pour vous les approprier...

Complexité, approximations asymptotiques

La notion de complexité d'un programme est fondamentale pour pouvoir évaluer l'intérêt pratique d'un programme. La complexité observée lors de test ou de benchmark est parfois suffisante mais ne prend en compte que certaines exécutions (celles qui sons testées par les tests). Il est souvent nécessaire de se faire une idée de la complexité théorique d'un programme pour pouvoir prédire son temps d'exécution (ou ses besoins en ressources) pour les exécutions futures.

Première approche de la complexité

Tout d'abord, nous ne nous intéresserons qu'à la complexité en temps, et (presque) jamais à la complexité en espace. Il ne faut pas en déduire que seule la complexité en temps est importante !

L'idée de base est de compter en combien de temps va s'exécuter un programme donné, mais la question elle même est mal posée :

• comment compte-t'on ?
• et surtout, que compte-t'on ?

Chronométrer le temps d'exécution ne permet pas de faire d'analyse fine, et ne permet pas facilement de prédire le comportement général de votre programme. Comme le temps dépend beaucoup du processeur utilisé, l'idéal serait de pouvoir compter le nombre de cycle nécessaires au programme. Cela est généralement impossible car cela dépend du type de processeur utilisé ainsi que des optimisations faites par le compilateur.

La complexité en temps d'un algorithme, c'est une estimation du nombre d'opérations atomiques effectuées par cette algorithme avant qu'il ne termine. Cette estimation doit être donnée comme une fonction dépendant de la taille de l'entrée sur laquelle est lancé l'algorithme.

La notion d'opération atomique est assez intuitive : c'est une opération algorithmique qui n'est pas divisible en sous-opérations. En première approximation, une opération est atomique si elle ne porte que sur des objets de type entier, caractère ou booléen. (Les types codés sur un ou deux mots). Un test (si (n==42) alors ...) ou une affectation (x:=3,1415926536) sont des opérations atomiques ; mais l'initialisation d'un tableau n'est pas atomique. (Il y a autant d'opérations qu'il y a d'éléments dans le tableau...)

Exemple : la recherche du maximum dans un tableau d'entiers positifs peut se faire comme suit

max := 0
pour i:=1 à taille
faire
  si (max < Tab[i])
  alors max:=Tab[i]
finfaire
affiche("Le maximum est %i.\n",max)

Le nombre d'opérations est le suivant :

• une opération pour l'initialisation de max
• une opération pour l'initialisation de i à 1
• un test pour voir si i==taille
• une opération pour le test max < Tab[1]
• "peut-être" une opération pour l'affectation max:=Tab[1]
• puis, pour chaque élément suivant du tableau :
  • un incrément du compteur
  • une affectation du compteur
  • un test pour voir si on a atteint la fin du tableau
  • un test
  • peut-être une affectation

Au total, si $n$ est la taille du tableau, on obtient entre $4n$ et $5n$ opérations. De manière générale, on s'intéresse surtout au pire cas ; on dira donc que cet algorithme s'exécute en "au plus $5n$ opérations".

Approximations asymptotiques

On ne peut habituellement pas compter de manière aussi précise le nombre d'opérations ; et ça n'a pas toujours du sens de vouloir être trop précis. (Est-ce que i:=i+1 correspond à une ou deux opérations atomiques ?) Nous allons donc utiliser les approximations asymptotique pour compter la complexité... Le but sera alors de distinguer les algorithmes "rapides", "lents", ou "infaisables". La notion de "grand O" permet de faire ça de manière systématique.

définition

si $f$ et $g$ sont des fonctions de $\mathbb {N}$ dans $\mathbb {N}$, on dit que $f$ est un "grand O" de $g$, et on écrit $f=O(g)$ si le quotient $|f(n)| \over |g(n)|$ est borné. Plus précisément, ça veut dire que $\exists B,\forall n,{|f(n)| \over |g(n)|}<B$

Le but de cette définition est multiple :

• elle cache une borne "au pire"
• elle permet d'identifier des complexités qui ne diffèrent que par une constante multiplicative ("$4n$ et $5n$, c'est presque la même chose")
• elle permet d'ignorer les cas initiaux et autres phénomènes négligeables
• elle permet de simplifier les calculs de complexité

Propriétés

• si $f=O(h)$ et $g=O(h)$ alors $\alpha f+\beta g=O(h)$
• si $f=O(g)$ et $g=O(h)$ alors $f=O(h)$
• si $f=O(g)$ et $f'=O(g')$ alors $f\times f'=O(g\times g')$
• si $f=O(g)$ et $f'=O(g')$ alors $f+f'=O(|g|+|g'|)$

Pour pouvoir simplifier les expressions, il est important de connaître les liens entre les fonctions usuelles : $\log$, les fonctions linéaires, les polynômes, les exponentielles, les doubles exponentielles...
Pour $n$ très grand : $1<\log(\log(n))<n^{\epsilon }<n<n^{c}<n^{\log(n)}<c^{n}<n^{n}<c^{(c^{n})}$
Avec $0<\epsilon <1$ et $c>1$.

---À compléter ? C'est vous qui voyez...---

Un exemple

---???---

Arithménique

Rappels, notation

pgcd

division Euclidienne, definition du modulo

nombre premier

Algorithme d'Euclide, nombres de Bezout

algo simple

calcul des nombres de Bezout

pgcd + nombres de Bezout  permet une verification du résultat

Nombres premiers

factorisation unique

infinité de nombres premiers

test de primalité probabiliste efficaces (pas de détails)

Le résultat suivant est connu sous le nom du "théorème fondamental des nombres premiers" ; sa preuve est assez difficile. Ce théorème donne un equivalent pour la proportion de nombres premiers inférieurs à $n$ : $\pi (n)\sim {\frac {n}{\ln(n)}}$, où $\pi (n)\!$ est le nombre de nombres premiers inférieurs à $n$.

Calcul modulo

définition, notation $a\equiv b{\pmod {m}}$

propriétés élémentaires

Propriété

si $a$ est premier avec $m$, alors on peut diviser par $a$ modulo $m$ en multipliant par l'inverse de $a$ modulo $m$.

Pour calculer cet inverse, on utilise une relation de Bezout $x\times m+y\times a=1\!$ ; et on a forcément $a\times y\equiv 1{\pmod {m}}\!$.

Cryptographie

Vagebqhpgvba

...

code de César, rot13 et autres permutations de lettres

Un système parfait : bloc note à usage unique

...

Un systeme symétrique : DES

principe des portes de Feistel

codage et decodage

Échange de clés de Diffie-Hellman

...

pb des attaque "man in the middle", authentification

Quelques références

• article wikipedia sur la cryptographie

• article wikipedia sur les codes correcteurs d'erreur