🗄Algorithms-and-Data-Structures

0 Introduzione 0.1 L’algoritmo Vogliamo cercare di creare algoritmi, ovvero soluzioni a problemi computazionali che non dipendono dal linguaggio di programmazione. 0.1.1 Definizione Procedura per risolvere un problema in un numero finito di passi (quindi un algoritmo deve finire) 0.1.2 Origine della parola Il nome “algoritmo” deriva da un nome di un matematico persiano dell 800 d.c. Muhammad ibn Musa al-Khwarizmi, che latinizzato diventa algorithmi, quindi i latini hanno creato la parola!...

Questo documento è totalmente concentrato sull’analisi del problema della selezione del k-esimo elemento. 7.1 Introduzione al problema Dato un array di elementi vogliamo cercare di trovare un modo efficiente per selezionare il k-esimo elemento, ossia un elemento che sia maggiore di k-1 elementi 7.1.1 Note sull’utilizzo Questo algoritmo è utile per esempio per sapere cosa displayare in una pagina di ricerca, perché per esempio posso avere blocchi di tanta roba 140k, mentre ovviamente posso selezionare solamente un blocco ristretto....

Merkle Trees: A Fundamental Structure in Cryptography Merkle trees, introduced by Ralph Merkle in 1979, are a pivotal data structure in cryptographic systems. These binary hash trees enable efficient and secure verification of data integrity within distributed systems. Their design capitalizes on hash functions to reduce computational overhead, making them indispensable in blockchain and peer-to-peer networks. What are Merkle Trees? Structure and Construction A Merkle tree is a rooted binary tree where:...

Iterazione Questo metodo semplicemente consiste di calcolare tutte le operazioni e scriverlo con una notazione asintotica. slide Sostituzione (induzione) slide Analisi della relazione di ricorrenza di fibonacci Si può dimostrare utilizzando l’induzione che una relazione di questo tipo $$ T(n) = \begin{cases} O(1) \\ T(n-1) + T(n-2) + 1 \end{cases} $$ Si trova che è $O(2^n), \Omega(2^{n/2})$ Analisi finale. Si può creare una stima corretta, utilizzando la formula per il calcolo di fibonacci (che dimostri facendo osservazioni su una funzione generatrice di essa, una serie infinita)....

6.1 Introduzione 6.1.1 L’importanza del topic Gli algoritmi di ordinamento sono molto di base per la comprensione dell’ampio raggio degli algoritmi. Utilizzano l’analisi, introducono tecniche di risoluzione dei problemi computazionali come greedy, divide et impera e simile. Permettono un primo uso di astrazioni e l’analisi di sottoproblemi. 6.1.2 Il problema Il problema è trovare una permutazione di un insieme di numeri iniziali tale per cui tale insieme di numeri si ordinato:...