Programmation - Maîtriser l'Algorithmique et le Codage

Objectifs d'apprentissage

• Maîtriser les structures de données fondamentales (listes, piles, files, arbres, tables de hachage) et leurs implémentations
• Comprendre et appliquer les algorithmes de tri et de recherche sur différentes structures de données
• Développer des compétences en programmation orientée objet pour la conception de structures complexes
• Appliquer les concepts d'algorithmique pour résoudre des problèmes concrets de traitement de données
• Analyser la complexité algorithmique et faire des choix d'implémentation éclairés
• Manipuler les expressions régulières et comprendre leur implémentation via les automates finis
• Acquérir des bases solides en Java pour l'implémentation des concepts étudiés

Public cible

Ce cours s'adresse aux étudiants en informatique (niveau licence ou classes préparatoires) ayant déjà des bases en programmation. Il convient également aux développeurs autodidactes souhaitant consolider leurs connaissances en structures de données et algorithmique. Les apprenants doivent être familiarisés avec les concepts de base de la programmation (variables, boucles, fonctions) et avoir une première expérience avec un langage orienté objet (de préférence Java).

Contenu détaillé

I. Listes

Ce module explore les listes comme structure de données fondamentale. Nous comparerons les structures dynamiques et séquentielles, avec un focus particulier sur les listes chaînées. Les algorithmes de tri spécifiques aux listes seront étudiés, ainsi que leur implémentation en programmation orientée objet. Le chapitre se conclut par une étude des listes bouclées et de leurs applications.

II. Piles et files

Nous analyserons les structures LIFO (piles) et FIFO (files), leurs cas d'usage typiques et différentes techniques d'implémentation. Une attention particulière sera portée sur le concept de type abstrait et les critères de choix d'implémentation selon le contexte d'utilisation.

III. Associations - Tables de hachage

Ce chapitre couvre les mécanismes d'association clé-valeur, en commençant par une étude de cas concret (statistiques de mots). Nous approfondirons le fonctionnement des tables de hachage, les méthodes de résolution des collisions et le choix optimal des fonctions de hachage.

IV. Arbres

Introduction complète aux structures arborescentes : définitions formelles, algorithmes Union-Find pour la gestion des partitions, et étude des arbres binaires. Nous explorerons des applications concrètes comme les arbres de syntaxe abstraite, les files de priorité et le codage de Huffman pour la compression de données.

V. Arbres binaires de recherche

Focus sur les techniques d'implantation des arbres binaires et leur utilisation pour la recherche efficace. Le module inclut l'étude des arbres équilibrés (AVL, arbres rouge-noir) et leurs algorithmes de maintien de l'équilibre.

VI. Expressions régulières

Approfondissement des langages réguliers et de leur notation. Ce chapitre couvre à la fois l'utilisation pratique des regex en programmation et leur implémentation sous-jacente, avec des techniques alternatives de filtrage.

VII. Les automates

Étude théorique et pratique des automates finis (déterministes et non-déterministes) et de leur relation avec les expressions régulières. Des exemples concrets en Java illustreront ces concepts.

Annexes

Deux annexes complètent le cours : une introduction rigoureuse à l'analyse de complexité algorithmique, et un guide pratique des concepts Java essentiels pour l'implémentation des structures étudiées, incluant la gestion des exceptions et les E/S.

Approche pédagogique

Le cours combine théorie et pratique avec : des exposés magistraux pour les concepts fondamentaux, des travaux dirigés pour l'application sur des cas concrets, et des projets de programmation en Java. Chaque structure de données sera implémentée de plusieurs façons pour en comprendre les compromis. Des analyses de performance concrètes permettront de valider les choix algorithmiques.

Prérequis techniques

Les exercices pratiques nécessitent un environnement de développement Java (JDK 11+) et un IDE (Eclipse, IntelliJ ou VS Code). Des connaissances de base en mathématiques discrètes (logique, ensembles) sont recommandées pour la partie théorique.