Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

This is an old revision of the document!


Initiation à la recherche

Responsable : Ph. Schnoebelen

Les ateliers commenceront le mardi 17 septembre 2019.

Organisation:

09 septembre: informations disponibles sur cette page web.

16 septembre: envoi de vos préférences pour les 3 ateliers de la première session et les 3 ateliers de la deuxième session. Cf instructions ci-dessous.

16 septembre: décision concernant les inscriptions aux 3+3 ateliers des deux sessions.

17 septembre: début des ateliers de la première session.

12 novembre: début des ateliers de la seconde session.

Joining a Working Group:

On Tuesday 17th, you will be assigned to one of four working groups (WG, “Ateliers” in French) and you will join a second WG mid November.

In order to assign students to WGs, we need to know what are your preferences (see descriptions of the WGs below). For this, please send a short mail to phs@lsv.fr stating what is your order of preference between the available options. Something as short as prefer WG1; otherwise WG2 + prefer WG4; otherwise WG5 is fine.

Also please let us know if you need the WG to be run in English (we don't yet know all of you) and feel free to add any informations or questions you think might be relevant.

The groups will be defined on Monday 16th morning, so we need your preferences by email BEFORE MONDAY 16TH AT 09h00 AM. Anyone who fails to submit his/her preferences in time will be assigned last, to remaining slots.

Présentation générale

Le cours “Initiation à la recherche” (3 ECTS) est une mise en situation dans la position de chercheur. Il se déclinera en 8 ateliers de recherche qui traiteront différents sujets sous la responsabilité d'un encadrant. Chacun des ateliers de recherche vise à développer les compétences suivantes :

- Faire l'état de l'art d'un sujet: déterminer le sujet, la question, les problèmes principaux et secondaires, les problèmes intéressants, faire une recherche bibliographique et retracer l'historique des contributions.

- Déterminer puis formaliser un problème: poser les définitions, énoncer les résultats à trouver, préciser les hypothèses, clôturer le sujet par généralisations et particularisations. Faire le lien avec d'autres problèmes déjà traités dans d'autres contextes.

- Expliquer à son encadrant de stage, à ses collègues une preuve: mettre en évidence les points faciles et difficiles de la preuve, les idées intéressantes et celles classiques. Etre capable aussi de détailler et d'expliciter les points qu'on n'a pas compris.

- Comprendre pourquoi ce sujet, cet article est intéressant: Trouver les enjeux du sujet/problème, expliciter les motivations, déterminer les applications, montrer les problèmes intéressants, dessiner les perspectives.

- Se familiariser avec le métier de chercheur et d'enseignant-chercheur: comment faire un CV et un dossier optimal pour être recruté comme CR/MCF, quelles sont les règles de la communauté scientifique, qu'est-ce que la fraude scientifique, comment et où publier, les institutions et les financements de la recherche, les MOOC, la Khan académie, les conférences TED, les nouvelles façons d'apprendre, les styles cognitifs, savoir enseigner dans le supérieur, la motivation,...etc.

Description: Chaque étudiant suit:

- un atelier 1ère session : du 17 sept. au 22 oct.
- un atelier 2ème session : du 12 nov. au 17 déc.

Chaque atelier est constitué de 6 séances de deux heures et d’une évaluation qui lui est propre. Les thèmes des ateliers proposés sont détaillés ci-dessous.

Planning: chaque mardi après-midi (2 heures) de septembre à décembre. Les plannings de chaque atelier sont fixés définitivement par le responsable de l'atelier.

Salle: Les salles réservées pour les ateliers sont C311, C402, C419, et C522 du bâtiment Cournot de l'ENS-P-S.

Évaluation: L'évaluation est précisée dans le descriptif de chaque groupe de travail.

Ateliers 1ère session: du 17 sept. au 22 oct.

WG1 Atelier “Distributed synthetic microbiology” / M. Függer

Encadrant: Matthias Függer.

Langue: Anglais

Salle: TBA

Mots clés: distributed systems, microbiology, synthetic biology, circuit design, dynamic systems

Description: The course is organized as a short research project. The course starts with a brief introduction into synthetic microbiological systems. We will then study such systems form a circuit design and distributed computing point of view.

Previous knowledge in microbiology, circuit design, or distributed computing is not obligatory.

Les objectifs pédagogiques: The objective is to learn to work within a scientific team. The team will choose a currently open research question, investigate the state-of-the-art and try to tackle the question. Work includes: organization of research meetings on existing work and new ideas and writing a research paper.

Estimation du volume de travail personnel demandé: Approximately 5h/week (2h/week in class).

Participants:

News:

  • Don't forget to write me a subscribe mail for the course.

Planning: Team meetings are announced here. Check this page regularly for updates.

  • Sept. 17, 14.00-16.00: Organization and Preliminaries
    • Initial presentation of research area
    • Todo until next time:
      • Write me a subscribe mail
  • Sept. 24, 14.00-16.00: Discussion of research questions in class
  • Oct. 1, 14.00-16.00: tba
  • Oct. 10, 14.15-16.00: tba
  • Oct. 15, 14.15-16.00: Meeting shifted to ... (tba)
  • Oct. 22, group-wise, 1h each: final presentations

Modalités d'évaluation: Students will be evaluated based on their involvement during team meetings (50%), and final writeup (50%).

WG2 Atelier “Loop-elimination in FIFO automata” / Ph. Schnoebelen

Encadrant: Philippe Schnoebelen.

Langue: English as soon as one participant is not fluent French speaker. All documents will be in English.

Salle: TBA.

Mots clés: theory of automata, computer-aided verification of programs.

Description: By loop-elimination we mean computing the effect of repeating a sequence of instructions an arbitrary number of times. Loop elimination is possible for FIFO automata (Boigelot & Godefroid 1999, Bouajjanni & Habermehl 1999) and for lossy FIFO automata (Abdulla et al., 2004). The goal of this working group is to try to extend these two results by developping a common generalization. In summary we will tackle an open problem in theoretical computer science. The group will meet weekly and will use emails, chats, .. for exchanges between two meetings.

Les objectifs pédagogiques: The working group will be an opportunity for attacking a research problem while working *as a group*. We will see how tasks like bibliographical research, understanding complex results, inventing new techniques, validating them, writing down proofs, checking the proofs, can be done collectively.

Les attentes individuelles et collectives: It is expected that each participant will contribute his/her ideas, time & energy, ensuring group success.

Estimation du volume de travail demandé: at least 5 hours per week (including the weekly meetings).

Participants: TBA

Planning: Six meeting on Tuesday at 14h, starting Sep 17th.

Modalités d'évaluation: Each participant will receive a mark made of (50%) the superviser's assessment of his/her contributions to the common project, and (50%) the superviser's assessment of the quality of his/her oral presentations and written material.

WG3 Atelier “Game theory/positional strategies” / S. Le Roux

Encadrant: Stephane Le Roux.

Langue: French or English as soon as it is better for one student.

Salle: TBA.

Mots clés: Bibliography, search of existing (or new) proofs of famous results, comparison of their respective advantages.

Description: We will consider games that are specially studied in computer science: with two players, on (finite) graphs, played in turns. Many such games have simple winning strategies that are called positional (aka memoryless). We will review (and improve?) different proof techniques and present them to each other. We will write a report of 4-5 pages.

Les objectifs pédagogiques: writing a bibliography; teaching each other via oral presentations and written documents; thinking together via brain storming; comparing the advantages of different proofs of the same theorem; setting scientific objectives; summarizing what we know; Sharing the workload in a fair way.

Les attentes individuelles et collectives: we are a team, i.e. individual work is a basis for collective success.

Estimation du volume de travail demandé: about five hours per week outside of the classroom.

Le travail sera: partly individual and partly collective, depending on the team and the specific situations we will face.

Participants: TBA

Planning: 6 réunions hebdomadaires le mardi de 14h à 16h, début le 17 septembre 2018.

Modalités d'évaluation:

  1. Each group/student will write (part of) an existing proof in their own words (15%) and present it orally to the others (25%).
  2. Each student is expected to take part in the discussions in the classroom (20%)
  3. The students will collectively or individually try to find new proofs (20%)
  4. The students will collectively write a short bibliography and a summary of the proofs we will know by the end of the workshop (20%)

WG4 Atelier “Shor's algorithm, and beyond” / C. Fontaine

Encadrante: Caroline Fontaine.

Langue: English as soon as one participant is not fluent French speaker. All documents will be in English.

Salle: TBA.

Mots clés: security, quantum cryptanalysis and post-quantum cryptography

Description: Encryption schemes as RSA or AES ensure today's messages confidentiality. In 1994, Peter Shor proposed a surprising algorithm showing that, with a quantum computer, could drastically decrease the complexity of factoring large integers, and thus the complexity of breaking RSA keys. Starting from this article, we will explore when such computers may speed up cryptanalysis, and when they cannot. This study does not require any knowledge in quantum computing nor physics. Depending on how fast and far the work will progress, we can also study some post-quantum encryption schemes. This is a very hot topic in today's research in cryptography. The goal is not to contribute to the state-of-art, but to understand why and how this article, with some others, is strongly modifying current and future cryptographic tools.

Les objectifs pédagogiques: to explore and build a bibliography, to present articles and ideas to the team, to write a survey, to build a collective understanding and analysis about the core and the impact of the algorithms.

Les attentes individuelles et collectives: there will be a mix of personal and collective contributions, as we will progress as a team.

Estimation du volume de travail demandé: around 5 hours per week (including the weekly meetings).

Participants: TBA

Planning: Six meeting on Tuesday at 14h, starting Sep 17th.

Modalités d'évaluation: 50% for collective involvement during the discussions, and 50% for personal contribution (presenting/writing, looking for new related articles)

Ateliers 2ème session: du 12 nov. au 17 déc.

WG5 Atelier “Understanding a Research Topic / Practice of State of the Art and Bibliography” / Th. Chatain

Teacher: Thomas Chatain

Language: French by default, English on request

Room: TBA

Mots clés: State of the art, synthesis, bibliography, identification of new research problems

Description: Every group of two students digs, from a recent research article, the state of the art of the research topic, understands and explains the interest of the contribution in regard to the major works in the field. They also propose ideas for new research in the area.

Pedagogical objective: Practice of bibliography and state of the art, become familiar with the style and contents of introductions of scientific articles, understand the life of a scientific community (major conferences, topics of interest...)

Workload: around 5 hours per week in addition to attending the sessions.

The research topic will be chosen by the students and validated by the teacher.

Participants:

Planning: every Tuesday from November 12 to December 17, 14:00-16:00

Evaluation: 1/4 bibliography, 1/4 synthesis of results and identification of research questions, 1/4 presentation, 1/4 write an introduction to an article

WG6 Atelier “Cell Fate prediction: The Boolean Approach” / Stefan Haar

Encadrant: Stefan Haar.

Langue: Anglais

Salle: TBA

Mots clés: bibliographie; bioinformatics

Description: In this module, the students will study the state of the art in the interdisciplinary field of epigenetic prediction. The problem is: derive, from available knowledge about a cell's regulatory network, what are the accessible phenotypes, and potentially what are the factors that decide between those. Based on selected authoritative articles - complemented by their own literature search where appropriate - from systems biology and from formal bio-informatics (boolean networks), they are expected to cooperate for preparing a sound and comprehensive in-class presentation of the topic.

Participants:

Planning: 4-5 réunions hebdomadaires le mercredi de 14h à 16h, début le 7 ou 22 novembre 2018 (les dates seront précisées ultérieurement).

Modalités d'évaluation:

  • 40% contrôle continu;
  • 60% présentation (~30min) ou équivalent.

Articles (further reading will be announced later):

WG7 Atelier “Autour d’un article scientifique fondateur” / L. Fribourg

Encadrant: Laurent Fribourg

Langue: Français sauf si anglais demandé

Salle: TBA

Description: Le but du groupe de travail est, à partir d’un article fondateur remontant à une dizaine d’années, de donner des clés permettant de :

  1. comprendre en quoi l’article a effectué une percée dans le domaine
  2. identifier certains papiers postérieurs ayant poursuivi significativement l’avancée
  3. entreprendre l’écriture d’un survey sur cette lignée de travaux.

La démarche est représentative d’une activité de base du chercheur qui s’intéresse à un nouveau sujet de recherche, et examine la littérature pour :

  • synthétiser les idées récentes,
  • cerner les difficultés sur lesquelles on bute aujourd’hui,
  • dégager des pistes auxquelles il pourrait contribuer.

Cette démarche aidera également l’étudiant à exposer synthétiquement son propre domaine de recherche en affirmant sa hauteur de vue sur les travaux passés et sa vision des enjeux à venir.

L’article fondateur étudié cette année est : F. Cucker and S. Smale. Emergent behavior in flocks. IEEE Trans. Automat. Control 52, 852-862, 2007.

Planning (indicatif):

  • séance 1 : je présente le contexte scientifique dans lequel s’inscrit l’article
  • séance 2 : l’article fondateur est présenté par un binôme et discuté.
  • séances 3-4-5 : quelques travaux remarquables dans le prolongement de l’article fondateur, sont identifiés et présentés par des binômes.
  • séance 6 : un panorama de synthèse est rédigé collectivement.

WG8 Atelier “Game theory/poker games” / S. Le Roux

Encadrant: Stephane Le Roux.

Langue: French or English as soon as it is better for one student.

Salle: TBA.

Mots clés: Bibliography, search of existing famous results.

Description: We will start from a simple poker game by von Neumann and Morgenstern, search the literature for more complex variants, and try to understand whether games with imperfect information can always be solved (efficiently). We may try to find or define ourselves a variant that has simple solutions, or implement an existing solution algorithm. We will write a short report.

Les objectifs pédagogiques: writing a bibliography; teaching each other via oral presentations and written documents; thinking together via brain storming; building informative toy examples; setting scientific objectives; summarizing what we know; Sharing the workload in a fair way.

Les attentes individuelles et collectives: we are a team, i.e. individual work is a basis for collective success.

Estimation du volume de travail demandé: about five hours per week outside of the classroom.

Le travail sera: partly individual and partly collective, depending on the team and the specific situations we will face.

Participants: TBA

Planning: 6 réunions hebdomadaires le mardi de 14h à 16h, début le 12 novembre 2018.

Modalités d'évaluation:

  1. Each group/student will write (part of) an existing proof in their own words (15%) and present it orally to the others (25%).
  2. Each student is expected to take part in the discussions in the classroom (20%)
  3. The students will collectively or individually try to find new proofs (20%)
  4. The students will collectively write a short bibliography and a summary of the proofs we will know by the end of the workshop (20%)

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA