INFO505 : Mathématiques pour l'informatique - Historique des versions

RDavid : /* Approximations asymptotiques */

2007-10-05T21:42:22Z

Approximations asymptotiques

← Version précédente		Version du 5 octobre 2007 à 21:42
Ligne 98 :		Ligne 98 :
	Pour pouvoir simplifier les expressions, il est important de connaître les liens entre les fonctions usuelles : <math>\log</math>, les fonctions linéaires, les polynômes, les exponentielles, les doubles exponentielles...<br/>		Pour pouvoir simplifier les expressions, il est important de connaître les liens entre les fonctions usuelles : <math>\log</math>, les fonctions linéaires, les polynômes, les exponentielles, les doubles exponentielles...<br/>
	Pour <math>n</math> très grand :		Pour <math>n</math> très grand :
	<math> 1 ~~< n^g~~ < \log(n^g) > ~~\log(~~\log(n)) < \log(n) < \log(n^k) < \log(\exp(n)) < n < n^k < \exp((n^g)) < \exp(~~\log~~(n)) < \exp(n) < \exp(n^k) < \exp(\exp(n)) </math> <br/>		<math> 1 < \log(\log(n))< \log(n^g) < \log(n) < \log(n^k) < \log(\exp(n))< n^g < n < n^k < \exp(\log(n)) < \exp((n^g)) < \exp(n) < \exp(n^k) < \exp(\exp(n)) </math> <br/>
	Avec <math>g<1</math> et <math>k>1</math>.		Avec <math>g<1</math> et <math>k>1</math>.

RDavid : /* Approximations asymptotiques */

2007-10-05T21:33:18Z

Approximations asymptotiques

← Version précédente		Version du 5 octobre 2007 à 21:33
Ligne 96 :		Ligne 96 :
	* si <math>f=O(g)</math> et <math>f'=O(g')</math> alors <math>f+ f'=O(\|g\|+\|g'\|)</math>		* si <math>f=O(g)</math> et <math>f'=O(g')</math> alors <math>f+ f'=O(\|g\|+\|g'\|)</math>

	Pour pouvoir simplifier les expressions, il est important de connaître les liens entre les fonctions usuelles : <math>\log</math>, les fonctions linéaires, les polynômes, les exponentielles, les doubles exponentielles...		Pour pouvoir simplifier les expressions, il est important de connaître les liens entre les fonctions usuelles : <math>\log</math>, les fonctions linéaires, les polynômes, les exponentielles, les doubles exponentielles...<br/>
			Pour <math>n</math> très grand :
			<math> 1 < n^g < \log(n^g) > \log(\log(n)) < \log(n) < \log(n^k) < \log(\exp(n)) < n < n^k < \exp((n^g)) < \exp(\log(n)) < \exp(n) < \exp(n^k) < \exp(\exp(n)) </math> <br/>
			Avec <math>g<1</math> et <math>k>1</math>.

	<tt>---À compléter ? C'est vous qui voyez...---</tt>		<tt>---À compléter ? C'est vous qui voyez...---</tt>

Hyvernat : /* Approximations asymptotiques */

2007-09-25T15:10:02Z

Approximations asymptotiques

← Version précédente		Version du 25 septembre 2007 à 15:10
Ligne 82 :		Ligne 82 :
	ça de manière systématique.		ça de manière systématique.

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

	Le but de cette définition est multiple :		Le but de cette définition est multiple :
	* elle cache une borne "au pire"		* elle cache une borne "au pire"
	* elle permet d'identifier des complexités qui ne diffèrent que par une constante multiplicative ("<math>4n</math> et <math>5n</math>, c'est presque la même chose")		* elle permet d'identifier des complexités qui ne diffèrent que par une constante multiplicative ("<math>4n</math> et <math>5n</math>, c'est presque la même chose")
	* elle permet d'ignorer les cas initiaux et autres phénomènes négligeables (c'est le "ultimement" de la définition)		* elle permet d'ignorer les cas initiaux et autres phénomènes négligeables (c'est le "ultimement" de la définition, qui ne sert strictement à rien)
	* elle permet de simplifier les calculs de complexité		* elle permet de simplifier les calculs de complexité

Hyvernat : /* Approximations asymptotiques */

2007-09-25T11:10:58Z

Approximations asymptotiques

← Version précédente		Version du 25 septembre 2007 à 11:10
Ligne 79 :		Ligne 79 :
	===Approximations asymptotiques===		===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.		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 <code>i:=i+1</code> 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
	(Est-ce que <code>i:=i+1</code> 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.		ça de manière systématique.

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

	Le but de cette définition est multiple :		Le but de cette définition est multiple :
Ligne 100 :		Ligne 96 :
	* si <math>f=O(g)</math> et <math>f'=O(g')</math> alors <math>f+ f'=O(\|g\|+\|g'\|)</math>		* si <math>f=O(g)</math> et <math>f'=O(g')</math> alors <math>f+ f'=O(\|g\|+\|g'\|)</math>

	Pour pouvoir simplifier les expressions, il est important de connaître les liens entre les fonctions usuelles : <math>\log</math>, les fonctions		Pour pouvoir simplifier les expressions, il est important de connaître les liens entre les fonctions usuelles : <math>\log</math>, les fonctions linéaires, les polynômes, les exponentielles, les doubles exponentielles...
	linéaires, les polynômes, les exponentielles, les doubles exponentielles...

	<tt>---À compléter ? C'est vous qui voyez...---</tt>		<tt>---À compléter ? C'est vous qui voyez...---</tt>

Hyvernat : /* Les support de TD et TP */

2007-09-25T11:09:46Z

Les support de TD et TP

← Version précédente		Version du 25 septembre 2007 à 11:09
Ligne 134 :		Ligne 134 :
	===Les support de TD et TP===		===Les support de TD et TP===

			* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0708/info505/td1.pdf TD 1]
	<tt>---rien pour le moment---</tt>

Hyvernat : /* Introduction */

2007-09-25T08:09:05Z

Introduction

← Version précédente		Version du 25 septembre 2007 à 08:09
Ligne 14 :		Ligne 14 :
	==Introduction==		==Introduction==

	[http://fr.wikipedia.org/wiki/Dijkstra Edsger Wybe Dijkstra], un grand monsieur de l'informatique a dit ''"Computer Science is not about computers,		[http://fr.wikipedia.org/wiki/Dijkstra 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.
	any more than astronomy is about telescopes."'' Autrement dit l'informatique ne peut pas se réduire à l'étude des ordinateurs.

	Le but de la première partie de ce cours est de regarder comment deux domaines des mathématiques pures sont devenues incontournables dans la société		Le but de la première partie 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 :
	de l'internet et du multimédia :
	* la cryptographie, issue de la théorie des nombres,		* la cryptographie, issue de la théorie des nombres,
	* les codes correcteurs d'erreur, issus des l'algèbre sur les corps finis.		* 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.		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 partie officielle du cours est un cours de mathématiques : le temps alloué ne nous permettra pas de regarder les détails d'implantation ou le test des outils mentionnés dans le cours. Je vous encourage à tester, programmer ou utiliser les concepts mentionnés pour vous les approprier...
	La partie officielle du cours est un cours de mathématiques : le temps alloué ne nous permettra pas de regarder les détails d'implantation ou le test
	des outils mentionnés dans le cours. Je vous encourage à tester, programmer ou utiliser les concepts mentionnés pour vous les approprier...


	==Complexité, approximations asymptotiques==		==Complexité, approximations asymptotiques==

Hyvernat : page initiale

2007-09-24T13:08:05Z

page initiale

Nouvelle page

Ce wiki est un complément de cours pour le cours "info-505, mathématiques pour l'informatique" donné à l'automne 2007. 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 [http://meta.wikimedia.org/wiki/Aide:Contenu 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.)

==Introduction==

[http://fr.wikipedia.org/wiki/Dijkstra 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 la première partie 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 partie officielle du cours est un cours de mathématiques : le temps alloué ne nous permettra pas de regarder les détails d'implantation ou le test
des outils mentionnés dans le cours. 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 (<code>si (n==42) alors ...</code>) ou une affectation (<code>x:=3,1415926536</code>) 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 <code>max</code>
* une opération pour l'initialisation de <code>i</code> à <code>1</code>
* un test pour voir si <code>i==taille</code>
* une opération pour le test <code>max < Tab[1]</code>
* "peut-être" une opération pour l'affectation <code>max:=Tab[1]</code>
* 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 <math>n</math> est la taille du tableau, on obtient entre <math>4n</math> et <math>5n</math> 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 <math>5n</math> 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 <code>i:=i+1</code> 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 <math>f</math> et <math>g</math> sont des fonctions de <math>\mathbb N</math> dans <math>\mathbb N</math>, on dit que <math>f</math>
est un "grand O" de <math>g</math>, et on écrit <math>f = O(g)</math> si le quotient <math>|f(n)|\over|g(n)|</math> est ultimement borné. Plus
précisément, ça veut dire que <math>\exists B \exists n_0,\forall n>n_0,{|f(n)|\over|g(n)|} < B</math>

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 ("<math>4n</math> et <math>5n</math>, c'est presque la même chose")
* elle permet d'ignorer les cas initiaux et autres phénomènes négligeables (c'est le "ultimement" de la définition)
* elle permet de simplifier les calculs de complexité

;Propriétés:
* si <math>f=O(h)</math> et <math>g=O(h)</math> alors <math>\alpha f + \beta g=O(h)</math>
* si <math>f=O(g)</math> et <math>g=O(h)</math> alors <math>f=O(h)</math>
* si <math>f=O(g)</math> et <math>f'=O(g')</math> alors <math>f\times f'=O(g\times g')</math>
* si <math>f=O(g)</math> et <math>f'=O(g')</math> alors <math>f+ f'=O(|g|+|g'|)</math>

Pour pouvoir simplifier les expressions, il est important de connaître les liens entre les fonctions usuelles : <math>\log</math>, les fonctions
linéaires, les polynômes, les exponentielles, les doubles exponentielles...

<tt>---À compléter ? C'est vous qui voyez...---</tt>

===Un exemple===

==Arithmétique : théorie de la cryptographie==

==Algèbre finie : les codes correcteurs d'erreurs==

==Quelques références==

* [http://fr.wikipedia.org/wiki/Cryptographie article wikipedia sur la cryptographie]

* [http://fr.wikipedia.org/wiki/Th%C3%A9orie_des_codes article wikipedia sur les codes correcteurs d'erreur]

==Détails techniques sur le cours==

===Organisation des séances===

Comme il n'y a qu'un seul groupe, le cours sera entièrement en mode cours / TD.

Le cours est divisé en deux parties indépendantes :
* une partie "mathématiques pour l'informatique" (par [[Utilisateur:Hyvernat|Pierre Hyvernat]])
* une partie "algorithmique des graphes" (faite par Françoise Deloule)

===Les support de TD et TP===

<tt>---rien pour le moment---</tt>

INFO505 : Mathématiques pour l'informatique - Historique des versions

RDavid : /* Approximations asymptotiques */

RDavid : /* Approximations asymptotiques */

Hyvernat : /* Approximations asymptotiques */

Hyvernat : /* Approximations asymptotiques */

Hyvernat : /* Les support de TD et TP */

Hyvernat : /* Introduction */

Hyvernat : page initiale

RDavid : /* Approximations asymptotiques */

RDavid : /* Approximations asymptotiques */

Hyvernat : /* Approximations asymptotiques */

Hyvernat : /* Approximations asymptotiques */

Hyvernat : /* Les support de TD et TP */

Hyvernat : /* Introduction */

Hyvernat : page initiale