Ricerca di contatti, progetti,
corsi e pubblicazioni

Theory of Computation

Descrizione

The class introduces the fundamental mathematical properties of computer hardware, software, and certain applications thereof. It explores what can and cannot be solved on a computer, how quickly, with how much memory, and on which type of computational model. The class is divided into two major parts: computability theory and complexity theory. Computability theory deals primarily with the question of whether a problem is solvable at all on a computer. Complexity theory considers how efficiently the problem can be solved. Two major aspects are considered: time complexity and space complexity, which respectively address a problem of how many steps does it take to perform a computation, and how much memory is required to perform that computation. The subjects have strong connections with engineering practice. Practical exercises will involve experimentation with various tools.

 

 

REFERENCES

  • Introduction to the Theory of Computation; Michael Sipser, 2006, second edition (Required)

Persone

 

Sharygina N.

Docente titolare del corso

Benedusi P.

Assistente

Blicha M.

Assistente

Informazioni aggiuntive

Semestre
Primaverile
Anno accademico
2018-2019
ECTS
6
Lingua
Inglese
Offerta formativa
Bachelor of Science in Informatics, Corso a scelta, Corso, 3° anno