Il concetto di ricorsione nasce dalla possibilità di eseguire un compito applicando lo stesso algoritmo ad un dominio ridotto rispetto a quello originale fondendo i risultati.
Le funzioni C possono essere usate ricorsivamente, cioè una funzione può chiamare se stessa sia direttamente che indirettamente.
Nella ricorsione è importante la condizione di uscita.
Il problema deve poter essere suddiviso in sotto-problemi più piccoli fino ad arrivare ad un sotto-problema banale di cui si conosce immediatamente la soluzione.
PROBLEMA: Voglio lavare una pila di 15 piatti.
Ho un sistema che riesce a lavare i piatti se ha in input una pila più piccola: (intuitivamente, il calcolatore è in grado di lavare 14 piatti).
Sia N=3
Assumiamo che il calcolatore sappia fare la stampa di N-1 interi (I primi due interi).
Il mio risultato è dato da:
dopo aver stampato i primi N-1 interi (2 interi)
stampa l’ennesimo intero (l’intero 3)
Attenzione: Gli elementi devono essere stampati in ordine crescente!
Considerazioni:
Calcolo del numero di Fibonacci
f (n) = f (n-1) + f (n-2); f(0) = 0 ; f(1) =1;
Insertion Sort
Autore: Nome, Cognome, matricola …
Titolo: nome della funzione (o modulo) implementata.
Scopo: obiettivi dell’algoritmo implementato(sintetico)
Specifiche: Nomi di funzioni, array, variabili importanti
Descrizione: Informazioni sull’algoritmo implementato.
Lista dei Parametri: Parametri input e output
Complessità di Tempo e Di Spazio
Altri parametri eventualmente vuoti:
Implementazione
Complessità di Tempo
L’algoritmo inserisce il componente interi[i] nel vettore già ordinato di componenti interi[0]…interi[i-1] spostando di una posizione tutti i componenti che seguono quello da inserire.
Ad ogni passo la procedura compie nel caso peggiore (vettore ordinato al contrario), N-1 confronti, essendo N la lunghezza del vettore corrente e i-1 spostamenti.
Le operazioni nel caso peggiore sono dunque (1+2+…+N-1), cioè, nel caso peggiore la complessità asintotica di tempo è O(n2). Nel caso migliore (vettore ordinato) bastano N-1 confronti.
Complessità di Spazio:
La struttura dati utilizzata per implementare l’algoritmo è un ARRAY monodimensionale, contenente i valori da ordinare, di conseguenza la complessità di spazio è O(n).
Esempi di esecuzione:
Dati in ingresso i numeri: 20 11 45, si ottiene in uscita: 11 20 45
L’Heapsort è un algoritmo di ordinamento molto efficiente:
Come l’insertion Sort e il Quicksort, l’Heapsort ordina sul posto
Meglio dell’Insertion Sort e del Quicksort, il running time dell’Heapsort è 0(nlogn) nel caso peggiore
L’algoritmo di Heapsort basa la sua potenza sull’utilizzo di una struttura dati chiamata Heap, che gestisce intelligentemente le informazioni durante l’esecuzione dell’algoritmo di ordinamento.
La struttura dati Heap (binaria) è un array che può essere visto come un albero binario completo
Proprietà fondamentale degli Heap è che il valore associato al nodo padre è sempre maggiore o uguale a quello associato ai nodi figli
Un Array A per rappresentare un Heap ha bisogno di due attributi:
La radice dell’Heap è sempre memorizzata nel primo elemento dell’array.
Dato un nodo i, il suo nodo padre, figlio sx e dx possono essere calcolati nel modo seguente:
N.B. Nel C il primo elemento di un vettore A è A[0]. Nel libro di testo “Algoritmi e Strutture Dati”, il primo elemento è invece A[1] e i valori precedenti sono dati dalle seguenti pseudo-funzioni:
Una subroutine molto importante per la manipolazione degli Heap è Heapfy.
Questa routine ha il compito di assicurare il rispetto della proprietà fondamentale degli Heap. Cioè, che il valore di ogni nodo non è inferiore di quello dei propri figli.
Di seguito mostriamo una funzione ricorsiva Heapify che ha il compito di far scendere il valore di un nodo che viola la proprietà di Heap lungo i suoi sottoalberi.
Il running time di Heapify è O(h) dove h è l’altezza dell’Heap. Siccome l’heap è un albero binario completo, il running time è O(logn). Più in dettaglio la sua complessità è la soluzione della ricorrenza T(n) ≤ T(2n/3) + _(1) utilizzando il master method (caso 2).
BuildHeap fa O(n) chiamate a Heapify. Per cui il running time di Buildheap è sicuramente O(nlogn). Si noti che le chiamate a Heapify avvengono su nodi ad altezza variabile minore di h. Da un’analisi dettagliata, risulta che il running time di Heapify è O(n).
Heapsort fa O(n) chiamate a Heapify. Dunque il running time di Heapsort è O(nlogn)
La complessità di spazio di Heapsort è invece O(n), visto che oltre il vettore di input necessita solamente di un numero costante di variabili per implementare l’algoritmo.
Le code di priorità rappresentano una delle applicazioni più efficienti della struttura dati Heap.
Una coda di priorità è una struttura dati utilizzata per mantenere un insieme S di elementi, a ciascuno associato un valore chiamato “chiave”.
Una coda di priorità supporta le seguenti operazioni
Insert(S,x): Inserisce l’elemento x nell’insieme S.
Maximum(S): Restituisce l’elemento di S con la chiave più grande.
Extract-Max(S): Rimuove e ritorna l’elemento di S con la chiave più grande.
Una delle applicazioni più comuni delle code di priorità è quella della schedulazione dei lavori su computer condivisi (per esempio per gestire le code di stampa)
La coda di priorità tiene traccia del lavoro da realizzare e la relativa priorità.
Quando un lavoro viene eseguito o interrotto, il lavoro con più alta priorità è selezionato da quelli in attesa utilizzando la procedura Extract-Max.
Ad ogni istante un nuovo lavoro può essere aggiunto alla coda.
1. Introduzione al Corso - Il Linguaggio C (I parte)
2. Linguaggio C – Seconda Parte
3. Ordinamento, Ricorsione e Code di Priorità
4. Esercitazione su Ricorsione e Code di Priorità
5. Stack e Code
6. Esercitazione di Laboratorio su Stack e Code
7. Implementazioni di Liste puntate
8. Esercitazione di laboratorio su Liste Puntate Semplici
9. Implementazioni di Liste Doppiamente Puntate e Circolari
10. Esercitazione di laboratorio su Liste Doppiamente puntate
12. Esercitazione di laboratorio su Alberi Binari di Ricerca
13. Alberi Binari di Ricerca. Cancellazione di un nodo
14. Esercizio di Laboratorio. Gioco su alberi
15. Grafi: Implementazione ed operazioni di base
16. Esercitazione di laboratorio: Implementazione operazioni di bas...
17. Grafi: Inserimento e Cancellazione di un nodo. Visite in ampiez...
18. Esercitazione di laboratorio: Problema del venditore Prima part...
19. Componenti fortemente connesse e alberi minimi di copertura
20. Esercitazione di laboratorio: Problema del venditore Seconda pa...