Università degli Studi di Roma "Tor Vergata"

Prima Parte (Logica)
Richiami di matematica: teoria degli insiemi elementare, algebra Booleana,
relazioni e funzioni, principio di induzione. Logica proposizionale:
connettivi logici, tabelle di verità, variabili, formule, tableaux. Sistemi
assiomatici. Correttezza e completezza. Logica del primo ordine:
quantificatori, relazioni, proprietà e predicati, formule della logica del
primo ordine. Tableaux del primo ordine. Cenni al fenomeno dell'incompletezza.

Seconda Parte (Reti Logiche)
Segnali analogici e informazione digitale. Sistemi numerici, operazioni
aritmetiche. Le codifiche ASCII e Unicode. I codici Gray. Porte logiche e
circuiti logici, cenni ai linguaggi per la descrizione dell'hardware (HDLs).
Funzioni Booleane e forme canoniche. Mappe di Karnaugh. Circuiti combinatori:
codificatori e decodificatori, multiplexer, sommatori e sottrattori. Circuiti
sequenziali: Latch e Flip-Flop. Sincronizzazione. Automi a stati finiti.

- Raymond M. Smullyan
A Beginner's Guide to Mathematical Logic
Dover Publications, 2014

- Sarah L. Harris, David Money Harris
Sistemi digitali e architettura dei calcolatori
Zanichelli, 2017

1. Numeri naturali, interi, razionali. Principio di induzione e binomio di
Newton. Numeri reali e loro proprietà. Estremo superiore ed inferiore.
2. Numeri complessi, rappresentazione cartesiana e polare.
Esponenziale complesso, formula di Eulero e radici complesse.
3. Funzioni reali di una variabile: dominio, immagine e grafico.
Funzioni monotone e invertibili. Funzioni esponenziali, logaritmiche e
trigonometriche.
4. Limite di una successione: definizione e proprietà. Successioni
monotone. Successioni infinitesime, infinite e confronti. Forme
indeterminate. Il numero di Nepero. Il teorema di Bolzano-Weierstrass.
5. Topologia sulla retta reale. Limite di una funzione: definizione e
proprietà. Infinitesimi, infiniti, confronti tra infinitesimi e infiniti, forme
indeterminate, limiti notevoli. Simbolo o-piccolo.
6. Funzioni continue. Teorema degli zeri, teorema dei valori intermedi.
Massimi e minimi di funzioni continue, teorema di Weierstrass.
7. Calcolo differenziale per funzioni di una variabile. Derivabilità e
retta tangente. Regole di derivazione. Derivata delle funzioni
elementari. Estremi locali e derivate. Teoremi di Rolle, di Lagrange e
di Cauchy. Derivata prima e monotonia. Derivata seconda e
convessità. Studio del grafico di funzioni. Teorema di de L’Hôpital.
Polinomio di Taylor e applicazioni al calcolo di limiti.
8. Calcolo integrale. Definizione di integrale di Riemann e sue
proprietà. Classi di funzioni integrabili. Teorema della media integrale
e teorema fondamentale del calcolo integrale. Integrazioni di funzioni
elementari. Metodi di integrazione: integrazione per parti, per
sostituzione. Integrazione delle funzioni razionali e sostituzioni
speciali.
9. Serie positive: teoremi di confronto. Teorema del confronto
integrale. Serie geometrica e serie armonica generalizzata. Serie a
segni alterni e criterio di Leibniz. Integrali impropri e studio della loro
convergenza.
10. Equazioni differenziali lineari a coefficienti costanti. Equazioni
differenziali a variabili separabili.

- M. Bramanti, C. D. Pagani, S. Salsa, Analisi matematica 1, Zanichelli
- A. Languasco, Analisi Matematica 1, Hoepli.
Ulteriori esercizi con le soluzioni svolte verrano forniti durante il corso
per aiutare gli studenti nella preparazione della prova scritta.

Logica (8 ore):
Proposizioni. Proposizioni composte. La negazione di una proposizione. La congiunzione, disgiunzione, e disgiunzione esclusiva, di due proposizioni. L'implicazione da una proposizione ad un'altra. L'equivalenza di due proposizioni. Proposizioni composte e programmazione. Predicati e quantificatori. La negazione di un quantificatore. La proprieta' distributiva della disgiunzione rispetto alla congiunzione, e della congiunzione rispetto alla disgiunzione. Le Leggi di De Morgan: la negazione di una congiunzione e' la disgiunzione delle negazioni, e la negazione di una disgiunzione e' la congiunzione delle negazioni.
Teoria degli Insiemi (12 ore):
La nozione di insieme e di appartenenza di un elemento ad un insieme. Sottoinsiemi di un insieme: inclusione di un insieme in un altro. L'insieme vuoto. Intersezione e unione di due insiemi. Proprieta' associativa e distributiva dell'unione e dell'intersezione. Diagrammi di Venn. L'insieme complementare di un insieme. Leggi di De Morgan. Il prodotto cartesiano di due insiemi e sue proprieta'. Funzioni tra insiemi. Funzioni iniettive, suriettive, e biunivoche. Composizione di funzioni. Associativita' della composizione. La composizione di due funzioni iniettive e' iniettiva, e similmente per funzioni suriettive e biunivoche. L'inversa di una funzione biunivoca. La funzione identita'. La composizione di una funzione e della sua inversa e' la funzione identita'. L'immagine e la controimmagine di un sottoinsieme mediante una funzione. La controimmagine di una unione e' l'unione delle controimmagini, e similmente per l'intersezione. Permutazioni. Calcolo del prodotto di due permutazioni, e dell'inversa di una permutazione, usando la notazione unilinea. Relazioni su insiemi. Relazioni simmetriche, riflessive, e transitive. Relazioni di equivalenza. Classi di equivalenza. Due classi di equivalenza o coincidono o sono disgiunte. L'insieme quoziente di un insieme rispetto ad una relazione di equivalenza. Partizioni di un insieme. L'insieme quoziente di un insieme rispetto ad una relazione di equivalenza e' una partizione.
Teoria dei Numeri (20 ore):
Dimostrazioni dirette. Dimostrazioni per assurdo. Il Principio di Induzione Matematica. Numeri naturali. Numeri interi. I numeri razionali sono un insieme quoziente (no dim.). I numeri complessi. L'unita' immaginaria. Somma, prodotto e quoziente di numeri complessi. Il coniugato e la norma di un numero complesso. Divisibilita' tra numeri interi. Numeri perfetti. Numeri primi e composti. Numeri coprimi. Ogni numero 1 e' prodotto di numeri primi. L'infinita' dei numeri primi. L'Algoritmo Euclideo per la determinazione del massimo comun divisore di due interi positivi. L'identita' di Bezout. Se un numero primo divide un prodotto allora divide uno dei fattori. Il Teorema Fondamentale dell'Aritmetica. Equazioni Diofantee lineari. Un'equazione Diofantea lineare a due incognite ha soluzione se e solo se il massimo comun divisore dei due coefficienti divide il termine noto. La soluzione generale di un'equazione Diofantea lineare a due incognite (no dim.). La relazione di congruenza. La relazione di congruenza e' una relazione di equivalenza (no dim.). Le classi di resto. Somma e prodotto di due classi di resto. La risoluzione di equazioni lineari in una incognita tra classi di resto. La funzione di Eulero. La funzione di Eulero del prodotto di due numeri e' il prodotto delle funzioni di Eulero dei due numeri se questi sono coprimi. La formula chiusa per la funzione di Eulero. La moltiplicazione per la classe di resto di un numero k modulo n e' una biezione delle classi di resto modulo n che sono coprime con n, se k ed n sono coprimi. Il Teorema di Fermat-Eulero. Il Teorema di Fermat. L'algoritmo di crittografia RSA. Numerazioni in basi diverse.
Combinatoria Enumerativa (16 ore):
La cardinalita' del prodotto Cartesiano di due insiemi e' il prodotto delle loro cardinalita'. La cardinalita' della potenza di due insiemi e' la potenza delle loro cardinalita'. La cardinalita' dell'unione di due insiemi e' uguale alla somma delle loro cardinalita' meno la cardinalita' dell'intersezione. Il problema fondamentale della combinatoria enumerativa e sue possibili soluzioni. Formule, ricorsioni, funzioni generatrici. Ci sono 2 alla n sottoinsiemi di un insieme di cardinalita' n. Coefficienti binomiali. Il numero di sottoinsiemi di cardinalita' k di un insieme di cardinalita' n e' n binomiale k. Il coefficiente di x alla k in (1+x) alla n e' n binomiale k. Assegnazione di oggetti distinguibili in categorie distinguibili, ognuna di cardinalita' data. Coefficienti multinomiali. La formula per i coefficienti multinomiali. Multinsiemi. Cardinalita' di un multinsieme. Permutazioni di multinsiemi. Il numero di permutazioni di un multinsieme. Composizioni. Parti di una composizione. Il numero di composizioni di un intero n in k parti e' n-1 binomiale k-1. Composizioni deboli. Il numero di composizioni deboli di un intero n in k parti e' n+k-1 binomiale k-1. Il Principio di Inclusione-Esclusione. Deragliamenti. Il numero di deragliamenti di Sn. La risoluzione delle ricorsioni lineari a coefficienti costanti.
Somme ed asintotica (8 ore):
Formule chiuse. La formula chiusa per la somma geometrica. Somme polinomiali. La formula chiusa per una somma polinomiale. Somme non polinomiali. Se f e' una funzione reale continua e monotona crescente allora la somma, per i=1,..,n, di f(i) e' limitata superiormente (rispettivamente, inferiormente) da f(n) + l'integrale di f(x) da 1 ad n (rispettivamente, f(1) + l'integrale di f(x) da 1 ad n). Similmente se f e' una funzione reale continua e monotona decrescente. Somme doppie. La tecnica di inversione dell'ordine di sommatoria per il calcolo e la stima di una somma doppia. Prodotti. La tecnica del logaritmo per il calcolo e la stima di prodotti. La formula di Stirling. Notazioni asintotiche. Successioni e funzioni asintoticamente piu' piccole di altre. Successioni e funzioni asintoticamente equivalenti. x alla a e' asintoticamente piu' piccola di x alla b se 0 1. o-piccolo. O-grande. Se f e' un o-piccolo di g allora f e' un O-grande di g. Se f e' asintoticamente equivalente a g allora f e' un O-grande di g. Un polinomio di grado k e' un O-grande di x alla k. Se f e' un o-piccolo di g allora g non e' un O-grande di f. Omega. f e' un O-grande di g se e solo se g e' un Omega di f. Teta. Insiemi infiniti. La cardinalita' di un insieme infinito. Non esiste una biezione tra un insieme ed il suo insieme delle parti. Un insieme ha cardinalita' strettamente piu' piccola del suo insieme delle parti.
Teoria dei Grafi (8 ore):
Grafi. Cammini. Sentieri. Cammini chiusi. Circuiti. Grafi connessi. Alberi. Il grado di un vertice. Sottoinsiemi indipendenti e completi. Isomorfismi tra grafi. Accoppiamenti. Grafi bipartiti. Accoppiamenti di un grafo bipartito. La caratterizzazione dei grafi bipartiti che ammettono un accoppiamento. Colorazioni di un grafo. Il numero cromatico di un grafo. Grafi vuoti e completi. Se il grado massimo di un grafo e' k allora il grafo puo' essere colorato con k+1 colori. Il numero cromatico di un grafo e' limitato superiormente dal massimo, su tutti i vertici v del grafo, di d(v)+1. Grafi diretti (digrafi). Cammini diretti. Sentieri diretti. Cammini chiusi diretti. Cicli. Raggiungibilita'. Distanza da un vertice ad un altro. Vertici comparabili e incomparabili. Catene. Grado interno ed esterno di un vertice. Digrafi aciclici. Orari paralleli. Passo, tempo, e numero di processori di un orario. Sentieri critici. Profondita' di un elemento in un digrafo aciclico. Un orario parallelo di tempo minimo in un digrafo aciclico e' dato dalla partizione il cui blocco i-esimo consiste di tutti gli elementi di profondita' i. Il tempo minimo per un orario parallelo e' uguale alla cardinalita' massima di un sentiero critico. Reti di comunicazione. Terminali. Nodi di input e nodi di output. Diametro di una rete di comunicazione. Problemi di smistamento. Smistamenti. La latenza e congestione di uno smistamento. La congestione di una rete di comunicazione. L'albero binario completo, suo diametro e congestione. La griglia. La congestione della griglia e' 2.

E. Lehman, F. Leighton, A. Meyer, Mathematics for Computer Science,
(ocw.mit.edu/courses/electrical-engineering-and-computer-science/
6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_notes.pdf)

Verranno trattari i seguenti temi: risoluzione automatica dei problemi; algoritmi e programmi; modelli di calcolo; linguaggi di programmazione; tipi di linguaggi di programmazione; compilazione ed interpretazione; linguaggi imperativi. linguaggio di programmazione C: struttura di un programma; tipi di dati semplici e strutturati; variabili; strutture di controllo; puntatori; funzioni; ricorsione; operazioni di input/output; strutture di dati elementari. Introduzione al linguaggio di programmazione Python. Algoritmi elementari di ricerca e ordinamento.

Dispense scritte dal docente.
Linguaggio C (seconda edizione) di B.Kernighan e D.Ritchie edito da Pearson Education Italia

Richiami di geometria euclidea (nel piano e nello spazio euclidei).
Vettori orientati nello spazio euclideo, nel piano, nella retta. Operazioni sui vettori applicati; basi e coordinate per vettori applicati. Riferimenti affini nello spazio euclideo; coordinate.
Equazioni vettoriali di rette e di piani. Vettore direttore di una retta, vettori di giacitura di un piano. Equazioni parametriche di rette e di piani.
Spazi vettoriali su un campo; sottospazi vettoriali; combinazioni lineari, sistemi di generatori. Dipendenza e indipendenza lineare di vettori. Base di uno spazio vettoriale. Coordinate di un vettore rispetto ad una base.
Estrazione di una base da un sistema di generatori. Teorema di esistenza (delle basi). Teorema del completamento. Dimensione di uno spazio vettoriale.

Marco Abate, "Algebra lineare", McGraw-Hill Libri Italia, Milano, 2000

INTRODUZIONE
- Approccio strutturale
- Pietre miliari nell'architettura dei computer
- Tipologie di computer
- Unità metriche
ORGANIZ. DEI SISTEMI DI CALCOLO
- Processori
- Memoria principale
- Memoria secondaria
- Input/Output
LIVELLO LOGICO DIGITALE
- Porte logiche e algebra di Boole
- Circuiti logici digitali elementari
- Memoria
- Chip della CPU e bus
- Esempi di Chip della CPU
- Esempi di bus
- Interfacce
LIVELLO DI MICROARCHITETTURA
- Esempio di microarchitettura
- Esempio di ISA:IJVM
LIVELLO DI ARC. DELL'INSIEME D'ISTRUZIONI
- Panoramica del livello ISA
- Tipi di dati
- Formati delle istruzioni
- Indirizzamento
- Tipi di istruzioni
- Flusso di controllo
LIVELLO DEL SISTEMA OPERATIVO
- INTRODUZIONE
- PROCESSI E THREAD
- GESTIONE DELLA MEMORIA
- FILE SYSTEM
- INPUT/OUTPUT
- DEADLOCK
LIVELLO DEL LINGUAGGIO ASSEMBLATIVO
- Introduzione al linguaggio assemblativo
- Macroistruzioni
- Il processo di assemblaggio
- Collegamento e caricamento
ARCHITETTURE PER IL CALCOLO PARALLELO
- Parallelismo nel chip
- Coprocessori
- Multiprocessori
- Multicomputer
- Virtualizzazione

1) Introduzione alla programmazione su ARM - Circuiti, architettura e sistema operativo dei calcolatori elettronici. UniversItalia, 2020, ISBN- 978-88-3293-426-7
2) Tanenbaum Andrew S., Architettura dei calcolatori: Un approccio strutturale, 6a Ed., Pearson Education, 2013
3) Tanenbaum Andrew S.,Bos Herbert I moderni sistemi operativi, Pearson, 2016
Testo Ausiliario
4) Informazione automatica e Java. Compendio di informatica e di programmazione. Autori: Simonetta A. Sillano M. e Perna D., EDIZIONI KAPPA

Spazi di probabilità. Probabilità condizionata. Formula delle probabilità totali. Formula di Bayes. Eventi indipendenti. Cenni di calcolo combinatorio. Introduzione alle variabili aleatorie. Funzione di distribuzione. Variabili aleatorie discrete e distribuzioni discrete di uso comune (ipergeometrica, binomiale, geometrica, binomiale negativa, Poisson). Variabili aleatorie discrete multidimensionali. Variabili aleatorie discrete indipendenti. Speranza matematica, momenti, varianza e covarianza per variabili aleatorie discrete. Disuguaglianza di Cebichev. Regressione lineare. Variabili aleatorie continue e distribuzioni continue di uso comune (uniforme, esponenziale, normale, Gamma). Processo di Poisson. Speranza matematica, momenti e varianza per variabili aleatorie continue. Legge dei grandi numeri. Teorema limite centrale. Approssimazione normale.

P. Baldi, Introduzione alla probabilità con elementi di statistica, McGraw-Hill, 2012 (seconda edizione). ISBN: 9788838667862

Paradigma Dichiarativo: In questa parte del corso, si vuole introdurre lo studente alla programmazione dichiarativa basata sulla logica. Dopo una prima analisi delle differenze dei paradigmi di programmazione procedurali e dichiarativi, viene introdotto il Prolog come un linguaggio dichiarativo. Il linguaggio verrà descritto dal punto di vista sintattico e verranno introdotti i principali tipi di dati e gli operatori. Verranno descritte delle applicazioni nell'ambito dell'intelligenza artificiale e dell'elaborazione del linguaggio naturale. Verrà infine introdotta il legame con la logica dei predicati e con la logica del prim'ordine.

Paradigma Funzionale: In questa parte del corso, lo studente verrà introdotto ai principi di programmazione funzionale. Il linguaggio utilizzato è il Python che è un linguaggio ibrido che contiene alcuni di questi principi.

Paradigma Dichiarativo: I. Bratko, Prolog Programming for Artificial Intelligence, Addison Wesley

Introduzione alle basi di dati e modello relazionale dove sono affrontati i seguenti argomenti: Introduzione al corso; Basi di Dati e Sistemi di Gestione di Basi di Dati; Modelli dei Dati e Linguaggi delle Basi di Dati; Modello Relazionale dei Dati.
Progettazione concettuale e logica dove sono affrontati i seguenti argomenti: progettazione concettuale di una base dati; progettazione logica di una base dati
Esercitazione: Progettazione di un modello E-R a partire da un caso di studio
Algebra relazionale dove sono affrontati i seguenti argomenti: l'Algebra Relazionale come Linguaggio per la scrittura di Interrogazioni.
Calcolo relazionale dove sono affrontati i seguenti argomenti: Calcolo Relazionale come linguaggio d’interrogazione.
Esercitazione: Progettazione concettuale e logica di una base dati a partire dal modello E-R derivante da un caso di studio, interrogazioni in algebra relazionale.
Linguaggio SQL ed intro alla progettazione dove sono affrontati i seguenti argomenti: introduzione al linguaggio SQL; caratteristiche evolute del SQL; SQL per le applicazioni; metodologie e modelli per la progettazione di una base dati.
Progettazione fisica e normalizzazione dove sono affrontati i seguenti argomenti: progettazione fisica di una base dati, normalizzazione.
Esercitazione: Progettazione fisica e normalizzazione di una base dati a partire dal progetto concettuale e logico derivante da un caso di studio.
Interrogazioni e transazioni dove sono affrontati i seguenti argomenti: organizzazione fisica e gestione delle interrogazioni; gestione delle transazioni.
Esercitazione sul linguaggio SQL: installazione del software DBMS, creazione e popolamento di un database, interrogazioni semplici ed annidate.
Sviluppo applicazioni dove sono affrontati i seguenti argomenti: metodi e librerie per lo sviluppo di applicazioni fondate su basi di dati.
Ottimizzazione delle prestazioni: Il processo di ottimizzazione delle query SQL, Tecniche di accesso ai dati dei DBMS relazionali, Tecniche di ottimizzazione, Interpretazione dei piani di esecuzione. Calcolo del costo di esecuzione per query SQL.
Basi di dati distribuite: Concetti di basi di dati distribuite, controllo della concorrenza e recovery delle base di dati distribuite. Architetture delle basi di dati distribuite.
Basi di dati NoSQL. Modelli dati non relazionali (Document-based, Graph-based, Column oriented). Architetture per DBMS non relazionali. Cluster, Sharding e persistenza. Modellazione dei dati in DBMS NoSQL.
Gestione dei Big Data. Trattamento di grandi quantità di dati. Map Reduce e Hadoop. Hadoop Distributed File System. Spark SQL.

- Atzeni, Ceri, Fraternali, Paraboschi, Torlone Basi di dati -Modelli e Linguaggi di interrogazione- ed. McGraw-Hill 4nd edition

materiale del corso è disponibile alla pagina del corso

Il corso riguarda l'analisi e la progettazione di algoritmi. L'enfasi è sugli algoritmi efficienti. Saranno presentati i principali strumenti teorici utili per l'analisi e le principali tecniche di progettazione algoritmica (tecnica greedy, divide-et-impera, programmazione dinamica). Il corso è diviso in due parti. La prima parte copre: notazione asintotica, diversi metodi per stimare la complessità computazionale di algoritmi ricorsivi, il problema dell'ordinamento, strutture dati efficienti per implementare dizionari e code con priorità, e il problema del calcolo della distanza di edit fra due parole. La seconda parte riguarda problemi e algoritmi su grafi. Saranno presentati algoritmi efficienti per visitare un grafo, calcolare cammini minimi (in grafi pesati), trovare un minimo albero di copertura, e calcolare il flusso massimo di una rete con vincoli di capacità sugli archi.

Algoritmi e Strutture Dati, Demetrescu, Finocchi, Italiano, McGraw-Hill
Algorithm Design, Jon Kleinberg e Eva Tardos, Addison Wesley (2005)

Parte I (I semestre)
Introduzione ai sistemi operativi. Classificazione dei sistemi operativi. Principali modelli strutturali. Gestione dei processi. Thread. Sincronizzazione dei processi. Scheduling della CPU. Deadlocks. Gestione della memoria. Gestione dell'I/O. Gestione del file system. Casi di studio: Unix e Linux
Parte II (II semestre)
Reti di calcolatori e Internet. Strato di applicazione. Strato di trasporto. Strato di rete e instradamento. Strato di collegamento e reti di area locale. Reti wireless.

Sistemi Operativi, X ed. - A. Silberschatz, P. Galvin, G. Gagne. Pearson.
Reti di Calcolatori e Internet: un approccio top-down, VII ed. - J. F. Kurose, K. W. Ross - Pearson.

Introduzione al corso: algoritmi, problemi, modelli di calcolo. Caratteristiche elementari dei linguaggi. Grammatiche di Chomsky e loro gerarchia. Generazione ed accettazione di linguaggi. Riconoscimento di linguaggi: automi. Automi a stati finiti deterministici e non deterministici; equivalenza tra essi. Relazioni tra automi a stati finiti e grammatiche di tipo 3 (regolari). Pumping lemma per i linguaggi regolari. Proprietà di chiusura dei linguaggi regolari. Predicati decidibili sui linguaggi regolari. Espressioni regolari e loro equivalenza con gli automi a stati finiti e con le grammatiche regolari. Minimizzazione di automi a stati finiti.. Linguaggi context free
- Grammatiche di tipo 2: forme ridotte e forme normali (Chomsky, Greibach). Propreità di chiusura dei linguaggi CF. Decidibilità di predicati su linguaggi CF. Pumping lemma per i linguaggi context free. Automi a pila e linguaggi context free. Automi a pila deterministici. Ambiguità e sua indecidibilità. L'algoritmo CYK. Analisi sintattica in un compilatore, linguaggi LL(k) e LR(k) (cenni).

G. Ausiello, F. D'Amore, G. Gambosi, L. Laura "Linguaggi, Modelli, Complessità" nuova edizione. Franco Angeli, 2014. ISBN 978-88-917-0553-2.
Dispense a cura del docente disponibili sul sito del corso.

Teoria della programmazione lineare. Le soluzioni di base. Il metodo del Simplesso. Il Simplesso in due fasi. La teoria della dualità. La dualità debole. La dualità forte. Le condizioni di complementarità. Il metodo del Simplesso duale. L'algoritmo Primale-Duale. Il linguaggio AMPL. Implementazione in AMPL degli algoritmi proposti nel corso.

Dispense a cura del docente.
M. Caramia, S. Giordani, F. Guerriero, D. Pacciarelli, Ricerca operativa. Programmazione lineare, intera e non lineare, ISEDI, 2018

Il corso riguarda l'analisi e la progettazione di algoritmi. L'enfasi è sugli algoritmi efficienti. Saranno presentati i principali strumenti teorici utili per l'analisi e le principali tecniche di progettazione algoritmica (tecnica greedy, divide-et-impera, programmazione dinamica). Il corso è diviso in due parti. La prima parte copre: notazione asintotica, diversi metodi per stimare la complessità computazionale di algoritmi ricorsivi, il problema dell'ordinamento, strutture dati efficienti per implementare dizionari e code con priorità, e il problema del calcolo della distanza di edit fra due parole. La seconda parte riguarda problemi e algoritmi su grafi. Saranno presentati algoritmi efficienti per visitare un grafo, calcolare cammini minimi (in grafi pesati), trovare un minimo albero di copertura, e calcolare il flusso massimo di una rete con vincoli di capacità sugli archi.

Algoritmi e Strutture Dati, Demetrescu, Finocchi, Italiano, McGraw-Hill
Algorithm Design, Jon Kleinberg e Eva Tardos, Addison Wesley (2005)

Macchine di Turing: trasduttori e riconoscitori, Macchine a un nastro e a k nastri, macchine deterministiche e non deterministiche. Macchina di Turing universale. Linguaggi e funzioni. Linguaggi e linguaggi complemento. Accettabilità e decidibilità di linguaggi. Calcolabilità di funzioni. La tesi di Church-Turing e modello di calcolo equivalenti alla macchina di Turing. Linguaggi non decidibili. Halting problem. Riducibilità tra linguaggi.
Misure di complessità: dtime, dspace, ntime, nspace. Classi di linguaggi: DTIME, DSPACE, NTIME, NSPACE. Gap theorem e funzioni time-constructible. Teoremi di compressione e di accelerazione. Definizione delle classi di complessità spaziale e temporale: P, NP, PSPACE, NPSPACE, EXP, coNP. Inclusione, inclusione propria, coincidenza. Completezza.
Problemi e codifiche. Problemi decisionali e loro complemento. La classe P. La classe NP. Problemi NP-completi e Teorema di Cook-Levin. Chiusura rispetto alla riduzione polinomiale. Esempi di dimostrazioni di NP-completezza: 3-SAT, Vertex Cover, 3-Colorability, Colorability, Independent Set, Clique, Hamiltonian Circuit/Path, Longest Path, Commesso Viaggiatore. Problemi NP-intermedi: il teorema di Ladner. Algoritmi pseudo-polinomiali, problemi numerici e NP-completezza in senso forte; il problema PARTIZIONE.

G. Ausiello, F. D'Amore, G. Gambosi, L. Laura "Linguaggi, Modelli, Complessità" nuova edizione. Franco Angeli, 2014. ISBN 978-88-917-0553-2.
Dispense a cura del docente disponibili sul sito del corso.

Introduzione al Paradigma OO, e a Java come linguaggio “puramente ad oggetti”, Gli Oggetti , Classi ed oggetti, Operatori, Controllo del flusso di esecuzione di un programma, Inizializzazione e eliminazione di oggetti, Controllo dell’accesso, Riuso di classi, Polimorfismo, Interfacce, Classi interne, Strutture dati, Gestione degli Errori: le Eccezioni, Tipi di dato, Generics (..e cosa li differenzia dai Template del C++), Arrays, I/O, Tipi enumerati, Meta-programmazione: le Annotazioni, Cenni su Programmazione Concorrente, Cenni sulla gestione della grafica, Cenni sulle novità di Java 8 e Java 9, Gestione OO di progetti e gestione avanzata delle dipendenze, Gestione avanzata di dipendenze a compile time: Maven, Gestione avanzata dipendenze a run-time: OSGi

Thinking in Java (4th edition), ISBN-10: 0131872486 | ISBN-13: 978-0131872486
ulteriore compendio allo studio: Sun Java Tutorials

Elementi di base dell'Analisi Numerica (interpolazione polinomiale, integrazione numerica, elementi di analisi di matrici, metodi iterativi per i sistemi lineari).

Libro di testo a cura del docente

PARTE 1 - INTRODUZIONE
Produzione industriale del software. Paradigmi di produzione: build&fix, waterfall, rapid prototyping, incremental, spiral.
PARTE 2 - FASI DEL PROCESSO SOFTWARE
Requisiti, specifica, progetto preliminare, progetto dettagliato, realizzazione, integrazione, uso e manutenzione. Qualità e fattori di qualità. Verifica e Validazione.
PARTE 3 - TECNOLOGIE E STRUMENTI DI PRODUZIONE SOFTWARE
Tecnologie per sistemi ad oggetti e componenti, tecnologie basate su architetture orientate ai servizi per sistemi eterogenei ed interoperabili. Strumenti di produzione, supporti alla notazione, specifica, progetto e documentazione di prodotti e servizi software.

Dispense rilasciate dal docente al termine di ogni argomento illustrato a lezione.