INF 413 P: Advanced Analysis of Algorithms


Coordinator  : Sorin MOGA
Co-coordinator  : Philippe LENCA
   

Presentation

The aim of this course is to present an approach which is and evidently will remain stable for a long time regardless of technical and technological mutations.

In fact, contrary to systems which are always undergoing the stress of their time and which respond to the demands of permanently evolving aims, this course presents the fundamental principles of computer science, particularly the algorithm.

Even today the typical image of computer science is unfairly reduced to that of a machine and a human trying to solve a problem. This image , which owes a lot to the banalisation of computer science is simply the media element of a proper science which expresses its principles, methods, demands and values. It is also a poor image in that it hids several aspects of a discipline whose increasing complexity is reflected in its presence in almost every sector of human activity today. It is and will remain unthinkable to conceive of a type of engineer today or tomorrow without informatics skills. Even if they won’t have to program themselves they have and will have to juggle with the potential of computing.

This potential is inscribed in the foundational state of computer science in that it commands the whole by preceding and situating all other practical aspects. It defines, in advance the horizon and limits evolution to what is or seems technically possible.
So firstly we shall speak od problems and their resolution without worrying about the effective mediation of machines and languages. Secondly we shall study the effective passage of algorithmic solutions brought to machines. This second part will be an introduction to programming.

Objectives

It is precisely these major ideas which constitute the ambition of this course. A course which willingly accepts the comfortable but limiting opposition between theory and practice and aims at an intermediary pedagogical and more binding dimension. We will pay particular attention to the complexity of the studied algorithms.

Duration: 21h


Organization

Scheduled activities

  • C1 (1h30)   Les structures de données
  • PC1 (1h30)   Les arbres binaires de recherche
  • TP1 (1h30)   Structures de données
  • TP2 (1h30)   Structures de données
  • C2 (1h30)   Les tables de hachage et la recherche de chaînes de caractères
  • PC2 (1h30)   Fonction d’adressage - Algorithme de Rabin-Karp
  • TP3 (1h30)   Etude K-means
  • TP4 (1h30)   Etude K-means
  • C3 (1h30)   Les metaheuristiques et l'optimisation combinatoire
  • PC3 (1h30)   Etude d'une metaheuristique pour le problème du routage de véhicules
  • TP5 (1h30)   Etude K-means
  • TP6 (1h30)   Etude K-means
  • TP7 (1h30)   Implémentation d'un algorithme génétique pour le routage de véhicules
  • TP8 (1h30)   Implémentation d'un algorithme génétique pour le routage de véhicules

Team


  C1
  1h30
  PC1
  1h30
  TP1
  1h30
  TP2
  1h30
  C2
  1h30
  PC2
  1h30
  TP3
  1h30
  TP4
  1h30
  C3
  1h30
  PC3
  1h30
  TP5
  1h30
  TP6
  1h30
  TP7
  1h30
  TP8
  1h30
 Sébastien BIGARET      x x     x x     x x x x
 Patrick MEYER  x   x x x   x x x   x x x x
 Sorin MOGA    x       x       x        
 Julie SOULAS    x       x       x        


Educational resource

Transparents de cours. Page moodle du module.

Recommended reading

Bibliographie donnée à l'intérieur des polycopiés:
- Introduction to Algorithms, Third Edition; Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein; MIT Press and McGraw-Hill; ISBN-10: 0262033844; http://mitpress.mit.edu/algorithms/
- Teach yourself Data Structures and Algorithms in 24 hours; Robert Lafore; Sams; ISBN-10: 0672316331


  Year 2018/2019
Last update: 10-JAN-18
Last validation:

IMT Atlantique
Campus de Brest
Technopôle Brest-Iroise
CS 83818
29238 Brest Cedex 3
France

Tél  +33 (0)2 29 00 11 11
Fax +33 (0)2 29 00 10 00