L'objectif de cette unité est d'introduire les structures de données et les techniques de conception de bases de l'algorithmique, et d'étudier les outils d'analyse et de preuve de corrections des algorithmes.
Notions de bases pour l'analyse des algorithmes; algorithmes de tris
Algorithmes de tris, optimalité asymptotique (notamment preuve de borne inférieure); tris linéaires
Tas binaire; tri par tas binaire
Dictionnaire; arbre binaire de recherche non-équilibré, insertion et suppression de clés
Équilibrage des arbres binaires de recherche; files de priorité (hors tas binaire)
Tables de hachage, chainage simple; nombre de collisions; extension : filtre de Bloom ou table coucou
Énumération et algorithmes par rebroussement (SAT, sac-à-dos, problèmes logiques)
Programmation dynamique, principe et exemples (ordonnancement sur une machine, sous-séquence monotone la plus longue)
Graphes et représentation par liste d'incidences; plus court chemins, algorithme de Dijkstra
Algorithmes de plus courts chemins : Bellman-Ford et Floyd-Warshall
Arbres couvrants de poids minimum, algorithmes de Prim, de Kruskal; structure d'union-find.
Compétences à acquérir
Évaluer la complexité et la correction d’une solution algorithmique (20%).
Mettre en œuvre des algorithmes et des structures de données (20%).
Choisir, sur des critères objectifs, les structures de données et construire ou sélectionner les algorithmes les mieux adaptés à un problème donné (15%).
Concevoir un algorithme en utilisant des stratégies algorithmiques adaptées aux problèmes (15%).
Modéliser un problème concret sous la forme d'un problème algorithmique connu (15%).
Faire preuve d'esprit critique vis-à-vis d'une solution technique pour en vérifier son efficacité, sa fiabilité et sa robustesse dans son contexte d'utilisation (15%).