Accueil - Connexion

Bases de l'algorithmique

178-2 Bases de l'algorithmique Informatique (formation initiale sous statut apprenti) S5
Cours : 10 h TD : 10 h TP : 0 h Projet : 0 h Total : 20 h
Responsable : Joan REYNAUD
Pré-requis
Cours "Introduction à la programmation"
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 (implantés en langage C).
Programme détaillé
- 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, tables de hachage, 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)
- Comparaison expérimentale de la complexité de divers algorithmes de tri (tris internes et tris
externes).
- Récursité (pile des appels récursifs, principe des mémo-fonctions).
- Piles, Files, Listes (ex : tri par distribution, manipulation d’expressions arithmétiques).
- Tri par tas, fusion de fichiers triés à l’aide d’un tas.
Compétences acquises
L’étudiant sait évaluer la complexité dans le pire des cas d’algorithmes simples.
Il est capable d’implanter en langage C et d’utiliser à bon escient les types abstraits de données suivants : tableaux, piles, files, listes, tables de hachage 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
- Algorithmes et structures de données en langage C, (C ANSI et C++). L. Ammeraal – InterEditions -1996
- Le langage C, norme Ansi. B. Kernigham – Dunod – 2000

© 2024 - ENSICAEN ( Mentions Légales - Crédits )