Natural Computing (2016/2017)

Course code
Name of lecturers
Giuditta Franco, Vincenzo Manca
Giuditta Franco
Number of ECTS credits allocated
Other available courses
Academic sector
Language of instruction
I sem. dal Oct 3, 2016 al Jan 31, 2017.

Lesson timetable

I sem.
Day Time Type Place Note
Wednesday 8:30 AM - 10:30 AM lesson Lecture Hall A from Oct 3, 2016  to Oct 19, 2016
Wednesday 12:30 PM - 2:30 PM lesson Office S72P1CV2 from Oct 19, 2016  to Jan 31, 2017
Thursday 2:30 PM - 5:30 PM lesson Lecture Hall C  

Learning outcomes

The course is designed to first recall basic concepts of traditional computational models, such as formal languages and automata, and then present several models of bio-inspired computing, also including bio-molecular algorithms. Main models of natural computing are presented, in terms of computational processes observed in and inspired by nature.

Some basic notions of discrete mathematics (sets, multisets, sequences, trees, graphs, induction, grammars and finite automata), of calculus, linear algebra and probability, are assumed, to explain a few computational methods both to elaborate genomic information and to investigate biological networks.

The course aims at developing the ability of the student i) to master notions of discrete structures and dynamics, ii) to deepen his/her notion of Turing computation and iii) extend it to informational processes involving either natural or bio-inspired algorithms. Student's knowledge of all the issues presented in class will be tested at the exam, together with his/her learning and understanding skills.


Introduction to natural computing, biological algorithms, and life algorithmic strategies.

Basic notions of discrete mathematics and of formal language theory (Chomsky's hierarchy, automata, and computability).
Elements of information theory (information sources, codes, entropy, and entropy divergences, typical sequences, first and second Shannon's theory).

Methods to extract and analyze genomic dictionaries.
Genomic profiles and distributions of recurrent motifs.
Software IGtools to analyze and visualize genomic data.

Computational models of bio-molecular processes, such as DNA self-assembly and membrane computing.
DNA computing and bio-complexity of bio-algorithms.
DNA algorithms to solve NP-complete problems.
MP grammars, networks, and computational dynamics.

Reference books
Author Title Publisher Year ISBN Note
Garey, M. R. and Johnson, D. S. Computers intractability: a guide to the theory of NP-completeness Freeman 1979 0-7167-1045-5
Gheorghe Paun, Grzegorz Rozenberg, Arto Salomaa DNA computing: new computing paradigms (Edizione 3) Springer 2013
Vincenzo Manca Infobiotics Springer 2013
David G. Luenberger Introduction to Dynamic Systems - Theory, Models, and Applications  
V. K. Balakrishnan Introductory Discrete Mathematics  

Assessment methods and criteria

-- One (unique) written exam is proposed in the last lecture, along with about ten questions which cover the whole program. The exam is passed if a majority of questions is answered correctly, with a final evaluation greater or equal to 18/30.

-- Oral exam, covering the whole program, in each exam session. It is passed with an evaluation greater or equal to 18/30.

Written and oral questions are aimed at verifying the knowledge of theorems and proofs, algorithms and data analysis methods (explained in class), as well as verifying the problem/exercise solving ability of the student, developed in the course. In this context, student's skills of learning, understanding, and communication are tested contextually to his/her knowledge of concepts explained in the course.

Optional homework assignment (project), may be agreed with students who have already passed the (written or oral) exam, in order to increase the final vote with additional marks. It is meant either to deepen some argument of the course, of interest for the student, or to develop software to apply some knowledge assimilated in the course to specific biological systems. This is an opportunity for the student to apply his/her knowledge learnt in the course, by expressing autonomous initiatives.

Teaching aids


Student opinions - 2015/2016

Statistics about transparency requirements (Attuazione Art. 2 del D.M. 31/10/2007, n. 544)

Data from AA 2016/2017 are not available yet