Complessità computazionale

Obiettivo del laboratorio è sensibilizzare gli studenti alle problematiche relative alla valutazione del costo computazionale di risoluzione di problemi, nonché alla risoluzione efficiente dei problemi stessi. A tal fine, saranno introdotti concetti basilari di complessità computazionale e di teoria degli algoritmi, e saranno organizzate attività sperimentali finalizzate a far percepire la differenza tra trattabilità e intrattabilità di un problema, la diversa efficenza di metodi di soluzione alternativi, la necessità di ricercare metodi efficienti di soluzione.

Lezione I ( 215 Kb)

• Problemi e algoritmi
• Linguaggi e modelli di calcolo
• Macchine di Turing
• Equivalenza linguaggi di programmazione e macchine di Turing e Tesi di Church

Lezione II ( 173 Kb)

• Tanti tipi di problemi
• Quanti sono gli algoritmi?
• Quanti sono i problemi?
• Autoreferenzialita e paradossi

Lezione III ( 85 Kb)

• Trattabilità di problemi computazionali

Lezione IV ( 142 Kb)

• Trattabile o intrattabile?
• L’algoritmo di Euclide

Lezione V ( 172 Kb)

• Complessita dell’ordinamento
• Complessita dei problemi

Lezione VI ( 80 Kb)

• Risoluzione e verifica di problemi