Aquilante, la malabestia

La home page personale di Marco Liverani, ovvero una raccolta di manuali, note ed altre informazioni

Note e appunti

In questa pagina ho raccolto alcuni degli appunti su vari temi di informatica e matematica che ho scritto negli anni, tipicamente con l'intento di fornire una breve sintesi dell'argomento destinata a colleghi, amici e studenti che avessero la necessità di affrontarlo per la prima volta. Anche in questo caso l'obiettivo è dunque quello di introdurre rapidamente: l'approfondimento ed una trattazione esaustiva vanno cercati altrove.

Algoritmi

Automi, linguaggi, calcolabilità Formato PDF
Elementi sulla teoria degli automi a stati finiti, sui linguaggi formali e le grammatiche e sulla teoria della calcolabilità e della complessità computazionale.
Algoritmi e complessità computazionale Formato PDF
Appunti sugli algoritmi, sui problemi e sulle classi di complessità computazionale per algoritmi e problemi.
Appunti introduttivi sulla progettazione di algoritmi Formato PDF
Appunti ed esempi sui concetti fondamentali relativi alla progettazione di algoritmi tenendo conto delle regole della programmazione strutturata e delle caratteristiche di base dei linguaggi di programmazione “imperativi/procedurali”. Il documento contiene alcuni esempi elementari sviluppati proponendo la pseudo-codifica degli algoritmi, la raprpesentazione dell'algoritmo mediante un diagramma di flusso ed una codifica in linguaggio C.
Strategie matematicheFormato PDF (30/11/2009)
Slide di una conferenza sui metodi, le strategie e i modelli per la soluzione di problemi di combinatoria tenuto insieme a Sara Nicoloso (IASI CNR); il seminario si è svolto il 30/11/2009 presso la Facoltà di Scienze della Formazione dell'Università Roma Tre, nell'ambito del ciclo di conferenze “Innovazione e tradizione nella matematica e nel suo insegnamento” curato dalla prof.ssa Ana Millán Gasca.
Algoritmi di ordinamento (sort) Formato PDF
Appunti sui principali algoritmi di ordinamento di una sequenza di dati (Selection sort, Insertion sort, Bubble sort, Quick sort, Merge sort, Heap sort, Counting sort, Bucket sort).
Cammini di costo minimo: problemi e algoritmi Formato PDF
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 Formato PDF
Appunti sintetici sui problemi, sulle tecniche risolutive e sugli algoritmi per il partizionamento in componenti connesse di grafi tale da ottimizzare una determinata funzione obiettivo. Vedi anche le slide di un ciclo di seminari tenuto da Bruno Simeone alla Rutgers University nel 1999.
Grafi clique iterati Formato PDF
Appunti sullo studio del comportamento di classi di grafi sottoposte all'azione iterata dell'operatore clique. Dato un grafo G si può calcolare il grafo K(G) ottenuto per intersezione delle clique (sottografi completi massimali) di G. In questi appunti sintetizzo alcuni dei risultati dello studio del comportamento di alcune classi di grafi sottoposte all'azione iterata di questo operatore: quale è il loro comportamento? Il numero di vertici diminuisce, si stabilizza o cresce fino all'infinito?

Linguaggi e programmazione

Protocollo HTTP, interfaccia CGI, linguaggio Perl Formato PDF
Le slide di un breve ciclo di lezioni introduttive su alcune delle tecnologie che sono alla base delle applicazioni web: il protocollo HTTP (HyperText Markup Language), l'interfaccia CGI (Common Gateway Interface) e il linguaggio Perl (Practical Extraction and Report Language) che può essere utilizzato facilmente per creare semplici web application. Sono disponibili anche le slide di un seminario analogo che ho tenuto nel 1996: formato HTML e formato PDF.
Appunti sulla progettazione di un'applicazione web CGI Formato PDF
Appunti per il corso di Sistemi per l'elaborazione delle informazioni (IN530) del Corso di Laurea Magistrale in Matematica dell'Università Roma Tre, sulla progettazione di una semplicissima applicazione web CGI.
HyperText Markup Language Formato PDF
Versione HTML dei lucidi di un seminario introduttivo al linguaggio per la creazione di ipertesti sul World-Wide Web. Disponibile anche in formato PDF; versione PDF dei lucidi di un seminario più recente (dicembre 2004) che ho tenuto sul linguaggio HTML.
Linguaggio C Formato PDF
Appunti sintetici e schematici sul linguaggio di programmazione C. Sono disponibili anche dei lucidi di un seminario che ho tenuto diversi anni fa sullo stesso argomento.
Linguaggio SQL Formato PDF
Le slide di un seminario introduttivo alle basi dati relazionali e al linguaggio di gestione e interrogazione SQL.
Esercizi di programmazione in linguaggio C Formato PDF
Una raccolta di esercizi svolti di programmazione in linguaggio C che ho preparato, negli anni passati, per le prove di esonero e di esame del mio corso di Informatica 1 presso il Corso di Laurea in Matematica dell'Università Roma Tre.

Ottimizzazione combinatoria

Appunti e dispense scritte per gli studenti del corso di Ottimizzazione Combinatoria, in cui presento alcuni aspetti della teoria della complessità computazionale, della teoria dei grafi e presento alcuni algoritmi risolutivi per problemi di ottimizzazione su grafi e reti di flusso.

Algoritmi e complessità computazionaleFormato PDF (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àFormato PDF.
Insiemi ed elementi di calcolo combinatorioFormato PDF (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 MathematicaFormato PDF (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 GrafiFormato PDF (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 e Programmazione LineareFormato PDF (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: problemi e algoritmiFormato PDF (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 connesseFormato PDF (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 stabileFormato PDF (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 Ottimizzazione combinatoria (algoritmi su grafi)

  • 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.

Sistemi Informativi Aziendali

Dispense sotto forma di slide del corso “Sistemi per l'elaborazione delle informazioni” che tengo presso il Corso di Laurea Magistrale in Matematica dell'Università degli Studi Roma Tre.

1. Dal computer al sistema informativoFormato PDF (aggiornamento del 18/2/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.
2. Componenti di un sistema informativo aziendaleFormato PDF (aggiornamento del 23/2/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.
3. Sistemi OperativiFormato PDF (aggiornamento del 1/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.
4. Reti di computerFormato PDF (aggiornamento del 9/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.
5. Database relazionaliFormato PDF (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.
6. Data WarehouseFormato PDF (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.
7. Applicazioni Web BasedFormato PDF (aggiornamento del 10/5/2015)
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.
8. Sicurezza dei Sistemi InformativiFormato PDF (aggiornamento del 24/5/2015)
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.
9. Principi di Ingegneria del SoftwareFormato PDF (aggiornamento del 24/5/2015)
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à.
10. Qualche cenno sul mercato del lavoro in ambito informatico in ItaliaFormato PDF (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.

Strumenti e tecnologie

Appunti su CVS
Appunti sintetici sull'uso del software CVS (Concurrent Versions System) per la gestione del controllo della configurazione e delle versioni dei sorgenti di un progetto software.
Appunti sulla documentazione di un progetto Java Formato PDF
Una breve nota sulla modalità con cui è opportuno documentare un progetto software object oriented in linguaggio Java, mediante diagrammi delle classi UML e annotazioni nei file sorgente per produrre documentazione tecnica ipertestuale con Javadoc.