Algorithms I

Teacher: Anne Benoit (Anne.Benoit)

Teaching language: French

Abstract:

This course is an in-depth introduction to the design and analysis of algorithms, the very heart of computer science. Topics covered include design techniques, complexity analysis, NP-completeness, several paradigms (divide-and-conquer, greedy algorithms, etc), and numerous examples.

Bibliography:

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, The MIT Press, 1990. Version française: Introduction à l'Algorithmique, 2e édition, Dunod, 2004.

Architecture, networks and system I

Teacher: Florent de Dinechin (Florent.de.Dinechin)

Teaching language: French

Abstract:

The purpose of this course is to provide a solid understanding of the inner working of a contemporary computer, in both hardware and oerating system aspects. Topics surveyed include: Coding, storing and transmitting information; Basic arithmetic; The von Neumann processor; The RISC processor; Operating systems basics. This course may also includes an initiation to VLSI CAD.

Prerequisites: None

Bibliography:

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

Computer Science Foundations I

Teacher: Michel Morvan (Michel.Morvan)

Teaching language: French

Abstract:

Prerequisites: None

Bibliography:

Programming I

Teacher: Daniel Hirschkoff (Daniel.Hirschkoff)

Teaching language: French

Abstract:

This course is an in depth introduction to programming and programming languages. It is essentially based on the OCaml language, but it also covers aspects of C programming, as well as, occasionally, other languages. Topics discussed will include imperative vs functional programming, control flow in programs, modularity and software engineering, type systems, and aspects of program compilation. Time allowing, more advanced questions or current topics in programming language research will be treated.

Prerequisites: None

Bibliography:

• the OCaml programming language: caml.inria.fr
• Brian W. Kernighan et Dennis M. Ritchie. Le langage C, norme ANSI (english title: "The C programming language"). Dunod, 2000 (1992). Traduit de l'américain.
• Emmanuel Chailloux, Pascal Manoury, et Bruno Pagano. Développement d'applications avec Objective Caml. Éditions O'Reilly, Paris, avril 2000.
• Guy Cousineau et Michel Mauny. Approche fonctionnelle de la programmation. Ediscience international, 1995. Site à consulter:
• AV Aho, R. Sethi, and JD Ullman, Compilateurs: principes, techniques et outils, InterEditions, 1989
• Harold Abelson and Gerald Jay Sussman. Structure and interpretation of computer programs. The MIT Press, McGraw-Hill, 1995. Existe aussi en français. Site à consulter:
• une page web liée au cours sera disponible à partir de l'adresse http://perso.ens-lyon.fr/daniel.hirschkoff

Programming project

Teacher: Eddy Caron (Eddy.Caron)

Teaching language: French

Abstract:

The goal of this project course is to have the students implement a programming language. This means writing a program that accepts a source file written in a given programming language, and execute the program containted in the source file.

A certain number of possible languages will be offered by the teacher, but students may also think of their own language. Depending on the skills of the students, and of the kind of language being studied, implementing the language can mean writing an interpreter (possibly enhanced with features like static analysis algorithms), or writing a compiler (with, e.g., emphasis on optimisations).

Prerequisites: None

English 1.1

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

Abstract:

Men of Science, Science in the service of Mankind, this will be our leading theme throughout the first semester. Students will be streamlined into four groups and will develop the four skills (written comprehension, written expression, oral comprehension, oral expression), with special emphasis on oral skills.

Prerequisites: There are several groups according to the initial level of the students.

Algorithms II

Teacher: Pascal Koiran (Pascal.Koiran)

Teaching language: French

Abstract:

Advanced Course on Algorithms. This course is focused mostly on graphs (basic theory and algorithms). It also offers a short introduction to linear programming.

Bibliography:

• Introduction to Graph Theory (West) for graph theory and some algorithms.
• Algorithms (Dasgupta - Papadimitriou - Vazirani) for algorithms and linear programming.

Prerequisites: Basic course on Algorithms corresponding to the first chapters of Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein).

Architecture, networks and system II

Teacher: Eric Fleury (Eric.Fleury)

Teaching language: French

Abstract:

The first ASR course leaves us with a simple, generic processor-memory system. This second courses focus on problems to design OS. How to manage system resources in this context. We will deal with process management, primary memory management, file system, secondary memory management, security... We illustrate these problems with different kind of operating system. The second part of ASR2 studies network aspects linked with OS. the third part based on both previous conclude with distributed operating system topic.

Prerequisites: ASR I

Bibliography:

• Principes des systèmes d'exploitation, Abraham Silberschatz, Peter B. Galvin, Addison-Wesley, 4^e édition, 1994.
• Distributed Operating Systems, Andrew S. Tanenbaum, Prentice Hall, 1995.
• Computer Networks, Andrew S. Tanenbaum, Prentice Hall, 3^e édition, 1996.

Computer Science Foundations II

Teacher: Natacha Portier (Natacha.Portier)

Teaching language: French

Abstract:

Prerequisites: None

Bibliography:

• René Cori et Daniel Lascar, Logique mathématique, Tome I, Dunod 2003
• René Cori et Daniel Lascar, Logique mathématique, Tome II, Dunod 2003
• Youri Matiiassevitch, Le dixième problème de Hilbert, Masson, 1995

Programmation II

Teacher: Philippe Audebaud (Philippe.Audebaud)

Teaching language: French

Abstract

The aim of this course is to complete student knowledge about programming and programming languages. We will try to understand how a program is verified and proved to be correct and how languages work, that is how they are implemented and what they mean (one says «what their semantics is»). We will say more on types and on object oriented languages.

Prerequisites: Programming I

Bibliography:

• F. Baader et T. Nipkow. Term Rewriting and All That. Cambridge University Press, 1998.
• Hankin; Lambda Calculi: a Guide for Computer Scientists, Oxford U. Press, 1994.
• C. Livercy. Théorie des Programmes (schémas, preuves, sémantique). Dunod, 1978. http://www.ens-lyon.fr/LIP/REWRITING/OLD_PUBLICATIONS_ON_LESCANNE/Livercy/
• G. Winskel, The formal semantics of programming languages: an introduction. MIT Press, 1993.

Constructing a Compiler

Teacher: Paul Feautrier (paul.feautrier)

Teaching language: French

Abstract:

In this course, the student will acquire the necessary knowledge for constructing a simple compiler:

• Syntax analysis, Lex and Yacc
• Design and use of an internal representation. Symbol Tables
• Organization of the target code
• Code generation.

The student will then apply this knowledge to the construction of a compiler for a toy languge, a simplified Pascal.

Prerequisites: Basic algorithmics, knowledge of at least one high level programming language

Bibliography:

• Aho, Sethi, Ullman. Compilers: theory, techniques and tools. Addison Wesley, 1996

English 1.2

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

Abstract:

Oral expression centred on an oral presentation of a scientific article (with slides) (as for a colloquium). Techniques and strategies for oral communication and day to day English. Oral comprehension: work on video extracts. The aim is to learn how to take down notes and to write a documentary summary (structured account of a four-minute video).

Prerequisites: There are several groups according to the initial level of the students.