Différences

Ci-dessous, les différences entre deux révisions de la page.

--- algose:feuille2 [2016/09/19 09:46] – créée blanc
+++ algose:feuille2 [2016/09/19 10:18] (Version actuelle) – supprimée blanc
@@ Ligne 1: / Ligne 1: @@
-===== Feuille 2 =====
-==== Notions de complexité algorithmique ====
-Il est important, lorsqu'on conçoit un algorithme de pouvoir donner à l'utilisateur des garanties de performance: que l'algorithme prendra au pire un temps linéaire, qu'en moyenne il prend un temps logarithmique, etc.
-  * Qu'est-ce que tout ça veut dire ?
-  * Quels calculs permettent d'établir ces "garanties" ?
-=== Ordre de grandeur et notation grand "O" ===
-L'analyse de la //complexité d'un algorithme// consiste en l'étude formelle de la quantité de ressources, en temps ou en espace, nécessaires à l'exécution. Par la suite on s'intéresse à la //complexité en temps// (le nombre d'étapes de calcul avant d'arriver à un résultat), qu'on chiffre en fonction de //la taille des objets à traiter//. Par exemple, lorsqu'on traite un tableau, c'est son nombre d'éléments.
-La complexité s'exprime par des //ordres de grandeur//, fonction de la taille $N$ de l'objet à traiter. Ces ordres de grandeur s'écrivent à l'aide des notations "grand $O$".
-  * Par exemple, on écrit et on dit qu'un algorithme est de l'ordre $O(N)$ lorsqu'il est //linéaire//.
-La notion grand $O$ peut être définie précisément. Soit deux fonctions $f(N)$ et $g(N)$, on dira que $f(N) \to O(g(N))$ lorsque $N \to \infty$ si et seulement s'il existe une constante $c$ telle que:
-$$|f(N)| \leq |c \cdot g(N)|$$
-pour $N$ assez grand; c'est-à-dire que l'inégalité est vérifiée dès lors que $N \geq N_0$ (pour une valeur $N_0$ qui dépend des fonction $f$ et $g$). On écrit alors plus simplement $f(N) = O(g(N))$ ou on dit tout simplement que l'algorithme dont la complexité est donnée par $f$ est "en $O(g(N))$".
-On utilisera toujours, en lieu de $g$, des fonctions types:
-  * logarithmique: $g(N) = \log(N)$
-  * linéaire: $g(N) = N$
-  * quadratique: $g(N) = N^2$ (la complexité des "mauvais" algorithmes de tri)
-  * ou encore $g(N) = N \log(N)$ (la complexité des "bons" algorithmes de tri)
-  * ...
-La notation grand $O$ possède des propriétés intéressantes, lorsqu'il s'agit de combiner des algorithmes qui se succèdent, ou alors qui sont imbriqués:
-  * Si $f_1(N) = O(g_1(N))$ et $f_2(N) = O(g_2(N))$ alors
-  * $(f_1 + f_2)(N) = O(g_1(N) + g_2(N))$
-  * $(f_1 \cdot f_2)(N) = O(g_1(N) \cdot g_2(N))$
-Sauriez-vous le démontrer ?
-La complexité peut être mesurée de plusieurs manières, notamment //dans le pire des cas// ou //en moyenne//.
-  * La **complexité dans le pire des cas** considère la complexité maximale sur toutes les entrées possibles.
-  * La **complexité en moyenne** est une moyenne de la complexité pondérée entre les différentes entrées possibles selon une distribution donnée.
-==== Exercice 1. Recherchez un élément dans un tableau ====
-Prenez l'algorithme de recherche d'un élément dans un tableau que vous avez écrit la semaine dernière.
-  * Combien de comparaisons doit-on effectuer si l'élément recherché est en position $i$ dans le tableau ?
-  * Quelle est la complexité de cet algorithme (combien de comparaisons doit-il effectuer) dans //le pire des cas// (//worst case complexity//) ?
-  * Quelle est la complexité //moyenne// ? Il faut faire la moyenne du nombre de comparaisons sur tous les cas possibles: lorsque l'élément cherché est en début de tableau, lorsqu'il est en second, ..., lorsqu'il est à la fin.
-==== Exercice 2. Décalez les entrées d'un tableau d'entiers ====
-Prenez l'algorithme de décalage des entrées d'un tableau que vous avez écrit la semaine dernière.
-  * Quelle est la complexité de cet algorithme en pire cas ? en moyenne ? Démontrez vos affirmations en faisant une utilisation rigoureuse de la notation $O$.
-==== Exercice 3. Fusionnez deux tableau d'entiers triés par ordre croissant ====
-La semaine dernière vous avez proposé deux algorithmes pour ce problème, un qui implémente une solution "naïve" et un autre une solution plus "maligne".
-  * Donnez la complexité en pire cas pour ces deux algorithmes.
-===== TD machine =====
-==== Générez des entiers au hasard ====
-La génération aléatoire d'entiers, de listes ou d'ensembles peut sembler "artificielle" -- elle ne l'est pas ! Quand vient le temps de tester un algorithme, il faut faire tourner des tas d'exemples pour s'assurer de son bon fonctionnement. Lorsqu'il s'agit de mesurer ses performances, on voudra s'assurer de soumettre tous les cas possibles à l'algorithme (plutôt que de ne lui soumettre que des cas plus "faciles", amenant à conclure erronément à de bonnes performances, ou au contraire à ne lui soumettre que des cas "difficiles" ...).
-**Qu'entend t-on par génération aléatoire ?** Pour les entiers dans l'intervalle $[a, b]$, c'est facile, on souhaite que chacun des entiers $a, a+1, \ldots, b$ ait une chance égale d'être tiré au hasard. On parle alors de génération //uniforme// (tirage à probabilités égales pour tous les entiers).
-Par exemple, on peut voir le jeu de pile ou face comme un tirage aléatoire uniforme sur l'intervalle $[0, 1]$. Pile = 1 et Face = 0. Un [[https://fr.wikipedia.org/wiki/%C3%89preuve_de_Bernoulli|tirage de Bernouilli]] est un jeu de pile ou face, où la probabilité d'avoir pile est égale à $p \in [0, 1]$.
-==== Exercice 4. La hasard en langage C ====
-La plupart des langages propose des librairies effectuant les opérations de base et nécessaires à la génération aléatoire: générer un entier au hasard parmi tous les entiers possibles.
-<file c ex_hasard.c>
-#include <stdio.h>
-#include <stdlib.h>
-#include <time.h>
-int main(void) {
-	int tab[10];
-        srand(time(NULL));
-	for(int i = 0; i < 10; ++i) {
-		tab[i] = rand() % 10;
-	}
-	printf("Voici les 10 nombres générés au hasard:\n");
-	for(int i = 0; i < 10; ++i) {
-		printf( "%d ", tab[i]);
-	}
-	printf("\n");
-        return EXIT_SUCCESS;
-}
-</file>
-Ce code insère 10 entiers choisis au hasard dans l'intervalle [0, 9] dans un tableau d'entiers (de taille 10) en utilisant la fonction ''rand()'' de la librairie standard (''stdlib.h''). On le compile avec la commande ''gcc -std=c99 -Wall ex_hasard.c -o ex_hasard''. On l'exécute ensuite depuis le même répertoire avec la commande ''./ex_hasard''.
-Observez comment on s'assure de tirer des nombres dans l'intervalle [0, 9], en effectuant l'opération ''rand() % 10''. En effet, la fonction ''rand()'' renvoie un nombre qui varie dans $\mathbb N$ (pas tout-à-fait, c'est plutôt dans [0, ''RAND_MAX''] mais ici on supposera que ''RAND_MAX'' $= \infty$). Cette opération calcule le reste après division par 10; c'est donc une valeur dans [0, 9]. Si les entiers sont tirés uniformément au hasard dans $\mathbb N$ (c'est ce dont nous assure la fonction ''rand()'') alors les entiers obtenus sont tirés uniformément au hasard dans [0, 9].
-==== Exercice 5. Est-ce bien au hasard ??? ====
-Nous allons maintenant vérifier que le tirage aléatoire est bien uniforme ... c'est-à-dire que les entiers ont bien tous la même probabilité d'être choisis. Comment faire ?
-  * On détermine un intervalle $[0, M]$. Nous prendrons $M = 9$ comme dans l'exemple.
-  * On utilise un tableau $T$ de taille $M$, dont les entrées sont initialisées à 0.
-  * On détermine un nombre de tirages $N$, suffisamment grand (on le fera varier en prenant des valeurs de plus en plus grandes).
-  * On effectue $N$ tirages aléatoires d'entiers dans $[0, M]$
-    * A chaque tirage ''k = rand() % M'', on incrémente la valeur correspondante du tableau.
-  * En fin de boucle, l'entrée $T[k]$ du tableau comptabilise le nombre de fois où le nombre $k$ a été tiré au hasard.
-  * Reste à calculer la fréquence d'apparition de chacun des nombres: on obtient cette fréquence en divisant les entrées du tableau par $M$. On affichera ces valeurs à mesure de leur calcul (on ne peut en effet pas les stocker dans le tableau, puisque c'est un tableau d'entiers alors que les ratios sont des réels).
-En vous basant sur le programme donné dans l'exercice 4, écrivez un programme qui implémente cet algorithme. Essayez votre programme avec différentes valeurs de $M$, et de $N$. Il est intéressant d'observer l'effet de $N$ (le nombre de tirages) sur la précision de la fréquence théorique (c'est la [[https://fr.wikipedia.org/wiki/Loi_des_grands_nombres|loi des grands nombres]] en théorie des probabilités).
-==== Exercice 6. Générez une liste d'entiers distincts au hasard ====
-Cet exercice vise à mettre au point un algorithme générant au hasard une liste d'entiers //distincts// parmi $\{1, \ldots, N\}$.
-**Première tentative** Implémentez l'algorithme suivant un peu gourmand, mais qui fonctionne à coup sûr:
-<code>
-entrée: N
-sortie: un tableau de N entiers distincts parmi {1, ..., N}
-on génère un tableau T de N entiers parmi {1, ..., N} (avec l'algorithme précédent)
-tant que les entiers du tableau T ne sont pas distincts deux à deux
-    on recommence
-</code>
-**Deuxième tentative**  Nous allons ruser un peu. Plutôt que de générer un tableau et de vérifier //a posteriori// si les entiers sont deux à deux distincts, nous allons nous assurer que tout va bien à chaque fois que l'on génère un nouvel entier.
-<code>
-entrée: N
-sortie: un tableau de N entiers distincts parmi {1, ..., N}
-T un tableau vide de taille N
-repeter pour i de 0 à N-1
-    k = entier choisi au hasard
-    tant que k est deja present dans T
-        k = entier choisi au hasard
-    T[i] = k
-</code>
-  * Evaluez combien le deuxième algorithme est plus rapide que le précédent. Pour cela, faites les tourner, et comptez pour chacun le nombre total d'entiers tirés au hasard pour arriver à générer au hasard un tableau d'entiers deux à deux distincts.
-  * Cet algorithme nécessite de chercher si un élément est dans le tableau. Comment avez-vous géré cette recherche ? Quelle solution peut-on envisager pour éviter de lancer une recherche "aveugle" dans la liste et ainsi maîtriser la complexité ?
-  * Analysez la complexité dans le pire des cas pour les deux algorithmes.