Titulo Estágio
Design and analyze an algorithm to compute the lattice of organizations in Artificial Chemistry
Área Tecnológica
Sistemas Evol. e Comp.
Local do Estágio
CISUC/ECOS
Enquadramento
The
set of stable sets (organizations) of chemical molecules form a partially
ordered set, or a lattice [1]. Depending on the type of chemical system (if
there is an outflow for each molecule, for example). Note that a lattice is a
partially ordered set, that satisfy special properties [2].
[1]:
Peter Dittrich, Pietro Speroni di Fenizio (2007) Chemical Organization Theory,
Bull. Math. Biol., 69(4):1199-1231, 2007
[2]:
Please refer to:
http://en.wikipedia.org/wiki/Lattice_(order)
[3]:F.
Centler; C. Kaleta; P. Speroni di Fenizio; Peter Dittrich (2008) Computing
Chemical Organizations in Biological Networks Bioinformatics 2008; doi:
10.1093/bioinformatics/btn228
Objetivo
You
should (1) develop an alternative algorithm, that uses those properties for
chemical systems where a lattice is expected, and (2) calculate the complexity
of such algorithm. Even among systems that produce a lattice, the variability
is huge. In reference to this diversity you should also (3) comment on what
kind of systems would the algorithm give particularly good or bad results. If
necessary the supervisor can provide some hints over how this algorithm could
be designed, but this should not stop you from thinking alternative methods.
Plano de Trabalhos - Semestre 1
Phase
1 - Revision of literature and State of the Art.
Phase
2 – Design of a New Algorithm using Lattice properties to shortcut some
calculations
Phase
3 - Code and Test the Algorithm on some well known Artificial Chemistries.
Phase
4 - Elaboration of a proposal for the dissertation.
Plano de Trabalhos - Semestre 2
Phase
5 - Calculation of the complexity of the algorithm, and evaluation of the worse
case, and average case, scenario.
Phase
6 - Analysis of the different kind of systems, which would provide a worse case
scenario, and which would provide a tractable example.
Phase
7 - Writing the Dissertation.
Phase
8 - Writing a scientific article.
Condições
The student must be proficient in Computational Complexity Theory, as well as be able to program well in either Python on C++. An understanding of Algebraic Lattice theory can be useful, but is not a requirement, as the basic concepts that will be needed can be easily absorbed in few days. An ability to read, write and speak in English is paramount as the supervisor only speaks english.
Observações
Orientador
Pietro Speroni di Fenizio e Luis Paquete
speroni@dei.uc.pt 📩