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.

 

PREREQUISITES

  • Algorithms & Data Structures, Automata & Formal Languages

RECOMMENDED COURSES

  • Algorithms & Data Structures 2

 

REFERENCES

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

Persone

 

Sharygina N.

Docente titolare del corso

Asadi S.

Assistente

Marescotti M.

Assistente

Informazioni aggiuntive

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