CALCOLABILITA' E COMPLESSITA' COMPUTAZIONALE

Insegnamento
CALCOLABILITA' E COMPLESSITA' COMPUTAZIONALE
Insegnamento in inglese
CALCULABILITY AND COMPUTATIONAL COMPLEXITY
Settore disciplinare
INF/01
Corso di studi di riferimento
MATEMATICA
Tipo corso di studio
Laurea Magistrale
Crediti
6.0
Ripartizione oraria
Ore Attività frontale: 42.0
Anno accademico
2017/2018
Anno di erogazione
2018/2019
Anno di corso
2
Lingua
ITALIANO
Percorso
APPLICATIVO
Docente responsabile dell'erogazione
CARUSO ANTONIO MARIO
Sede
Lecce

Descrizione dell'insegnamento

Il corso necessita delle conoscenze e capacità concrete di programmazione  e di analisi e sviluppo di algoritmi acquisite durante la triennale. Inoltre è richiesta la conoscenza di nozioni di matematica discreta (algebra lineare, analisi asintotica, funzioni, insiemi) e di calcolo delle probabilità (spazi di probabilità, variabili aleatoree continue e discrete, leggi di convergenza).

Conoscenze e comprensione. Possedere una preparazione di base sui concetti teorici relativi alla calcolablità e alla complessità computazionale.

Capacità di applicare conoscenze e comprensione: # essere in grado di produrre semplici dimostrazioni rigorose di risultati matematici non identici a quelli già conosciuti, ma chiaramente correlati ad essi, # essere in grado di formalizzare matematicamente problemi relativi alla calcolabilità o complessità di funzioni/algoritmi di moderata difficoltà, in modo da facilitare la loro analisi e risoluzione, # essere capaci di leggere e comprendere, in modo autonomo, testi avanzati o articoli di rivista relativi a questi settori.

Autonomia di giudizio. L’esposizione dei contenuti e delle argomentazioni sarà svolta in modo da migliorare la capacità dello studente di riconoscere dimostrazioni rigorose e individuare ragionamenti fallaci.

Abilità comunicative. La presentazione degli argomenti sarà svolta in modo da consentire l’acquisizione di una buona capacità di comunicare problemi, idee e soluzioni riguardanti l’Informatica Teorica, sia in forma scritta che orale.

Capacità di apprendimento. Saranno indicati argomenti da approfondire, strettamente correlati con l’insegnamento, al fine di stimolare la capacità di apprendimento autonomo dello studente.

Lezioni frontali ed esercitazioni in aula

L’esame consiste di una prova scritta e di una prova orale. La prova scritta verifica l’abilità si produrre dimostrazioni rigorose di semplici affermazioni matematiche correlate con gli argomenti del corso. La prova orale verifica l’abilità di esporre in modo chiaro e rigoroso alcuni contenuti del corso.

Gli studenti che ottengono la sufficienza alla prova scritta in un appello possono presentarsi alla prova orale non più tardi dell’appello successivo. Se lo studente non supera la prova orale è tenuto a rifare la prova scritta.

Pagina del Corso: http://bilbo.unisalento.it/antonio/didattica/algoritmi-e-complessita/

Logica e Calcolabilità: Sintassi e Semantica del calcolo proposizionale: operatori, formule ben formate, tavole di verità, tautologie vs contraddizioni, formule soddisfacibili, SAT. ‘conseguenze logiche’, ‘dimostrazioni formali’ vs ‘dimostrabilità’. Correttezza e Completezza della logica proposizionale. Cenni di logiche del primo ordine. (3 lezioni). Calcolabilità: definizioni di funzione calcolabile, modelli di calcolo: schemi primitivi ricorsivi, totalità, aritmetizzazione, teorema di Cantor, insiemi transfiniti e loro cardinalità, Tecnica di dimostrazione Diagonale. Funzione di Ackerman e Schemi pienamente Ricorsivi. Funzioni parziali. Macchine di Turing, linguaggi, riconoscimento vs calcolo di funzione. Problema della Fermata, linguaggi R, RE, co-RE. Riduzioni tra linguaggi. Linguaggi funzionali vs imperativi vs object-oriented. (6 lezioni)

Complessità e Algoritmi: Classi di Complessità: DTIME, NDTIME, PSPACE, NPSPACE. P vs NP. Definizioni diverse per NP e loro relazioni. NPSPACE, EXP, etc. Problemi Np-Completi e NP-Ardui, Teorema di Cook-Levin, SAT e riduzioni polinomiali, esempi di varie riduzioni. Limiti e Utilità della teoria della complessità computazionale. Algoritmi di Approssimazione, esempi vari. Algoritmi Probabilistici, Max-SAT, Matching, etc. Effetto soglia sulle istanze di SAT. (7 lezioni)

Complex Networks: Grafi e Reti. Stutture dati e algoritmi di base. Visite, Componenti Connesse, Alberi di copertura di costo minimo, strutture dati Union-Find, e loro analisi e implementazione in Python. Reti Complesse come modelli di reti per il Web: da Erdos-Renyi to Power-law graphs. Crawling su Web e schema di costruzione di un motore di ricerca. (5 lezioni).

Quasi tutti i testi sotto sono reperibili liberamente come PDF su web. Usare un motore di ricerca per trovarli.

Italiano:

Inglese:

Semestre
Primo Semestre (dal 02/10/2018 al 21/12/2018)

Tipo esame
Non obbligatorio

Valutazione
Orale - Voto Finale

Orario dell'insegnamento
https://easyroom.unisalento.it/Orario

Mutuato da
CALCOLABILITA' E COMPLESSITA' COMPUTAZIONALE (LM39)

Scarica scheda insegnamento (Apre una nuova finestra)(Apre una nuova finestra)