Algorithmique 2

L’UE se compose d'une matière enseignée sur 1 période : Algorithmique 2 P3 (CM/TD, TP)

Période 3 : principe de récursivité, algorithmes récursifs, méthode de dichotomie et applications. Utilisation de types composés (enregistrements). Notion de pointeur et d’allocation dynamique de mémoire. Introduction aux entrées/sorties dans un fichier texte au moyen des flux en C++.
Période 4 : introduction aux structures de données récursives, définition et utilisation de listes chainées. Complexité algorithmique, notation Grand O. Algorithmes de tris simples (par sélection, à bulles, par insertion) & de tri rapide.

Notions et contenus
UE Algorithmique 1

Compétences
Période 3 : être capable de concevoir un algorithme modulaire et l’écrire dans le langage C++.
Période 4 : compréhension de la récursivité. Manipulation du signe somme (sommation, changement d’indice).

Période 3 : approfondir les connaissances en algorithmique impérative et comprendre l’approche récursive (définition et exécution de fonctions récursives). Assimiler les notions de pointeurs et d’allocation dynamique. Écrire des algorithmes manipulant des entrées et sorties de plus grande taille. Pouvoir lire et écrire dans un fichier.
Période 4 : définir et manipuler des listes chainées au moyen de primitives, et les utiliser dans un contexte applicatif. Savoir analyser la complexité d’un algorithme et comprendre l’intérêt de cette analyse pour le choix d’un algorithme. Comprendre différentes méthodes de tri et pouvoir les redéfinir et les appliquer.