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 permetterà di salvarvi nel caso abbiate deciso al...
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’algoritmo esegue confronti nel caso peggiore ...
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 abbastanza semplice ed immediato. Per esempio, il codice...
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 differisce dall’altezza del sottoalbero destro al pi...
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 algoritmo di ordinamento per chiavi intere, chiam...
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 levenshtein_distance(char *x, char *y){ int m=strle...
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 S2. Queste operazioni elementari includono: canc...
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 livello dello heap. I primi livelli sono tutti complet...
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 confronti e ha la particolarità di sfruttare una ...
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 della libreria standard del C che è l’esem...
