INFO204 : science informatique - Historique des versions

Hyvernat : /* Administration */

2011-01-23T21:44:26Z

Administration

← Version précédente		Version du 23 janvier 2011 à 21:44
Ligne 20 :		Ligne 20 :

	Ces notes serviront de première note pour la moyenne finale. (Il y aura également deux contrôles « traditionnels ».)		Ces notes serviront de première note pour la moyenne finale. (Il y aura également deux contrôles « traditionnels ».)


	===Cours===

	* cours 1 (semaine 2) : la base 2
	* TD 1 (semaine 3) : fin du cours, début du TD 1 (exercice 1, questions 1, 2, 4 et 5, début de l'exercice 3)
	* cours + TD (semaine 4) : TD1, cours (base héxadecimale, représentation complément à 1)
	* TD (semaine 5) : interro 1, cours (représentation des flottants, code ASCII)
	* cours (semaine 5) : cours (ASCII, encodage), TD 2
	* TD (semaine 9) : fin du TD2, quelques mots sur l'encodage des images (PNM)

	===Supports de TD / TP===

	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/td1.pdf TD1, format pdf]
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/td2.pdf TD2, format pdf]
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/td3.pdf TD3, format pdf]
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/td4.pdf TD4, format pdf]
	----
	----
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/tp1.html TP1]
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/tp2.html TP2], ainsi que le lien vers les [[clés publiques]] de tout le monde
	----
	----
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/controle1.pdf CC1 (avec correction), format pdf]

	== Introduction ==		== Introduction ==

Deamons : /* Les nombres négatifs */

2010-05-18T12:42:53Z

Les nombres négatifs

← Version précédente		Version du 18 mai 2010 à 12:42
Ligne 278 :		Ligne 278 :

	Une méthode pratique de tête :		Une méthode pratique de tête :
	Pour convertir un nombre en son ~~commplément~~ à deux, il faut garder tout les "0" de la droite jusqu'au premier 1(on le garde aussi), puis on inverse tous les suivants.		Pour convertir un nombre en son complément à deux, il faut garder tout les "0" de la droite jusqu'au premier 1(on le garde aussi), puis on inverse tous les suivants.
	Exemple :		Exemple :
	* 56 : <tt>0000000000000000000000000011<b>1000</b></tt>,		* 56 : <tt>0000000000000000000000000011<b>1000</b></tt>,

Deamons : /* Les nombres négatifs */

2010-05-18T12:42:28Z

Les nombres négatifs

← Version précédente		Version du 18 mai 2010 à 12:42
Ligne 266 :		Ligne 266 :

	* on prend sa valeur absolue en base 2,		* on prend sa valeur absolue en base 2,
	* on ~~ajoute~~ 1,		* on inverse tous les bits,
	* on ~~inverse~~ ~~tous les bits~~.		* on ajoute 1.

	Par exemple, pour représenter -43 :		Par exemple, pour représenter -43 :

	* 43 : <tt>00000000000000000000000000101011</tt>,		* 43 : <tt>00000000000000000000000000101011</tt>,
	* on ~~ajoute~~ 1 : <tt>~~00000000000000000000000000101100~~</tt>,		* on inverse tous les bits : <tt>111111111111111111111111111010100</tt>,
	* on ~~inverse~~ ~~tous les bits~~ : <tt>~~11111111111111111111111111010011~~</tt>.		* on ajoute 1 : <tt>111111111111111111111111111010101</tt>.

	Avec ce codage, 0 n'a qu'une seule représentation. <tt>11111111111111111111111111111111</tt> représente l'entier -1.		Avec ce codage, 0 n'a qu'une seule représentation. <tt>11111111111111111111111111111111</tt> représente l'entier -1.

			Une méthode pratique de tête :
			Pour convertir un nombre en son commplément à deux, il faut garder tout les "0" de la droite jusqu'au premier 1(on le garde aussi), puis on inverse tous les suivants.
			Exemple :
			* 56 : <tt>0000000000000000000000000011<b>1000</b></tt>,
			* -56 : <tt>1111111111111111111111111100<b>1000</b></tt>,


	Dans tous les cas, pour savoir si un nombre est positif ou négatif, il suffit de regarder son bit de poids fort :		Dans tous les cas, pour savoir si un nombre est positif ou négatif, il suffit de regarder son bit de poids fort :

Hyvernat : /* Supports de TD / TP */

2010-05-06T19:08:53Z

Supports de TD / TP

← Version précédente		Version du 6 mai 2010 à 19:08
Ligne 40 :		Ligne 40 :
	----		----
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/tp1.html TP1]		* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/tp1.html TP1]
			* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/tp2.html TP2], ainsi que le lien vers les [[clés publiques]] de tout le monde
	----		----
	----		----

Hyvernat : /* Supports de TD / TP */

2010-05-05T20:14:10Z

Supports de TD / TP

← Version précédente		Version du 5 mai 2010 à 20:14
Ligne 35 :		Ligne 35 :
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/td1.pdf TD1, format pdf]		* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/td1.pdf TD1, format pdf]
	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/td2.pdf TD2, format pdf]		* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/td2.pdf TD2, format pdf]
			* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/td3.pdf TD3, format pdf]

			* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/td4.pdf TD4, format pdf]
	----		----
	----		----
			* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/tp1.html TP1]
			----
			----
			* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/controle1.pdf CC1 (avec correction), format pdf]

	== Introduction ==		== Introduction ==

Hyvernat : /* Introduction à la complexité */

2010-03-08T08:20:05Z

Introduction à la complexité

← Version précédente		Version du 8 mars 2010 à 08:20
Ligne 329 :		Ligne 329 :

	== Introduction à la complexité ==		== Introduction à la complexité ==

			==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 nous intéresserons surtout à 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...)

			<u>Exemple :</u> 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"''.

			Le code Python correspondant serait :

			def maximum(t):
			"""renvoie le maximum d'un tableau t d'entiers positifs."""
			max = 0
			for e in t:
			if e > max:
			max = e
			return(max)

			Le nombre d'operations est similaire, mais il n'est pas facile de savoir exactement combien d'etapes sont effectué lors de l'affectation des valeurs du tableau à <tt>e</tt>...



			===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 borné. Plus précisément, ça veut dire que <math>\exists B,\forall n, {\|f(n)\|\over\|g(n)\|} < B</math> c'est à dire, quand <math>f</math> et <math>g</math> sont positives : <math>\exists B,\forall n, f(n) < B \times g(n)</math>

			Le but de cette définition est multiple :
			* 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
			* 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...<br/>
			Pour <math>n</math> très grand :

			<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>.

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

			===Un exemple===

Hyvernat : /* Les caractères et tout le reste... */

2010-03-08T07:55:41Z

Les caractères et tout le reste...

← Version précédente		Version du 8 mars 2010 à 07:55
Ligne 326 :		Ligne 326 :

	Ceci permet de représenter 2<sup>7</sup> + 2<sup>5+6</sup> + 2<sup>4+6+6</sup> + 2<sup>3+6+6+6</sup> = 2164864 caractères.		Ceci permet de représenter 2<sup>7</sup> + 2<sup>5+6</sup> + 2<sup>4+6+6</sup> + 2<sup>3+6+6+6</sup> = 2164864 caractères.


			== Introduction à la complexité ==

Hyvernat : /* Supports de TD / TP */

2010-03-01T12:26:28Z

Supports de TD / TP

← Version précédente		Version du 1 mars 2010 à 12:26
Ligne 34 :		Ligne 34 :

	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/td1.pdf TD1, format pdf]		* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/td1.pdf TD1, format pdf]
			* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0910/info204/td2.pdf TD2, format pdf]

	----		----

Hyvernat : /* Cours */

2010-03-01T12:25:20Z

Cours

← Version précédente		Version du 1 mars 2010 à 12:25
Ligne 29 :		Ligne 29 :
	* TD (semaine 5) : interro 1, cours (représentation des flottants, code ASCII)		* TD (semaine 5) : interro 1, cours (représentation des flottants, code ASCII)
	* cours (semaine 5) : cours (ASCII, encodage), TD 2		* cours (semaine 5) : cours (ASCII, encodage), TD 2
			* TD (semaine 9) : fin du TD2, quelques mots sur l'encodage des images (PNM)

	===Supports de TD / TP===		===Supports de TD / TP===

Hyvernat : /* Les caractères et tout le reste... */

2010-02-04T21:36:10Z

Les caractères et tout le reste...

← Version précédente		Version du 4 février 2010 à 21:36
Ligne 315 :		Ligne 315 :

	L'unicode contient tous les accents possibles, ainsi que les caractères asiatiques (par exemple), mais il nécessite 32 bits, ce qui est assez inefficace pour les textes européens. On utilise donc un codage spécifique (UTF-8) qui utilise 8 bits pour les caractères courants, 16 bits pour les caractères moins courants, 24 bits pour les encore moins courants et 32 bit pour ce qui reste.		L'unicode contient tous les accents possibles, ainsi que les caractères asiatiques (par exemple), mais il nécessite 32 bits, ce qui est assez inefficace pour les textes européens. On utilise donc un codage spécifique (UTF-8) qui utilise 8 bits pour les caractères courants, 16 bits pour les caractères moins courants, 24 bits pour les encore moins courants et 32 bit pour ce qui reste.

			Pour reconnaître les octets, on utilise :

			* caractère sur un octet (ASCII) : <tt>0bbbbbbb</tt>,
			* caractère sur deux octets : <tt>110bbbbb 10bbbbbb</tt>,
			* caractère sur trois octets : <tt>1110bbbb 10bbbbbb 10bbbbbb</tt>,
			* caractère sur quatre octets : <tt>11110bbb 10bbbbbb 10bbbbbb 10bbbbbb</tt>.

			Ceci permet de représenter 2<sup>7</sup> + 2<sup>5+6</sup> + 2<sup>4+6+6</sup> + 2<sup>3+6+6+6</sup> = 2164864 caractères.

INFO204 : science informatique - Historique des versions

Hyvernat : /* Administration */

Deamons : /* Les nombres négatifs */

Deamons : /* Les nombres négatifs */

Hyvernat : /* Supports de TD / TP */

Hyvernat : /* Supports de TD / TP */

Hyvernat : /* Introduction à la complexité */

Hyvernat : /* Les caractères et tout le reste... */

Hyvernat : /* Supports de TD / TP */

Hyvernat : /* Cours */

Hyvernat : /* Les caractères et tout le reste... */

Hyvernat : /* Administration */

Deamons : /* Les nombres négatifs */

Deamons : /* Les nombres négatifs */

Hyvernat : /* Supports de TD / TP */

Hyvernat : /* Supports de TD / TP */

Hyvernat : /* Introduction à la complexité */

Hyvernat : /* Les caractères et tout le reste... */

Hyvernat : /* Supports de TD / TP */

Hyvernat : /* Cours */

Hyvernat : /* Les caractères et tout le reste... */