logo-polimi
Loading...
Risorse bibliografiche
Risorsa bibliografica obbligatoria
Risorsa bibliografica facoltativa
Scheda Riassuntiva
Anno Accademico 2019/2020
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 - Civ (Mag.)(ord. 270) - MI (495) GEOINFORMATICS ENGINEERING - INGEGNERIA GEOINFORMATICA*AZZZZ089181 - THEORETICAL COMPUTER SCIENCE
Ing Ind - Inf (Mag.)(ord. 270) - MI (263) MUSIC AND ACOUSTIC ENGINEERING*AZZZZ089181 - THEORETICAL COMPUTER SCIENCE
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA*AZZZZ089181 - THEORETICAL COMPUTER SCIENCE

Obiettivi dell'insegnamento

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.

 


Risultati di apprendimento attesi

 

Expected learning outcomes

 

Dublin Descriptors

Expected learning outcomes

Knowledge and understanding

Students will learn:

  • The principles and the fundamental models of automatic computation.
  • The basic principles of the design and analysis of algorithms and data structures.

Applying knowledge and understanding

By means of exercise lessons on specific problems, the student will acquire:

 

  • A critical attitude towards the use, the creation and the modification of models of computation.

 

  • A capacity to apply, adapt, and evaluate algorithms and data structures in practical applications.

 

  • A capacity to evaluate the feasibility and convenience of developing and verifying computer-based systems and software tools.

 

Lifelong learning skills

After successful completion of the course, the students will be able to evaluate autonomously and critically models of computation, algorithms and data structures.

 

 

 


Argomenti trattati

 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.

 

 


Prerequisiti

Prerequisites

The course program assumes the knowledge of topics that are typically covered in Computer Science 1 courses. A further requirement is knowledge of the content of the Logic and Algebra course.

 


Modalità di valutazione

Assessment

The exam is based on written questions, possibly integrated, upon request by the teacher, by a further oral interrogation. The written part of the exam is open book (textbook and personal notes allowed).

 

Type of assessment

Description

Dublin descriptor

Written test

 

  • Solution of algebraic and numerical problems for the computational complexity figures
  • Solution of design exercises concerning algorithms
  • Open questions of theoretical nature on the topics covered by the course

 

  • 1, 2
  • 1, 2, 5
  • 1, 2, 5

 

 


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
Risorsa bibliografica obbligatoriaDino Mandrioli, Davide Martinenghi, Angelo Morzenti, Matteo Pradella, and Matteo Rossi, Lecture Notes on Monadic First- and Second-Order Logic on Strings, Anno edizione: 2019
Note:

Unedited lecture notes; available for download in PDF format from the course Beep platform.


Forme didattiche
Tipo Forma Didattica Ore di attività svolte in aula
(hh:mm)
Ore di studio autonome
(hh:mm)
Lezione
30:00
45:00
Esercitazione
20:00
30:00
Laboratorio Informatico
0:00
0:00
Laboratorio Sperimentale
0:00
0:00
Laboratorio Di Progetto
0:00
0:00
Totale 50:00 75:00

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.4 / 1.6.4
Area Servizi ICT
10/07/2020