Theory of Complexity

Teacher:

• Carlo Toffalori

Lessons schedule:

• 1st time slot
• 2nd time slot
• 3rd time slot

Students Office hours:

• Xday from x(a|p)m to y(a|p)m

D1 - CONOSCENZA E CAPACITÀ DI COMPRENSIONE Risultati attesi: Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:

1. illustrare la tesi di Church e Turing e l’esistenza (modulo questa assunzione) di problemi insolubili in Informatica e Matematica,
2. valutare il costo delle computazioni e la complessità degli algoritmi e descrivere i parametri atti a misurarli,
3. riconoscere problemi informatici e matematici risolubili a costi accessibili, oppure risolubili solo a costi inaccessibili,
4. discutere il ruolo delle classi P e NP, del problema P = NP e dei linguaggi NP-completi,
5. illustrare le altre classi principali dello zoo della complessità.

D2 - CAPACITÀ DI APPLICARE CONOSCENZA E COMPRENSIONE Risultati attesi: Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:

1. valutare in semplici casi l’efficienza di un algoritmo,
2. identificare input e output di un algoritmo,
3. descrivere un algoritmo di soluzione, distinguendo i passi successivi del suo sviluppo.

D3 - AUTONOMIA DI GIUDIZIO Risultati attesi: Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:

1. distinguere input e output di un’istanza di un problema e i passi successivi di un algoritmo che conduce dall’uno all’altro,

D4 - ABILITÀ COMUNICATIVE Al termine di questa attività formativa, lo studente dovrà dimostrare di essere in grado di:

1. esporre in modo ordinato e coerente una procedura.

D5 - CAPACITÀ DI APPRENDIMENTO

….

Course Slides

• slide 1st lesson

Reference books

• 1st book
• 2nd book
• …

Exam Dates A.Y. 2015/2016

• Winter session dates here
• Summer session dates here
• Autumn session dates here
• Winter session dates here (2016)

Exam rules:

Exam Results

• N/A