Models of Natural Computing (2014/2015)

Course not running

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

Lesson timetable

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.


Introduction to natural computing

Basic notions and data structures: multisets, sequences, strings, trees, graphs
Formal languages and Chomsky hierarchy
Specific characterization of REG, REC, CF classes
Finite state automata, Turing machines, computational universality and complexity
A nutshell of information theory

Computational models of bio-molecular processes, such as DNA self-assembly
Computational complexity of bio-algorithms
DNA algorithms
Methods to extract genomic dictionaries

Some specific bio-inspired algorithms
Membrane computing, and metabolic grammars
Biological networks

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

Assessment methods and criteria

Midterm written exam, and final oral exam (or seminar, or assignment). Written test will focus on exercises and general questions on the first part of the program, on traditional computational models, while oral exam (seminar or project) will focus on (respectively, a specific topic of) the second part.

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

Teaching aids