Università degli Studi di Roma "Tor Vergata"

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)

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

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.

John V. Guttag. “Introduzione alla programmazione con Python”. EGEA, 2021.

Introduzione allo studio della Fisica. Moto in una dimensione. Vettori. Moto in due dimensioni. Le leggi del moto. Ulteriori applicazioni delle leggi di Newton. Energia e trasferimento di energia. Energia potenziale, Quantità di moto, urti e introduzione alla dinamica dei sistemi di punti materiali. Moto rotazionale e dinamica dei corpi rigidi. Orbite planetarie: leggi di Keplero e legge di gravitazione universale. Moto armonico. Temperatura, leggi dei gas ideali e teoria cinetica dei gas. Primo principio della termodinamica. Secondo principio della termodinamica. Entropia. Elementi di elettrostatica ed elettrodinamica classica.

Serway-Jewett,"Fisica per Scienze ed Ingegneria" (quinta edizione), ed. EdiSES, vol. 1 e 2 (il docente preciserà in classe quali parti del testo serviranno per l'esame).

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

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