Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
didattica:magistrale:toc:ay_1617:main [2016/09/09 16:08] mescal [General Info] |
didattica:magistrale:toc:ay_1617:main [2020/09/17 16:55] (current) |
||
|---|---|---|---|
| Line 3: | Line 3: | ||
| ===== News ===== | ===== News ===== | ||
| <WRAP center round important 95%> | <WRAP center round important 95%> | ||
| - | * <wrap em>**Insert the date here**</wrap>: the course web site is now on-line | + | * <wrap em>**September 7th, 2016**</wrap>: the course web site is now on-line |
| </WRAP> | </WRAP> | ||
| Line 55: | Line 55: | ||
| <WRAP round 95% center box> | <WRAP round 95% center box> | ||
| - | .... | + | Verso una definizione astratta del concetto di algoritmo. Macchine di Turing. Tesi di Church e Turing. Cenni sul problema dell’arresto, sul decimo problema di Hilbert e su altri problemi insolubili in matematica e in informatica.\\ |
| + | Il problema della complessità. Complessità di una macchina di Turing.\\ | ||
| + | Il parametro tempo: la tesi di Cook-Karp, le classi P e NP, il problema P=NP. Linguaggi NP-completi. Teorema di Cook-Levin. Linguaggi NP-intermedi. La gerarchia polinomiale.\\ | ||
| + | Il parametro spazio: le classi L, NL, PSPACE. Teorema di Savitch. Linguaggi NL-completi. Linguaggi PSPACE-completi. Teorema di Baker-Gill-Solovay.\\ | ||
| + | Complessità probabilistica: le classi PP, BPP, RP e ZPP.\\ | ||
| + | Complessità interattiva: le classi AM, MA, AM[Poly] e IP. Cenni sul teorema di Shamir.\\ | ||
| + | Cenni su complessità e circuiti. | ||
| </WRAP> | </WRAP> | ||
| ---- | ---- | ||
| Line 62: | Line 68: | ||
| **Course Slides** | **Course Slides** | ||
| * slide 1st lesson | * slide 1st lesson | ||
| - | * | + | |
| **Reference books** | **Reference books** | ||
| - | * 1st book | + | * F. Corradini-S. Leonesi-S. Mancini-C. Toffalori, Teoria della Computabilità e della Complessità, McGraw-Hill Italia, 2005 |
| - | * 2nd book | + | |
| - | * ... | + | |
| - | * | + | |
| </WRAP> | </WRAP> | ||
| ---- | ---- | ||
| ===== Exams ===== | ===== Exams ===== | ||
| <WRAP box round center 95%> | <WRAP box round center 95%> | ||
| - | **Exam Dates A.Y. 2015/2016** | + | **Exam Dates A.Y. 2016/2017** |
| - | * Winter session dates here | + | * |
| - | * Summer session dates here | + | |
| - | * Autumn session dates here | + | |
| - | * Winter session dates here (2016) | + | |
| **Exam rules**: | **Exam rules**: | ||
| + | |||
| + | Il raggiungimento dei risultati di apprendimento D1, D2, D3 e D4 sarà verificato attraverso una prova orale finale con semplici esercizi e da discussioni durante il corso. Altre informazioni potranno essere reperite nello spazio web del docente sul [[http://docenti.unicam.it/pdett.aspx?ids=N&tv=d&UteId=196&ru=PO|portale docenti]]. | ||
| ** Exam Results ** | ** Exam Results ** | ||
| * N/A | * N/A | ||
| </WRAP> | </WRAP> | ||
