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

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-11-1 [2019/10/11 08:22]
schabanel [Approximation Algorithms& Molecular Algorithms(2019/2020, 8x3h, 3 ECTS)Wednesdays 8:45-11:45 Room SG1014]
cours:c-2-11-1 [2019/11/01 15:25] (current)
schabanel [Approximation Algorithms& Molecular Algorithms(2019/2020, 8x3h, 3 ECTS)Wednesdays 8:45-11:45 Room SG1014]
Line 10: Line 10:
 ** <color gray>Molecular programming</color> ** ** <color gray>Molecular programming</color> **
   * <color gray>Lecture 5: Wed 9 OCT //Molecular algorithms 1/4//</color>   * <color gray>Lecture 5: Wed 9 OCT //Molecular algorithms 1/4//</color>
-  * Lecture 6: Wed 16 OCT //Molecular algorithms 2/4// +  * <color gray>Lecture 6: Wed 16 OCT //Molecular algorithms 2/4//</color> 
-  * Lecture 7: Wed 23 OCT //Molecular algorithms 3/4//+  * <color gray>Lecture 7: Wed 23 OCT //Molecular algorithms 3/4//</color>
   * <color gray>// No lecture on Wed 30 OCT //</color>   * <color gray>// No lecture on Wed 30 OCT //</color>
   * Lecture 8: Wed 6 NOV //Molecular algorithms 4/4//   * Lecture 8: Wed 6 NOV //Molecular algorithms 4/4//
 ** <color gray>Final exam</color> ** ** <color gray>Final exam</color> **
-  * <color gray>// No lecture on Wed 13 OCT //</color> +  * <color gray>// No lecture on Wed 13 and 20 OCT //</color> 
-  * <color purple>**Final Exam: Wed 20 or 27 NOV**</color>+  * <color red>**Final Exam: Wed 27 NOV 8:45-11:45**</color>
  
 ---- ----
Line 25: Line 25:
  
 Lectures will take place every **Wednesdays 08:45-11:45 in room SG1014** starting on 11/9.  Lectures will take place every **Wednesdays 08:45-11:45 in room SG1014** starting on 11/9. 
 +
 +----
 +
 +Internship proposals:
 +  * :!: **__2020 M2 Internship proposal:__ [[http://perso.ens-lyon.fr/nicolas.schabanel/stage/2020_M2_Internship.pdf|DNA computing: Theory, Models and wet lab experiments]]**
 +
 +----
  
 ==== Goals ==== ==== Goals ====
Line 131: Line 138:
 ==== Course Summary 2019-20: Molecular programming  (Lectures 5-8) ==== ==== Course Summary 2019-20: Molecular programming  (Lectures 5-8) ====
  
-**Lecture 5: Introduction to DNA programming & Tile Assembly Systems [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture1.pdf|Slides]] ]**+**Lecture 7 (2019.10.23): Universality in assembly Model (II): experiment, intrinsic universality and Oritatami** 
 +  * **An experimental realisation of a universal computer (II) [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture2B.pdf|Slides (again)]] ]** 
 +    * Examples of nanotube circuits 
 +    * A 6-bits Turing universal nanotube circuit 
 +    * Minimizing errors with proof-reading tiles 
 +    * Counting the glues 
 +    * Sequence design 
 +    * Experiment results 
 +  * **Intrinsic Universality in tile assembly model [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture3A.pdf|Slides]] ]** 
 +    * Intrinsic universality at T°2 
 +    * The supercell, the probes 
 +    * One (polygonal) tile is enough 
 +  * **Oritami: a computational model for co-transcriptional folding [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture3B.pdf|Slides]] ]** 
 +    * RNA co-transcriptional folding 
 +    * Oritatami model 
 +    * A first example: a binary counter 
 +    * Proving its correctness 
 +    * Rule design is NP-hard but FP-tractable 
 +    * Oritatami is Turing complete 
 +    * Simple intrinsic Oritatami simulation of cellular automata 
 +  * **Exercise sessions [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW3.pdf|HW3]] ]** 
 +    - :!: Window movie Lemma //**return your solution to questions 1.1 and 1.2 by Wed Nov 6 before 11:45**// 
 + 
 +**Lecture 6 (2019.10.16): Universality in assembly Model (I): Theory and experiment** 
 +  * **Universality in assembly Model (I) [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture2A.pdf|Slides]] ]** 
 +    * Simulating a Turing machine at temperature T°=2 in aTAM 
 +    * Optimal hardcoding of a binary string at T°=2 in aTAM 
 +    * Simulating a Turing machine at temperature T°=1 in aTAM in 3D 
 +  * **An experimental realisation of a universal computer (I) [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture2B.pdf|Slides]] ]** 
 +    * Single stranded tile nanotubes 
 +    * Atomic Force Microscopy (AFM) 
 +    * Marking 0s and 1s using biotin-streptavidin 
 +    * kTAM kinetic assembly model 
 +    * Error correction using proof-reading tiles 
 +    * DNA nanotube circuit model  
 +  * **Exercise sessions [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW2.pdf|HW2]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW2-SOL.pdf|Solutions]] ]** 
 +    - Staged self-assembly (from HW1) 
 +    - Exponential random variables and kTAM implementation 
 +    - :!: Tileset for simulating cellular automata   
 +    - Probabilistic simulation of Turing Machine at T°=1 in 2D 
 + 
 +**Lecture 5 (2019.10.09): Introduction to DNA programming & Tile Assembly Systems [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/Lecture1.pdf|Slides]] ]**
   * Introduction to DNA programming & overview of the field   * Introduction to DNA programming & overview of the field
   * Abstract tile assembly systems:   * Abstract tile assembly systems:
     * Definition     * Definition
     * Minimizing the assembly time     * Minimizing the assembly time
-  * **Exercise sessions [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW1.pdf|HW1]] ]**+  * **Exercise sessions [ [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW1.pdf|HW1]] | [[http://perso.ens-lyon.fr/nicolas.schabanel/enseignement/MPRI/2019-2020/HW1-SOL.pdf|Solutions]] ]**
     - Guess the assembly 1     - Guess the assembly 1
     - Guess the assembly 2     - Guess the assembly 2
-    - :!: A binary counter //**return your solution by Wed Oct 16 before 11:45**//+    - :!: A binary counter
     - Staged self-assembly     - Staged self-assembly
     - Assembly time = O(rank of the produced shape)     - Assembly time = O(rank of the produced shape)
 
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