INFO803 : informatique

Ce wiki est un complément de cours pour le cours "info-803, informatique". 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 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.)

Détails techniques sur le cours

Nouvelles

Les nouvelles récentes sont en haut de la liste...

• Hyvernat 16 janvier 2008 à 17:10 (CET) création du wiki

Organisation des séances

Comme vous n'êtes pas nombreux, le cours sera entièrement en mode cours / TD.

• 17 janvier 2008 à 15:25 (CET) : cours 1 : quelques dates, rappels sur les approximations asymptotiques, "diviser pour rêgner" (puissance avec la méthode chinoise)
• 23 janvier 2008 à 11:45 (CET) : cours 2 : méthode de Karatsuba pour multiplier les polynômes, début du TD 1
• 30 janvier 2008 à 14:46 (CET) : séances 3 et 4 : tri-fusion et multiplication de Strassen, début du TD 2 (Fibonacci)
• 6 février 2008 à 15:57 (CET) : séances 5 et 6 : programmation dynamique (recherche du parenthésage minimisant le nombre de multiplication lors du calculs du produit d'une chaîne de matrices, comment rendre la monnaie de manière optimale)
• 13 février 2008 à 14:19 (CET) : séances 7 un 8 : algorithmes gloutons

Les support de TD et TP

• TD 1
  • lien wikipedia vers le tri fusion
  • voici, comme promis, le tri fusion ecrit en Caml :

 let rec fusionne l1 l2 =
   match l1,l2 with              (* le 'match' veut dire qu'on regarde la forme de l1 et l2 *)
       []      , l2'     -> l2'  (* [] est la liste vide *)
     | l1'     , []      -> l1'
     | a1::l1' , a2::l2' -> if (a1<a2)
                            then a1::(fusionne l1' l2)
                            else a2::(fusionne l1 l2')
 
 let rec tri_fusion l =
   let rec coupe ll =             (* 'coupe' divise la liste ll en deux : *)
     match ll with                (*    les éléments 'pairs' sont mis dans la partie gauche *)
         []         -> ([],[])    (*    les éléments 'impairs' sont mis dans la partie droite *)
       | [a]        -> ([a],[])
       | a1::a2::ll -> let (l1,l2) = coupe ll in (a1::l1 , a2::l2)
   in
     match l with
         []  -> []
       | [a] -> [a]
       | _   -> let (l1,l2) = coupe l in fusionne (tri_fusion l1) (tri_fusion l2)

• TD 2

• TD 3

---

---

Introduction, quelques dates

Vous pouvez partir de cette page pour avoir un peu plus de details...

La préhistoire : le calcul

• le boulier chinois
• la pascaline de Pascal, inventée en 1641/42 : elle ne permet de faire que des additions (et des sourstractions
• Leibniz rajoute la multiplication à la pascaline (1673)
• les "moulins à chiffres" de Charles Babbage (1834-36), malheureusement jamais construits...
• l'apparition du relais electro-mécanique (1900) d'une frequence de 100 Hz, permet la construction du Harvard Mark I en 1944
• la "tabulating business machine" de Hollerith permet d'automatiser les calculs pour le recensement de la population américaine. Ceci donnera ensuite la société "international business machine" (IBM).
• l'invention du tube à vide permet le developpement d'ordinateurs entièrement électroniques : l'ENIAC en est le premier exemplaire (1946) ; il pèse environ 30 tonnes...

Les programmes et instructions

• les orgues de Barbarie
• les metiers à tisser de Vaucanson et Jacquard (1801)

Les ordinateurs "modernes"

• la machine de Turing (ordinateur théorique)
• le Manchester Mark I (1948) et l'EDVAC (1951) améliorent l'ENIAC et commencent à ressembler à des ordinateurs modernes
• l'UNIVAC I est le premier ordinateur commercialisé, en 1951.

Rappels : 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é

 (Ce qui suit est récupéré du cours d'info-614... Je n'ai pas encore parlé de complexité, mais c'est pas tres compliqué.)

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 (si (n==42) alors ...) ou une affectation (x:=3,1415926536) 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 max
• une opération pour l'initialisation de i à 1
• un test pour voir si i==taille
• une opération pour le test max < Tab[1]
• "peut-être" une opération pour l'affectation max:=Tab[1]
• 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 $n$ est la taille du tableau, on obtient entre $4n$ et $5n$ 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 $5n$ 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 i:=i+1 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 $f$ et $g$ sont des fonctions de $\mathbb {N}$ dans $\mathbb {N}$, on dit que $f$ est un "grand O" de $g$, et on écrit $f=O(g)$ si le quotient $|f(n)| \over |g(n)|$ est borné. Plus précisément, ça veut dire que $\exists B,\forall n,{|f(n)| \over |g(n)|}<B$

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 ("$4n$ et $5n$, 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 $f=O(h)$ et $g=O(h)$ alors $\alpha f+\beta g=O(h)$
• si $f=O(g)$ et $g=O(h)$ alors $f=O(h)$
• si $f=O(g)$ et $f'=O(g')$ alors $f\times f'=O(g\times g')$
• si $f=O(g)$ et $f'=O(g')$ alors $f+f'=O(|g|+|g'|)$

Pour pouvoir simplifier les expressions, il est important de connaître les liens entre les fonctions usuelles : $\log$, les fonctions linéaires, les polynômes, les exponentielles, les doubles exponentielles...
Pour $n$ très grand : $1<\log(\log(n))<n^{\epsilon }<n<n^{c}<n^{\log(n)}<c^{n}<n^{n}<c^{(c^{n})}$
Avec $0<\epsilon <1$ et $c>1$.

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

Algorithmique : diviser pour rêgner

Un exemple instructif : calcul d'un puissance

Le but est de calculer $x^{n}$ en optimisant le nombre de multiplications. La manière naïve de calculer cette puissance dans la variable r est la suivante :

r := x
pour i:=1 à n-1
faire
  r := r * x
finfaire

On utilise exactement $n-1$ multiplications par $x$.

Une méthode plus rapide est d'utiliser les propriétés suivantes : $x^{2n}=(x^{n})^{2}$ et $x^{2n+1}=x(x^{n})^{2}$. L'algorithme écrit de manière récursive est alors

exp(x,n) {
 si (n = 1) alors renvoie(x)
 si (n%2 = 0)
 alors
  r := exp(x,n/2);
  renvoie(r*r);
 sinon
  r := exp(x,(n-1)/2);
  renvoie(x*r*r);
 finsi
}

(L'opérateur % est l'opérateur "modulo"...)

Si $p$ est le nombre de 1 dans l'ecriture en base 2 de $n$, on fait alors exactement $\lfloor \log(n)\rfloor +p-1$ multiplications par $x$. (On rappelle que $\lfloor \log(n)\rfloor +1$ donne la taille de l'ecriture de $n$ en base 2...)

On trouve donc au final une complexité en $\Theta (\log(n))$...

Exercice :

• critiquer la complexité trouvée
• critiquez votre critique
• essayer de trouver une version itérative pour ce calcul
• pourquoi ne faut-il surtout pas "simplifier" en mettant "renvoie(exp(x,n/2)*exp(x,n/2))" et "renvoie(exp(x,n/2)*exp(x,n/2))" dans les branches du "si ..." ?

Un exemple plus intéressant : multiplication des polynômes par la méthode de Karatsuba

---

La "programmation dynamique"

Un exemple "bidon" : Fibonacci

---

Un exemple intéressant : multiplication d'une chaîne de matrices

---

Un autre exemple : comment rendre la monnaie de manière optimale

---

Les algorithmes gloutons

Programmation d'une chaine sportive

--

Codage optimal de Huffman

--