Ricorsione e problem-solving

1 Introduzione
1.1 Premessa
1.2 Tipologie di problemi
1.3 Risoluzione mediante esplorazione di spazi
1.4 Gli algoritmi di visita dello spazio
1.5 La simmetria delle soluzioni
1.6 Il paradigma risolutivo proposto
2 La ricorsione
2.1 Introduzione
2.1.1 Analisi di complessità
2.2 Problemi ricorsivi in ambito matematico
2.2.1 Il fattoriale
2.2.2 I numeri di Fibonacci
2.2.3 Il massimo comune divisore
2.2.4 Il massimo di un vettore di interi
2.2.5 La moltiplicazione di 2 interi positivi
2.3 Problemi ricorsivi in ambito informatico
2.3.1 Ricerca binaria o dicotomica
2.3.2 Ordinamenti ricorsivi: il MergeSort
2.3.3 Ordinamenti ricorsivi: il QuickSort
2.3.4 Funzioni ricorsive su liste concatenate
2.3.5 Funzioni ricorsive su alberi binari
2.4 Matematica ricreativa
2.4.1 Le Torri di Hanoi
2.4.2 Il triangolo di Sierpinski
2.5 Meccanismi computazionali per l’esecuzione di funzioni ricorsive
2.6 Dualità ricorsione-iterazione
2.7 La ricorsione in C: variabili globali, locali e parametri
2.8 Esercizi svolti
2.9 Esercizi proposti
3 La visita degli spazi
3.1 Introduzione
3.2 Richiami di calcolo combinatorio
3.2.1 Principio di addizione
3.2.2 Principio di moltiplicazione
3.2.3 Disposizioni semplici
3.2.4 Disposizioni con ripetizioni
3.2.5 Permutazioni semplici
3.2.6 Permutazioni con ripetizione
3.2.7 Combinazioni semplici
3.2.8 Combinazioni con ripetizione
3.2.9 Insieme delle parti (“powerset”)
3.2.10 Partizionamenti
3.3 Esplorazione esaustiva dello spazio delle soluzioni
3.3.1 La scomposizione in sottoproblemi
3.3.2 Funzioni ricorsive e strutture dati
3.3.3 Principio di moltiplicazione
3.3.4 Principi-base dell’esplorazione dei modelli di spazio
3.3.5 Disposizioni semplici
3.3.6 Disposizioni ripetute
3.3.7 Permutazioni semplici
3.3.8 Permutazioni ripetute
3.3.9 Combinazioni semplici
3.3.10 Combinazioni ripetute
3.3.11 L’insieme delle parti (powerset)
3.3.12 I partizionamenti
3.4 Determinazione di una sola tra le soluzioni dello spazio
3.5 I problemi di ottimizzazione
3.5.1 Il conto corrente
3.5.2 Lo zaino
4 Vincoli e pruning
4.1 Introduzione
4.2 Rappresentazione e valutazione dei vincoli
4.2.1 La somma di un sottoinsieme di interi
4.3 Il pruning dello spazio degli stati
4.3.1 La somma di un sottoinsieme di interi: versione con pruning
4.3.2 Lo zaino: versione con pruning
4.3.3 Il quadrato magico
4.4 Metodo del Branch and Bound
4.5 Esercizi svolti
4.5.1 Sostanze
4.5.2 Prodotti e Fornitori
5 Problemi sui grafi
5.1 Richiami sui grafi
5.2 Visita di grafi
5.3 Il labirinto
5.4 Rete di calcolatori
5.5 Esercizi proposti
6 Problemi svolti
6.1 Interruttori e lampadine
6.2 Longest Increasing Sequence
6.3 Le 8 regine
6.4 Aritmetica verbale
6.5 Il Sudoku
6.6 Il Tour del Cavallo
6.7 Biblioteca personale
6.8 Acquisto di scaffalature
6.9 Generazione automatica di quiz
6.10 Spesa in tempo di crisi
6.11 Assegnazione ottima di compiti - 1
6.12 Regali e diplomazia
6.13 Somme incomplete
7 Problemi proposti
7.1 Uso dei modelli del Calcolo Combinatorio
7.2 Futoshiki
7.3 Il Nonogram
7.4 Il turista low-cost
7.5 Assegnazione ottima di compiti - 2
7.6 Il gioco del 15
7.7 Orario settimanale di Scuola Serale
7.8 Conteggio di regioni
Bibliografia