Pre-requisites: II.1102
Level: Advanced
Organization: Lectures/conferences (18h) + Lectures/labs (24h)
Assessment:
Examination + project and defense

Overview

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.

Learning Objectives

Skills

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.

Knowledge

Concepts

  • 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

Know-how

  • 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.

Teaching method

The module is divided into two parts. The first sessions are devoted to lectures on specific areas (genetic or probabilistic algorithms, neural networks, data mining) and give rise to several areas of projects. The sessions of the second part follow a lecture/Lab scheme and introduce basic concepts of algorithmic (complexity, optimization) and graph theory; skills acquired are assessed by examination.

Bibliography

Course material.