Algoritmi

Questa sezione della documentazione della libreria ASD si occupa degli algoritmi.

Algoritmi
Nome	Figura	Descrizione
fibonacci
fibonacci1	1.3	Algoritmo numerico per il calcolo dell'n-esimo numero di Fibonacci.
fibonacci2	1.4	Algoritmo ricorsivo per il calcolo dell'n-esimo numero di Fibonacci.
fibonacci3	1.6	Algoritmo iterativo per il calcolo dell'n-esimo numero di Fibonacci.
fibonacci4	1.8	Algoritmo iterativo con programmazione dinamica per il calcolo dell'n-esimo numero di Fibonacci.
fibonacci5	1.10	Algoritmo basato su potenze ricorsive per il calcolo dell'n-esimo numero di Fibonacci.
fibonacci6	1.11	Algoritmo basato su potenze ricorsive per il calcolo dell'n-esimo numero di Fibonacci.
ricerca
ricercaSequenziale	2.2	Algoritmo per la ricerca sequenziale.
ricercaBinariaIter	2.4	Implementazione iterativa dell'algoritmo per la ricerca binaria.
ricercaBinariaRic	2.5	Implementazione ricorsiva dell'algoritmo per la ricerca binaria.
ricercaRandomizzata	2.8	Algoritmo randomizzato per la ricerca sequenziale.
ordinamento
selectionSort	4.2	Ordinamento per selezione.
insertionSort	4.4	Ordinamento per inserimento.
bubbleSort	4.5	Ordinamento a bolle.
heapSort	4.11, 4.8, 4.10	L'algoritmo heapSort.
mergeSort	4.14, 4.13	L'algoritmo mergeSort.
itermergeSort		L'algoritmo mergeSort iterativo.
quickSort	4.16	L'algoritmo quickSort.
quickSort (in loco)	4.17	L'algoritmo quickSort con l'uso della procedura partition per partizionare in loco.
iterquickSort		L'algoritmo quickSort iterativo.
integerSort	4.20	L'algoritmo integerSort.
bucketSort	4.22	L'algoritmo bucketSort.
radixSort	4.23	L'algoritmo radixSort.
selezione
minimo	5.1	Ricerca del minimo.
secondoMinimo	5.2	Ricerca del secondo minimo.
heapSelect	5.4	L'algoritmo heapSelect.
select1	5.5	Adattamento dell'algoritmo quickSort al problema della selezione.
select2	5.6	Una variante dell'algoritmo di selezione select1.
quickSelect	5.7	L'algoritmo randomizzato quickSelect.
select	5.10	L'algoritmo deterministico select.
visita di un albero
visitaDFS	3.13	Visita in profondità iterativa (preordine) di un albero a partire da un nodo r.
visitaDFSRicorsiva_preordine	3.14	Visita in profondità ricorsiva (preordine) di un albero a partire da un nodo r.
visitaDFSRicorsiva_simmetrica	3.14	Visita in profondità ricorsiva (simmetrica) di un albero a partire da un nodo r.
visitaDFSRicorsiva_postordine	3.14	Visita in profondità ricorsiva (postordine) di un albero a partire da un nodo r.
visitaBFS	3.15	Visita in ampiezza di un albero a partire da un nodo r.
profondita	3.16	Calcolo della profondita' di un albero.
visita di un grafo
visitaBFS	11.7	Algoritmo di visita in ampiezza in un grafo G a partire dal vertice s.
visitaDFS	11.9	Algoritmo ricorsivo per la visita in profondita' di un grafo G a partire da un vertice s.
connessoGrafo	11.13	Algoritmo che verifica se un grafo G e' connesso.
fortementeConnesso	11.15	Algoritmo che verifica se un grafo orientato G e' fortemente connesso.
minimo albero ricoprente di un grafo non orientato
Kruskal	12.4	Implementazione dell'algoritmo di Kruskal con strutture dati union-find.
Prim	12.7	Algoritmo di Prim implementato con coda con priorita'.
cammini minimi di un grafo orientato
BellmanFord	13.4	Algoritmo di Bellman e Ford per il calcolo delle distanze a partire da una sorgente s in un grafo orientato.
ordinamentoTopologico	13.6	Algoritmo per il calcolo di un ordinamento topologico del grafo orientato aciclico G.
distanzeAciclico	13.7	Algoritmo per il calcolo delle distanze a partire da una sorgente s in un grafo orientato aciclico G.
Dijkstra	13.11	Algoritmo di Dijkstra implementato con una coda con priorita'.
FloydWarshall	13.12	Algoritmo di Floyd e Warshall per il calcolo delle distanze tra tutte le coppie di vertici.