10. Algoritmi e strutture dati

A tutti capita di dover riordinare un mazzo di carte da gioco e probabilmente ognuno ha una propria tecnica per fare questa operazione.

Ma esiste un modo più efficiente degli altri, cioè un procedimento in grado di portare a termine questo compito nel minor tempo possibile?

Immaginiamo di predisporre un tabellone composto da tante caselle quante sono le carte, ciascuna con l'indicazione della carta che deve ospitare. Ad esempio, se siamo alle prese con un mazzo di carte francesi che vogliamo ordinare con la sequenza dei semi tipici del poker (cuori, quadri, fiori e picche come suggerisce la filastrocca "come quando fuori piove") il 2 di quadri occuperà la casella n. 15, il 3 di fiori la casella n. 29 ecc..

Ebbene per posizionare le carte sul tabellone sarà sufficiente estrarre una carta alla volta e posizionarla direttamente nella casella opportuna.

Questo è un esempio di procedura che, sfruttando un precisa struttura dei dati, risolve il problema in un numero esatto di azioni, pari al numero di carte.

Una procedura che si comporta in questo modo, si dice che ha una complessità lineare perché raddoppiando la taglia del problema (il numeri di carte in questo caso) raddoppia il tempo di esecuzione, nulla di più.

Procedure con queste caratteristiche sono molto apprezzate perché molto efficienti.

La soluzione proposta funziona a patto di avere a disposizione un opportuno tabellone che, quindi, è parte integrante della soluzione.

Generalizzando, molte procedure informatiche richiedono una precisa struttura di dati per essere implementate. Anzi possiamo dire che per implementare delle soluzioni algoritmiche molto spesso occorre prima concepire una struttura di dati in grado di modellare il problema e solo successivamente ci si può concentrare sulla procedura vera e propria.

Padroneggiare le strutture dati più ricorrenti, che consentono di modellare una grande quantità di problemi, è quindi di fondamentale importanza quando si cerca una soluzione algoritmica per una classe di problemi.

Sito:  7ecnologie

Sezione: 10. Algoritmi e strutture dati

Indice delle sezioni: 01. Problem Solving - 02. Office automation - 03. Sistemi - 04. Numerazione posizionale - 05. Logica Matematica - 06. Diagrammi di flusso - 07. Scratch - 08. C language - 09. Python - 10. Algoritmi e strutture dati - 11. Base di dati - 12. SQL - 13. Reti - 14. Sicurezza informatica - 15. Blockchain e Bitcoin - 16. Calcolo numerico - 17. Robotica e domotica - 18. HTML & CSS - 19. Tecnologie e società

Indice dei capitoli: 00. Risorse - 01. Tipi base - 02. Strutture lineari dinamiche - 03. Alberi e grafi