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”

Appunti

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

Appunti per il corso di Informatica 1

Appunti sintetici su alcuni dei temi principali del corso di Informatica 1 (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

[PDF]

Appunti sugli algoritmi e la complessità computazionale

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

[PDF]

Appunti sulla teoria degli automi e della calcolabilità

Appunti sulla teoria degli automi a stati finiti, sui linguaggi e le grammatiche, sulla teoria della calcolabilità e della complessità computazionale. Ottobre 2005

[PDF]

Appunti introduttivi sulla progettazione di algoritmi

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. Ottobre 2007

[PDF]

Appunti sulle Reti di Petri

Appunti elementari introduttivi sulle reti di Petri (Petri nets).

[PDF]

Appunti sul 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.

[PDF]

Appunti sui grafi clique iterati

Dato un grafo G si può calcolare il grafo K(G) ottenuto per intersezione delle clique di G. In questi appunti sintetizzo alcuni dei risultati dello studio del comportamento di alcune classi di grafi sottoposte all'azione iterata di questa operazione: quale è il loro comportamento? Il numero di vertici diminuisce, si stabilizza o cresce fino all'infinito? Novembre 2005

[PDF]

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. Luglio 2006

[PDF]

Guide e manuali

UNIX: introduzione elementare

Una guida al sistema operativo UNIX per principianti che ho scritto alcuni anni fa e che recentemente ho rivisto, corretto ed ampliato. Settembre 2005

[PDF | HTML]

Principali comandi della shell UNIX

Uno specchietto riepilogativo commentato di alcuni tra i principali comandi della shell UNIX.

[PDF]

Programmazione della shell Bash

Manuale introduttivo al linguaggio di programmazione Bash, per la realizzazione di shell script di sistema e script CGI per semplici applicazioni web based.

[PDF | HTML]

Grafi e ottimizzazione combinatoria con Mathematica

Appunti sull'uso del software Mathematica con il pacchetto DiscreteMath::Combinatorica per la rappresentazione e lo studio di grafi e di problemi di ottimizzazione combinatoria. Agosto 2005

[PDF]

Introduzione al Perl

Una guida introduttiva alla programmazione in linguaggio Perl.

[Postscript | PDF | HTML]

Slide di presentazioni e seminari

Strategie matematiche

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. Novembre 2009

[PDF]

Protocollo HTTP, interfaccia CGI, linguaggio Perl

Slide di un seminario introduttivo alla programmazione di applicazioni web utilizzando il linguaggio Perl. Dicembre 2004

[PDF]

Linguaggio HTML

Introduzione al linguaggio HTML e ai fogli di stile CSS; HTML come strumento per la definizione della struttura di un documento, come strumento per definire documenti ipertestuali, come strumento per definire l'interfaccia utente di una applicazione web, come strumento per definire il lay-out tipografico di un documento. Dicembre 2004

[PDF]

Cenni sul linguaggio C

Slide con alcuni appunti sulle basi del linguaggio C. Febbraio 1999

[PDF]

Introduzione al linguaggio SQL

Slide di un seminario introduttivo al linguaggio SQL e alle basi dati relazionali. Dicembre 2004

[PDF]

Il più grande problema (irrisolto) dell'informatica

Slide di un seminario introduttivo ai concetti di base della complessità computazionale e al problema "P=NP" tenuto agli studenti del quinto anno del Liceo Scientifico Statale "Giuseppe Peano" di Roma (aprile 2005); sono anche disponibili delle note integrative, meno schematiche dei lucidi, che ho lasciato agli studenti al termine del seminario.

[Slide | Note]

Home page

Corso di Informatica 1

Ottimizzazione Combinatoria

Documenti, slide e appunti

Link e bibliografia

Tesi di laurea