Détails de l'UE "Algorithmique et introduction à la théorie de la complexité - S5" (6 ECTS)
Publics concernés
Responsable(s) pédagogique(s)
Pré-requis / co-requis
Initiation à l'algorithmique et outils informatiques
Algorithmique et structures des données
Programmation 1
Programmation 2
Programmation C
Programmation C avancée
Objectifs
Continuer l'étude de l'algorithmique et de structures de données avec une introduction plus formelle de la notion de complexité.
Connaissances / compétences acquises
Maîtriser les bases d'algorithmique et des structures de données.
Apprendre à analyser la complexité des algorithmes.
Connaître des techniques d'algorithmique comme diviser pour régner, la programmation dynamique ou les algorithmes gloutons.
Contenu détaillé de l'enseignement
Complexité des algorithmes.
Structures de données : leur représentation, leurs opérations de base et leurs applications :
structures de données classiques (file, pile, liste);
arborescences (arbre binaire de recherche, AVL, B-arbres);
tas, files de priorité;
tables de hachage;
graphes et algorithmes classiques sur les graphes.
Algorithmes de recherche et de tri ainsi que leur complexité.
Techniques d'algorithmique : diviser pour régner, programmation dynamique, algorithmes gloutons.
Méthode d'enseignement
CM et TD traditionnels : oui
Nombre d’heures de travail à la maison : l’équivalent du volume horaire d’enseignement
Nombre de séances de TP : 6 séances de 3h avec rédaction de compte rendu de TP
Evaluation par les étudiants
Un questionnaire est rempli par chaque étudiant en fin de semestre.
Indications bibliographiques
Cormen et al. Introduction à l'algorithmique. Dunod 2010.
Sedgewick et Wayne. Algorithms. Pearson 2011.
Dasgupta, Papadimitriou, Vazirani. Algorithms. Addison-Wesley 2006.
Liste des UEs
Liste des parcours
Maquette 2016/2017 - Les informations portées sur ces pages sont non-contractuelles et n'engagent en rien la responsabilité de la faculté des sciences et technologies de l'UPEC.