Descriptif
L’objectif de cet enseignement est de développer la pensée algorithmique. L’approche suivie dans ce cours est d’étudier des algorithmes connus de la littérature. Ces algorithmes utilisent majoritairement des structures de données adaptées, ces structures seront étudiées également dans le cadre de ce cours au travers de l’utilisation d’une bibliothèque logicielle développée pour ce contexte.
Objectifs pédagogiques
- Être capable de concevoir un algorithme de manière systématique et scientifique. Il illustre la démarche d'analyse, de formalisation, de conception et d'implantation d'algorithmes répondant à des spécifications exprimées sous différentes formes.
- Être capable de :
- comprendre la structure de pile et dans quels cas l'utiliser ;
- comprendre la structure de file et dans quels cas l'utiliser ;
- comprendre la structure de liste chaînée et dans quels cas l'utiliser ;
- comprendre la structure d’union-find et dans quels cas l’utiliser ;
- comprendre les structures d'arborescentes (arbre binaire, tas) et dans quels cas les utiliser ;
- comprendre la structure de graphe et dans quels cas l'utiliser.
- Connaître le fonctionnement des itérateurs sur les structures de données linéaires, ainsi que les parcours d’arbres et de graphes.
- Connaître le fonctionnement et les contextes d’utilisation des algorithmes standards sur les graphes (plus court chemin, d’arbre couvrant de poids minimal, de vérification de connexité, etc.).
33 heures en présentiel
Diplôme(s) concerné(s)
UE de rattachement
- UE.2.3 Numérique 2 : UE.2.3 Numérique 2
Format des notes
Numérique sur 20Pour les étudiants du diplôme (FIG) Diplôme d'Ingénieur de l'Ecole Nationale Supérieure de Techniques Avancées
Le rattrapage est autorisé (Note de rattrapage conservée)- le rattrapage est obligatoire si :
- Note initiale < 6
- le rattrapage peut être demandé par l'étudiant si :
- 6 ≤ note initiale < 10
Le coefficient de l'UE est : 3
L'UE est évaluée par les étudiants.
Programme détaillé
- Séance 1 : Notion d'algorithme, Différentes formes de spécification, Importance des domaines d'entrée et de sortie
- Séance 2 : Élaboration d'un algorithme par raffinements successifs, Importance du test
- Séance 3 : Notions de complexité, Paradigme diviser pour régner, Paradigme de programmation dynamique, Paradigme d'algorithme glouton
- Séance 4 : Compilation séparée et introduction aux bibliothèques logicielles
- Séance 5 : Structures de données linéaires : listes chainées, piles, files, ensembles
- Séance 6 : Structures de données arborescentes - partie 1 : arbres et parcours d'arbres
- Séance 7 : Structures de données arborescentes - partie 2 : tas et union-find
- Séance 8 : Les graphes - partie 1 : graphes et parcours
- Séance 9 : Les graphes - partie 2 : plus court chemin, arbre couvrant de poids minimal, etc.
- Séance 10 : Examen sur machine