• We are currently looking for masters students in Grenoble to implement the "Quantum Game of Life" as their masters project for this academic year.
• If you are interested, please or look at the Masters Project description.

From 2009 to 2010 I was involved in the teaching labs for Programmation 1 (L3, Functional Programming) and assistant lecturer of the new module Introduction à l'Informatique Théorique (M2, Introduction to theoretical computer science).

• Course homepage
• Lecture 1: Graph Theory

  Starting with Euler's solution to the Seven Bridges of Königsberg problem, we discussed the main definitions and concepts used in graph theory. Exercises included Tournament graphs and Kings, and the handshake problem (couples variant).

• Lecture 2: Finite Automata and Regular Languages

  Topics covered in this lecture included DFAs and NFAs, (including the extended transition function), and regular expressions and the relationship between FAs and REs. We also covered the Pigeonhole principle, and how to show a language isn't regular using the Pumping lemma. We also looked at palindromes. All exercises are included in the updated slides.

• Lecture 3: Turing Machines

  In this lecture we covered the formal definition of Turing Machines, their transition function, and Instantaneous Descriptions (IDs). The notions of acceptance and decidability for TM were briefly presented. We also looked at Non-Deterministic Turing Machines (NTMs), and equivalence. Variations such as multi-tape and multi-track machines were also discussed and shown to be equivalent to the standard TM. We finally discussed the Busy Beaver function and its implications, using a TM simulator. There was also a short discussion of quantum computing.

• Lecture 4: Recursion and the Halting problem

  In this session we looked at total and partial functions, and recursion. Using Haskell notation we defined the factorial and Fibonacci functions using recursion and pattern matching. We then analysed the properties the McCarthy 91 function, and developed inductive proofs of its behaviour. We then discussed and proved the undecidability of the Halting problem, and the relation to the Busy Beaver 'S' function. Lastly, we discussed and sketched a proof of Rice's theorem, and the need to be careful in forming statements.

• Lecture 5: (Reversible) Quantum computation

  In this lecture we covered quantum computation, specifically the quantum circuit model. We started with a historical overview, discussing Shor's factorisation algorithm and Grover's Quantum Database Search. (Notes 1)
  We then developed a circuit model of classical, finite, reversible computation - using Tofolli and Fredkin gates, and a discussion of Maxwell's demon. (Notes 2) The basic linear algebra needed for quantum computation was then presented, followed by a development of the quantum circuit model. Lastly, the Deutsch algorithm was presented and analysed. (Notes 3)

  Further reading: A full development and description of Shor's algorithm can be found here, and a continuation of the above notes, including a full formalisation of irreversible quantum computation and the functional quantum programming language QML, is given in my thesis.

• Lab exercise sheets can be found here