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à

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

Appunti sugli algoritmi, sui problemi e sulle classi di complessità computazionale per algoritmi e problemi.

Strategie matematiche (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)

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

Partizionamento ottimo di grafi in componenti connesse

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

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

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.

HyperText Markup Language

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

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

Le slide di un seminario introduttivo alle basi dati relazionali e al linguaggio di gestione e interrogazione SQL.

Esercizi di programmazione in linguaggio C

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à computazionale (1/10/2008)

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 (4/10/2008)

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 (7/10/2008)

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 (18/10/2008)

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 (29/10/2008)

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.

Partizionamento ottimo di grafi in componenti connesse (8/12/2008)

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 (5/1/2009)

Definizione del problema del matrimonio stabile, esempi; generalizzazioni del problema, applicazioni; l'algoritmo risolutivo di Gale e Shapley, proprietà dell'algoritmo.

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

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.