Pré-requis |
|
Objectifs de l'enseignement |
Le cours donne les bases d'algorithmique indispensable à tout futur développeur : notions sur la complexité des algorithmes et étude de divers types abstraits de données et des algorithmes associés |
Programme détaillé |
Nombres, bases. - Notions de base d'algorithmique. - Complexité des algorithmes : spatiale et temporelle, règles simples de calcul, application aux algorithmes de recherche et de tri. - Étude des types abstraits de données suivants : tableaux, piles et files, listes linéaires chaînées, arbres, tas. - Évaluation de la complexité des opérations de recherche/insertion/suppression d'éléments sur ces types de données. |
Applications (TD ou TP) |
APPLICATIONS (TD OU TP) Bases (2,8,16,10,60) -Instructions, schémas itératifs -Complexité -tris -Récursité (montante, descendant). - Types abstraits Piles, Ensembles, Files, Listes, arbres Certaines de ces applications seront réalisées en TP du module « Programmation et langage C ». De plus, un projet mené en collaboration avec le module « Programmation et langage C » facilite l'appropriation des compétences acquises. |
Compétences acquises |
L'étudiant sait évaluer la complexité dans le pire des cas et en moyenne d'algorithmes simples. Il est capable d'utiliser à bon escient les types abstraits de données suivants : tableaux, piles, files, listes, arbres et tas. |
Bibliographie |
Introduction à l'algorithmique. T. Cormen et al. - Dunod - 1994 Types de données et algorithmes. C. Froidevaux et al. - Mc Graw-Hill - 1990 |