FDI – Computability (1st semester, 6 ECTS)

Cours : Guillaume Hanrot

TD : Marc De Visme & Pierre Pradic

Chapters :

First computation models:

  • Finite automata / regular languages : deterministic vs non deterministic, equivalence between automata / regular expressions, minisation, limits of regular languages, pumping lemma.
  • Grammars : Chomski’s hierarchy, equivalence context-free / stack, limits of context-free with pumping.

Church-Turing thesis:

  • Turing machines.
  • Equivalence with : recursive functions, lambda-calculus.

Decidable / Undecidable:

  • Undecidable, stopping problem.
  • Theorems: Rice, Kleene.

An introduction to complexity theory:

  • Time-complexity classes, Space-complexity classes, deterministic and non-deterministic classes.
  • Elementary inclusion and separation results.
  • Classes P and NP: certificate-based characterization of NP; Cook’s theorem.

ASR1 – Computer Architecture (1st semester, 6 ECTS)

Cours : Florent de Dinechin

TD : Florent de Dinechin & Guilhem Gamard & Alexandre Talon


  1. History of mechanical computing.
  2. Coding information.
  3. Combinatorial circuits.
  4. Sequential circuits.
  5. Von Neuman architecture.
  6. RISC processors.
  7. Interruptions and shared time.
  8. I/O.
  9. Virtual memory and cache.
  • A. Tanenbaum. Architecture de l’ordinateur. 5e ed., Pearson Education, 2006
  • F. Wahid: Digital Design. Wiley, 2006.
  • Hennessy & Patterson. Computer Architecture: A Quantitative Approach. 3rd ed., Morgan Kaufmann, 2003.

PROG – Programming Languages Theory (1st semester, 6 ECTS)

Cours : Daniel Hirschkoff

TD : Adrien Durier & Alexis Ghyselen & Julien Braine

Programming languages and programs are usually not built as mathematical entities, but rather as technological objets (whose properties can be described as rigorously as possible, in manuals or standards).

This course is about the semantics of programming languages, which provides mathematical tools that make it possible

  • to describe and analyse the statics of programs: what are the constructs made available by the language, what can be read on the code (about the usage of functions, the managment of resources, the risk of errors like division by zero or getting into an infinite loop);
  • to do the same for the dynamics of programs: how a program is supposed to run, what resources are involved at execution time, etc.
  • to discuss translations from a language to another (which is called compilation), and, more generally, to describe programs that manipulate programs.


  • G. Winskel, The semantics of programming languages, MIT Press.
  • J. Reynolds, Theories of Programming Languages, CUP.
  • a web page dedicated to the course will be made available from http://perso.ens-lyon.fr/daniel.hirschkoff

The course consists in 2 hours of lecture per week, together with 2 hours of exercices (on machine, or on paper).

Le cours est organisé selon le schéma hebdomadaire suivant: 2h de cours; 2h de travaux pratiques sur machine; des devoirs à la maison à faire en binôme, un partiel, un examen.

LOG – Mathematical logics (2nd semester, 6 ECTS)

Cours : Natacha Portier

TD : Guilhem Gamard & Alexis Ghyselen

Naive set theory :

  •  Set theory, Cantor-Bernstein.
  • Ordinals, cardinals, well quasi order, Veblen hierarchy.
  • Axiom of choice.

First order theories :

  • First order languages, natural deduction.
  • First order theory, and extensions.
  • Peano Arithmetics (PA), Zermelo-Fraenkel Set Theory (ZF).

Tarski’s models :

  • Structures and isomorphisms
  • Completeness, compactness, Löwenheim-Skolem theorems.
  • Applications to PA and ZF.

Incompleteness theorems  :

  • Undecidability of arithmetics, link with recursive functions.
  • Gödel’s incompleteness theorems.

ASR2 – Operating Systems & Networks (2nd semester, 6 ECTS)

Cours : Michaël Rao

TD : Guilhem Gamard & Rémy Grunblatt & Etienne Moutot


Understanding operating systems and programming applications interacting with the system.


  •  Jean-Marie Rifflet et Jean-Baptiste Yunès, “UNIX : programmation et communication”, Dunod, 2003.
  •  Andrew S. Tanenbaum et Herbert Bos, “Modern Operating Systems, 4th Ed”,Pearson 2015..

English 2 (2nd semester, 3 ECTS)

Cours : Véronique Rancurel, Hélène Windish, Karen Rizo, David Alzapiedi (Veronique.Rancurel)

Ce module  est centré sur l’expression orale et la compréhension orale. Présentation orale, avec transparents, d’un article scientifique (simulation de colloque), apprentissage des techniques et stratégies de communication, anglais du quotidien . Entraînement à la prise de notes à partir de documents vidéo authentiques avec compte rendu écrit.