Organization: Lectures/conferences (18h) + Lectures/labs (24h)
Assessment: Examination + project and defense
Many problems, mostly of great practical importance (network routing, optimal task scheduling, shortest path), rely on advanced topics in modeling and algorithmic. Indeed, the resolution of such problems requires both to analyze the data to be manipulated in order to choose the best representation, and also to design the most suitable algorithms. One should then be able to estimate the complexities of these algorithms to compare or optimize them.
The Advanced algorithmic module aims to prepare engineering students to develop skills in a broad spectrum of areas where algorithms and modeling play an important role. The module is particularly focused in introducing the main themes of the considered areas (including graph theory and optimization) and the acquisition of technical, practical and fundamental algorithms of these areas. All of this teaching helps to develop the concepts and skills following.
- Complexity classes
- Heuristics and approximation algorithms for solutions
- Linear programming and search for optimum
- Graph Theory (flow problems, shortest path, ...)
- Genetic algorithms, Probabilistic algorithms
- Data mining and classification
- Neural Networks
- Estimate and compare the complexities of algorithms
- Apply standard algorithms of operational research (Simplex, Knapsack Problem)
- Modeling problem with graph, and choose the right algorithms to use (eg Kruskal’s or Prim’s algorithms for spanning tree, Dijkstra’s for shortest path, or Ford-Fulkerson’s for flow problems, ...)
- Analyze data and determine the criteria for classification
- Design a neural network or a genetic algorithm, and analyze the influence of parameters on their behavior.