مخطط الموضوع
- عام
- Pré-requis
Pré-requis
Vidéo expliquant la notion des pointeurs en langage C.
- Chapitre 1 : Complexité algorithmique
Chapitre 1 : Complexité algorithmique
Le calculer de certaines complexités nous permet d'obtenir un outil de comparaison entre plusieurs algorithmes.
Nous allons commencer par définir la complexité d’un algorithme, puis étudier les données
qui lui sont liées. - Chapitre 2 : Algorithmes de tri
Chapitre 2 : Algorithmes de tri
Un tri est une opération de classement d'éléments d'une liste selon un ordre total défini. Sur le plan pratique, on considère généralement deux domaines d'application des tris : les tris internes et les tris externes.
Des ressources supplémentaires (vidéos) expliquant les différents algorithmes de tri
- Chapitre 3 : Listes, piles et files
Chapitre 3 : Listes, piles et files
Nous allons étudier dans la suite 3 exemples complets de TAD classiques : la liste linéaire, la pile LIFO, la file FIFO.
Des ressources supplémentaires (Vidéos, Pages Web, PDF) expliquant les listes, piles et files.
- Chapitre 4 : Les arbres
Chapitre 4 : Les arbres
La structure d'arbre est très utilisée en informatique. Sur le fond on peut considérer un arbre comme une généralisation d'une liste car les listes peuvent être représentées par des arbres.
- Travaux dirigés
Travaux dirigés
Ecrire un algorithme permettant de faire une recherche d'un élément dans un tableau en affichant leur position si trouvé + Calcul de la complexité O \ Ω.
Ecrire un algorithme permettant de faire une recherche d'un élément dans un tableau trié en utilisant la méthode dichotomique (méthode «diviser pour régner») + Calculer sa complexité
Ecrire un algorithme permettant d'insérer un nouveau élément entier dans un tableau trié. Calculer la complexité de cette algorithme.
Ecrire un algorithme qui permet de fusionner deux tableaux triés T1 et T2 par ordre croissant dans un troisième tableau T. Calculer la complexité de cet algorithme.
Ecrire un algorithme permettant d'implémenter une fonction puissance qui prend en entrée deux paramètres X et N pour calculer X au puissance de N.
Ecrire un autre algorithme pour le calcul d'une somme S=X puissance 1 + X puissance 2 + ..... + X puissance N.
Calculer la complexité de chaque algorithme.
- Travaux pratiques
Travaux pratiques
Compilateurs 32 et 64 bits
Environnement de développement en C++
Un exemple en C++ expliquant la création d'un arbre binaire étiqueté avec un calcul du temps d'exécution en utilisant la bibliothèque time.h.
Le TP est obligatoire pour tout les étudiants, c'est à envoyer par E-Mail avant le départ des examens.