INFO719 : rappels d'algorithmique et programmation C - Historique des versions

Hyvernat : /* Code C de l'examen */

2009-01-09T19:03:33Z

Code C de l'examen

← Version précédente		Version du 9 janvier 2009 à 19:03
Ligne 351 :		Ligne 351 :
	==Code C de l'examen==		==Code C de l'examen==

			Voila le code C des exercices de programmation de l'examen. Reportez-vous au sujet et à la correction pour des détails supplémentaires. Ce qui suit est un fichier C complet...


			#include <stdio.h>

			/* Recherche dans un tableau trié */
			int cherche(int T[], int t, int e)
			{
			int debut = 0; // le début du sous-tableau qui nous intéresse
			int fin = t; // la fin du sous-tableau qui nous intéresse
			int milieu; // le milieu du sous-tableau qui nous intéresse
			int indice = -1; // l'indice de l'élément que l'on cherche

			// on regarde au milieu du tableau, et si on trouve l'élément e, on
			// s'arrête.
			// Sinon, on regarde dans la partie (droite ou gauche) pertinente.
			// On s'arrête quand on obtient un tableau vide.

			while ((indice == -1) && (fin - debut) > 1) {
			milieu = debut + (fin - debut) / 2;
			if (e == T[milieu]) {
			indice = milieu;
			} else {
			if (e < T[milieu]) {
			fin = milieu;
			} else {
			debut = milieu;
			}
			}
			}
			return (indice);
			}


			/* Calcul d'une approximation du sinus avec le developpement en série entière */
			double devSinus(float x, int n)
			{
			double numerateur = (double)x; // la valeur de (-1)^n x^(2n+1)
			double X = (double)(-x * x);
			long int fact = 1; // la valeur de (2n+1)!
			int i;
			double resultat = x;

			for (i = 1; i < n + 1; i = i + 1) {
			numerateur = numerateur * X;
			fact = fact * (2 * i) * (2 * i + 1);
			resultat = resultat + (numerateur / fact);
			}

			return (resultat);
			}


			/* La fonction résidu très simple, mais il faut connaitre la propriété
			* mathématique associée...
			*/
			int residuSimple(int n, int b)
			{
			int residu = n % (b - 1);
			if (residu == 0) {
			residu = b - 1;
			}
			return (residu);
			}

			/* le résidu un peu plus simple que dans l'enoncé : */
			int residuMoinsSimple(int n, int b)
			{
			int residu = n;
			while (residu >= b) {
			residu = (residu / b) + (residu % b);
			}
			return (residu);
			}


			/* le résidu comme dans l'enoncé : */

			// (1) La fonction qui fait la somme des chiffres (en base n) du nombre n
			int residuUneEtape(int n, int b)
			{
			int residuPartiel = 0;

			while (n > 0) {
			residuPartiel = residuPartiel + (n % b);
			n = n / b;
			}
			return (residuPartiel);
			}

			// (2) La fonction résidu
			int residuEtapes(int n, int b)
			{
			int residu = n;
			while (residu >= b) {
			residu = residuUneEtape(residu, b);
			}
			return (residu);
			}


			/* fonction principale pour tester les fonctions... */
			int main()
			{

			/* // Pour tester la fonction cherche...
			int T[100000];
			int i;
			for (i = 0; i < 100000; i++)
			T[i] = 2 * i;

			int e;
			int indice;
			printf("Entrez un nombre : \n");
			scanf("%i", &e);
			indice = cherche(T, 100000, e);
			if (indice != -1)
			printf("%i apparait dans le tableau en position %i.\n", e, indice);
			else
			printf("%i n'apparait pas dans le tableau.\n", e);
			*/


			int n, b;
			printf("Entrez un nombre : \n ");
			scanf("%i", &n);

			printf("Entrez une base : \n ");
			scanf("%i", &b);

			printf("Calcul du résidu de %i en base %i :\n", n, b);

			printf(" - méthode simple : %i\n", residuSimple(n, b));
			printf(" - méthode moins simple : %i\n", residuSimple(n, b));
			printf(" - méthode par étapes : %i\n", residuSimple(n, b));

			return (0);
			}

	=Introduction=		=Introduction=

Hyvernat : /* Code C de l'examen */

2009-01-09T19:01:13Z

Code C de l'examen

← Version précédente		Version du 9 janvier 2009 à 19:01
Ligne 348 :		Ligne 348 :
	----		----
	----		----

			==Code C de l'examen==


	=Introduction=		=Introduction=
Ligne 395 :		Ligne 398 :
	* le Manchester Mark I (1948) et l'[http://fr.wikipedia.org/wiki/EDVAC EDVAC] (1951) améliorent l'ENIAC et commencent à ressembler à des ordinateurs modernes		* le Manchester Mark I (1948) et l'[http://fr.wikipedia.org/wiki/EDVAC EDVAC] (1951) améliorent l'ENIAC et commencent à ressembler à des ordinateurs modernes
	* l'[http://fr.wikipedia.org/wiki/UNIVAC_I UNIVAC I] est le premier ordinateur commercialisé, en 1951.		* l'[http://fr.wikipedia.org/wiki/UNIVAC_I UNIVAC I] est le premier ordinateur commercialisé, en 1951.




	=Rappels d'algorithmique=		=Rappels d'algorithmique=

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

2009-01-09T19:00:05Z

Les support de TD et TP

← Version précédente		Version du 9 janvier 2009 à 19:00
Ligne 52 :		Ligne 52 :

	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info719/TP/index.html le TP2 est seulement disponible online.]		* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info719/TP/index.html le TP2 est seulement disponible online.]

			* '''[http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info719/examen.pdf l'examen corrigé]''' (voir aussi plus bas pour le code C...)

	==Correction TDP0==		==Correction TDP0==

Hyvernat : /* Organisation des séances */

2008-11-18T10:39:48Z

Organisation des séances

← Version précédente		Version du 18 novembre 2008 à 10:39
Ligne 34 :		Ligne 34 :
	* huitième séance (4/11/2008) : cours de C, structures et pointeur,		* huitième séance (4/11/2008) : cours de C, structures et pointeur,
	* TP2 (5/11/2008) : le jeu de la vie,		* TP2 (5/11/2008) : le jeu de la vie,
			* neuvième séance (18/11/2008) : tableaux et pointeurs, processus de compilation,

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

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

2008-11-05T09:53:14Z

Les support de TD et TP

← Version précédente		Version du 5 novembre 2008 à 09:53
Ligne 49 :		Ligne 49 :

	* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info719/td2.pdf TD2]		* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info719/td2.pdf TD2]

			* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info719/TP/index.html le TP2 est seulement disponible online.]

	==Correction TDP0==		==Correction TDP0==

Hyvernat : /* Organisation des séances */

2008-11-05T09:51:56Z

Organisation des séances

← Version précédente		Version du 5 novembre 2008 à 09:51
Ligne 28 :		Ligne 28 :
	* troisième séance (23/09/2008) : TP0 (reprise du TD1 en salle machines),		* troisième séance (23/09/2008) : TP0 (reprise du TD1 en salle machines),
	* quatrième séance (30/09/2008) : fin du TP0,		* quatrième séance (30/09/2008) : fin du TP0,
	* cinquième séance (07/10/2008) : approximations asymptotiques, ~~debut~~ TD2,		* cinquième séance (07/10/2008) : approximations asymptotiques, début TD2,
			* sixième séance (14/10/2008) : TD2,
			* septième séance (21/10/2008) : fin TD2,
			* TP1 (24/10/2008) : matrices de markov,
			* huitième séance (4/11/2008) : cours de C, structures et pointeur,
			* TP2 (5/11/2008) : le jeu de la vie,

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

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

2008-10-07T08:15:26Z

Les support de TD et TP

← Version précédente		Version du 7 octobre 2008 à 08:15
Ligne 42 :		Ligne 42 :
	*** soit installer une "émulation Unix" pour Windows ([http://www.cygwin.com/ Cygwin], en précisant à l'installation que vous voulez installer au moins <tt>gcc</tt>, <tt>gdb</tt> et <tt>make</tt> dans la partie <tt>Devel</tt>)		*** soit installer une "émulation Unix" pour Windows ([http://www.cygwin.com/ Cygwin], en précisant à l'installation que vous voulez installer au moins <tt>gcc</tt>, <tt>gdb</tt> et <tt>make</tt> dans la partie <tt>Devel</tt>)
	*** soit installer un environnement de programmation C pour Windows (par exemple, [http://www.bloodshed.net/dev/devcpp.html Dev-C++])		*** soit installer un environnement de programmation C pour Windows (par exemple, [http://www.bloodshed.net/dev/devcpp.html Dev-C++])

			* [http://www.lama.univ-savoie.fr/~hyvernat/Enseignement/0809/info719/td2.pdf TD2]

	==Correction TDP0==		==Correction TDP0==

Hyvernat : /* Un peu de complexité */

2008-10-07T08:11:29Z

Un peu de complexité

← Version précédente		Version du 7 octobre 2008 à 08:11
Ligne 457 :		Ligne 457 :
	=Un peu de complexité=		=Un peu de complexité=

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

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


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

			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
			* 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 :
			<math> 1 < \log(\log(n)) < n^\epsilon < n < n^c < n^{\log(n)} < c^n < n^n < c^{(c^n)} </math> <br/>
			Avec <math>0<\epsilon<1</math> et <math>c>1</math>.

			---À compléter ? Par exemple, vous pouvez rajouter les fonctions <math>\log(n)</math> et <math>n\log(n)</math>...---

	=Références=		=Références=

Hyvernat : /* Un peu de complexité */

2008-10-07T08:09:36Z

Un peu de complexité

← Version précédente		Version du 7 octobre 2008 à 08:09
Ligne 454 :		Ligne 454 :

	Voir le TD1 et les exemples de correction dans la [[#Correction TDP0 \| correction du TP0]].		Voir le TD1 et les exemples de correction dans la [[#Correction TDP0 \| correction du TP0]].

			=Un peu de complexité=



	=Références=		=Références=

Hyvernat : /* Le langage C, partie 1 */

2008-10-07T08:08:49Z

Le langage C, partie 1

← Version précédente		Version du 7 octobre 2008 à 08:08
Ligne 449 :		Ligne 449 :

	Pour la syntaxe de base et des exemples concernant les conditions et les boucles, reportez-vous au chapitre [http://clips.imag.fr/commun/bernard.cassagne/Introduction_ANSI_C/node9.html « les bases »] et [http://clips.imag.fr/commun/bernard.cassagne/Introduction_ANSI_C/node31.html « les tableaux »] du polycopié de Bernard Cassagne.		Pour la syntaxe de base et des exemples concernant les conditions et les boucles, reportez-vous au chapitre [http://clips.imag.fr/commun/bernard.cassagne/Introduction_ANSI_C/node9.html « les bases »] et [http://clips.imag.fr/commun/bernard.cassagne/Introduction_ANSI_C/node31.html « les tableaux »] du polycopié de Bernard Cassagne.


			== Qelques exercices... ==

			Voir le TD1 et les exemples de correction dans la [[#Correction TDP0 \| correction du TP0]].

	=Références=		=Références=

INFO719 : rappels d'algorithmique et programmation C - Historique des versions

Hyvernat : /* Code C de l'examen */

Hyvernat : /* Code C de l'examen */

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

Hyvernat : /* Organisation des séances */

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

Hyvernat : /* Organisation des séances */

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

Hyvernat : /* Un peu de complexité */

Hyvernat : /* Un peu de complexité */

Hyvernat : /* Le langage C, partie 1 */

Hyvernat : /* Code C de l'examen */

Hyvernat : /* Code C de l'examen */

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

Hyvernat : /* Organisation des séances */

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

Hyvernat : /* Organisation des séances */

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

Hyvernat : /* Un peu de complexité */

Hyvernat : /* Un peu de complexité */

Hyvernat : /* Le langage C, partie 1 */