i programmatori vita algoritmi e strutture di dati è un tema molto importante, se si vuole andare fuori nel mondo della programmazione e fare qualche soldo. Oggi vedremo cosa fanno e dove vengono utilizzati con esempi più semplici. Questo elenco è preparato tenendo presente il loro uso nella programmazione competitiva e nelle attuali pratiche di sviluppo.

Algoritmi di ordinamento

L’ordinamento è il concetto più studiato in Informatica. L’idea è di organizzare gli elementi di un elenco in un ordine specifico. Sebbene ogni linguaggio di programmazione principale abbia librerie di ordinamento integrate, è utile se sai come funzionano. A seconda del requisito si consiglia di utilizzare uno di questi.

• Merge Sort
• Quick Sort
• Bucket Sort
• Heap Sort
• Counting Sort

Ancora più importante si dovrebbe sapere quando e dove usarli. Alcuni esempi in cui è possibile trovare l’applicazione diretta delle tecniche di ordinamento includono:

• Ordinamento per prezzo, popolarità ecc nei siti di e-commerce

Algoritmi di ricerca

Ricerca binaria (in strutture di dati lineari)

La ricerca binaria viene utilizzata per eseguire una ricerca molto efficiente sul set di dati ordinati. La complessità temporale è O (log2N). L’idea è di dividere ripetutamente a metà la parte dell’elenco che potrebbe contenere l’elemento, fino a restringerlo a un elemento possibile. Alcune applicazioni sono:

• Quando si cerca un nome di canzone in un elenco ordinato di canzoni, esegue la ricerca binaria e la corrispondenza delle stringhe per restituire rapidamente i risultati.
• Usato per eseguire il debug in git attraverso git bisect

Depth/Width First Search (in Graph data structures)

DFS e BFS sono strutture di dati che attraversano alberi/grafici e cercano. Non approfondiremo il modo in cui funzionano DFS/BFS, ma vedremo come sono diversi attraverso la seguente animazione.

Applicazioni:

• Usato dai motori di ricerca per il web-indicizzazione
• Utilizzato nel campo dell’intelligenza artificiale per creare bot, per esempio, un scacchi bot
• Trovare il percorso più breve tra due città in una mappa, e tante altre applicazioni

Hash

Hash di ricerca è attualmente la tecnica più utilizzata per trovare le opportune dati chiave o ID. Accediamo ai dati dal suo indice. In precedenza ci affidavamo all’ordinamento + Ricerca binaria per cercare l’indice mentre ora usiamo l’hashing.

La struttura dei dati è indicata come Hash-Map o Hash-Table o Dictionary che associa le chiavi ai valori, in modo efficiente. Possiamo eseguire ricerche di valore usando i tasti. L’idea è di utilizzare una funzione hash appropriata che esegua la mappatura dei valori key ->. La scelta di una buona funzione hash dipende dallo scenario.

Applicazioni:

• Nei router, per memorizzare l’indirizzo IP- > Coppia di percorsi per i meccanismi di routing
• Per eseguire il controllo se un valore esiste già in un elenco. La ricerca lineare sarebbe costosa. Possiamo anche usare Set data structure per questa operazione.

Programmazione dinamica

La programmazione dinamica (DP) è un metodo per risolvere un problema complesso scomponendolo in sottoproblemi più semplici. Risolviamo i sottoproblemi, ricordiamo i loro risultati e usandoli facciamo il nostro modo di risolvere il problema complesso, rapidamente.

*scrive “1+1+1+1+1+1+1+1 =” su un foglio di carta* A cosa equivale?
*contando * Otto!
*scrive un altro “1+” a sinistra* Che dire di questo?
*rapidamente * Nove!
Come facevi a sapere che erano nove così in fretta?
Hai appena aggiunto un altro
Quindi non hai bisogno di raccontare perché ti sei ricordato che ce n’erano otto! La programmazione dinamica è solo un modo elegante per dire ‘ricordare cose per risparmiare tempo dopo’

Applicazioni:

• Ci sono molti algoritmi e applicazioni DP, ma ne nominerei uno e ti soffiano via, metodo Duckworth-Lewis nel cricket.

Esponenziazione quadrando

Dire che si desidera calcolare 232. Normalmente ripeteremmo 32 volte e troveremmo il risultato. E se ti dicessi che può essere fatto in 5 iterazioni?

L’esponenziazione per quadratura o esponenziazione binaria è un metodo generale per il calcolo rapido di grandi potenze intere positive di un numero in O(log2N). Non solo, il metodo viene utilizzato anche per il calcolo delle potenze di polinomi e matrici quadrate.

Applicazione:

• Il calcolo di grandi potenze di un numero è principalmente richiesto nella crittografia RSA. RSA utilizza anche l’aritmetica modulare insieme all’esponenziazione binaria.

String Matching and Parsing

Pattern matching / searching è uno dei problemi più importanti nell’informatica. Ci sono state molte ricerche sull’argomento, ma arruoleremo solo due necessità di base per qualsiasi programmatore.

Algoritmo KMP (String Matching)

L’algoritmo Knuth-Morris-Pratt viene utilizzato nei casi in cui dobbiamo abbinare un modello breve in una stringa lunga. Ad esempio, quando Ctrl+F una parola chiave in un documento, eseguiamo la corrispondenza del modello nell’intero documento.

Espressione regolare (String Parsing)

Molte volte dobbiamo convalidare una stringa analizzando una restrizione predefinita. È molto utilizzato nello sviluppo Web per l’analisi e la corrispondenza degli URL.

Algoritmi di test di primalità

Esistono modi deterministici e probabilistici per determinare se un dato numero è primo o meno. Vedremo sia modi deterministici che probabilistici (non deterministici).

Setaccio di Eratostene (deterministico)

Se abbiamo un certo limite nell’intervallo di numeri, diciamo determinare tutti i numeri primi nell’intervallo da 100 a 1000, allora Sieve è un modo per andare. La lunghezza dell’intervallo è un fattore cruciale, perché dobbiamo allocare una certa quantità di memoria in base all’intervallo.

Per qualsiasi numero n, test incrementale fino a sqrt(n) (deterministico)

Nel caso in cui si desideri controllare pochi numeri che sono scarsamente distribuiti su un lungo intervallo (ad esempio da 1 a 1012), Sieve non sarà in grado di allocare abbastanza memoria. È possibile controllare ogni numero n attraversando solo fino a sqrt(n) ed eseguire un controllo di divisibilità su n.

Fermat primality test e Miller–Rabin primality test (entrambi non sono deterministici)

Entrambi sono test di compositeness. Se si dimostra che un numero è composto, allora sicuramente non è un numero primo. Miller-Rabin è più sofisticato di quello di Fermat. Infatti, Miller-Rabin ha anche una variante deterministica, ma poi è un gioco di scambi tra complessità temporale e accuratezza dell’algoritmo.

Applicazione:

• L’uso più importante dei numeri primi è nella crittografia. Più precisamente, sono utilizzati in crittografia e decrittografia in algoritmo RSA che è stata la prima implementazione di crittografia a chiave pubblica
• Un altro uso è nelle funzioni Hash utilizzate nelle tabelle Hash