IST Syllabus L2 Programme UE Algorithmique et structure de données

Semestre 3

UE Algorithmique et structure de données

24h CM – 24h TD

Prérequis de L1
Mathématiques : Algèbre linéaire 1, Analyse 1, Algèbre linéaire 2, Analyse 2
Informatique : Informatique 1, Informatique 2 
 

Prérequis pédagogique de L1

Reprise des prérequis en algorithmique et en programmation Python et C, enseignés en S1 et S2 :

Notions fondamentales en algorithmique : structures de contrôle itératives et récursives
Bases de la programmation en C : parcours des tableaux avec l’utilisation des pointeurs et du formalisme tableau.
Ecriture des algorithmes sans les ruptures de séquences.

Compétences disciplinaires
Comprendre et manipuler les structures de données fondamentales ainsi que les algorithmes associés (recherches séquentielles et dichotomiques, insertions, suppressions, tris, fusions, etc.).
Développer la capacité à choisir la structure de données la plus adaptée à un problème donné, en tenant compte de la complexité algorithmique.
Maîtriser les techniques de représentation des données sous forme contiguë (tableaux), chaînée (listes) et hiérarchiques (arbres binaires).

Maîtriser les techniques d'analyse récursives et du paradigme "Diviser pour mieux régner", indispensables à l’écriture d’algorithmes récursifs tels que la fusion de deux listes, le parcours de listes ou encore le parcours d’arborescences, etc.
Approfondir la programmation en langage C à travers des exercices appliqués et des projets guidés, mettant en pratique l'utilisation efficace de la mémoire et des pointeurs.

Compétences transversales (Soft skills)  
Développement de la rigueur et de l'esprit d'analyse à travers la réalisation de projets guidés en travaux dirigés.

Contenus du cours
Ce module propose une introduction approfondie aux structures de données essentielles en programmation, accompagnée des algorithmes fondamentaux correspondants (parcours global et partiel, insertions, suppressions, …).

Programmation en C avancée
Types complexes : struct, union, types énumérés (enum), etc.
Tableaux dynamiques et allocation mémoire (malloc, calloc, free).
Modularité et organisation du code (fichiers .h et .c, compilation séparée)

Structures de données séquentielles
Tableaux statiques et dynamiques.

Structures de données linéaires
Listes chaînées.
Piles et files :  implémentations chaînées et contigus (tableaux statiques et dynamiques).

Structures de données hiérarchiques
Arbres binaires
Arbres binaires de recherche.
Arbres parfaits
Files de priorité.