Objectifs du cours :

Ce cours a pour objectif de renforcer la capacité des étudiants à concevoir, analyser et implémenter des solutions algorithmiques efficaces en langage C, tout en s’appuyant sur des structures de données dynamiques avancées et des algorithmes fondamentaux. Il s’inscrit dans la continuité du cours d’Algo et éléments de programmation 1, et vise à doter les étudiants des bases solides nécessaires pour structurer et manipuler des données de manière pertinente et performante. Après une introduction au principe de la récursivité ainsi qu’à la notion de complexité, les étudiants aborderont les listes chaînées. Les étudiants apprendront à choisir les structures adaptées à un problème donné et à maîtriser les algorithmes de tri et de parcours associés. Le cours articule apports théoriques, mise en pratique régulière et projet collaboratif, afin de développer à la fois les compétences techniques et la capacité à travailler en équipe.

Compétences à acquérir :

• Identifier et décrire les structures de données dynamiques classiques
• Énoncer les principes de la récursivité et les cas d’usage courants
• Expliquer le fonctionnement des structures de données dynamiques, leurs avantages, inconvénients et complexités
• Décrire et comparer différents algorithmes de tri et de parcours selon leur efficacité
• Implémenter en langage C les structures de données vues en cours dans le cadre d’un programme fonctionnel
• Intégrer et adapter les algorithmes étudiés dans la résolution de problèmes concrets.
• Concevoir un programme modulaire intégrant plusieurs structures et algorithmes pour répondre à un besoin donné (via le projet de groupe).

Plan de cours :

1. Rappels sur les fonctions & récursivité
o Rappels sur les fonctions, introduction à la complexité
o Principes de récursion (simple et terminale)
o Problèmes classiques : factorielle, Fibonacci, tour de Hanoï
o Analyse de complexité d’une fonction récursive

2. Listes chaînées
o Principe et implémentation
o Opérations de base : parcours, insertion, suppression
o Listes avancées : head et tail, circulaire, chaînage double

3. Problèmes classiques
o Tri fusion et tri rapide
o Comparaison des complexités
o Notions de récursivité implicite

4. Projet de groupe incrémental