LICENCE DE MATHEMATIQUES

INFORMATIQUE
TP

Traduire en langage C les exercices suivants

Chronomètrage de fonctions

Problèmes de mémoire

1. Tri à bulle

On fournit le cadre général de la méthode, l'étudiant doit :

Construire l'algorithme en langue naturelle

Convertir celui-ci en langage C

Poser des contraintes sur l'existance de fonctions (lecture, ecriture, echange, ...)

Prévoir les points délicats liés aux passages de paramètres

Finallement écrire sur le papier cette convertion

Correction

Retour

2. Tri rapide (QuickSort)

Un bon exemple de récursion est le tri rapide (quicksort), inventé par C.A.R. Hoare en 1962. Etant donné un tableau, on choisit un élément noté x dans celui-ci et on répartit les autres en deux sous-ensembles - ceux qui sont inférieurs à x et ceux qui lui sont supérieurs ou égaux. On applique ce même processus à ces deux sous-ensembles, récursssivement. Lorsqu'un sous-ensemble a moins de 2 éléments, ce n'est pas la peine de le trier, ce qui arrête la récurssion.

On peut içi choisir de partager tous les sous-ensembles par rapport à leur élément central.

Correction

3. Tri de complexité Linéaire

Elaborer un tri de complexité linéaire en plaçant certaines contraintes. Amener les élèves à trouver ces contraintes.

4. Algorithme de coloration de graphes

Il s'agit de manipuler expérimentalement un algorithme de complexité exponentiel. Fixer une structure de données simplifiée, de type matrice d'adjacence. L'algorithme en question est un algorithme de coloration des sommets d'un graphe non orienté simple connexe. L'algorithme 'glouton' de coloration de graphes:

Début

G=(V,E)

Y=V

couleur=0

Tant que YØ Faire

couleur=couleur + 1

Z=Y

Tant que ZØ Faire

i=min{j | ijn et v_j Z}

colorier v_i par couleur

Y=Y-v_i

Z=Z-v_i-{les voisins de v_i}

Fin

Fin

Fin