Corso di Ottimizzazione Combinatoria (IN440)

Esercizi e sorgenti dei programmi

In questa pagina sono raccolti un insieme di esercizi e di sorgenti di programmi realizzati durante le esercitazioni in laboratorio. Sono disponibili le istruzioni per l'installazione e l'utilizzo del programma Cygwin in ambiente Windows per la compilazione e l'esecuzione di programmi in linguaggio C.

Combinatoria su insiemi

Stringhe Binarie
Calcola e visualizza tutte le 2n stringhe binarie S = (s0, s1, ..., sn−1) di lunghezza n.
Permutazioni
Calcola e visualizza tutte le n! permutazioni degli elementi di un insieme di cardinalità n.

Algoritmi su grafi e reti di flusso

Libreria grafi.c
Una libreria di funzioni utili in linguaggio C per la realizzazione di programmi su grafi.
Componenti Fortmente Connesse
Codifica delle funzioni per il calcolo delle componenti fortemente connesse di un grafo G orientato.
Ordinamento topologico
Programmino per il calcolo dell'ordinamento topologico dell'insieme dei vertici di un grafo orientato aciclico.
Algoritmo di Bellman-Ford per grafi orientati aciclici
Codifica dell'algoritmo di Bellman-Ford per la costruzione dei cammini di costo minimo da una sorgente singola su un grafo orientato, aciclico, con pesi assegnati agli spigoli.
Cammini di costo minimo tra tutte le coppie di vertici di un grafo pesato
Codifica dell'algoritmo ALLPAIRSSHORTESTPATH per la soluzione del problema del calcolo del costo del cammino minimo per collegare ogni coppia di vertici di un grafo con pesi assegnati agli spigoli. L'algoritmo adotta la tecnica della programmazione dinamica.
Cammini di costo minimo tra tutte le coppie di vertici di un grafo pesato (ottimizzato)
Codifica dell'algoritmo FASTALLPAIRSSHORTESTPATH per la soluzione del problema del calcolo del costo del cammino minimo per collegare ogni coppia di vertici di un grafo con pesi assegnati agli spigoli. L'algoritmo adotta la tecnica della programmazione dinamica ed introduce un criterio di ottimizzazione che lo rende più efficiente rispetto all'algoritmo ALLPAIRSSHORTESTPATH.
Algoritmo di Floyd-Warshall
Codifica dell'algoritmo di Floyd-Warshall per la soluzione del problema del calcolo del cammino di costo minimo per collegare ogni coppia di vertici di un grafo con pesi assegnati agli spigoli. L'algoritmo adotta la tecnica della programmazione dinamica e calcola anche la matrice di adiacenza del grafo chiusura transitiva di G.
Algoritmo Push-Relabel
Codifica dell'algoritmo PUSHRELABEL per la soluzione del problema del calcolo del valore del flusso massimo su una rete G.
Partizionamento di un albero
Calcolo di tutte le p-partizioni in p componenti connesse non nulle di un albero T con n vertici.

Altri programmi in linguaggio Python

Grafico di una spirale
Disegno del grafico di una spirale utilizzando le funzioni offerte dalla libreria grafica Graphics Documento in formato PDF per il il linguaggio Python.
Insieme di Mandelbrot
Rappresentazione grafica dell'insieme di Mandelbrot sul piano complesso, mediante l'utilizzo della libreria Graphics Documento in formato PDF per il il linguaggio Python.

Università degli Studi Roma Tre - Dipartimento di Matematica e Fisica - Corso di laurea in Matematica - Corso di Ottimizzazione Combinatoria (IN440)

Author: Marco Liverani - Last modified: Saturday September 05, 2020 - Document URI: https://www.mat.uniroma3.it/users/liverani/IN440/esercizi.shtml