DAA - Introduzione

Un algoritmo è un insieme di passaggi di operazioni per risolvere un problema durante l'esecuzione di attività di calcolo, elaborazione dati e ragionamento automatico. Un algoritmo è un metodo efficiente che può essere espresso in una quantità finita di tempo e spazio.

Un algoritmo è il modo migliore per rappresentare la soluzione di un particolare problema in modo molto semplice ed efficiente. Se abbiamo un algoritmo per un problema specifico, possiamo implementarlo in qualsiasi linguaggio di programmazione, il che significa che il filealgorithm is independent from any programming languages.

Progettazione di algoritmi

Gli aspetti importanti della progettazione di algoritmi includono la creazione di un algoritmo efficiente per risolvere un problema in modo efficiente utilizzando il minimo tempo e spazio.

Per risolvere un problema, è possibile seguire diversi approcci. Alcuni di essi possono essere efficienti rispetto al consumo di tempo, mentre altri approcci possono essere efficienti dalla memoria. Tuttavia, è necessario tenere presente che sia il consumo di tempo che l'utilizzo della memoria non possono essere ottimizzati contemporaneamente. Se richiediamo che un algoritmo venga eseguito in minor tempo, dobbiamo investire in più memoria e se richiediamo che un algoritmo venga eseguito con meno memoria, dobbiamo avere più tempo.

Fasi di sviluppo del problema

I seguenti passaggi sono coinvolti nella risoluzione dei problemi computazionali.

Definizione del problema
Sviluppo di un modello
Specifica di un algoritmo
Progettare un algoritmo
Verifica della correttezza di un algoritmo
Analisi di un algoritmo
Implementazione di un algoritmo
Test del programma
Documentation

Caratteristiche degli algoritmi

Le caratteristiche principali degli algoritmi sono le seguenti:

Gli algoritmi devono avere un nome univoco
Gli algoritmi dovrebbero avere una serie di input e output definiti in modo esplicito
Gli algoritmi sono ben ordinati con operazioni non ambigue
Gli algoritmi si arrestano in un periodo di tempo finito. Gli algoritmi non dovrebbero funzionare all'infinito, ovvero un algoritmo deve terminare ad un certo punto

Pseudocodice

Lo pseudocodice fornisce una descrizione di alto livello di un algoritmo senza l'ambiguità associata al testo normale ma anche senza la necessità di conoscere la sintassi di un particolare linguaggio di programmazione.

Il tempo di esecuzione può essere stimato in modo più generale utilizzando Pseudocode per rappresentare l'algoritmo come un insieme di operazioni fondamentali che possono poi essere conteggiate.

Differenza tra algoritmo e pseudocodice

Un algoritmo è una definizione formale con alcune caratteristiche specifiche che descrive un processo, che potrebbe essere eseguito da un computer completo di Turing per eseguire un compito specifico. In generale, la parola "algoritmo" può essere utilizzata per descrivere qualsiasi compito di alto livello in informatica.

D'altra parte, lo pseudocodice è una descrizione informale e (spesso rudimentale) leggibile dall'uomo di un algoritmo che ne lascia molti dettagli granulari. La scrittura di uno pseudocodice non ha limitazioni di stili e il suo unico obiettivo è descrivere i passaggi di alto livello dell'algoritmo in modo molto realistico nel linguaggio naturale.

Ad esempio, di seguito è riportato un algoritmo per l'ordinamento di inserzione.

Algorithm: Insertion-Sort 
Input: A list L of integers of length n  
Output: A sorted list L1 containing those integers present in L 
Step 1: Keep a sorted list L1 which starts off empty  
Step 2: Perform Step 3 for each element in the original list L  
Step 3: Insert it into the correct position in the sorted list L1.  
Step 4: Return the sorted list 
Step 5: Stop

Ecco uno pseudocodice che descrive come il processo astratto di alto livello menzionato sopra nell'algoritmo Insertion-Sort potrebbe essere descritto in un modo più realistico.

for i <- 1 to length(A) 
   x <- A[i] 
   j <- i 
   while j > 0 and A[j-1] > x 
      A[j] <- A[j-1] 
      j <- j - 1 
   A[j] <- x

In questo tutorial, gli algoritmi verranno presentati sotto forma di pseudocodice, che è simile per molti aspetti a C, C ++, Java, Python e altri linguaggi di programmazione.