Models of Natural Computing (2015/2016)

Course partially running (all years except the first)

Course code
Name of lecturer
Giuditta Franco
Giuditta Franco
Number of ECTS credits allocated
Other available courses
Academic sector
Language of instruction
I semestre dal Oct 1, 2015 al Jan 29, 2016.

Lesson timetable

I semestre
Day Time Type Place Note
Tuesday 8:30 AM - 11:30 AM lesson Lecture Hall A  
Wednesday 8:30 AM - 10:30 AM lesson Lecture Hall C  

Learning outcomes

Main models of natural computing will be presented, in terms of computational processes observed in and inspired by nature. 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. A few computational methods both to elaborate genomic information and to investigate biological networks will be as well explained.

By this course the student is expected to deepen his/her notion of Turing computation and extend it to informational processes involving either natural or bio-inspired algorithms. However, no previous biological or computational specific knowledge is assumed from the student.


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

Basic notions and data structures: multisets, sequences, strings, trees, graphs
Formal languages and grammars, Chomsky hierarchy
Specific characterization of REG, REC, CF classes
Finite state automata, Turing machines, computational universality and complexity
A nutshell of information 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 a couple of NP-complete problems
Metabolic grammars, networks, and computational dynamics

Reference books
Author Title Publisher Year ISBN Note
Vincenzo Manca Infobiotics Springer 2013

Assessment methods and criteria

One midterm written exam (which applies for the first part of the course program) plus one work assignment (for the second). In alternative, a final oral exam may be chosen for the whole program.

Written test will focus on exercises and general questions on traditional computational models, while work assignments will focus on topics of computational genomics (typically dictionary based genomic sequence analysis).

Midterm written test applies only for the exam session in February. In next sessions, only oral exams will be allowed.

Teaching aids


Student opinions - 2015/2016

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

Outcomes Exams Outcomes Percentages Average Standard Deviation
Positive 26.82% 23 4
Rejected 9.75%
Absent 63.41%
Ritirati --
Canceled --
Distribuzione degli esiti positivi
18 19 20 21 22 23 24 25 26 27 28 29 30 30 e Lode
18.1% 9.0% 9.0% 0.0% 9.0% 9.0% 9.0% 0.0% 0.0% 9.0% 18.1% 0.0% 0.0% 9.0%

Data from AA 2015/2016 based on 41 students. I valori in percentuale sono arrotondati al numero intero più vicino.