logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2014/2015
Scuola Scuola di Ingegneria Industriale e dell'Informazione
Insegnamento 089181 - THEORETICAL COMPUTER SCIENCE
Docente Morzenti Angelo Carlo
Cfu 5.00 Tipo insegnamento Monodisciplinare

Corso di Studi Codice Piano di Studio preventivamente approvato Da (compreso) A (escluso) Insegnamento
Ing Ind - Inf (Mag.)(ord. 270) - MI (434) INGEGNERIA INFORMATICA* AZZZZ089181 - THEORETICAL COMPUTER SCIENCE
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA* AZZZZ089181 - THEORETICAL COMPUTER SCIENCE

Programma dettagliato e risultati di apprendimento attesi

Goals of the course

Computer science has undergone a very rapid evolution from its start until today. This has brought significant benefits to the quality of life but has also created problems with the reliability of computer based systems. In many cases, in fact, the adopted design techniques proved to be inadequate to the complexity of the addressed problems.

Among the causes of the unsatisfactory reliability of computer systems one of the most frequently mentioned is the lack of a solid theoretical background on which effective design techniques must be founded.

The goal of the course of Theoretical Computer Science is to fill this gap by addressing systematically the fundamental problems of computer science and showing that a rigorous approach based on the theoretical foundations of the discipline has a great relevance on practical applications.

 

The course covers the following topics:

1. The models of Computer Science

· Automata (finite state and stack automata, Turing Machines)

· Grammars

· Nondeterministic models

· Use of mathematical logic for modeling systems and describing their properties: relations between logic, languages and automata.

2. Computation theory

· Power of the models of computation

· Church Thesis

· Undecidable problems

· Techniques for proving undecidability

3. The complexity of computing

· Fundamental notions of complexity analysis

· Models of computation and relations among their computational complexity

· Linear speed-up. Complexity hierarchies.

· Hints towards intractable problems and NP-completeness.


Note Sulla Modalità di valutazione

The exam is based on written questions, possibly integrated, upon request by the teacher, by a further oral interrogation.


Bibliografia
Risorsa bibliografica obbligatoriaDino Mandiroli, Carlo Ghezzi, Theoretical foundations of computer science, Editore: John Wiley & sons, Anno edizione: 1987, ISBN: 0-471-85918-4
Risorsa bibliografica facoltativaDino Mandiroli, Paola Spoletini, Mathematical logic for computer science: an introduction, Editore: Esculapio, Anno edizione: 2010, ISBN: 978-88-7488-373-8

Mix Forme Didattiche
Tipo Forma Didattica Ore didattiche
lezione
30.0
esercitazione
20.0
laboratorio informatico
0.0
laboratorio sperimentale
0.0
progetto
0.0
laboratorio di progetto
0.0

Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua Inglese
Disponibilità di materiale didattico/slides in lingua inglese
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese
schedaincarico v. 1.6.1 / 1.6.1
Area Servizi ICT
08/12/2019