Where and when: Room 14 at Institut Fourier, on Wednesday.
Prerequisites: Nothing strictly required.
Objective: Describing objects by discrete structures has many advantages, but makes all the more clear the limits of our understanding. For instance, one can compute easily presentations of fundamental groups of simplicial complexes, but in general, determining whether this group is trivial is impossible (undecidable). This course proposes an algorithmic approach to treat, in favorable cases, some fundamental problems in topology, often interpreted in terms of problems in fundamental groups. These problems are the homotopy between curves, the existence of homeomorphisms between spaces, and the triviality of a knot. The case of surface groups will be important to us.
The first part will be dedicated to basics notions on algorithms and complexity and on combinatorial group theory. The viewpoint will remain elementary and will be motivated by topological and algorithmic problems on graphs and surfaces.
Tentative plan for this part:
Course notes:
Validation: Midterm and final exam.