Actualités et agenda
Nos formations
Matières
Cycle informatique & réseaux 2nde année
Responsable(s)
F.WINDAL, G.CHÊNEVERT
Intervenant(s)
J.ROLAND
Présentation
Prérequis
• Notions algorithmiques de base telles que les tableaux, les listes, les files, les tris simples, la récursivité.
• Connaissance d'un langage de programmation procédural.
• Connaissance d'un langage de programmation procédural.
Objectifs
• Maîtriser les algorithmes et structures de données traditionnels.
• Savoir choisir une structure de donnée ainsi que les algorithmes associés afin de résoudre un problème de manière correcte et efficace.
• Avoir les outils pour concevoir des algorithmes et structures de données.
• Savoir choisir une structure de donnée ainsi que les algorithmes associés afin de résoudre un problème de manière correcte et efficace.
• Avoir les outils pour concevoir des algorithmes et structures de données.
Présentation
1. Fondamentaux : types de données abstrait, analyse des algorithmes (complexité en moyenne et au pire cas)
2. Structures de données : structures liées et contiguës, files à priorités,
arbre binaire de recherche, arbre rouge noir, table de symboles, table de hachage
3. Backtracking : recherche de sous-ensembles, recherche de permutations, le problème des 8 reines
4. Les graphes : terminologie, implémentation (structures de données), parcours, cycles et connexité (recherche des composantes connexes, détection des cycles), plus courts chemins (Dijkstra, Bellman, Bellman-Ford), arbres sous-tendants minimaux (Prim, Kruskal)
5. Programmation dynamique : notion de sous structure optimale, application au problème du sac-à-dos
6. Les algorithmes gloutons : notion d’heuristiques, problème du sac-à-dos, comparaison avec la technique de programmation dynamique, codage de Huffman, matroïde
7. Chaînes de caractères : expression régulière, automates finis
8. Gestion mémoire : mémoire externe, B-tree
2. Structures de données : structures liées et contiguës, files à priorités,
arbre binaire de recherche, arbre rouge noir, table de symboles, table de hachage
3. Backtracking : recherche de sous-ensembles, recherche de permutations, le problème des 8 reines
4. Les graphes : terminologie, implémentation (structures de données), parcours, cycles et connexité (recherche des composantes connexes, détection des cycles), plus courts chemins (Dijkstra, Bellman, Bellman-Ford), arbres sous-tendants minimaux (Prim, Kruskal)
5. Programmation dynamique : notion de sous structure optimale, application au problème du sac-à-dos
6. Les algorithmes gloutons : notion d’heuristiques, problème du sac-à-dos, comparaison avec la technique de programmation dynamique, codage de Huffman, matroïde
7. Chaînes de caractères : expression régulière, automates finis
8. Gestion mémoire : mémoire externe, B-tree
Modalités
Organisation
| Type | Nombre d'heures | Remarque | |
|---|---|---|---|
| Présentiel | |||
| Travaux Dirigés | 30,00 | ||
| Cours - face à face | 30,00 | ||
| Travail personnel | |||
| Travail personnel | 60,00 | ||
| Charge de travail globale de l'étudiant | 120,00 | ||
Évaluation