Università degli Studi di Roma "Tor Vergata"

1)INSIEMI NUMERICI; 2)SUCCESSIONI; 3)SERIE; 4)FUNZIONI DI UNA VARIABILE: LIMITI E CONTINUITA';5) CALCOLO DIFFERENZIALE PER FUNZIONI DI UNA VARIABILE;6) CALCOLO INTEGRALE PER FUNZIONI DI UNA VARIABILE; 7) EQUAZIONI DIFFERENZIALI

Matematica. Calcolo infinitesimale e algebra lineare.
Bramanti, Marco Pagani, Carlo D Salsa, Sandro
Editore: Zanichelli Editore (2004)
ISBN 10: 8808075478

NTRODUZIONE (PAC 1 LIBRO 1)
• Organizzazione COMPUTER STRUTTURATO
• TAPPE IN ARCHITETTURA DEL COMPUTER
• IL COMPUTER ZOO
• UNITÀ METRICA

COMPUTER SYSTEMS ORGANIZZAZIONE (PAC 2 Libro 1)
• PROCESSORI
• memoria principale
• memoria secondaria
• INPUT OUTPUT
LA LOGICA livello digitale (PAC 3 Libro 1)
• CANCELLI E algebra booleana
• circuiti logici di base DIGITALI
• MEMORIA
• CHIPS CPU E AUTOBUS
• CHIPS ESEMPIO CPU
• AUTOBUS ESEMPIO
• Interfaccia
IL LIVELLO microarchitettura (PAC 4 LIBRO 1)
• UN ESEMPIO microarchitettura
• UN ESEMPIO ISA: ijvm
Il set di istruzioni ARCHITETTURA LIVELLO (PAC 5 LIBRO 1)
• PANORAMICA DEL LIVELLO ISA
• TIPI DI DATI
• formati delle istruzioni
• AFFRONTARE
• tipi di istruzioni
• flusso di controllo
Il livello di sistema operativo della macchina (PAC 1,2,3,4,5,6 LIBRO 2)
• Introduzione
O Sistemi operativi
CHIAMATE O SISTEMA
O SISTEMA OPERATIVO STRUTTURA
• PROCESSI E FILO
O PROCESSI
O FILETTI
o Interprocess COMUNICAZIONE
o PROGRAMMAZIONE
• GESTIONE DELLA MEMORIA
o NO ASTRAZIONE MEMORIA
o Spazio indirizzo
o la memoria virtuale
O Algoritmi PAGINA DI RICAMBIO
• FILE SYSTEM
o FILE
O DIRECTORIES
o Sistema di file di implementazione
• INPUT OUTPUT
O PRINCIPI DI I / O HARDWARE
O PRINCIPI DEL SOFTWARE I / O
O STRATI SOFTWARE / O
O DISCHI
O OROLOGI
IL LIVELLO Assembly Language (PAC 7 LIBRO 1)
• Introduzione al linguaggio Assembler
• MACRO
• il processo di assemblaggio
• COLLEGAMENTO E CARICO
Architetture parallele computer (PAC 8 LIBRO 1 e CAP 8 LIBRO 2)
• On-Chip PARALELISM
• COPROCESSORE
• multiprocessori
• multi-computer
• Virtualizzazione
• sistemi distribuiti

LIBRO 1: Architettura dei calcolatori. Un approccio strutturale di Andrew S. Tanenbaum (Autore), Todd Austin (Autore), Pearson – Prentice Hall
LIBRO 2: I moderni sistemi operativi di Andrew S. Tanenbaum (Autore), Pearson – Prentice Hall
TESTO AUSILIARIO: Informazione automatica e Java. Compendio di informatica e di programmazione Simonetta A. Sillano M. e Perna D., EDIZIONI KAPPA

In particolare 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; 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 (array, liste e dizionari).

Durante il corso verranno presentati una quantita' di problemi che saranno risolti facendo riferimento principalmente al linguaggio C.

Il corso e' diviso in due moduli da 6 CFU ciascuno. Il primo modulo e' di introduzione generale ai temi sopra elencati. Il secondo e' orientato alla soluzione dei problemi proposti utilizzando linguaggi di programmazione ad alto livello: a tale scopo verrà presentato il linguaggio C ed introdotto il linguaggio Python.

Dispense scritte daldocente;
Linguaggio C (seconda edizione) di B.Kernighan e D.Ritchie edito da Pearson Education Italia
AA.VV. Pensare da informatico: Imparare con Python

- Introduzione. Sistema Internazionale di misura. Grandezze fondamentali e derivate. Analisi dimensionale. Ordini di grandezza. Cifre significative. Vettori e somma di vettori in 2 e 3 dimensioni.

- Componenti cartesiane di un vettore. Versori. Moto rettilineo. Velocità media e velocità istantanea. Legge oraria. Moto rettilineo uniforme.

- Moto rettilineo uniformemente accelerato. Legge oraria del moto rettilineo uniformemente accelerato. Esempi e problemi risolti sul moto rettilineo.

- Caduta libera di gravi lungo la verticale. Legge oraria per il moto rettilineo generico. Moto nel piano. Vettore posizione. Vettore spostamento. Vettore velocità. Vettore accelerazione. Proiezione di un moto piano su due assi cartesiani ortogonali. Moto piano con accelerazione costante.

- Moto di un grave: equazione della traiettoria, tempo di volo e gittata. Moto circolare uniforme: accelerazione centripeta (direzione, verso e modulo), periodo, frequenza, velocità angolare.

- Vettore accelerazione nel moto sul piano. Moto relativo: legge di composizione delle velocità in una e due dimensioni (solo moto relativo traslatorio). Dinamica del punto materiale: concetto di forza, prima legge della dinamica (principio di inerzia), sistemi di riferimento inerziali, massa inerziale, seconda legge della dinamica. Unità di misura della forza.

- Riepilogo delle tre leggi della dinamica. Forza peso. Reazione vincolare. Equilibrio statico: esempi. Moto uniformemente accelerato su piano inclinato liscio. Macchina di Atwood.

- Applicazioni delle leggi della dinamica a problemi semplici. Forze di contatto. Forza di attrito statico. Forza di attrito dinamico. Piano inclinato con attrito. Forze agenti nel moto circolare uniforme. Pendolo conico.

- Ulteriori applicazioni delle leggi della dinamica. Auto in curva piana con attrito statico. Auto in curva sopraelevata senza attrito. “Giro della morte”. Introduzione al moto del pendolo semplice. Forza di attrito viscoso con modulo proporzionale alla velocità del corpo; velocità limite. Lavoro di una forza costante. Unità di misura del lavoro. Prodotto scalare di due vettori: definizione, proprietà e suo legame con le componenti cartesiane dei due vettori.
- Interpretazione grafica del lavoro di una forza costante. Lavoro compiuto da una forza variabile e sua interpretazione grafica. Forza elastica: legge di Hooke, costante elastica, lavoro compiuto dalla forza elastica. Teorema delle forze vive. Energia cinetica.

- Applicazioni del teorema delle forze vive. Potenza media e potenza istantanea. Unità di misura della potenza.

- Calcolo della potenza sviluppata da una forza costante. Energia potenziale della forza peso. Conservazione dell’energia meccanica totale. Applicazioni.

- Forze conservative e forze non conservative. Energia potenziale elastica. Legame tra una forza conservativa e la sua energia potenziale. Gradiente di una funzione scalare. Posizioni di equilibrio di un corpo sotto l'azione di una forza conservativa. Equilibrio stabile ed equilibrio instabile. Punti di inversione del moto sotto l'azione di una forza elastica.

- Quantità di moto. Legge di conservazione della quantità di moto totale per un sistema isolato di due punti materiali interagenti. Impulso esercitato da una forza e sua interpretazione grafica. Urti elastici e anelastici. Calcolo delle velocità finali in urti totalmente anelastici e in urti elastici.

- Dissipazione di energia cinetica in un urto unidimensionale. Urto con mutua interazione elastica. Urti in due dimensioni: concetti di base e caso particolare. Centro di massa di un sistema di N corpi. Prima equazione cardinale della dinamica dei sistemi.

- Metodo pratico per la determinazione della posizione del centro di massa di un corpo solido. Calcolo della posizione del centro di massa di un sistema di punti materiali e di una figura piana omogenea. Moto del centro di massa. Moto rotazionale: parametri cinematici (posizione angolare, velocità angolare, accelerazione angolare). Spostamento angolare vettoriale infinitesimo. Vettori velocità angolare e accelerazione angolare. Moto rotazionale con accelerazione angolare costante. Legame tra velocità tangenziale e velocità angolare. Prodotto vettoriale e sue proprietà.
- Energia cinetica rotazionale. Sistemi rigidi e corpi rigidi. Momento d’inerzia di un corpo rigido rispetto a un asse fissato. Teorema di Huygens-Steiner. Esempi di calcolo del momento d’inerzia. Momento di una forza rispetto a un polo fissato. Equilibrio statico di un corpo rigido.

- Dinamica del moto rotazionale. Lavoro di una forza nel moto rotazionale. Momento angolare rispetto a un polo fissato. Legame tra momento risultante delle forze esterne agenti su un sistema e momento angolare totale del sistema. Seconda equazione cardinale della dinamica dei sistemi. Teoremi di König. Requisiti per la conservazione del momento angolare totale di un sistema. Moto di puro rotolamento di un corpo rigido con simmetria di rotazione.

- Moto rettilineo di un punto materiale sotto l'azione di una forza elastica (moto armonico). Posizione, velocità e accelerazione nel moto armonico. Parametri caratteristici del moto armonico: ampiezza, pulsazione, fase iniziale, periodo e frequenza.

- Energia nel moto armonico. Pendolo semplice. Isocronismo delle piccole oscillazioni di un pendolo. Pendolo fisico. Moto rettilineo di un punto materiale sotto l'azione di una forza conservativa. Moto piano di un punto materiale sotto l'azione di una forza centrale. Forza gravitazionale e legge di gravitazione universale. Energia potenziale gravitazionale. Esperimento di Cavendish per la misura della costante universale G. Moto dei pianeti e leggi di Keplero. Energia potenziale efficace.
- Equilibrio termico. Temperatura e sua definizione operativa. Scala centigrada (Celsius) e scala Fahrenheit. Dilatazione lineare, superficiale e di volume di corpi solidi. Gas ideali o perfetti. Leggi di Boyle, Gay-Lussac, Charles. Equazione di stato dei gas perfetti. Costante universale R e costante di Boltzmann.

- Forma ''puntuale'' dell'equazione di stato dei gas perfetti. Teoria cinetica dei gas. Interpretazione microscopica della pressione e della temperatura di un gas perfetto. Teorema di equipartizione dell'energia. Energia interna di un gas monoatomico. Velocità quadratica media delle molecole di un gas perfetto.

- Distribuzione di Maxwell del modulo delle velocità molecolari di un gas. Energia interna di un sistema. Scambi energetici tra sistemi a temperatura diversa: il calore. Unità di misura del calore: la caloria. Esperienza di Joule ed equivalente meccanico della caloria. Capacità termica e calore specifico. Legge fondamentale della calorimetria. Convenzione dei segni del calore negli scambi energetici. Misura del calore specifico di un campione di una data sostanza. Calorimetro delle mescolanze. Transizioni di fase e calore latente. Lavoro nelle trasformazioni termodinamiche. Sorgenti termiche (termostati). Dipendenza del lavoro dalla trasformazione seguita tra due stati fissati.

- Conservazione dell'energia e primo principio della termodinamica. Trasformazioni adiabatiche. Trasformazioni isobare. Trasformazioni isocore. Trasformazioni isoterme. Trasformazioni cicliche (cicli). Dipendenza della pressione atmosferica dalla quota. Calori specifici molari a volume costante e a pressione costante di un gas perfetto. Caso dei gas monoatomici. Legge di Mayer. Trasformazioni adiabatiche quasi statiche di un gas perfetto: legge di Poisson.

- Calori specifici molari ed equipartizione dell'energia. Caso dei gas biatomici a temperature ''ordinarie''. Macchine termiche e loro cicli. Rendimento di una macchina termica. Secondo principio della termodinamica: enunciato di Kelvin-Planck. Trasformazioni reversibili e irreversibili. Ciclo di Carnot e suo rendimento. Pompe di calore e frigoriferi. Secondo principio della termodinamica: enunciato di Clausius. Equivalenza dei due enunciati. Idealità del ciclo di Carnot. Disuguaglianza di Clausius. Il concetto di entropia. Variazione di entropia lungo un cammino reversibile. Variazione dell'entropia totale di un sistema isolato (''freccia'' del tempo). Esempi di calcolo della variazione di entropia in trasformazioni irreversibili

Serway – Jewett
Fisica per Scienze ed Ingegneria – Volume Primo (quinta edizione)
EdiSES

Algebra lineare ( I°parte)
• Lo spazio dei vettori numerici reali a ! componenti
Definizione e proprietà di combinazioni lineari, indipendenza e dipendenza lineare tra vettori
numerici.
• L’algebra delle matrici reali
Il linguaggio delle matrici e le principali operazioni (somma, prodotto, matrice trasposta, inversa,
triangolare).
Metodo di eliminazione di Gauss (per righe) e riduzione a scala di una matrice.
• Sistemi di equazioni lineari omogenei e non omogenei
Risoluzione con l’algoritmo di Gauss
• Determinanti
Metodo di Laplace (per righe e per colonne), proprietà, calcolo del determinante con il metodo di
eliminazione di Gauss, relazione tra l’annullamento del determinante di una matrice quadrata e la
dipendenza lineare delle righe (o delle colonne) Matrice inversa, calcolo dell’inversa con l’algoritmo
di Gauss. La regola di Kramer.
Algebra lineare (II°parte)
• Spazi vettoriali sul campo reale e su F2.
• Sottospazio vettoriali
• Basi e dimensione di uno spazio vettoriale.
• Intersezione e somma di due sottospazi vettoriali.
Formula di Grassmann
• Matrici e applicazioni lineari
Nucleo, Immagine, teorema principale.
Il codice di Hamming.
Geometria'analitica'
• Lo spazio vettoriale dei vettori geometrici
Interpretazione geometrica delle operazioni di somma e prodotto per uno scalare. Interpretazione
geometrica della dipendenza e indipendenza lineare di vettori geometrici,
Prodotto scalare di due vettori geometrici. Basi ortonormali dello spazio dei vettori geometrici.
Prodotto scalare in Rn e formula di Shwartz.
• Sistemi di coordinate cartesiane nello spazio.
Equazioni parametriche e cartesiane di un piano. Equazioni parametriche di una retta. Relazioni di
parallelismo e perpendicolarità tra rette e piani.

- Note del corso di Geometria I del prof. Giambattista Marini, reperibili al sito
http://www.mat.uniroma2.it/~marini/amg.pdf
(Altre dispense di Algebra lineare si possono trovare in rete e sono essenzialmente equivalenti).
- Esercizi di Geometria e Algebra lineare, reperibili ai siti
http://www.dm.unito.it/quadernididattici/abbena/nuovo01.pdf
http://www.dmf.unisalento.it/~calvaruso/Homepage/pages/esercizi.pdf

Parte I: Sistemi operativi (I semestre)
• Introduzione ai sistemi operativi.
• Storia e classificazione dei sistemi operativi.
• Principali modelli strutturali.
• Gestione dei processi.
• Threads.
• Sincronizzazione dei processi.
• Gestione della memoria.
• Gestione dell’ I/O.
• Gestione del file system.
• I sistemi operativi Unix e Linux.
• Casi di studio: Unix e Linux

Parte II: Reti di calcolatori (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

Testi di riferimento
Sistemi operativi, II ed. - P. Ancilotti, M. Boari, A. Ciampolini, G. Lipari - McGraw-Hill
Reti di Calcolatori e Internet, VI ed. - Un approccio top-down - J.F. Kurose, K.W. Ross - Pearson - Addison Wesley.

Testi consigliati per approfondimenti
Sistemi Operativi, IX ed., A. Silberschatz, P. Galvin, G. Gagne. Pearson.
I moderni Sistemi Operativi, III ed., A. S. Tanenbaum. Pearson - Prentice Hall.
Sistemi operativi, D. M. Dhamdhere, McGraw-Hill.
Reti di Calcolatori e Internet, B. A. Forouzan, McGraw-Hill.

Introduzione al corso: clicca qui
Capitolo 1: Un'introduzione informale agli algoritmi: clicca qui
Capitolo 2: Modelli di calcolo e metodologie di analisi: clicca qui
Capitolo 4: Ordinare in tempo quadratico (Selection Sort, Insertion Sort): clicca qui
Capitolo 4: Algoritmi di ordinamento che usano la tecnica del divide et impera: MergeSort e QuickSort: clicca qui
Capitolo 4: lower bound ordinamento per confronti: clicca qui
Capitolo 4: Heap Sort: clicca qui
Capitolo 4: Algoritmi di ordinamento lineari (per dati di input con proprietà particolari): IntegerSort, BucketSort e RadixSort: clicca qui
Capitolo 3: Strutture dati elementari; rappresentazioni indicizzate e collegate di alberi; algoritmi di visita di alberi: clicca qui
Capitolo 6: Alberi binari di ricerca; alberi AVL clicca qui
Capitolo 10: Tecnica della programmazione dinamica. Algoritmo per il calcolo della distanza fra due stringhe: clicca qui
Capitolo 8: Code con priorita' clicca qui

Libro di testo
Si suggerisce come testo di riferimento il seguente libro:
Demetrescu, Finocchi, Italiano
Algoritmi e Strutture Dati
McGraw-Hill
Gli argomenti svolti possono essere anche reperiti su altri testi, a piacere dello studente. I lucidi presentati a lezione sono gli argomenti che fanno parte del programma.

ITALIANO. Spazi di Probabilità. Probabilità condizionata. Variabili aleatorie discrete, speranza matematica, momenti, varianza. Variabili aleatorie continue, speranza matematica, momenti, varianza. Processo di Poisson. Legge dei grandi numeri. Teorema limite centrale.

P. Baldi, Calcolo delle Probabilità, McGraw-Hill, 2007.

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 7 e Java 8, Gestione OO di progetti e gestione avanzata delle dipendenze, Gestione avanzata di dipendenze a compile time: Maven, Gestione avanzata dipendenze a run-time: OSGi

Libri di testo:
- Paradigma ad Oggetti: Thinking in Java (4th edition), ISBN-10: 0131872486 | ISBN-13: 978-0131872486
- Paradigma Dichiarativo: I. Bratko, Prolog Programming for Artificial Intelligence, Addison Wesley
- Paradigma Funzionale: verrà comunicato al secondo semestre
Ulteriore materiale:
- Sun Java Tutorials

Introduzione 

- Modello relazionale 
- Algebra relazionale 
- Calcolo relazionale 
- Disegno logico DB 

Schema Entity-relationship 
- Disegno fisico DB 
-Query language e implementazioni su mySQL 
DML 
SQL 

- Organizzazione fisica dei dati 
- Ottimizzazione degli indici 

- Ottimizzazione delle interrogazioni

- Transazioni 
------ Locking a due fasi, Timestamp,MVCC 
------ MySQL e Storage Engine 

- Basi di dati attive 
------ Trigger e Stored Procedure
- Basi di dati geospaziali e GIS 
- Basi di dati su architetture distribuite 
------ Commit a due fasi 
- Architetture per l' analisi dei dati 
------ Data Warehouse 
------ Data Mining
Linked Open Data e DB NoSQL

- Implementazione progetto

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

- Fondamenti matematici: logica, insiemi, relazioni, funzioni, strutture algebriche fondamentali
- Insiemi finiti e infiniti; numerabilità e non numerabilità di insiemi
- Caratteristiche elementari dei linguaggi
- Grammatiche di Chomsky e loro gerarchia
- Generazione ed accettazione di linguaggi
- Riconoscimento di linguaggi: automi
- Automi a stati finiti determinitici 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)
- Pumping lemma per i linguaggi context free
- Automi a pila e linguaggi context free
- Automi a pila deterministici
- Ambiguità
- Cenni sul parsing
- L'algoritmo CYK

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.

Introduzione

- Modello relazionale
- Algebra relazionale
- Calcolo relazionale
- Flusso di progetto e visione dei dati
- Modello concettuale dei dati
- Disegno logico DB

Schema Entity-relationship
- Disegno fisico DB
- Forme normali
- Query language e implementazioni su mySQL
DML
SQL

- Organizzazione fisica dei dati
- Ottimizzazione degli indici
- Modellazione dei dati in UML
- Normalizzazione e Denormalizzazione
- Ottimizzazione delle interrogazioni
------ MySQL e ottimizzazioni

- Transazioni
------ Locking a due fasi, Timestamp,MVCC
------ MySQL e Storage Engine

- Basi di dati attive
------ Trigger e Stored Procedure
------ Cursor, Trigger e Stored Procedure in MySQL

- Aspetti delle Basi di dati della conoscenza (Prof. Basili)
- Basi di dati geospaziali e GIS
- Basi di dati su architetture distribuite
------ Commit a due fasi
- Architetture per l' analisi dei dati
------ Data Warehouse
------ Data Mining

- Implementazione progetto

Testi di riferimento




- Atzeni, Ceri,Parboschi, Torlone Basi di dati, modelli e linguaggi di interrogazione McGraw-Hill ;
- Welling-Thomson MySQL Tutorial (opzionale) ;

- Atzeni,Ceri,Fraternali,Paraboschi,Torlone Basi di dati -
Architetture e linee di evoluzione ed. McGraw-Hill 2nd edition
- Schwartz,Zaitsev,Tkachenko,Zawodny, Lentz & Balling High Performance MySQL ed. O'Reilly 2nd edition





Per chi non ha già comprato i libri di testo precedenti esiste una nuova edizione unica per il I e II semetre :

Atzeni,Ceri,Fraternali,Paraboschi,Torlone Basi di dati - ed. McGraw-Hill 4nd edition (59 euro)



- lucidi di L. Vigliano presentati a Lezione

Consigliati :
- Elmasri,Navathe Sistemi di basi di dati Pearson

Parte 1, calcolabilità.
Macchine di Turing: trasduttori e riconoscitori, macchine ad un nastro e a k nastri, macchine deterministiche e non deterministiche; Macchina di Turing universale.
Linguaggi e funzioni: accettabilità e decidibilità di linguaggi, calcolabilità di funzioni. La tesi di Church-Turing e modelli di calcolo equivalenti alla macchina di Turing.
Linguaggi non decidibili: insiemi numerabili e non numerabili, diagonalizzazione. L’Halting Problem.
Parte 2, complessità:
Misure di complessità: DTIME, DSPACE, NTIME, NSPACE.
Classi di linguaggi. 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. Riducibilità polinomiale e chiusura di P rispetto alla riducibilità polinomiale. Problemi in P: 2-SAT, 2-COLORABILITA'. Funzioni in FP: trasformazione di una funzione booleana in forma congiuntiva normale.
La classe NP. Linguaggi NP-completi e Teorema di Cook. 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.

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.

Programma del Corso Specifico del Modulo B
Paradigma Dichiarativo (Modulo B 4CFU)
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 (Modulo B 2CFU)
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.

Libri di testo:
- Paradigma ad Oggetti: Thinking in Java (4th edition), ISBN-10: 0131872486 | ISBN-13: 978-0131872486
- Paradigma Dichiarativo: I. Bratko, Prolog Programming for Artificial Intelligence, Addison Wesley
- Paradigma Funzionale: verrà comunicato al secondo semestre
Ulteriore materiale:
- Sun Java Tutorials

Programma
Prima Parte:
Il ciclo di vita del software
Gestione dei requisiti software (Principalmente).
Design (Cenni).
Sviluppo (Cenni).
Verifica e validazione (Cenni).
Il linguaggio di modellazione UML e il suo uso nell'analisi dei requisiti.

Testi di riferimento
I. Sommerville
Software Engineering 7
(o edizioni successive)
(come integrazione consultare anche:
MACIASZEK, L.A. and LIONG, B.L. (2005):
Practical Software Engineering. A Case Study Approach
Addison Wesley)
Per UML:
L. Baresi, L. Lavazza, M. Pianciamore
Dall'idea al codice con UML 2
Addison Wesley

PROCESSO SOFTWARE
Pianificazione di progetti di sviluppo software, progetto preliminare, progetto dettagliato. Qualità del software e fattori di qualità.
ARCHITETTURE, STANDARD E TECNOLOGIE DI PRODUZIONE SOFTWARE .
Architetture basate su componenti, architetture orientate ai servizi.
Model-driven Engineering (MDE) e approccio MDE basato su Model Driven Architecture (MDA). Standard MDA (MOF, XMI, etc.). Cenni su linguaggi e strumenti di model transformation (QVT, ATL, etc.).

Dispense delle lezioni.