Computer algebra

Contents of the course

  • Gcd and extended Gcd : Euclidean algorithm, Extended Euclidean Algorithm (complexity analysis, properties), quasi-linear gcd (Knuth-Schonhage).
  • Algorithms for polynomials : evaluation, interpolation. Product tree. Quasi-linear algorithms for multiple point evaluation and interpolation.
  • Algorithms for linear algebra : Gauss pivoting (over a field), applications (image, kernel, determinant, linear system solving) ; multimodular methods and Hensel lifting over Z and K[X].
  • Elimination theory and resultant. Applications to the computation of theintersection of two plane algebraic curves.
  • Polynomial factoring over Z/pZ : Berlekamp algorithm, Cantor-Zassenhaus algorithm, Hensel lifting over Z/p^k Z.
  • Application to Error-Correcting Codes : Reed-Solomon codes. Decoding algorithms, list decoding algorithms.
  • (… to be completed)

See the french version of this page for informations about the organisation of this course.

Cryptography and Security

Course contents:

Cryptography aims at securing communications against malicious parties.  This field enjoys numerous links with theoretical computer science (complexity theory, security proofs) but has also a very rich practical counterpart: Cryptographic protocols are part of every-day life (electronic commerce, payment cards, electronic voting, etc).
This course is an introduction to the different facets of modern cryptography. The following topics will be addressed:

  • Symmetric encryption
  • Asymmetric encryption
  • Cryptographic hashing
  • Authentication
  • Pseudo-random number generators
  • Zero-knowledge proofs
  • Public-key infrastructure
  • Cryptanalysis
  • Provable security
  • Secret sharing

We will also describe several practical applications, such as PGP, TLS/SSL and electronic voting.

Evaluation sheet.

Teaching staff

Program analysis and systems verification

Contents of the course

  • Ordered structures and Topologies. Scott domains. Denotational and Axiomatic semantics. Abstract interpretation.
  • Principles of model-checking. kripke structures and Büchi automata. Temporal logics (LTL, CTL, …).

Practical matters related to the organisation of the course will be presented at the first course.

People in charge:

Parallel algorithms and parallel programming

Program

Parallelism is now ubiquitous in computers because all modern computers contain multicore processors. This lecture series focuses on the design of efficient parallel algorithms and on their actual implementation. The lectures will deal with the theoretical models used to design and analyze parallel algorithms. A number of classical algorithmic problems will be studied in details: complexity study, algorithm design and analysis, approximation algorithms, etc. The lectures will be supplemented with six exercise sessions, and six laboratory sessions. The aim of the lab sessions is to introduce students to parallel programming through message passing (MPI).

Overview

  • The theoretical model of sorting networks
  • The theoretical model of PRAMS
  • Algorithms on processor rings and processor grids: vector-matrix product, matrix-matrix product, 2D stencils, etc.
  • Taks graph scheduling, with and without communications, with and without resource constraints: complexity, approximation algorithms, and heuristics
  • Dependence analysis and automatic parallelization
  • Introduction to algorithms for GPUs

Students will be graded through a final examination and a continuous assessment. The continuous assessment will comprise both a mid-term examination and a programming homework.

Teachers

Performance evaluation

Description :

This course presents basic tools for qualitative and quantitative performance evaluation of communication and computing systems. It is a
theoritical course but some real systems will be analyzed such as communication networks. This course will also present an introduction to
statistics and some discussions about the experimental method.

Plan of the course :

  1. Short refresher about probability prerequisites
  2. Simulation schemes and random generation
  3. Discrete time Markov chains
  4. Continuous time Markov chains and queuing theory
  5. Markovian decision process
  6. Petri nets
  7. Statistics

Prerequisites :

A classical but strong background in probability is necessary (like some knowledge about finite state Markov chains or convergence of random  variables).

People in charge of the course:

  • Eric Thierry (a web page dedicated to the course will be made available from E. Thierry’s page).
  • Julien Herrmann

Distributed Systems

Program

This lecture focuses on algorithmic for distributed systems. We will introduce distributed algorithms to solve communication problem, resource allocation, synchronization, … Thus leader election problems, waves algorithm, termination, routing, fault tolerance, self-stabilization, etc. are some examples that we will see  during the lecture. Different kind of distributed system programming and implementation will be studied through ERLANG, CORBA or the DIET middleware.

Speakers

Language

English upon request.