Home page di Marco Liverani

Documenti, slide e appunti

“Chiedersi se un computer potrà mai pensare è un po' come
interrogarsi sulla possibilità che un sommergibile impari a nuotare”
−− Edsger Wybe Dijkstra (1930-2002)

Appunti

Appunti per il corso di Sistemi per l'elaborazione delle informazioni (IN530)

Slide utilizzate per le lezioni del corso presso il Corso di Laurea Magistrale in Matematica dell'Università degli Studi Roma Tre:

Presentazione del corso (aggiornamento del 16/3/2015): Presentazione del corso e dei suoi oobiettivi, orario delle lezioni, prova finale, bibliografia.
Dal computer al sistema informativo (aggiornamento del 16/3/2015): Breve cronologia dell'evoluzione dei sistemi informatici dagli anni '50/'60 ad oggi; principali architetture applicative: applicazioni centralizzate, applicazioni client server, applicazioni web based “three-tier”, architetture SOA (service oriented architecture), infrastrutture cloud.
Componenti di un sistema informativo aziendale (aggiornamento del 16/3/2015): Presentzione di un'ipotesi semplificata di struttura organizzativa aziendale e delle esigenze di carattere informativo e di condivisione dei dati tra le diverse unità organizzative dell'azienda; componenti che costituiscono la struttura del sistema informativo aziendale; focalizzazione sulle diverse componenti software di un sistema informativo.
Sistemi Operativi (aggiornamento del 16/3/2015): Scopo e caratteristiche principali di un sistema operativo, struttura del sistema operativo, kernel, gestione dei processi e scheduler, gestione della memoria primaria, gestione del filesystem, gestione delle periferiche e delle unità di I/O, gestione della memoria secondaria, gestione della sicurezza, interfaccia verso gli utenti, il sistema X Window.
Reti di computer (aggiornamento del 16/3/2015): Funzioni di una rete, classificazioni in base alla topologia, all'estensione fisica, alla modalità di comunicazione; modello a livelli dell'architettura informatica del software per la gestione della rete, il modello ISO/OSI, il modello OSI semplificato, l'architettura TCP/IP; descrizione delle funzioni e dei protocolli relativi ai cinque livelli della pila OSI semplificata (Fisico, Data Link, Network access, Transport, Application); alcuni protocolli applicativi (FTP, Telnet, SMTP, POP3, DNS), il sistema dei nomi di dominio; alcuni dispositivi hardware di rete.
Database relazionali (aggiornamento del 24/3/2015): Obiettivi dell'archiviazione informatica di informazioni, principali funzioni di un DBMS (DataBase Management System), il modello relazionale, il concetto di relazione, schema entità/relazioni, schema fisico; normalizzazione del database, forme normali, forma normale di Boyce e Codd; il linguaggio SQL, le istruzioni DDL (create, drop), le istruzioni DCL (grant, revoke), le istruzioni DML (insert, select, update, delete); inclusione di istruzioni SQL in altri linguaggi di programmazione, strumenti ORM; altri modelli di database, NO-SQL database.
Data Warehouse (aggiornamento del 20/4/2015): Sistemi operazionali e informazionali, scopi e caratteristiche di un data warehouse; struttura logica di un data warehouse, fatti, misure, dimensioni, il Dimensional Fact Model; operazioni comuni di analisi su un data warehouse; ipercubi, modello MOLAP e ROLAP; architettura di un sistema data warehouse.
Applicazioni Web Based (aggiornamento del 18/4/2017): Architettura di una web application, server HTTP, protocollo HTTP, URL, linguaggio di marcatura del testo HTML e fogli di stile CSS; interfaccia CGI (Common Gateway Interface) ed esempi per la realizzazione di una web application in linguaggio Perl; il framework JEE, i servlet Java e le pagine JSP (Java Server Pages); programmazione lato client e linguaggio Javascript. Vedi anche gli Appunti per la progettazione di un'applicazione web CGI.
Sicurezza dei Sistemi Informativi (aggiornamento del 9/5/2017): Requisiti della sicurezza delle informazioni: riservatezza (confidenzialità), integrità, disponibilità; minacce e attacchi informatici al sistema informativo, contromisure di sicurezza fisica e logica; sicurezza perimetrale, sicurezza degli end-point, sicurezza applicativa, sistemi AAA (authentication, authorization, accounting); sistemi di identity management; autenticazione, autenticazione forte, single sign-on, sistemi di access management, sistemi di identity federation, il sistema SPID italiano; raccolta di log e i sistemi SIEM; alcune normative sulla sicurezza delle informazioni.
Principi di Ingegneria del Software (aggiornamento del 21/5/2017): Ciclo di vita del prodotto software, fasi del ciclo di vita, attività e principali deliverable, figure professionali coinvolte; aspetti rilevanti nella progettazione del prodotto software, definizione dei requisiti, tipologie di requisito, definizione dell'architettura; UML (unified modeling language), use case diagram, class diagram, sequence diagram, activity diagram; gestione della configurazione; cenni sui sistemi di gestione per la qualità.
Qualche cenno sul mercato del lavoro in ambito informatico in Italia (aggiornamento del 21/5/2017): Mercato del lavoro, richiesta e offerta, settori economici, il mercato del lavoro in Italia, qualche statistica sulle tipologie di imprese e sulla distribuzione dei lavoratori, tipologie di imprese nell'ambito del mercato del lavoro nel settore dell'information technology, ruoli e piani di carriera in ambito informatico, cenni sui contratti di lavoro.

Appunti per il corso di Ottimizzazione Combinatoria (IN440: Algoritmi su grafi e reti di flusso)

Appunti su alcuni dei principali argomenti trattati durante il corso di Ottimizzazione Combinatoria (IN440) presso il Corso di Laurea in Matematica dell'Università Roma Tre:

Algoritmi e complessità computazionale (23/2/2014): algoritmi, pseudo-codifica degli algoritmi, principi della programmazione strutturata. Problemi decidibili e indecidibili, complessità computazionale di un algoritmo, algoritmi polinomiali e super-polinomiali; notazioni O(f(n)), Ω(f(n)), Θ(f(n)). Limite inferiore alla complessità dell'algoritmo risolutivo per il problema dell'ordinamento; classi di complessità per problemi: le classi P, NP, NP-completa e NP-hard. Vedi anche gli Appunti sulla calcolabilità.
Insiemi ed elementi di calcolo combinatorio (2/3/2014): insiemi, operazioni sugli insiemi, corrispondenze e relazioni tra insiemi, cardinalità; insieme delle parti; permutazioni, disposizioni semplici e con ripetizioni, combinazioni semplici, coefficiente binomiale.
Ottimizzazione Combinatoria con Mathematica (15/3/2014): introduzione all'uso del pacchetto software Mathematica; il package DiscreteMath::Combinatorica contenente una libreria di funzioni per il calcolo combinatorio e le operazioni sui grafi.
Elementi di Teoria dei Grafi (5/3/2014): grafi, grafi orientati, grafi completi, grado dei vertici di un grafo; cammini e cicli, cicli hamiltoniani, circuiti euleriani, grafi connessi e fortemente connessi; isomorfismi tra grafi, planarità, Teorema di Kuratowski; operazioni tra grafi; alberi, alberi con radice, foreste.
Problemi di Ottimizzazione (13/4/2014): problemi in forma decisionale, di ricerca, di enumerazione e di ottimizzazione; formulazione generale di un problema di ottimizzazione; formulazione di un problema di programmazione matematica: problemi di programmazione non lineare, di programmazione convessa, di programmazione lineare; problemi di programmazione lineare intera, esempi.
Cammini di costo minimo (29/12/2017): Problema del cammino di costo minimo da una sorgente singola su un grafo, gli algoritmi di Dijkstra e di Bellman-Ford, problema del cammino di costo minimo per tutte le coppie di vertici del grafo, tecnica di programmazione dinamica, algoritmo di Floyd-Warshall, algoritmo per il calcolo della chiusura transitiva di un grafo.
Partizionamento ottimo di grafi in componenti connesse 10/5/2014: problemi di partizionamento di grafi, problemi di p-partizionamento di grafi in componenti connesse, problemi di clustering e di equipartizione, metodi risolutivi ed algoritmi, complessità dei problemi, applicazioni ed esempi.
Il problema del matrimonio stabile 11/5/2014: definizione del problema del matrimonio stabile, esempi; generalizzazioni del problema, applicazioni; l'algoritmo risolutivo di Gale e Shapley, proprietà dell'algoritmo.

Slide del corso di Ottimizzazione Combinatoria (IN440: Algoritmi su grafi e reti di flusso)

Slide delle lezioni del corso di Ottimizzazione Combinatoria (IN440) presso il Corso di Laurea in Matematica dell'Università Roma Tre:

Introduzione al corso. Presentazione del corso, orari e argomenti delle lezioni, testi, modalità di esame.
Complessità computazionale. Problemi e algoritmi, complessità computazionale di un algoritmo, complessità computazionale di un problema, classi di complessità P, NP, NP-complete, NP-hard.
Insiemi e calcolo combinatorio. Insiemi, insieme delle parti, permutazioni di un insieme, disposizioni, combinazioni, coefficiente binomiale, triangolo di Tartaglia, quadrati latini, il gioco del Sudoku.
Introduzione alla teoria dei grafi. Principali definizioni e proprietà dei grafi, alberi, cammini, grafi Hamiltoniani, grafi Euleriani, clique, grafi clique-iterati, grafi multipartiti, isomorfismi tra grafi, grafi planari, colorazione di grafi.
Algoritmi elementari su grafi. Algoritmi di visita in ampiezza e in profondità di un grafo, componenti fortemente connesse di un grafo orientato, punti di articolazione, ponti, alberi binari di ricerca.
Ottimizzazione combinatoria e programmazione matematica. Tipi di problema, i problemi di ottimizzazione, problemi di programmazione matematica, di programmazione convessa, di programmazione lineare, cenni sul metodo del simplesso.
Alberi ricoprenti di costo minimo. Alberi ricoprenti, il problema del minimum spanning tree, algoritmo di Kruskal, Algoritmo di Prim, Algoritmo di Boruvka-Sollin.
Cammini di costo minimo. Il problema del calcolo dei cammini di costo minimo da una singola sorgente, algoritmo di Dijkstra, algoritmo di Bellman-Ford, programmazione dinamica, calcolo dei cammini di costo minimo fra tutte le coppie di vertici di un grafo, algoritmo All Pairs Shortest Path, algoritmo di Floyd-Warshall, chiusura transitiva di un grafo orientato.
Flusso massimo su una rete. Reti di flusso, capacità della rete, flusso, capacità residua e cammini aumentanti, algoritmo di Ford e Fulkerson, Teorema del Flusso Massimo e Taglio Minimo, algoritmo di Edmonds-Karp, algoritmo Push-Relabel.
Partizionamento di grafi in componenti connesse. Definizione dei problemi di equipartizione di un grafo e di clustering, funzioni obiettivo, strategie per la costruzione di algoritmi risolutivi, equipartizione di alberi e di cammini.
Problemi di matching e il matrimonio stabile. Definizione del problema del matrimonio stabile, generalizzazioni del problema, esempi, algoritmo di Gale & Shapley.
Codici di Huffman. Codici, codici a lunghezza fissa e variabile, codici prefissi, algoritmo per la costruzione di un codice di Huffman.
Algoritmi approssimanti per problemi NP-completi. Algoritmi approssimanti, rapporto di approssimazione, algoritmi approssimanti per il problema della copertura di vertici (vertex cover), algoritmi approssimanti per il problema della copertura di insiemi (set cover).
Riepilogo degli argomenti. Riepilogo degli argomenti trattati nelle lezioni del corso IN440.
Linguaggio Python. Introduzione alla programmazione in linguaggio Python, sintassi generale, strutture di controllo, variabili e strutture dati di base.
Grafica in linguaggio Python. La libreria Python MatPlotLib e il modulo PyLab, la libreria Graphics, esempi.
Strutture dati in Python. La libreria pythonds, gli oggetti per la rappresentazione delle strutture dati di pila (stack), coda (queue), coda a doppia entrata (deque), albero binario di ricerca, heap binario, grafo.
Wolfram Mathematica. Introduzione all'utilizzo del software Wolfram Mathematica, modalità di utilizzo generale, operazioni su insiemi, operazioni su grafi, visualizzazione di grafi e alberi.
Introduzione a Latex. Linguaggi di mark-up, TeX e LaTeX, modelli di documento in Latex, struttura di un documento (articolo), sintassi generale dei comandi Latex, tag per la formattazione del testo, tag per liste ed elenchi, figure e note a pié di pagina, pseudo-codice di algoritmi, codice di programmi.

Appunti per il corso di Algoritmi e Strutture Dati (IN110)

Appunti sintetici su alcuni dei temi principali del corso di Algoritmi e Strutture Dati (IN110) presso il Corso di Laurea in Matematica dell'Università Roma Tre:

Introduzione: organizzazione della didattica del corso, riferimenti bibliografici, ecc.
Algoritmi e diagrammi di flusso: introduzione alla programmazione, abilità e competenze del programmatore, linguaggi, diagrammi di flusso, programmazione strutturata.
Modelli di calcolo: macchina di Turing, modello di Von Neumann.
Linguaggi di programmazione: linguaggi imperativi, linguaggi dichiarativi, compilatori ed interpreti.
Rappresentazione delle informazioni: numerazione in base 2 e in base 16, organizzazione della memoria di un calcolatore, tipi di dato.
Introduzione al linguaggio C: appunti introduttivi sul linguaggio di programmazione C.
Grafi e alberi: cenni introduttivi sulla teoria dei grafi.

Algoritmi di sort

Appunti sugli algoritmi di ordinamento: Selection sort, Insertion sort, Bubble sort, Quick sort, Merge sort, Heap sort, Counting sort, Bucket sort. Luglio 2005

Home page di Marco Liverani

Documenti, slide e appunti

Appunti

Guide e manuali

Slide di presentazioni e seminari