ACTIONS
Les perspectives ...
tous les log ic ie ls du mo nde : c'est
un e mac hin e univ e rse ll e, comm e
d éfinie par la th èse de Churc hTurin g (vo ir a rti c le e n page 40 ).
Ce rés ultat implique pa r e xe mpl e
que toutes les « inte lli ge nces mécaniques» (ordin ate ur, robo t, etc.) so nt
qu a i itativ e me nt équiv a le ntes : e ll es
se ront ju ste plu s o u mo in s ra pides o u
pe rformantes.
Un autre rés ultat mo ntre le li en entre
la sc ience informatique et de grand s
concepts. C'est la théori e algorith -
mique de ! ' inform ati on. La co mplex ité d ' un message e n te rme d ' info rmatio n (au sens où " bl ablabl a .. . " mê me
répété une infinité de fo is contie nt
mo in s d ' info rm atio n qu ' une page de
longueur fini e) se défi nit par « la longueur du plus petit programme écrit
a vec une machine uni verselle qui
génère le message en question ». Bref,
la long ue ur du plu s petit programme
indique la complex ité du message. Il
n'est pas du tout év ide nt, ma is c'est le
cas, que cette dé finition est pertine nte,
bien fond ée, ne dé pend de la machine
cho isie qu 'à une co nstante près, et
offre une form ali satio n profonde de
cette idée de « compl exité ».
De même la notion de suite aléato ire
prend un visage nouveau : ce n'est plu s
une suite « générée par le hasard » (au
sens préc is de la théorie des probabili -
tés), mais une suite qui ne peut être ...
générée par un programme de taill e
fini e (une suite « imprédictible » en
INTE R NAUG R A PH I E
• https://fr.wikipedia.org/w iki/Sciences_du_ numérique
• https://www.allistene.fr
• http://www. inria.fr/conte nt/downl oad/2437 l /605690/
version/5/fi le/Plan-strategique-Objectif-2020. pdf
que lque sorte). Nous voil à donc devant
une vision nouve lle de cette noti on
d 'aléa.
Au fur et à mesure que cette sc ience se
po pul ari sera , la pensée info rmatique
enrichi ra les connaissances humaines
et é larg ira notre vision sur ces sujets.
La relation auec les mathématiques
La modé li sation et la réso lution de
no mbre ux pro bl è mes re ncontrés en
info rmatique offrent des dé fi s nouveaux pour les mathématiques pour
les deux di sciplines info rmatiques et
mathématiques.
Il est en effet rare que les techniques
mathématiques usuelles pui ssent être
utili sées « clés en main ». Les objets
manipulés tout comme les types de
réponses attendues (par exemple en
termes d 'effecti vité) appara issent souvent comme non class iques aux mathématic iens.
L' info rmatique théorique intervient,
entre autres, dans les domaines sui -
va nts : calcul fo rme l, arithmétique des
ordin ateurs, géométrie pour l' image,
algorithmique (du tex te, sur les arbres ,
graphes), automates, systèmes dy namiques, ana lyse d ' algorithmes, complex ité du ca lcul , info rmatique quantiqu e, log ique, bases de données,
preuves de programmes, vérifi cation
log icie ll e et matéri elle, codes correcteurs, cry ptographie .. .
Tout un programme !
ARTI CLE COLLECTIF COORDONNÉ
PAR THI ERRY VI ÉV ILL E
ET CHRISTIN E FROIDEVAUX
Tangente Hors-série n°52. Mathématiques & informatique
Les perspectives ...
tous les log ic ie ls du mo nde : c'est
un e mac hin e univ e rse ll e, comm e
d éfinie par la th èse de Churc hTurin g (vo ir a rti c le e n page 40 ).
Ce rés ultat implique pa r e xe mpl e
que toutes les « inte lli ge nces mécaniques» (ordin ate ur, robo t, etc.) so nt
qu a i itativ e me nt équiv a le ntes : e ll es
se ront ju ste plu s o u mo in s ra pides o u
pe rformantes.
Un autre rés ultat mo ntre le li en entre
la sc ience informatique et de grand s
concepts. C'est la théori e algorith -
mique de ! ' inform ati on. La co mplex ité d ' un message e n te rme d ' info rmatio n (au sens où " bl ablabl a .. . " mê me
répété une infinité de fo is contie nt
mo in s d ' info rm atio n qu ' une page de
longueur fini e) se défi nit par « la longueur du plus petit programme écrit
a vec une machine uni verselle qui
génère le message en question ». Bref,
la long ue ur du plu s petit programme
indique la complex ité du message. Il
n'est pas du tout év ide nt, ma is c'est le
cas, que cette dé finition est pertine nte,
bien fond ée, ne dé pend de la machine
cho isie qu 'à une co nstante près, et
offre une form ali satio n profonde de
cette idée de « compl exité ».
De même la notion de suite aléato ire
prend un visage nouveau : ce n'est plu s
une suite « générée par le hasard » (au
sens préc is de la théorie des probabili -
tés), mais une suite qui ne peut être ...
générée par un programme de taill e
fini e (une suite « imprédictible » en
INTE R NAUG R A PH I E
• https://fr.wikipedia.org/w iki/Sciences_du_ numérique
• https://www.allistene.fr
• http://www. inria.fr/conte nt/downl oad/2437 l /605690/
version/5/fi le/Plan-strategique-Objectif-2020. pdf
que lque sorte). Nous voil à donc devant
une vision nouve lle de cette noti on
d 'aléa.
Au fur et à mesure que cette sc ience se
po pul ari sera , la pensée info rmatique
enrichi ra les connaissances humaines
et é larg ira notre vision sur ces sujets.
La relation auec les mathématiques
La modé li sation et la réso lution de
no mbre ux pro bl è mes re ncontrés en
info rmatique offrent des dé fi s nouveaux pour les mathématiques pour
les deux di sciplines info rmatiques et
mathématiques.
Il est en effet rare que les techniques
mathématiques usuelles pui ssent être
utili sées « clés en main ». Les objets
manipulés tout comme les types de
réponses attendues (par exemple en
termes d 'effecti vité) appara issent souvent comme non class iques aux mathématic iens.
L' info rmatique théorique intervient,
entre autres, dans les domaines sui -
va nts : calcul fo rme l, arithmétique des
ordin ateurs, géométrie pour l' image,
algorithmique (du tex te, sur les arbres ,
graphes), automates, systèmes dy namiques, ana lyse d ' algorithmes, complex ité du ca lcul , info rmatique quantiqu e, log ique, bases de données,
preuves de programmes, vérifi cation
log icie ll e et matéri elle, codes correcteurs, cry ptographie .. .
Tout un programme !
ARTI CLE COLLECTIF COORDONNÉ
PAR THI ERRY VI ÉV ILL E
ET CHRISTIN E FROIDEVAUX
Tangente Hors-série n°52. Mathématiques & informatique