Ateneo - UPO

Il corso di calcolabilità e complessità è una sorta di pausa di riflessione sull'informatica in sé, che dà una distintiva profondità e ampiezza di visione e fornisce potenti strumenti tecnico-cognitivi di ampia applicabilità. Il corso si concentra sul significato di computazione, attraverso l'analisi dei modelli di calcolo e della loro potenza, e sulla inerente difficoltà dei problemi (non dei singoli algoritmi), mettendoli in relazione dal punto di vista delle risorse che richiedono. Invece di proporre tecniche e strumenti per realizzare sistemi e risolvere problemi, in questo corso ci si domanda se con un computer si può fare tutto: la risposta è no, in alcuni casi è proprio impossibile, in altri ci vuole troppo tempo o troppa memoria. Conoscere i limiti degli strumenti che si adoperano è fondamentale per essere in grado di porsi obiettivi raggiungibili, ridimensionando le richieste, accettando soluzioni approssimate. Le risposte che si ottengono in questo corso sono del tutto generali, valide e significative in qualunque ambito dell'informatica. In particolare, motivano e validano da un punto di vista teorico l’adozione delle tecniche tipiche dell’Intelligenza Artificiale.

Testo principale: Thomas A. Sudkamp, Languages and Machines, Pearson International Edition, 2006. Per alcune (poche) parti: C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994. Consultazione, per l’NP-completezza: Garey-Johnson, Computers and Intractability, Freeman, 1979. Del materiale aggiuntivo è fornito sul sito online del corso.

Conoscenza e capacità di comprensione:
Il corso introduce concetti fondamentali di calcolabilità e di complessità strutturale. La presentazione è basata sul modello di Macchina di Turing. Vengono spiegate tecniche per analizzare e confrontare la potenza di modelli di calcolo da una parte e la difficoltà di problemi dall'altra (simulazione, diagonalizzazione, dove-tailing e riduzione). Tali tecniche vengono applicate sia nell'ambito della calcolabilità che della complessità, per ottenere risultati classici quali la tesi di Church, l'esistenza e alcune proprietà di problemi non decidibili, proprietà di linguaggi e formalismi Turing-completi, la giustificazione dell'uso dell'O-grande in complessità, proprietà delle gerarchie di problemi rispetto alla loro difficoltà, l'esistenza di problemi NP-completi e la potenza della risorsa spazio rispetto al tempo.
Capacita' di applicare conoscenza e comprensione:
-capacità di confrontare modelli di calcolo
-capacità di applicare metodologie di analisi della inerente difficoltà dei problemi
-in particolare capacità di riconoscere il contesto in cui applicare le tecniche dimostrative di simulazione, riduzione e diagonalizzazione
-capacità di applicare le tecniche descritte in casi semplici.
Come effetto collaterale, verranno consolidate le competenze di programmazione.
Autonomia di giudizio:
verranno acquisiti strumenti , tecnici e cognitivi, che sono potenti e di ampia applicabilità, e si imparerà a riconoscere i limiti degli strumenti che dell'informatica, competenza fondamentale per essere in grado di porsi obiettivi raggiungibili, ridimensionando le richieste, e accettando soluzioni approssimate.
Abilità comunicative:
Per ottenere tali obbiettivi, verrà acquisito un linguaggio formale specifico. Inoltre verrà migliorata la padronanza della lingua inglese a livello tecnico informatico.
Capacita' di apprendimento:
si affinerà il rigore delle capacità di ragionamento logico. Mettendo in discussione l'onnipotenza degli strumenti di calcolo, si acquisirà un nuovo punto di vista dal quale rivedere quanto appreso nei corsi precedenti. Infine, gli strumenti tecnici e cognitivi che vengono sviluppati in questo corso sono applicabili a tutte le aree dell'informatica e dunque sono un arricchimento a prescindere dalle specifiche nozioni affrontate nel corso.

Conoscenza dei concetti fondamentali di programmazione, logica, analisi, e preferibilmente di architetture degli elaboratori e linguaggi formali. Capacità di programmare in Java.

Il corso consta di lezioni teoriche in aula e di attività in laboratorio. L' attività in laboratorio è parte integrante del corso.
A lezione vengono presentati in modo formale definizioni e teoremi (con le rispettive dimostrazioni) per comunicare le nozioni, lavorare sul rigore del ragionamento logico e insegnare la terminologia formale. In particolare viene posta enfasi sulle tecniche alla base delle dimostrazioni e dei ragionamenti, confrontandone l'applicazione in vari ambiti, a supporto della concettualizzazione delle stesse e come stimolo per acquisirle a guisa di strumento di lavoro di utilizzo piú vasto.
Inoltre si incoraggia la partecipazione suggerendo l'applicazione di tecniche, sviluppando il ragionamento con il richiamo di concetti fondamentali e risultati già presentati nel corso.
In laboratorio si richiede la realizzazione di progetti software per approfondire la comprensione dei modelli studiati e per cogliere fino in fondo il carattere costruttivo delle dimostrazioni di quasi tutti i teoremi presentati durante il corso. La partecipazione in laboratorio trasforma per ciascuna persona l'eventuale frequenza passiva in esigenza di confrontarsi attivamente con le nozioni e i risultati che si studiano, e specialmente con i ragionamenti seguiti.

Sulla piattaforma DIR sono a disposizione: tutte le informazioni pratiche sul corso, indicazioni sui libri di testo e il programma, materiale didattico aggiuntivo, argomenti trattati e indicazioni bibliografiche per ogni singola lezione compilati subito dopo la lezione, specifiche ed eventuale materiale aggiuntivo per l'attività che si svolge in laboratorio. In tal modo, chi frequenta può rivedere e approfondire l'attività di ciascuna lezione; coloro che non frequentano hanno a disposizione tutto il materiale per mantenersi al passo con il corso oppure per prepararsi in autonomia.

Poiché il libro di testo consigliato è in inglese, lo studio sarà uno strumento per migliorare la propria padronanza del linguaggio tecnico informatico in inglese.

L'attività in laboratorio richiede una partecipazione attiva e individuale e induce a porsi dei quesiti (e spesso di conseguenza a porne alla docente); in tal modo permette una regolare verifica del modo in cui gli argomenti vengono recepiti.
L'attività prevede principalmente sviluppo in linguaggio Java: quindi al di là delle funzioni ai fini degli obiettivi formativi specifici del corso, è in generale un ulteriore momento per consolidare le proprie competenze di programmazione e per affinare le proprie capacità di utilizzo del linguaggio Java.

Le persone con disabilità o con Disturbi Specifici dell’Apprendimento (DSA) o con
Bisogni Educativi Speciali (BES) possono richiedere servizi e strumenti specifici a loro dedicati
rivolgendosi allo Staff Sviluppo e Coordinamento Carriere e Servizi alle Studentesse e agli Studenti e
consultando la pagina dedicata del sito di Ateneo: https://uniupo.it/it/servizi/servizi-studenti-
disabili-e-dsa
Le persone con disabilità, DSA, BES, una volta preso contatto con lo Staff di Ateneo,
possono contattare la docente titolare dell'insegnamento in relazione alla declinazione delle
modalità di esame, in merito agli aspetti didattici.

Esame orale
L'esame orale consta in media di tre domande: una generale introduttiva sui metodi formali, una su argomenti di calcolabilità e una riguardante argomenti di complessità. Lo scopo è verificare la comprensione dei concetti fondamentali e che l'esposizione sia fatta con proprietà di linguaggio, che siano stati acquisiti gli strumenti metodologici e li si sappiano applicare. Pertanto viene richiesto da una parte di esporre definizioni e dimostrazioni, e dall'altra di ragionare su contesti leggermente modificati o di fare collegamenti tra argomenti diversi trattati nel corso, o di applicare le tecniche apprese a problemi visti durante il corso o simili. Durante il colloquio si verifica anche il livello di formalità raggiunto nell'espressione e nel ragionamento.
Il numero di domande poste all'orale è puramente indicativo perché, a seconda del modo in cui vengono date le risposte (formalità, chiarezza, completezza, precisione,...), possono essere necessarie piú domande o ne possono bastare meno per verificare che gli obiettivi formativi siano stati raggiunti.

Introduzione alla calcolabilità:
La prima parte di programma è volta all'acquisizione di tecniche formali e di strumenti per l'analisi e la formalizzazione del concetto di calcolabilità (Macchine di Turing, definizioni formali e funzionamento. Confronto di modelli diversi di macchina. Tecnica di simulazione. Funzioni calcolabili secondo Turing.)
Segue una formalizzazione basilare di classi di difficoltà di problemi in base ad aspetti puramente di calcolabilità, senza tenere conto di limiti di risorse (Insiemi ricorsivi e ricorsivamente enumerabili. Enumeratori.).
Il discorso prosegue con risultati generali e fondamentali che, nel seguire l'evoluzione storica, forniscono un primo raccordo con il mondo dell'informatica attuale (Tesi di Church, Codifica di macchine di Turing e macchina universale).
Seguono risultati negativi che sottolineano i limiti degli strumenti informatici e vengono contestualmente forniti strumenti per l'estensione di tali risultati negativi (Diagonalizzazione, Esistenza di funzioni non calcolabili, Dimostrazioni del fatto che un insieme non è ricorsivo o non è ricorsivamente enumerabile, Indecidibilità, problema dell'HALT, riduzioni e teorema di Rice).
Infine, la parte di calcolabilità si conclude rapportando gli strumenti e i risultati appresi, ad aspetti dell'informatica che si usano tutti i giorni o noti agli studenti da altri corsi (Importanza del costrutto "while" nei linguaggi di programmazione, Confronto di macchine di Turing con modelli di calcolo piú deboli (automi a stati finiti e a pila), grammatiche illimitate e dipendenti da contesto e ricorsività).

Introduzione alla complessità strutturale: la parte di complessità relativizza l'analisi e la formalizzazione fatte precedentemente, nonché gli strumenti introdotti, ad una situazione piú realistica in cui le risorse sono limitate; si focalizza in particolare sul rapporto tra la difficoltà di problemi, e il significato delle classi di complessità nondeterministiche. (Misure di complessità, modelli e rappresentazione di problemi. Teorema di accelerazione lineare. Macchine di Turing non deterministiche, significato di non determinismo. Le classi P ed NP, problemi in NP, riduzioni polinomiali, NP-completezza, SAT e il teorema di Cook. Complessità in termini di spazio, relazioni tra complessità in termini di spazio e tempo, e spazio non deterministico e tempo; teorema di Savitch. Esistenza di problemi di complessità arbitraria, teoremi della gerarchia e funzioni time e space constructible.)

Conoscenze
Cconcetto di modello di calcolo, macchine di Turing, concetto di funzione calcolabile, ricorsività e ricorsiva enumerabilità di insiemi, classi di complessità in termini di tempo, P ed NP e loro rapporto, NP-completezza, complessità in termini di spazio; tecniche di simulazione, riduzione e diagonalizzazione; esistenza di problemi non decidibili e di problemi che richiedono troppe risorse di computazione per essere trattati in pratica
Competenze ed abilità
Spiegare il significato di modello di calcolo e in particolare dare una definizione formale di macchina di Turing.
Applicare la tecnica di simulazione su esempi presentati nel corso ma, data la varietà di tali esempi, acquisendo la flessibilità per estenderla ad altre situazioni e contesti.
Definire e spiegare i concetti di funzione calcolabile, insiemi ricorsivi e ricorsivamente enumerabili, ovvero le proprietà di calcolabilità di proprietà e funzioni.
Presentare e discutere le tecniche per dimostrare la non ricorsività o la non ricorsiva enumerabilità di un insieme, ovvero piú in generale le proprietà di calcolabilità di una proprietà.
Enunciare e spiegare il significato della Tesi di Church.
Definire le classi di complessità in termini di tempi e di spazio.
Definire e spiegare il significato di non determinismo.
Definire il concetto di NP-completezza e la sua importanza.
Analizzare il rapporto tra classi di complessità in funzione della variazione di risorse.
Enunciare, spiegare e dimostrare i teoremi presentati a lezione.
Analizzare la funzione delle specifiche ipotesi nei teoremi presentati a lezione.
Mostrare applicazioni della tecnica di riduzione nell'opportuno ambito di utilizzo nel mondo della calcolabilità e in quello della complessità.
Mostrare applicazioni della tecnica di diagonalizzazione nell'opportuno ambito di utilizzo nel mondo della calcolabilità e in quello della complessità.
Proporre la tecnica giusta da utilizzare in particolari variazioni di qualche problema visto a lezione.