Recent Posts
frammenti di razionalità
Return To Blog Listing
Tutto ciò che mi passa per la testa per quanto riguarda musica, programmazione, politica ecc...
Recent Posts Tagged With 'algoritmi'
Performance di alcuni linguaggi di programmazione
Non avendo nulla di meglio da fare, mi son messo a valutare le performance di esecuzione dei linguaggi che conosco nella risoluzione del “Problema di Flavio Giuseppe”, la cui soluzione vi ...
Quickselect
Il Quickselect è un algoritmo randomizzato ricorsivo che trova l’elemento che si troverebbe in k-esima posizione se l’array in cui si trova fosse ordinato. Su un array di grandezza l...
Usare Graphviz e DOT per stampare un albero binario
Graphviz è un pacchetto di software open source sviluppato dagli AT&T Research Labs per la rappresentazione di grafi descritti mediante il linguaggio di scripting DOT. DOT è un linguaggio abbast...
Alberi AVL
Gli alberi AVL sono degli alberi binari bilanciati in altezza. Un albero binario si dice bilanciato in altezza se, per ciascun nodo dell’albero, l’altezza del sottoalbero sinistro differis...
Radix sort
Il radix sort è un algoritmo di ordinamento che permette di ordinare un insieme di n record con chiavi intere comprese tra e con un costo computazionale pari a . L’algoritmo utilizza un altro...
Levenshtein distance - An optimized version
We can adapt the algorithm to use less space, instead of , since it only requires that the previous row and current row be stored at any one time. This is the second version of the algorithm int le...
Programmazione dinamica - Distanza di Levenshtein
La Distanza di Levenshtein è la distanza tra due stringhe S1 ed S2, dove per distanza intendiamo il numero minimo di operazioni elementari che occorre fare per trasformare la stringa S1 nella stringa...
Heapsort - costo computazionale
Per dimostrare che il costo computazionale dello heapsort è occorre prima dimostrare alcune proprietà dello heap. Proprietà 1 Uno heap con n nodi ha altezza Dimostrazione: Sia il numero di livel...
Heapsort - implementazione
L’heapsort è un efficiente metodo di ordinamento caratterizzato da un costo computazionale nel caso peggiore pari a . Lo heapsort rientra nella classe degli algoritmi di ordinamento basati sui ...
Generic quicksort
Nel post precedente ho parlato di come poter usar i void* in C come tipi generici da usare per render estremamente flessibile le funzioni e il codice in generale; ho parlato pure dellla funzione qsort...