Algorithm and Complexity

Objectifs pédagogiques

The goal of this course is to present the analysis of classical algorithms in the first part. The second part will present ‘hard’ problems, meaning problems that are difficult to solve, and their related complexity classes.

Description du cours

  • Algorithm Analysis, Complexity
  • Data Structures: Heap and Tree
  • Graph algorithms
  • Turing Machine, Computability
  • Reduction between hard problems
  • Complexity Classes (Time, Space)

Mots-clés

Analysis of Algorithms, Complexity, Reductions, Hard problem.

Prérequis

Algorithms will be coded in C.

Bibliographie

  • Introduction to Algorithms (3rd edition), by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, 2009
  • Introduction to the Theory of Computation (3rd edition), by Michael Sipser, 2012

Biographie de l’enseignant

Pierre-Alain Fouque is a Researcher Professor at the University of Rennes 1 and the Scientific Director of the CyberSchool. His research involves symmetrical public-key cryptography, proof of security protocols used in real life such as TLS or Signal, attacks by auxiliary canals, and the development of automatic attack detection tools by learning. His research is carried out at IRISA.

Ce site utilise des cookies afin d’améliorer votre expérience utilisateur et de réaliser des statistiques d’audience.
J'accepteJe refuseEn savoir plus